3: Data Link Layer¶

约 3909 个字预计阅读时间 20 分钟

数据链路层：构建数据链路和逻辑链路，区别于物理层，物理层构建的是物理链路
- 物理层和数据链路层的本质作用都是用来构建网络通信、访问通道
- 物理链路是真实存在的物理线路和设备，数据链路层是一些必要的硬件（比如网络适配器）和软件（传输协议）组成的
- 数据链路层向上提供网络层的服务，处理传输的错误，调节数据流以确保接收方不会被淹没

3.1 Basic Concepts¶

3.1.1 Service Protocols to the Network Layer¶

Unacknowledged connectionless service 无确认无连接：源主机发送帧以前不需要事先建立链路连接，目的主机收到后不需要发回确认信号。
- 以太网是提供此类服务的典型数据链路层。
Acknowledged connectionless service 有确认无连接：源主机发送帧以前不需要事先建立链路连接，目的主机收到后必须发回确认信号。
- 802.11（WiFi）是这种链路层服务的典型例子。
Acknowledged connection-oriented service 有确认面向连接：建立链路、传输帧、释放链路。目的主机每收到一帧都要发回确认信号。
- 保证每个帧只被接收一次，并且所有帧都按正确顺序接收。
- 适用于长距离、不可靠的链路，如卫星信道或长途电话电路。

3.1.2 Framing（组帧）¶

Frame（帧）：是数据链路层发送数据的单位

Packet（数据包）和Frame的关系

Byte Count / Character Count
- 在帧首部使用一个计数字段来记录该帧的字节数（包括字段本身）。
- 一旦计数字段出错，帧的划分就也会出错。
Byte Stuffing
- 用一个标志字节（记作FLAG）用作开始和结束的分隔符。
- 问题：标志字节出现在数据帧
  - 为了避免数据段中的标志字节被当作开始或者结束符，对在它们前面加一个转义字节（ESC）进行填充
  - 为了防止数据字段末尾出现ESC字符，导致结束符FLAG被当作数据字段中普通字符，对数据字段中的ESC字符的前面也加一个ESC字符。
- 用于PPP协议（后面讲）
Bit Stuffing
- 用于HDLC和USB协议
- 每个帧以一个特殊的比特串（flag sequence）开始和结束，即01111110（十六进制的0x7E）
- 发送方扫描数据字段，发现5个连续的1就插入一个0。接收方看到五个连续的1后跟一个0时，它会自动解填充（即删除）这个0。
- 如果接收方失去同步，它只需查找flag sequence，因为它们只能出现在帧边界。
Physical Layer Coding Violation
- Manchester 编码中，用高-低电平对表示1，低-高电平对表示0，则可以用不合法的高-高和低-低表示帧的开始与结尾。
- 将 4B/5B 编码中的保留序列作为分隔符

3.2 Error Detection & Correction¶

错误控制的方式
- Error Correcting（纠错功能）
- Error Detecting with Retransmission（错误检测和重发）
Error correcting code（纠错码，可能不考）
- 假设一帧由 $m$ 个数据位和 $r$ 个冗余位组成，记 $n=m+r$，并将该编码描述成$(m,n)$码
- Hamming Distance（海明距离）：两个 codeword（码字）中不同的位的个数，如1000 1001与1011 0001的距离为3。可以用$D(x, y)$来表示。
  - 若干段编码组成的编码集合的hamming distance：任意两个编码组合的最小的hamming distance
  - 定理：$D(a,c)\leq D(a,b)+D(b,c)$
  - 想要检测至多$d$位的错误，我们采用的编码中，所有编码构成的集合的hamming distance应该至少为$d+1$
  - 想要修正至多$d$位的错误，编码构成的集合的hamming distance应该至少为$2d+1$。
    - 举例：对于一组编码 [0000000000,0000011111,1111100000,1111111111] ，hamming distance为5，最多能修正2位的错误。比如说我们接收到0000000111，如果我们认为最多会有2位出错，我们就知道正确的编码应该是0000011111；但是如果我们认为最多会有3位出错，我们边不能知道正确的编码是0000011111还是0000000000了。
- Hamming Code（海明码）：
  - 如果由$m$个信息位，$r$ 个校验位，则有公式$m+r+1\leq 2^r$。
  - 编码方式：比方说$m=4$，则$r=3$；将第$i$个（base 1）校验位放在第$2^i$位上，然后信息位按原顺序依次填入。
  - 海明码的海明距离为3，可以发现2bit的错误，可以纠正1bit的错误。校验位出错也能检出。
  - 假设传输的数据为8bit的00111001，在将信息位填入它们对应的位置后，对应位值为1的位序号有1010、1001、0111和0011。则 Hamming Code 为$1010\oplus 1001\oplus 0111\oplus 0011 = 0111$，依次填入校验位，结果为001101001111。假设传输出现错误，接收到的数据为001101101111，则计算 Syndrome Code 为$0111\oplus 1010\oplus 1001\oplus 0111\oplus 0110\oplus 0011 = 0110$，即出错位置为0110。
  - 这里描述的是偶校验海明码，默认情况下采取偶校验。奇校验在计算 Hamming Code 和 Syndrome Code 时，需要将校验位的值额外各取一次反。
- Binary convolutional codes、Reed-Solomon codes、Low-Density Parity Check codes：略
Cyclic Redundancy Check（CRC，循环冗余校验）
- 传输双方约定一个生成多项式（Generator Polynomial）。发送方生成一个校验码（CRC码），将其附加到原始数据末尾。接收方在接收到数据后，重新计算CRC码并与接收到的CRC码进行比较。
  - 生成多项式的最高位和最低位必须是1，每个生成多项式都可以表示为一个二进制数。举例来说，CRC-4的生成多项式为10011，即$x^4 + x + 1$。
  - CRC码计算流程如下：
    - 在原始数据后面添加生成多项式长度减1个0（即CRC码的位数）。例如，对于生成多项式CRC-4（5位），则在数据后面添加4个0。
    - 将预处理后的数据（原始数据 + 添加的0）与生成多项式进行模2除法运算。
      1. 将生成多项式与被除数（预处理后的数据）对齐，从最高位开始进行异或运算。
      2. 将异或结果作为新的被除数，继续与生成多项式进行异或运算，直到所有位都被处理。
    - 将计算得到的余数（也就是CRC校验码）附加到原始数据后面，替换掉之前添加的0。
- $r$阶的多项式能够检测所有长度$\leq r$的突发错误，长度大于$r+1$的错误漏检的概率为$(1/2)^r$。

3.3 Elementary Protocols¶

Protocol 1 Utopia协议：无限制simplex（单工）协议
- 认为不会丢帧或者帧损坏

3.3.1 Stop-and-Wait Protocols（停止-等待协议）¶

Protocol 2
- 最简单的通信协议，simplex traffic（单向通信），认为不会丢帧或者帧损坏。
- 可以解决发送速率大于接收速率的问题。
- 基本思路：每次发送一个包，发送完毕不立即发送下一个数据包，开始计时。等到接收方收到表示发送成功的数据包(ACK)之后，才可以进行下一次的发送。
- Half-duplex channel足以支持该协议。
Protocol 3
- 可以解决丢帧或者帧损坏问题，实现方法称为称为ARQ（Automatic Repeat reQuest，发送方超时了就可以重发而不必等待接收方信号）或PAR（Positive Acknowledgement with Retransmission，用ACK表示收到数据）
- 添加帧头部序列号和超时重传
  - 如果发送方收到了NAK包，需要重新发送同一个数据包
  - 如果数据丢失或者ACK丢失，发送方在一定时间内等不到接收方的回复数据包，就会Time Out，尝试主动重发。
  - 如果是ACK丢失，接收方在收到重发后丢弃原来接收的数据。
  - 引入一个1bit的序列号，使得接收方可以区分一个帧是重传的还是新来的。每发一次，序列号由0变1或由1变0。
- 协议效率的计算
  - $T_{frame}$ 表示发送方发出去完整的一个帧需要的时间，$T_{prop}$ 表示传输到接收方需要的时间
  - $T_{prop}=\frac{distance}{\mathcal {speed}}$ 而且 $T_{frame}=\frac{frame\_size}{bit\_rate}$
  - 令$\alpha = \frac{T_{prop}}{T_{frame}}$ 则链路利用率 $U=\frac 1 {2\alpha +1}$
- 停止等待协议的编程实现（不考，略）

3.3.2 Sliding Window Protocols（滑动窗口协议）¶

Bidirectional transmission
Piggybacking（稍待确认）：无需每个数据帧都返回ACK，而是在下一个数据帧中捎带确认信号。
Sliding window（滑动窗口）：发送方与接收方分别维护一组序列号（窗口），分别对应允许发送的帧以及允许接收的帧。
- 发送方的窗口随着新帧的发送和确认帧的接收而调整，接收方的窗口随着帧的接收和传递给网络层而调整。
- 允许乱序接收

Protocol 4 1-bit Sliding Window Protocol（滑动窗口协议）
- 与停止等待协议区别不大，不过可以双向传输
Protocol 5 GBN（Go back N，后退N帧协议）
- 发送方在发送N个数据帧后，如果发现这N个帧的前一个数据帧在计时器超时的时候仍然没有收到确认信息ACK，则重新传输出错帧及随后N个帧。接收方只按序接收数据帧，如果出现损坏帧或者丢帧，则丢弃后面接收到的所有帧。
- Cumulative Acknowledgement（累计确认）：为了降低开销，接收方可以在正确接收到连续$n$个帧后，只对最后一个帧发送确认信息，而无需确认前面的帧。
- 缓冲区：由于发送方可能需要在未来的某个时间重传所有未确认的帧，因此它必须缓冲所有已传输的帧，直到收到相应的ACK信号。
- 如果采用$n$比特对帧进行编号，发送窗口大小$W_T$有$1