«计算机网络»笔记：第3章 数据链路层
3.1 设计目标
服务
-
差错控制
-
流量控制（避免数据淹没）
-
介质接入控制（如多个同时访问）
-
地址控制（Addressing）
-
打包（Packetiziing）（帧的封装和解封）
帧是网络层的传输单元（PDU）。包括帧头部，负载和帧尾部。
一个路由器工作在网络层，但内部也包含物理层和数据链路层作为基础。
路由选择是根据网络层。上述图中虚线的范围，也即相邻两台路由器之间的就是数据链路层。是一跳之内的通信。
实现
数据链路层实现于适配器（Adapter）中，也即网卡。包括 Ethernet 卡，PCMCIA 卡，802.11 卡。
类型
提供的服务
-
无确认，无连接的服务。（如：Ethernet）
-
有确认，无连接的服务。（如：802.11 WiFi）
-
有确认，面向连接的服务。（如 ATM，异步传输模式）
成帧
从收到的二进制串中判断帧的起始——拆分比特流。
成帧方法
-
字符计数（如 DDCMP(DEC)）
-
字节填充的标志字节
-
比特填充的标志比特
-
物理层冲突编码
字符计数法
用第一个字段记录帧的长度，后面就读取这个长度的数据作为帧内容。
字节填充
用开始标志（SOH，0x01，Start of header）和结束标志（EOT，0x04，End of trailer）标记。
如果帧负载中出现了开始和结束标志一样的数据，就用转义标志（ESC，0x1B）转义。
同样也要对出现在负载的 ESC 转义。
（零）比特填充（Bit stuffing）
上面面向字符的传输会导致利用率不高，而且依赖于特定的编码字符集。
比特填充的长度任意。
起始判定：用 0111 1110 标记帧的起始。
填充方法：如果出现连续五个 1，就插入一个 0.
数据：0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0
填充后：0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0
物理层非法编码
例如曼彻斯特编码总是高低电平交替的，那么就可以用连续高、连续低作为起始标志。
差错控制
3.2 错误检测和更正
差错类型
-
翻转错误
-
插入错误
翻转错误分为：
-
单比特差错
-
突发差错（多比特错误）
检错方法
-
奇偶校验
-
CRC
-
Checksum
纠错方法
-
FEC，前向纠错
-
ARQ，自动重传
ECC，Error Correcting Code
汉明纠错
要检测 t-bit 差错，两个码字的距离至少 $t+1$
要纠正 t-bit 差错，两个码字的距离至少 $2t+1$
为什么是 2t+1：假设两个独立码字的判定区域是 t，那么必须防止两者有交集，当等于 2t 时恰好相切，所以要比 2t 大并且是整数，所以是 2t+1
Q：更正单比特错误至少要几个校验位？
设 m 是消息比特，r 是校验比特，n 是码字长度（$n = m+r$）
则合法编码有 $2^m$ 个。每个合法码字和它距离为 1 的有 $n$ 个（第 1 位出错、第二位出错、……第 n+1 位出错）（+1 是校验码）。
因此合法码字（消息+校验）有 $(n+1)2^m$ 个。
由于合法码字的数量不能超过码字理论上限（n bit，每个两种可能，$2^n$）因此有：
$$ (n+1)2^m \leq 2^n $$带入 $n =m+r$ 化简得：$(m+r+1) \leq 2^r$
可以记住：码的总长度+1要小于校验码的可能个数
Hamming 码的编码解码简便法
编码：
例如数据是 1011
b7 b6 b5 b4 b3 b2 b1
1 1 0 p3 1 p2 p1
将为 1 的位号表示为二进制，然后各位异或（别进位）
b3 011
b6 110
b7 111
-----------
010
得到的即为 p3p2p1=010。结果：
1 1 0 0 1 1 0
解码：
b7 b6 b5 b4 b3 b2 b1
1 1 0 0 1 1 0
将为 1 的其位号表示为二进制：
b7 111
b6 110
b3 011
b2 010
------------
000
S4S2S1 = 000，异或为 0，无措。
如果是可靠通道如有线电路，通常用检错码，错的重传就行。
如果是不可靠通道如无线电路，通常用纠错码。
EDC，Error Detecting Code
差错检测
-
奇偶校验
-
交错校验
交错校验（n校验位）
将数据分为 $k \times n$ 矩阵，发送时一行一行地发送，在最后增加校验位。
如果突发长度是 $n$ 可以检出单比特错误。
多项式编码校验 （Polynomial）
3.3 基本数据链路协议
防止接收方缓存溢出。基本方法是 基于反馈的流控：
-
停止-等待
-
滑动窗口
Protocal 1: 乌托邦单工协议，不需要差错控制和流量控制 Protocal 2: 无差错信道上的单工停止等待协议 Protocal 3: 带重传的 ACK (PAR) Protocal 4: 一比特滑动窗口 Protocal 5: Go Back N （回退 N 步）协议 Protocal 6: 选择重传协议
3.4 滑动窗口协议
窗口大小的选择：
- 不能序号重叠：$W_T \leq 2^n -1$。例如序号空间是 0~7，则窗口大小不能超过 7
GBN 协议
ack_expected指向 buffer 的头
next_frame_to_send指向 buffer 的尾的下一个
| buff |
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
^ ^
ack_expected next_frame_to_send
缺点：
- 一次只能收一帧，出错要重发多个帧
SR 协议
要求：
-
$W_T + W_R \leq 2^n$
-
$W_T \geq W_R$
$W_T$：发送窗口
$W_R$：接收窗口
$n$：序号 bit 数
实际中，取二者相等，为 $2^{n-1}$
性能分析
$t_t$：发送时延
$t_p$：传播时延
$t_q$：排队时延等
$\alpha = t_p / t_t$
$t_{\text{xrf}}$：帧传输时间
$$ t_{\text{xrf}} = t_t + t_p + t_q $$总时间：
-
发送时延
-
传播时延
-
处理时延
-
ack 时延
-
ack 传回时延
-
ack 处理时延
一般只考虑前两个，后面的忽略不计。
信道利用率：
$$ U = \dfrac{t_t}{2t_p + t_t} = \dfrac{1}{1+2\alpha} $$如果差错率是 $p$，
$$ U = \dfrac{1-p}{1+2\alpha} $$
如果窗口大小 $W\geq 2\alpha +1$，信道利用率是 $1$。
如果 $W < 2\alpha +1$，信道利用率是 $\dfrac{W}{2\alpha +1}$
注：带宽时延积 $BD = \dfrac{t_p}{t_t} = \alpha$
对于 稍待确认 的：
$$ U = \dfrac{W}{2\alpha+2} $$3.5 数据链路协议示例
数据链路的类型：
-
PPP
- HDLC，PPP
-
广播链路
-
可能是多个发送，多个接收，即出现共享信道。
-
CSMA/CD，CSMA/CA
-
HDLC
HDLC：High-Level Data Link Control
特点：
-
面向连接，同步传输
-
零比特填充
基本结构：
Flag | Addr | Cntl | Data | Chksum | Flag
Flag 采用 01111110 填充
Checksum 使用 CRC
控制字段用于区分帧类型
1 2 3 4 5 6 7 8
0 < NS > P/F < NR > // 信息帧
1 0 < S > P/F < NR > // 监督帧
1 1 < M > P/F < NR > // 监督帧
NS：发送序号
NR：接收序号
S：监督功能位
M：无编号，管理类型
SLIP：串行线 IP 协议
特点：
-
字节填充
-
无差错控制
-
只支持 静态 IP，无验证
0xc0 做分隔符
0xDB 0xDC 转义 0xC0
0xDB 0xDB 转义 0xDB
PPP
-
面向字节
-
用户认证
-
多协议
-
多物理层
-
压缩、连接协商
-
无连接
-
无流控
-
无差错控制
-
无序号
底层：物理层
-
同步：PPP over SONET
-
异步
-
PPPoE（PPP over Ethernet）
链路层：LCP（Link Control Protocol）
-
CRC 校验
-
用户验证
网络层：NCP（Network Control Protocol）
无序号
字节填充
-
转义字符：0x7D
-
Flag：0x7E
-
Flag 和 ASCII <= 0x20 的控制字符进行转义
工作过程：
-
建立链路
-
认证
-
建立网络层
-
在网络层传输数据
-
断开网络层
-
断开链路