3.1 设计目标

服务

  1. 差错控制
  2. 流量控制(避免数据淹没)
  3. 介质接入控制(如多个同时访问)
  4. 地址控制(Addressing)
  5. 打包(Packetiziing)(帧的封装和解封)

是网络层的传输单元(PDU)。包括帧头部,负载和帧尾部。

image-20210603200543926

一个路由器工作在网络层,但内部也包含物理层和数据链路层作为基础。

image-20210603201824692

路由选择是根据网络层。上述图中虚线的范围,也即相邻两台路由器之间的就是数据链路层。是一跳之内的通信。

实现

数据链路层实现于适配器(Adapter)中,也即网卡。包括 Ethernet 卡,PCMCIA 卡,802.11 卡。

类型

提供的服务

  1. 无确认,无连接的服务。(如:Ethernet)
  2. 有确认,无连接的服务。(如:802.11 WiFi)
  3. 有确认,面向连接的服务。(如 ATM,异步传输模式)

成帧

从收到的二进制串中判断帧的起始 ——拆分比特流

成帧方法

  1. 字符计数(如 DDCMP (DEC))
  2. 字节填充的标志字节
  3. 比特填充的标志比特
  4. 物理层冲突编码

字符计数法

用第一个字段记录帧的长度,后面就读取这个长度的数据作为帧内容。

image-20210603202924785

字节填充

image-20210603203119521

开始标志(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 错误检测和更正

差错类型

  1. 翻转错误
  2. 插入错误

翻转错误分为:

  1. 单比特差错
  2. 突发差错(多比特错误)

检错方法

  1. 奇偶校验
  2. CRC
  3. Checksum

纠错方法

  1. FEC,前向纠错
  2. ARQ,自动重传

ECC,Error Correcting Code

汉明纠错

要检测 t-bit 差错,两个码字的距离至少 $t+1$

要纠正 t-bit 差错,两个码字的距离至少 $2t+1$

为什么是 2t+1:假设两个独立码字的判定区域是 t,那么必须防止两者有交集,当等于 2t 时恰好相切,所以要比 2t 大并且是整数,所以是 2t+1

image-20210603205236401

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

差错检测

  1. 奇偶校验
  2. 交错校验

交错校验(n 校验位)

将数据分为 $k \times n$ 矩阵,发送时一行一行地发送,在最后增加校验位。

image-20210603213528633

如果突发长度是 $n$ 可以检出单比特错误。

多项式编码校验 (Polynomial)

image-20210603213825308

3.3 基本数据链路协议

防止接收方缓存溢出。基本方法是 基于反馈的流控

  1. 停止 - 等待
  2. 滑动窗口

Protocal 1: 乌托邦单工协议,不需要差错控制和流量控制 Protocal 2: 无差错信道上的单工停止等待协议 Protocal 3: 带重传的 ACK (PAR) Protocal 4: 一比特滑动窗口 Protocal 5: Go Back N (回退 N 步)协议 Protocal 6: 选择重传协议

3.4 滑动窗口协议

窗口大小的选择:

  1. 不能序号重叠:$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 协议

要求:

  1. $W_T + W_R \leq 2^n$
  2. $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 $$

总时间:

  1. 发送时延
  2. 传播时延
  3. 处理时延
  4. ack 时延
  5. ack 传回时延
  6. 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 数据链路协议示例

数据链路的类型:

  1. PPP
    1. HDLC,PPP
  2. 广播链路
    1. 可能是多个发送,多个接收,即出现共享信道。
    2. CSMA/CD,CSMA/CA

HDLC

HDLC:High-Level Data Link Control

特点:

  1. 面向连接,同步传输
  2. 零比特填充

基本结构:

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 协议

特点:

  1. 字节填充
  2. 无差错控制
  3. 只支持 静态 IP,无验证

0xc0 做分隔符

0xDB 0xDC 转义 0xC0

0xDB 0xDB 转义 0xDB

PPP

  1. 面向字节

  2. 用户认证

  3. 多协议

  4. 多物理层

  5. 压缩、连接协商

  6. 无连接

  7. 无流控

  8. 无差错控制

  9. 无序号

底层:物理层

  • 同步:PPP over SONET

  • 异步

  • PPPoE(PPP over Ethernet)

链路层:LCP(Link Control Protocol)

  • CRC 校验
  • 用户验证

网络层:NCP(Network Control Protocol)

无序号

字节填充

  • 转义字符:0x7D
  • Flag:0x7E
  • Flag 和 ASCII <= 0x20 的控制字符进行转义

工作过程:

image-20210603232825520

  1. 建立链路
  2. 认证
  3. 建立网络层
  4. 在网络层传输数据
  5. 断开网络层
  6. 断开链路