《计算机网络与通信》课程笔记
一、概述
因特网服务提供者 ISP(Internet Service Provider)
ARPANET：最早的因特网，1969年，使用分组交换技术，后来TCP/IP协议成为标准协议
互联网的组成：边缘（用户）+核心（路由器、链路）
两种通信方式：客户-服务器方式 C/S(Client/Server)、对等方式 P2P(Peer-to-Peer)
三种交换方式：电路交换、分组交换、报文交换
- 电路交换：面向连接
- 三阶段：建立连接、通信、释放连接
- 分组交换
- 可以无连接也可以面向连接
- 划分成较短的、固定长度的数据段
- 存储转发
- 报文交换
- 存储转发传输整个报文
时延=传输时延+处理时延+排队时延+传播时延
- 发送时延：数据块长度/发送速率
- 处理时延：交换结点为存储转发而进行一些必要的处理所花费的时间
- 排队时延：结点缓存队列中分组排队所经历的时延
- 传播时延：信号在传输媒体上传播所需的时间（取决于信道距离）
- 传输速率可以提高，但传播速率是物理特性决定的
时延带宽积：传播时延与带宽的乘积，链路上最大的比特数量
信道利用率：信道被利用的时间占比，非越高越好
网络利用率U：信道利用率加权平均值
$当前时延D=\dfrac{空闲时延D_0}{1-U}$
网络协议三要素：语法、语义、时序
实体(Entity)：任何可发送或接收信息的硬件或软件进程
协议(Protocol)：控制对等实体之间的通信的规则集
第n层协议向第n+1层提供服务，是第n-1层的用户
OSI/TCP-IP
二、物理层
主要任务：确定与传输媒体的接口的一些特性，包括：机械特性、电气特性、功能特性、过程特性
数据通信系统可划分为三大部分：源系统(发送端)、传输系统(传输网络)、目的系统(接收端)。
信道(channel)分类：单工通信（只能单向传输）、半双工通信（双向传输但不能同时）、全双工通信（双向传输且可以同时）
导引型传输媒体：双绞线、同轴电缆、光纤
非导引型传输媒体：无线电波、微波、红外线
宽带接入技术：非对称数字用户线ADSL(Asymmetric Digital Subscriber Line)、光纤同轴混合网HFC(Hybrid Fiber Coax)、光纤到…FTTx(Fiber To The x)
2.1 调制
基本带通调制方式：调幅AM、调频FM、调相PM
一种多元制的振幅相位混合调制方法：正交振幅调制(Quadrature Amplitude Modulation，QAM)
- 可供选择的相位有12种，而对于每一种相位有1或2种振幅可供选择。
- 共有16种不同的组合，每种组合可以用4bit二进制数表示，因此这16个点中的每个点可对应于一种4bit的编码。
、
2.2 信道极限容量
奈氏准则-奈奎斯特：在带宽为W(Hz)的低通信道中，若不考虑噪声影响，则码元传输的最高速率是2W(码元/秒 波特Baud)
信噪比(Signal-to-Noise Ratio, SNR)：信号功率与噪声功率之比
$SNR=10\log_{10}(\dfrac{S}{N})$(单位：dB)
香农定理：$C=W\log_2(1+\dfrac{S}{N})$(单位：bps)
W为信道的带宽(Hz)，S为信道内所传信号的平均功率(数据传输速率=码元传输速率*码元携带的比特数)，N为信道内部的高斯噪声功率
信道极限容量例题
- 信道带宽为3000Hz，信噪比为30dB，则最大数据速率为多少？
- 根据信噪比公式，$SNR=10log_{10}(\frac{S}{N})=30dB \Rightarrow \frac{S}{N}=10^3$
- 根据香农公式，$C=W\log_2(1+\frac{S}{N})=3000\log_2(1+10^3) \approx 3000\times9.97 \approx 30000bps$
- 下列因素中,不会影响信道数据传输率的是( )
- A. 信噪比 B. 频率宽带 C. 调制速率 D. 信号传播速度
- A：$\frac{S}{N}$, B：W, C：S的因子, D：不影响
- 若信道在无噪声情况下的极限数据传输速率不小于信噪比为30dB条件下的极限数据传输速率，则信号状态数至少是？
- 记信道带宽为W，一个码元所占位数k。
- 根据信噪比公式，$SNR=10log_{10}(\frac{S}{N})=30dB \Rightarrow \frac{S}{N}=10^3$
- 根据奈氏准则和香农公式：$2W\times k \ge W\log_2(1+10^3) \Rightarrow 2k \ge \log_2(1+10^3)\approx 10 \Rightarrow k \ge 5$
- 状态数至少是$2^5=32$
2.3 信道复用技术
- 复用器(multiplexer)：复用开始前，多个低速信道合成一个高速信道的设备
- 分用器(de-multiplexer)：复用结束后，将高速信道分解为多个低速信道的设备
频分复用FDM(Frequency Division Multiplexing)：将频带分成若干窄带，各路信号分别搬移到适当的频率位置，彼此互不干扰。
频分复用的所有用户在同样的时间占用不同的带宽资源，这里的“带宽”是频率带宽而不是数据的发送速率。
时分复用TDM(Time Division Multiplexing)：将时间分成若干时隙，每个时隙用来传输一个信号，然后把这些时隙信号叠加在一起传输。
时分复用可能会造成线路资源的浪费，解决方法：统计时分复用STDM（Statistical TDM）
波分复用WDM(Wavelength Division Multiplexing)：光的频分复用，使用一根光纤来同时传输多个光载波信号。
码分多址CDMA(Code Division Multiple Access)：多个不同地址的用户共享码分复用(CDM, Code Division Multiplexing)信道。
码片(chip)：每一个比特时间划分为m个短的间隔，称为
码片序列：每个站被指派一个唯一的m bit码片序列
以$S=00011011, T=00101110$为例
- S发送1：发送码片序列$S=00011011$
- S发送0：发送码片序列的反码$S_x=11100100$
- 按照惯例，1记为+1，0记为-1，码片序列S为-1 -1 -1 +1 +1 -1 +1 +1
- 码片特点：
- 规格化内积$S\cdot S=\frac{1}{m}\sum_{i=1}^{m}S_iS_i=1$
- 规格化内积$S\cdot Sx=\frac{1}{m}\sum{i=1}^{m}SiS{xi}=-1$
CDMA的重要特点
- 每个站分配的码片序列不仅必须各不相同，并且还必须互相正交(规格化内积为0)
- S和T正交：$S\cdot T=\frac{1}{m}\sum_{i=1}^{m}S_iT_i=0$
- 在实用的系统中是使用伪随机码序列
三、数据链路层
数据链路(data link)：除了物理线路外，还必须有通信协议来控制这些数据的传输。
数据链路由物理链路和实现这些协议的硬件和软件构成。
数据链路层使用的信道：点对点信道、广播信道
数据链路层的三个基本问题：封装成帧、透明传输、差错检测
- 封装成帧：在一段数据的前后分别添加首部和尾部，然后就构成了一个帧，确定帧的界限。
- 透明传输：使数据链路层的协议对上层是透明的，网络层不必关心数据链路层的具体实现。
- 差错检测：在传输过程中可能会产生比特差错，为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施
使用载波监听多点接入/碰撞检测协议CSMA/CD的以太网不能进行全双工通信而只能进行双向交替通信(半双工通信)
- 多点接入CSMA：许多计算机以多点接入的方式连接在一根总线上
- 碰撞检测CD：每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞
3.1 循环冗余校验CRC
循环冗余校验CRC(Cyclic Redundancy Check)是一种差错检测方法，通过在数据末端添加冗余位，确定数据是否在传输过程中发生变化。
模二运算：一种不考虑进位的二进制按位运算。
- 加法/减法：相加减而不考虑进位/借位，即二进制按位异或运算
- 乘法：列竖式，逐位相乘，按位异或
- 除法：列竖式，商上余数的首位，按位相减
CRC冗余码的计算和校验：
- 原始二进制数据$M=1100$
- 将原始数据左移$r=3$位（冗余位位数）得到$M\times 2^r=1100|000$
- 约定一个$r+1=4$位生成多项式$G=1011$作为除数
- 生成多项式的最高位和最低位都必须是1
- 当传输的数据X的任何一位发生错误时，被G除的余数不为0
- 数据X的不同位发生错误时，被G除的余数不同
- 模二除法：$(M \times 2^r) \div G = Q \cdots R$
- $1100000 \div 1011 = 1110 \cdots 010$
- 商$Q=1100$，余数$R=010$
- 此时有$M \times 2^r = Q \times G + R$ 成立
- 将余数R添加到原始数据M后面，得到传输的数据$X=1100|010$
- $M \times 2^r + R = Q \times G + R + R = Q \times G$
- 接收端将接收到的数据X对G进行模二除法，若余数为0则无差错，否则有差错
差错定位/纠正：
| X=A1~A7 | 余数 | 出错位 |
|---|---|---|
| 1100010 | 010 | 无差错 |
| 1100011 | 001 | 7 |
| 1100000 | 000 | 6 |
| 1100110 | 110 | 5 |
| 1101010 | 011 | 4 |
| 1110010 | 110 | 3 |
| 100010 | 111 | 2 |
| 010010 | 101 | 1 |
3.2 帧检验序列FCS
帧检验序列FCS(Frame Check Sequence)是数据链路层的差错检测技术，用于检测数据在传输过程中是否发生了变化。
CRC和FCS的关系：CRC是一种常用的差错检测方法，而FCS是添加在数据后面的冗余码。FCS可以用CRC这种方法得出，但CRC并非用来获得FCS的唯一方法。
无差错接受：接收端对收到的每一帧进行CRC检验，若余数为0则无差错，接受，否则丢弃
码距：同一编码中，任意两个合法编码之间不同二进数位数的最小值。
- 码距越大，抗干扰能力、纠错能力越强，数据冗余越大，编码效率越低
- 检错位数=码距//2，纠错位数=(码距-1)//2
- 特殊情况：码距=3，检错1纠错1，或检错2纠错0
校验码中增加冗余项的目的就是为了增大码距
仅用循环冗余检验CRC差错检测技术只能做到无差错接受，要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。
- 需要考虑的问题：帧重复、帧丢失、帧乱序
- 解决方法：帧编号、确认和重传
OSI/RM模型的观点：数据链路层要做成无传输差错的。但这种理念目前不被接受
3.2 点对点协议PPP
PPP是现在全世界使用的最多的数据链路层协议，用户使用拨号电话线接入互联网时，一般都是使用PPP协议。
PPP协议的组成部分（自下而上）：
- 一个将IP数据报封装到串行链路的方法。既支持异步链路，也支持同步链路
- 一个用来建立、配置和测试数据链路连接的链路控制协议LCP(Link Control Protocol)
- 一套网络控制协议NCP(Network Control Protocol)。允许在点到点连接上使用多种网络层协议
PPP的帧格式
| 字段 | 长度 | 值 | 说明 |
|---|---|---|---|
| 帧开始标志F | 1B | 01111110(0x7E) | |
| 地址A | 1B | 11111111(0xFF) | 规定值，无作用 |
| 控制C | 1B | 00000011(0x03) | 规定值，无作用 |
| 协议P | 2B | IP数据报：0x0021 PPP链路控制数据：0xC021 网络控制数据：0x8021 |
表示上层协议类型 |
| 信息字段 | 0~1500B | IP数据报等数据 | 可变长度，不包括FCS |
| 帧校验序列FCS | 2B | CRC校验码 | |
| 帧结束标志F | 1B | 01111110(0x7E) |
3.3 透明传输实现：字节填充和比特填充
PPP异步传输（逐字符）：字节填充
- 字节填充转义符：0x7D
- 0x7E转义为0x7D 0x5E
- 0x7D转义为0x7D 0x5D
- ASCII码小于0x20,+0x20转义。如0x03转义为0x7D 0x23
字节填充例题：一个PPP帧的信息字段为 7E 7D 5E FE 27 7D 5D 7D 27 7E，求真正的信息字段
- 标出转义字符：76 (7D 5E) FE 27 (7D 5D) (7D 27) 7E
- 字符转义：76 (7E) FE 27 (7D) (07) 7E
PPP同步传输（逐比特位连续发送）：比特填充
- 在发送端，只要发现有5个连续的1，则立即填入一个0
- 在接收端，只要发现有5个连续的1，且后面紧跟一个0，则删除这个0
比特填充例题：若接收端收到的 PPP 的数据部分是0001110111110111110110 ，问删除发送端加入的零比特后变成怎样的比特串
- 标出111110：0001110(111110)(111110)110
- 删除零比特：0001110(11111)(11111)110
3.4 使用广播信道的数据链路层
局域网拓扑结构
- 总线网：所有站点共享一条总线。
- 匹配电阻：避免总线有害电磁波反射
- 星形网：所有站点都连接到一个中心站点。
- 集线器：中心站点的功能是转发数据
- 环形网：所有站点连接成一个环形。
- 干线耦合器：环形网的数据传输方向是固定的（顺时针/逆时针）
媒体共享技术
- 静态划分信道：TDM、FDM、WDM、CDM
- 代价高，不适合局域网
- 动态媒体接入控制（多点接入）
- 随机接入：随机发送信息，要有冲突检测和冲突解决机制
- 受控接入：多点线路探询(polling)或轮询
局域网的数据链路层的两个子层：辑链路控制LLC(Logical Link Control)子层、媒体接入控制MAC(Media Access Control)子层
网卡的作用：进行串行/并行转换、实现以太网协议、存储MAC地址
3.4 以太局域网（以太网）
以太网单程端到端时延 $\tau$ ，争用期长度 $2\tau$ ，帧长 $L(bit)$ ，数据发送速率 $C(bps)$ ，帧发送时间 $T_0=\frac{L}{C}$
发送一帧的平均时间：$k\cdot 2\tau + T_0 + \tau$（发送完成后等待一个$\tau$的传播时间）
信道利用率：$S=\dfrac{T_0}{k\cdot 2\tau + T_0+\tau}$
要提高以太网的信道利用率，就必须减小$\tau$与$T_0$之比：$a=\frac{\tau}{T_0}$。
a越大，表明争用期所占的比例增大，每发生一次碰撞就浪费许多信道资源，使得信道利用率明显降低
理想情况下的极限信道利用率$S_{max}=\dfrac{T_0}{T_0+\tau}=\dfrac{1}{1+a}$
以太网MAC帧格式（DIX Ethernet V2 标准）：
| 字段 | 长度 | 值 | 说明 |
|---|---|---|---|
| 前同步码 | 7B | 固定为10101010交替 | 调整时钟频率 |
| 帧开始定界符 | 1B | 10101011 | |
| 目的地址 | 6B | 目的MAC地址 | |
| 源地址 | 6B | 源MAC地址 | |
| 类型 | 2B | 上层协议类型 | |
| 数据 | 46~1500B | IP数据报 | 可变长度，不包括FCS |
| FCS | 4B | CRC校验码 |
3.5 HDLC协议
HDLC(High-level Data Link Control)是一种数据链路层协议，是ISO组织制定的一种数据链路层协议，是一种面向比特的协议。
| HDLC协议 | PPP协议 | |
|---|---|---|
| 信道 | 点对点 | 点对点 |
| 面向 | 比特 | 字节 |
| 透明性 | 0比特填充 | 字节填充 |
| 通信 | 全双工、半双工 | 全双工 |
| 可靠性 | 使用编号和确认机制，提供可靠传输 | 只保证无差错接收CRC检验 |
| 多一个2字节的协议字段。当协议字段值为0x0021时，表示信息字段是IP数据报 |
四、网络层
4.1 网络层的基本概念
4.1.1 网络层提供的两种服务
| 虚电路服务 | 数据报服务 | |
|---|---|---|
| 思路 | 可靠通信应当由网络来保证 | 通信的可靠性应当由用户主机来保证 |
| 建立的连接 | 必须有 | 不需要 |
| 终点地址 | 仅在连接建立阶段使用，每个分组使用短的虚电路号 | 每个分组都有终点的完整地址 |
| 分组的转发 | 属于同一条虚电路的分组均按照同一路由进行转发 | 每个分组独立选择路由进行转发 |
| 结点出故障时 | 所有通过出故障的结点的虚电路均不能工作 | 出故障的结点可能会丢失分组，一些路由可能会发生变化 |
| 分组的顺序 | 总是按发送顺序到达终点 | 到达终点时不一定按发送顺序 |
| 端到端的差错处理和流量控制 | 可以由网络负责，也可以由用户主机负责 | 由用户主机负责 |
4.1.2 中间设备/中继系统
- 物理层：转发器(repeater)
- 数据链路层：网桥(bridge)
- 网络层：路由器(router)
- 网络层以上：网关(gateway)
4.2 IP协议
网际协议IP是TCP/IP体系中两个最主要的协议之一。与IP协议配套使用的还有三个协议：
- 地址解析协议ARP(Address Resolution Protocol)
- 网际控制报文协议ICMP(Internet Control Message Protocol)
- 网际组管理协议IGMP(Internet Group Management Protocol)
4.2.1 IP地址分类
IP地址分为A、B、C、D、E五类，每类地址的网络号和主机号的划分不同。
| 类别 | 前缀 | 网络号 | 主机号 | 第一字节范围 | 子网掩码 | 主机数 | 预留私有地址网段（RFC 1918） |
|---|---|---|---|---|---|---|---|
| A类 | 0 | 7位 | 24位 | 0~127 | /8 | 2^24-2=16777214 | 10.0.0.0~10.255.255.255 |
| B类 | 10 | 14位 | 16位 | 128~191 | /16 | 2^16-2=65534 | 172.16.0.0~172.31.255.255 |
| C类 | 110 | 21位 | 8位 | 192~223 | /24 | 2^8-2=254 | 192.168.0.0~192.168.255.255 |
| D类 | 1110 | 多播地址28位 | - | 224~239 | - | - | - |
| E类 | 1111 | 保留地址 | - | 240~255 | - | - | - |
4.2.2 地址解析协议ARP
当主机A欲向本局域网上的某个主机B发送IP数据报时，就先在其ARP高速缓存中查看有无主机B的IP地址。
如有，就可查出其对应的硬件地址，再将此硬件地址写入MAC，然后通过局域网将该MAC发往此硬件地址。
如没有，ARP进程在本局域网上广播发送一个ARP请求分组收到ARP响应分组后，将得到的P地址到硬件地址的映射写入ARP高速缓存。
4.2.3 IP数据报的封装格式
IP数据报的封装格式：
| 字段 | 长度 | 值 | 说明 |
|---|---|---|---|
| 版本 | 4b | IPv4为4 | IP协议的版本号 |
| 首部长度 | 4b | 首部长度 | 最大为1111(15)，单位为4字节，即首部最大为60字节 |
| 区分服务 | 8b | 服务类型，一般不使用 | |
| 总长度 | 16b | IP数据报的总长度 | 单位为字节，包括首部和数据部分 |
| 标识 | 16b | 标识符 | 用于标识发送的数据报 |
| 标志 | 3b | 标志位 | MF：1位，1表示还有分片 DF：1位，1表示不允许分片 保留位：1位 |
| 片偏移 | 13b | 片偏移 | 单位为8字节，表示该片相对于原始数据报的偏移量 |
| 生存时间 | 8b | TTL | 数据报在网络中可通过的路由器数的最大值，每经过一个路由器减1，为0时丢弃 |
| 协议 | 8b | 协议号 | 指出此数据报携带的数据使用何种协议，如TCP为6，UDP为17 |
| 首部校验和 | 16b | 首部校验和 | 只检验数据报的首部不检验数据部分 这里不采用CRC检验码而采用简单的计算方法 |
| 源地址 | 32b | 源IP地址 | 发送数据报的主机的IP地址 |
| 目的地址 | 32b | 目的IP地址 | 接收数据报的主机的IP地址 |
| 选项 | 可变 | 选项字段的长度是可变的，最长为40字节 |
IP数据报分片例：一数据报的总长度为3820字节，其数据部分的长度为3800字节(使用固定首部)，MTU=1420字节
- 首部长度：20字节
- 分片最长数据长度：1420-20=1400字节
- 分片数据长度：3800=1400+1400+1000
- 分片1：偏移0，MF=1
- 分片2：偏移1400/8=175，MF=1
- 分片3：偏移2800/8=350，MF=0
4.3 IP层分组转发过程
4.3.1 分组转发算法
- 从数据报的首部提取目的主机D的IP地址,得出目的网络地址为N
- 若网络N与此路由器直接相连，则把数据报直接交付目的主机D；否则是间接交付，执行下一步
- 若路由表中有目的地址为D的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则，执行下一步
- 若路由表中有到达网络 N 的路由，则把数据报传送给路由表指明的下一跳路由器；否则，执行下一步
- 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器，否则，报告转发分组出错
4.3.2 子网划分
借位：从主机最高位开始借位变为新的子网位，剩余部分仍为主机位
例如192.168.1.0/24可划分为：
- 2个子网：192.168.1.0/25、192.168.1.128/25
- 4个子网：192.168.1.0/26、192.168.1.64/26、192.168.1.128/26、192.168.1.192/26
192.168.1.55/26 的网络号：将IP地址转换为二进制，取前26位即可。
192.168.1.55(00|110111)=>192.168.1.0
4.3.3 划分子网的分组转发算法
- 从数据报的首部提取目的主机D的IP地址
- 先用直接相连的各网络的子网掩码和D逐位相“与”，看是否和相应的网络地址匹配。若匹配，则将分组直接交付；否则就是间接交付，执行下一步
- 若路由表中有目的地址为D的特定主机路由，则将分组传送给指明的下一跳路由器；否则，执行下一步
- 对路由表中的每一行的子网掩码和 D 逐位相“与”，若其结果与该行的目的网络地址匹配，则将分组传送给该行指明的下一跳路由器；否则，执行下一步
- 若路由表中有一个默认路由，则将分组传送给指明的默认路由器；否则，报告转发分组出错
4.3.4 无分类IP地址CIDR
一个 CIDR 地址块可以表示很多地址，这种地址的聚合常称为路由聚合，它使得路由表中的一个项目可以表示很多个（例如上千个）原来传统分类地址的路由。
最长前缀匹配：在路由表中查找一个与目的地址最匹配的路由表项，即查找最长的前缀匹配。
4.4 网际控制报文协议ICMP
ICMP 允许主机或路由器报告差错情况和提供有关异常情况的报告。
ICMP 不是高层协议，而是IP层的协议。
ICMP 报文作为IP层数据报的数据，加上数据报的首部，组成IP数据报发送出去。
ICMP差错报文：终点不可达、时间超限、参数问题、改变路由(重定向)、源抑制
ICMP询问报文：回送请求和回答报文、时间戳请求和回答报文
ICMP应用：PING、Traceroute
4.5 路由选择协议
内部网关协议 IGP:具体的协议有多种，如RIP和OSPF等
外部网关协议 EGP:目前使用的协议就是BGP
4.5.1 RIP协议
RIP是一种基于距离矢量（Distance-Vector）算法的协议，它使用跳数（Hop Count）作为度量值来衡量到达目的地址的距离。
在RIP网络中，缺省情况下，设备到与它直接相连网络的跳数为0，通过一个设备可达的网络的跳数为1，其余依此类推。也就是说，度量值等于从本网络到达目的网络间的设备数量。
为限制收敛时间，RIP规定度量值取0～15之间的整数，大于或等于16的跳数被定义为无穷大，即目的网络或主机不可达。由于这个限制，使得RIP不可能在大型网络中得到应用。
RIP路由器工作流程：
- RIP路由器A,B初始的路由表中只有自己的直连路由。
- 每30秒，向相邻路由器发送自己的路由表。
- 收到相邻路由器的路由表后，更新自己的路由表：
- 新增：如果收到的路由表中有自己没有的路由，则添加到自己的路由表中。
- 更新：如果收到的路由表中有自己已有的路由，且新的跳数更小，则更新自己的路由表的跳数。
- RIP计时器：
- 更新计时器：每30秒左右发送一次路由表。
- 失效计时器：180秒（6倍更新时间）未更新，标记为不可达。
- 刷新计时器：无效路由240秒未更新，从路由表中删除。
RIP协议的缺点：坏消息传播慢、收敛时间长、不适合大型网络
4.5.2 OSPF协议
使用了 Dijkstra 提出的最短路径算法SPF(Shortest Path First)，是分布式的链路状态协议
支持可变长度的子网划分和无分类编址 CIDR
五种分组类型：问候分组Hello、数据库描述分组Database Description、链路状态请求分组Link State Request、链路状态更新分组Link State Update、链路状态确认分组Link State Acknowledgement
当互联网规模很大时，OSPF 协议要比距离向量协议 RIP 好得多，且没有“坏消息传播得慢”的问题
4.5.3 BGP协议
BGP 只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由
一个BGP 发言人与其他自治系统中的BGP发言人要交换路由信息就要先建立TCP连接，然后在此连接上交换BGP报文以建立BGP会话(session)，利用 BGP 会话交换路由信息。
BGP协议的特点：支持CIDR、只在发生变化时更新有变化的部分
四种BGP报文：打开报文Open（与相邻BGP发言人建立联系）、更新报文Update（发送路由信息）、通知报文Notification（发送差错）、保持报文Keepalive（确认Open和保持连接）
4.6 路由器的构成
常用交换方法：通过存储器、通过总线、通过纵横交换结构
4.7 IP多播
TCP/IP 协议使用的以太网多播地址块的范围是：从 00-00-5E-00-00-00 到 00-00-5E-FF-FF-FF
为了使路由器知道多播组成员的信息，需要利用网际组管理协议IGMP (Internet Group Management Protocol)，同时也需要路由器多播选择协议
IGMP阶段：加入多播组、探寻成员变化
多播路由选择协议转发多播数据报时使用三种方法：洪泛与剪除（适合于较小的多播组，RPB）、隧道技术、基于核心的发现技术
反向路径广播RPB(Reverse Path Broadcasting)：路由器收到多播数据报时，检查数据报的源地址，如果数据报的源地址是最短路径树上的成员，则转发数据报，否则丢弃
五、传输层/运输层
运输层向它上面的应用层提供通信服务
只有位于网络边缘部分的主机的协议栈才有运输层，而网络核心部分中的路由器在转发分组时都只用到下三层的功能
应用进程之间的通信又称为端到端的通信，运输层提供应用进程间的逻辑通信
| 运输层 | 网络层 |
|---|---|
| 为应用进程之间提供端到端的逻辑通信 | 为主机之间提供逻辑通信 |
| 对报文进行差错检测 | 对首部进行差错检测 |
| 需要两种不同的运输协议，即面向连接的TCP和无连接的UDP | 无连接的IP协议 |
协议端口号：用于标识主机上的应用进程，简称端口。16位，范围0~65535
- 服务端：0~1023为熟知端口号，1024~49151为登记端口号
- 客户端：49152(65536/4*3)~65535为短暂端口号
| 协议 | FTP | Telnet | SMTP | DNS | HTTP | SMTP | HTTPS |
|---|---|---|---|---|---|---|---|
| 熟知端口号 | 21/20 | 23 | 25 | 53 | 80 | 110 | 443 |
5.1 用户数据报协议UDP v.s. 传输控制协议TCP
| 用户数据报协议UDP(User Datagram Protocol) | 传输控制协议TCP(Transmission Control Protocol) | |
|---|---|---|
| 连接服务 | 无连接的协议，提供无连接服务 | 面向连接的协议，提供面向连接服务 |
| 可靠性 | 不可靠 | 全双工的可靠信道 |
| 运输协议数据单元TPDU | UDP报文/用户数据报 | TCP报文段 |
| 传输方式 | 单播、多播、广播 | 点对点单播，不支持多播和广播 |
| 面向 | 报文 | 字节流 |
| 复杂性 | 简单 | 复杂 |
| 应用 | 多媒体 | 文件传输、电子邮件、WWW |
| 应用层协议 | DNS、TFTP、SNMP、NFS | HTTP、FTP、Telnet、SMTP |
| 拥塞控制 | 无 | 有 |
| 首部开销 | 8字节 | 20字节 |
5.2 用户数据报协议UDP
只在IP数据报之上增加了复用和分用（端口）、差错检测功能
5.2.1 UDP首部格式
| 字段 | 长度 | 值 | 说明 |
|---|---|---|---|
| 伪首部 | 12B | 源IP地址、目的IP地址、协议号、UDP长度 | 用于计算校验和 |
| 源端口 | 2B | 0~65535 | 标识发送方应用进程 |
| 目的端口 | 2B | 0~65535 | 标识接收方应用进程 |
| 长度 | 2B | 8~65535 | UDP报文长度 |
| 校验和 | 2B | 0~65535 | 校验UDP首部和数据 |
5.2.2 UDP校验和
要加上12字节的伪首部，包含：源IP地址、目的IP地址、协议号、UDP长度
- 二进制反码求和：
- 统计出每一位上1的个数：24135445 04247779
- 从末尾开始，模二进位；首位进位加到末位
- 24135445 042477(7+9/2=11)1
- 24135445 04247(7+11/2=12)11
- 24135445 0424(7+12/2=13)011
- …
- (2+6/2=5)0010110 11001011
- 10010110 1100101(1+5/2=3)
- 10010110 110010(1+3/2=2)1
- 10010110 11001(0+2/2=1)01
- 10010110 11001101
- 取反码：01101001 00110010，即为校验和
5.3 传输控制协议TCP
套接字(socket)：IP地址:端口号
每一条 TCP 连接唯一地被通信两端的两个端点（即两个套接字）确定。
5.3.1 TCP首部格式
| 字段 | 长度 | 值 | 说明 |
|---|---|---|---|
| 源端口 | 2B | 0~65535 | 标识发送方应用进程 |
| 目的端口 | 2B | 0~65535 | 标识接收方应用进程 |
| 序号 | 4B | 0~4294967295 | 每个字节都被编号，这是本报文段的第一个字节的序号 |
| 确认号ack | 4B | 0~4294967295 | 期望收到对方的下一个报文段的数据的第一个字节的序号，=序号+数据长度 |
| 数据偏移 | 4b | 0~15 | TCP首部长度，单位为4字节，最大为60字节 |
| 保留 | 6b | 0 | 保留位 |
| 控制位 | 6b | URG、ACK、PSH、RST、SYN、FIN | URG：紧急数据优先传送 ACK：确认号字段有效 PSH：接收方尽快将累积数据交给应用层 RST：连接差错，重置连接 SYN：连接请求/接受 FIN：发送完毕，释放连接 |
| 窗口rwnd | 16b | 0~65535 | 接收窗口大小，单位为字节 |
| 校验和 | 16b | 0~65535 | 首部和数据的校验和 |
| 紧急指针 | 16b | 0~65535 | 紧急数据的长度（字节），紧急数据最后一位=序号+紧急指针-1 |
| 选项 | 可变 | 最大报文段长度MSS、窗口扩大选项（3字节）、时间戳选项（10字节）、选择确认选项 | |
| 填充 | 可变 | 使首部长度为4的倍数 |
5.3.2 TCP可靠传输工作原理
自动重传请求ARQ(Automatic Repeat reQuest)：使用确认和重传机制，我们就可以在不可靠的传输网络上实现可靠的通信。
重传是自动进行的，不需要接收方发送重传请求。
TCP连接的每一端都必须设有两个窗口：一个发送窗口和一个接收窗口。TCP 两端的四个窗口经常处于动态变化之中。
TCP 的可靠传输机制用字节的序号进行控制，TCP所有的确认都是基于序号而不是基于报文段。
TCP连接的往返时间RTT也不是固定不变的，需要使用特定的算法估算较为合理的重传时间。
| 停止等待协议 | 连续ARQ协议 | |
|---|---|---|
| 发送分组数量 | 1 | 多个 |
| 控制传输 | 停止-等待 | 滑动窗口协议 |
| 确认方式 | 单独确认 | 单独确认+累积确认 |
| 超时定时 | 每个发送的分组 | 每个发送的分组 |
| 分组编号 | 每个分组 | 每个分组 |
| 重传机制 | 一个分组 | 回退N |
5.3.3 停止等待协议
停止等待协议是一种简单的ARQ协议。
在发送完一个分组后，必须暂时保留己发送的分组的副本。
分组和确认分组都必须进行编号。
优点：简单、易于实现
缺点：信道利用率低 $U=\dfrac{数据发送时间T_D}{T_D+往返时间RTT+ACK读取时间T_A}$
- 无差错
- A发送分组1，启动定时器，等待B确认（ACK）
- B收到分组1，发送ACK
- A收到ACK，发送分组2
- 分组差错
- A发送分组1，启动定时器，等待B确认
- 分组1损坏丢弃/中途丢失
- A超时未收到ACK，重发分组1
- B收到分组1，发送ACK
- 确认差错/迟到
- A发送分组1，启动定时器，等待B确认
- B收到分组1，发送ACK
- ACK中途丢失
- A超时未收到ACK，重发分组1
- B收到分组1，重复，丢弃，重发ACK
- A收到重发的ACK，发送分组2
5.3.4 连续ARQ协议
连续ARQ协议是一种流水线协议，允许发送方发送多个分组而不必等待接收方的确认。
确认方式：接收方累积确认：不必对收到的分组逐个发送确认，而是对按序到达的最后一个分组发送确认，表示：到这个分组为止的所有分组都已正确收到了。
累积确认的优点是：容易实现，即使确认丢失也不必重传。
重传方式：回退N：5个分组，第3个出错，接收方只对前2个分组发送确认，发送方收到确认后，重传第3个分组及后面的分组。
5.3.5 TCP可靠通信具体实现
- 假定A向B发送数据，当前A收到了B发来的确认报文，其中窗口=20，确认号=31（表示期望收到A的下一个报文的序号为31，且30以前的报文都已收到）。
- 此时A的发送窗口[31,50]，B的接收窗口[31,50]。A发送31~41
- 假设B收到31~33，发送确认号34，窗口=20的ACK，同时B的接收窗口滑动至[34,53]。
- A收到ACK，窗口滑动至[34,53]。
- 未收到的数据在超时后重传。
- 发送缓存用于存储：已发送但未收到确认的数据、准备发送的数据
- 接收缓存用于存储：已接收但未被使用的数据、未按序到达的数据
5.3.6 超时重传时间RTO的选择
- 报文往返时间RTT：从发送方发送数据报到接收方收到确认报文的时间
- 加权移动平均往返时间RTTs：当监测到一个新的RTT时，计算新的RTTs
- $RTT_S=(1-\alpha)RTT_S+\alpha RTT$，其中$\alpha$一般取$\dfrac{1}{8}$
- 平均偏差RTTd：初值为第一次RTT的一半，之后每次RTT的偏差为
- $RTT_D=(1-\beta)RTT_D+\beta|RTT_S-RTT|$，其中$\beta$一般取$\dfrac{1}{4}$
- 超时重传时间RTO：略大于RTTs，$RTO=RTT_S+4*RTT_D$
针对超时重传无法准确计算RTT的情况，可以使用Karn算法：
- 只要报文段重传了，就不采用其往返时间RTT样本
- 报文段每重传一次，就把超时重传时间RTO增大一些，一般加倍
5.4 TCP流量控制
端到端的问题
5.4.1 滑动窗口实现流量控制
流量控制：让发送方发送速率不要太快，要让接收方来得及接收。
下图的传输流程通过3次更改接收窗口大小来实现流量控制。
死锁：
B向A发送rwnd=0的ACK后，A不再发送数据。
B又有了一些缓存，向A发送rwnd>0的ACK，但是丢失了。
A等待B的ACK，B等待A的数据，形成死锁。
解决：收到rwnd=0后启动持续计时器，每次到期发送一个“零窗口探测报文段”
5.4.2 控制发送时机
- 缓存存放的数据达到最大报文段长度MSS字节时，发送一个TCP报文段
- 由发送方进程通过PSH、URG标志位控制发送时机
- 发送方计时器到期，发送一个报文段
Nagle算法：应用逐字节发送数据时，通过延迟发送小报文段来提高网络利用率。
- 发送方发送第一个数据字节，缓存后续字节
- 收到接收方的ACK后，发送缓存中的数据
- 当到达的数据达到发送窗口大小一半或MSS时，发送缓存中的数据
糊涂窗口综合症：交换的数据段大小不是全长而是一些较小的数据。由于每个数据段的有用数据（数据部分）较少，因而消耗的资源也更多，相应的传输效率也更低。
解决：接收方等待缓存有足够空间后，再发送rwnd>0的ACK
5.5 TCP拥塞控制
流量控制:是端到端的问题(接收端控制发送端)，点对点通信量的控制。抑制发送端发送速率，以便使接收端来得及接收。
拥塞控制:是一个全局性的过程，涉及到与降低网络传输性能有关的所有因素。防止过多数据注入到网络，使网络中的路由器或链路不致过载。
5.5.1 拥塞控制的基本原理
出现资源拥塞的条件：对资源需求的总和>可用资源
原因：链路容量不足、资源分配不均、路由器缓存空间和流量分布不均、处理机性能不足等
开环控制：设计网络时就考虑到拥塞控制，力求避免拥塞的发生
闭环控制：基于反馈环路
- 监测网络系统以便检测到拥塞在何时、何处发生
- 将拥塞发生的信息传送到可采取行动的地方
- 调整网络系统的运行以解决出现的问题
拥塞通知的传递策略：显示拥塞通告ECN
5.5.2 TCP拥塞控制算法
TCP采用基于窗口的方法进行拥塞控制，属于闭环控制。
TCP发送方维持一个拥塞窗口 CWND(Congestion Window):
- 拥塞窗口的大小取决于网络的拥塞程度，并且动态地在变化
- 发送端利用拥塞窗口根据网络的拥塞情况调整发送的数据量
- 网络没有出现拥塞，拥塞窗口增大一些，以便发送更多的分组，提高网络的利用率
- 网络出现拥塞或有可能出现拥塞，拥塞窗口减小一些，减少注入到网络中的分组数
TCP拥塞判断依据：重传定时器超时
TCP进行拥塞控制的算法有4种：慢开始、拥塞避免、快重传、快恢复
5.5.3 慢开始和拥塞避免
发送方最大报文段SMSS(Sender Maximum Segment Size)：MTU/MSS
初始拥塞窗口cwnd大小：
- 旧规定：1~2个SMSS
- 新规定RFC5681：
- $SMSS>2190B$：$cwnd=2SMSS$，<=2个报文段
- $2190B\ge SMSS>1095B$：$cwnd=3SMSS$，<=3个报文段
- $1095B\ge SMSS$：$cwnd=4SMSS$，<=4个报文段
- 慢开始门限ssthresh（状态变量）：防止cwnd增长过快引起网络拥塞
- $cwnd<ssthresh$：慢开始算法
- $cwnd\ge ssthresh$：拥塞避免算法
慢开始算法：cwnd从1开始，2，4，8，16指数增长，若超出ssthresh则取ssthresh
避免拥塞：cwnd>=ssthresh后，线性增长，每个RTT增加1
遇到超时：ssthresh=cwnd/2，cwnd=1，慢开始
5.5.3 快重传和快恢复
快重传FR(Fast Retransmission)算法可以让发送方尽早知道发生了个别报文段的丢失。
发送方只要一连收到三个重复确认，应当立即进行重传(即“快重传”)，这样就不会出现超时，发送方不会误认为出现了网络拥塞。
快恢复算法：在快重传的基础上，将ssthresh减半，cwnd=ssthresh，然后进入拥塞避免状态
5.6 TCP传输连接管理
TCP协议工作流程：
- 建立连接：三次握手
- 发起方向接收方发送SYN报文，请求建立连接
- SYN=1，seq=x，表示发送方本次报文的第一个字节的序号是x
- 接收方收到SYN报文后，回复SYN+ACK报文，表示同意建立连接
- SYN=1，ACK=1
- seq=y，表示接收方本报文的第一个字节的序号是y
- ack=x+1，表示接收方期望收到的下一个报文的序号是x+1，因为SYN报文占了一个序号
- 发起方收到SYN+ACK报文后，回复ACK报文，表示连接建立成功
- ACK=1
- seq=x+1，表示发送方本报文的第一个字节的序号是x+1
- ack=y+1，表示发送方期望收到的下一个报文的序号是y+1，因为SYN+ACK报文占了一个序号
- 三次握手完成，连接建立成功
- 发起方向接收方发送SYN报文，请求建立连接
- 数据传输：数据传输阶段
- 断开连接：四次挥手
- 发起方向接收方发送FIN报文，请求断开连接
- FIN=1，seq=u
- 接收方收到FIN报文后，回复ACK报文，表示收到断开请求
- ACK=1，seq=v，ack=u+1
- 接收方向发起方发送FIN+ACK报文，请求断开连接
- FIN=1，ACK=1，seq=w，ack=u+1
- 发起方收到FIN+ACK报文后，回复ACK报文，表示收到断开请求，等待2MSL后断开连接
- ACK=1，seq=u+1，ack=w+1
- 四次挥手完成，连接断开成功
- 发起方向接收方发送FIN报文，请求断开连接
- 谁想建立或断开连接，谁就是发起方。发起方就是客户端，接收方就是服务器端。
- MSL(Maximum Segment Lifetime)：报文最大生存时间，2MSL是为了保证网络中的所有报文都已经消失，不会再次出现在网络中，保证TCP协议的全双工连接能够可靠关闭
TCP四个计时器：超时重传计时器、持续计时器(0窗口报文探测计时器)、时间等待计时器(2MSL关闭连接)、保活计时器、TCP发送报文计时器。
六、应用层
6.1 域名系统DNS
域名服务器类型：
- 根域名服务器：管理顶级域名的服务器
- 顶级域名服务器：管理在该顶级域名服务器注册的二级域名服务器
- 权威域名服务器：管理自己的域名
- 本地域名服务器：提供域名解析服务，也称默认域名服务器
域名查询方式：
- 递归查询：主机向本地域名服务器发出查询请求，本地域名服务器不知道答案，则以DNS客户身份向根域名服务器发出查询请求
- 迭代查询：本地域名服务器向根域名服务器发出查询请求，根域名服务器告知本地域名服务器下一步应该向哪个域名服务器查询，本地域名服务器再向下一级域名服务器发出查询请求
6.2 文件传输协议FTP
文件传送协议 FTP (File Transfer Protocol) 是因特网上使用得最广泛的文件传送协议
实现了通过网络实现异构计算机间的文件“拷贝”、提供交互式的访问、屏蔽了各计算机系统的细节
FTP使用2个TCP连接：控制连接和数据连接
- 控制连接（TCP21）：用于传送请求，在整个会话期间保持打开状态
- 数据连接（TCP20）：用于传送文件内容，每次传送文件时打开，传送完毕后关闭
- 端口号：服务器使用熟知端口TCP21/20，客户端使用其他端口号>1023
FTP传输模式：文本模式/ASCII模式、二进制模式/Binary模式
6.3 简单文件传输协议TFTP
TFTP(Trivial File Transfer Protocol)是一个很小易于实现的文件传输协议
只支持传输文件，不支持交互，使用UDP数据报传输，端口号UDP69
文件长度恰好为 512 字节的整数倍，则在文件传送完毕后，还必须在最后发送一个只含首部而无数据的数据PDU
6.4 远程终端协议Telnet
C/S模式，TCP连接，NVT格式，端口号默认TCP23
Telnet协议的缺点：明文传送
| Telnet | SSH | |
|---|---|---|
| 功能 | 远程登录 | 远程登录 |
| 运输层协议 | TCP | TCP |
| 加密 | 明文 | RSA加密、支持压缩 |
| 端口号 | 23 | 22 |
6.5 万维网WWW
超文本传输协议HTTP(HyperText Transfer Protocol)是万维网的应用层协议，面向事务，本身无连接，是可靠交换文件的基础
HTTP协议永远都是客户端发起请求，服务器端响应请求，是无状态的协议，默认端口：TCP80
URL：<协议>://<主机>:<端口>/<路径>
HTTP报文：
- 请求报文：请求行、请求头、空行、请求体
- 响应报文：状态行、响应头、空行、响应体
状态码：三位数字
- 1xx：信息性状态码，接收到请求，继续处理
- 2xx：成功状态码，请求成功接收、理解、接受
- 3xx：重定向状态码，需要进一步操作
- 4xx：客户端错误状态码，请求包含语法错误或无法完成
- 5xx：服务器错误状态码，服务器无法完成明显有效的请求
6.6 电子邮件
两个重要标准：简单邮件传送协议、互联网报文交换格式(Internet Message Format)
三个主要构件：用户代理、邮件服务器、SMTP和POP3协议
发送邮件流程：
- 发件人UA向发件人邮件服务器发送邮件
- SMTP，TCP25
- 发件人邮件服务器以客户的身份向收件人邮件服务器发送邮件
- SMTP，TCP25
- 收件人从收件人邮件服务器接收邮件
- POP3，TCP110
SMTP三阶段：握手、传输、结束
POP3：仅客户端内读取
IMAP：客户端与邮件更新同步
6.7 DHCP协议
- DHCP Discover报文
- 客户端启动时，客户主机->DHCP服务器：谁能给我一个IP地址？
- 源地址：0.0.0.0
- 源端口：UDP 68
- 目的地址：255.255.255.255(广播)
- 目的端口：UDP 67
- DHCP Offer报文
- 服务器接收到广播数据包后，DHCP服务器->客户主机：我能给你分配IP地址192.168.1.2
- 源地址：服务器IP地址
- 源端口：UDP 67
- 目的地址：255.255.255.255(广播)
- 目的端口：UDP 68
- DHCP Request报文
- 客户端接收到DHCP服务器分配的IP地址后，客户主机->DHCP服务器：好的，我接受你分配的IP地址192.168.1.2，请求确认
- 源地址：0.0.0.0
- 源端口：UDP 68
- 目的地址：255.255.255.255(广播)
- 目的端口：UDP 67
- DHCP ACK报文
- 服务器接收到广播数据包后，DHCP服务器->客户主机：好的，我已经确认分配给你IP地址
- 源地址：服务器IP地址
- 源端口：UDP 67
- 目的地址：255.255.255.255(广播)
- 目的端口：UDP 68
DHCP端口号：UDP 67(服务器)和UDP 68(客户端)