计算机网络第三章--数据链路层

每日一言

Data link layer design issues

Design lssues:

• Framing 封装成帧
• Error Control 差错控制
• Flow Control 流量控制

Services Provded to Network Layer

1. Unacknowledged connectionless services 无确认的无连接服务
   用途：LANs、Ethernet
   接收方不会对于收到的帧进行确认
2. Acknowledged connectionless service 有确认的无连接服务
   用途：wireless system
   接收方收到帧后会给发送方发送确认

Framing

Key problem: Node B must recognize exactly what set of bits constitutes a frame, that is, it must determine where the frame begins and ends.

将比特流划分成帧的主要目的是为了检测和纠正物理层在比特传输过程中可能出现的错误，数据链路层功能需要借助帧为单位来实现

Framing Methods （重要：名字，实现方法）

• Byte count 字节计数
• Flag bytes with byte stuffing 字节填充
• Flag bytes with bit stuffing 比特填充
• Physical layer coding violations 物理层编码违例法 (易考：名字虽与物理层有关，但却是数据链路层的方法)

Byte Count

实现方法：发送方在帧的头部字段中指定该帧的字节数

问题：一个差错就会破坏帧的边界，导致一连串帧错误

Byte Stuffing

实现方法：每个帧的开始和结束处插入一个特殊字节(Flag bytes)

问题：如果有效载荷部分包含与Flag bytes 相同的字节怎么办

答：在有效载荷中与Flag Bytes 相同的字节前面加入转译字节

Bit Stuffing

采用比特填充的帧，其开始和结束都有一个特殊的比特串：01111110 (0x7E) 连续的六个1

问题：如果有效载荷部分存在6个连续的1怎么办

答：发送方在每个 11111 的后面插入一个0，防止出现连续的六个1

接收方：若出现连续的5个1

• 若下一比特是0，则为有效载荷，直接丢弃后面的0
• 若下一比特是1，则为Flag bytes，一个帧结束

Physicial Layer Coding Violations

核心思想：选择的Flag 不会在数据部分出现。

曼切斯特编码/差分曼切斯特编码：

• 正常的信号在周期中间有跳变，持续的高电平(或低电平)为违例码，可以用作界定符

4B/5B编码方案：

• 4bit数据映射为5bit数据，剩余的一半字码(16个码字)未使用，可以用作定界符

Error control: correction and detection纠错与检错

错误控制：Make sure all frames are evenyually delivered to the network layer at the destination and in the proper order

• 接收方向发送方提供反馈(feedback)，确认消息(ACK)
• 由于硬件故障可能导致帧完全丢失，当帧确认消息丢失时，**定时器(timer)**会超时
• 定时器(timer)和序列号(sequence number)，保证每个帧恰好被传递到目的地的网络层一次。

Error Control Methods

Classification of Errors:

• Lost frames(丢失帧)
• Damaged frames(损坏帧)：some bits are in error

Error detection:

• Error-detecting codes 检错码

Error correction:

• Error-correcting codes 纠错码

Error Control Concepts

• Single-bit error:单个比特错误
• burst error:多个比特错误

Code word(码字)：一个包含m个数据位和r个校验位的n位单元(n = m+r)

Hamming Distance(海明距离)：两个码字之间不同对应比特的数目

• 检错：检查d个bit的错误，需要使用海明距离为d+1的编码
• 纠错：纠正d个bit的错误，需要使用海明距离为2d+1的编码

Error-Correcting Codes:Hamming code

求码字长度

要纠正单个bit的错误，校验位的长度需要满足公式：

$$
m + r +1 \leq 2^r
$$

例如数据位为 m=7 的码元，需要正确能够矫正单比特的错误

$$
7+r+1 \leq 2^r
$$

解得 $ r \geq 4$ 所以码字的最小长度为$7+4 = 11$

码字的编排

1. 码字的每个bit位都被编号，最左侧的第一个bit位为1，向右依次递增
2. 校验位从左向右依次被放到2的次幂的位置上(1,2,4,8…)
3. 其余位置(3,5,6,7,…) 填充数据位

如何校验数据

校验规则：

1. r1 对3,5,7,9… 等都具有$x%2 = 1$这一特性的数据位进行偶校验
2. r2对3,6,7,10…等都具有$(x/2^{1}) % 2 = 1$这样特性的数据位进行偶校验
3. 同理，r3校验的数据位满足：$(x / 2^{2}) % 2 = 1$

Error-Dectecting Code

• Odd & Even Parity(奇偶校验)
• Cyclic Redundancy Checks(CRCs) 循环冗余校验，数据链路层广泛使用的方法

Odd & Even Parity

Parity Check for Blocks (r位校验码)

• 每个数据块被视为一个矩阵。
• 为矩阵的每一列计算一个奇偶校验位，并将其附加到矩阵的最后一行 。
• 矩阵按行依次传输。

• 能够检测长度小于等于 r 的单个突发错误。
• 可以捕获所有由奇数个翻转比特组成的错误。
• 对于长度大于 r 且包含偶数个翻转比特的突发错误，无法检测到的概率为$2^{-r}$ 。

CRC(Cyclick Redundancy Check) 重要

发送方：

1. 生成多项式G(x)为的最高项的次幂为r，则需要先在m个数据为后补r个0。
2. 然后用n位除以生成多项式，得到结果
3. 将结果于n位相加，得到传输字码T(x)

接收方：

• 无错误：没有传出错误时,T(x)/G(x) = 0
• 有错误：结果为E(x)/G(x)，(E(x)表示错误多项式)
• 漏检：E(x)/G(x) = 0

效果：

• 所有长度小于等于r的突发错误都可以被检测

Error Correcting or Detecting

• 低可靠信道：如无线网，会出现很多错，选择纠错码更好
• 高可靠信道：如光纤，使用检错码，并仅重传偶尔发现的错误，效率更高

Error Control Summary

Flow Control

流量控制主要用于处理发送方想要传输帧的速度比接收方能够接受的速度更快的情况，其本质是限制发送方可以发送的数据量。

两种实现方法：

• Feedback-based(基于反馈):接收方发送反馈信息，告知发送方可以发送更多数据
• Rate-based(基于速率)

Elementary data link protocols 基本数据链路协议

• An Unrestricted(无限制的) Simplex(单工) Protocol
• A Simplex Stop-and-Wait Protocol 单工停止等待协议
• A Simplex Protocol for a Noisy Channel 噪声信道的单工协议

Protocol 1 :Utopia(乌托邦)

假设：

• Simplex: Data are transmitted in one direction only
• 完美信道：never damages or loss frames
• 始终就绪：the transmitting and receiving network layers are always ready
• Processing time can be ignored. Infinite buffer space is avaliable

完美但不现实

frame s 是分装成帧的结构体，其结构如下：

typedef struct{
    frame_kind kind;
    seq_nr seq;
    seq_nr ack;
    packet info;
}frame;

Protocol 2: Stop-and-Wait Protocol for a Error-free Channel

假设：

• Channel is error-free
• Data traffic is still simplex(但是需要半双工链路支持发送Acknowledge)

限制：

• 如果发送方以高于接收方处理能力的速度发送数据，那么接收方会被数据淹没(overwhelming)

Protocol 3: A Simplex Protocol for a Noisy Channel

增加限制：

• 通信信道会出错，导致：
  • 帧在传输过程中可能会被损坏(damage)，接收方能够检测出来。
  • 帧在传输过程中可能会直接丢失(lost)，永远不可能到达接收方。
• 解决方法：
  • 发送方增加一个计时器(timer)，如果经过一段时间没有收到确认，发送方计时器将超时(timeout)，于是再次发送改帧

可能出现的四种情况：

在第四种情况：ACK丢失时。接收方无法分辨后面传来的帧与前一次传来的帧是同一帧。

Sequence Number 序列号

Distinguish a frame that it is seeing for the first time from a restransmission 区分首次收到的帧和重传的帧

• Put a sequence number in the header of each frame.

链路层：只需要1bit的位置就可以，编号范围为0，1.

ARQ(Automatic Repeat reQuest) 自动重复请求

总结：

Timer:不易设置的过短，会导致发送方发送无意义的帧，虽然不影响正确性，但是影响性能

Sliding window protocols 滑动窗口协议

停等协议对于信道的利用率很低，所以下面推出：

• 流水线协议/管道协议：允许发送方在没收到确认前连续发送多个帧。(滑动窗口协议的本质思想)

Sliding Window Protocols Basis

Goal：

• 对可以连续发出的最多帧数进行限制

Sequence Number

• 循环重复使用有限的帧序号

Flow Control

• Sending window： 大小$W_S$表示在收到对方确认的信息之前，可以连续发出的最多数据帧数。
• Receving window：大小$W_R$表示可以连续接收的最多数据帧数。

Sending window 发送窗口：

• 发送窗口维护了一组序列号，这些序列号对应着允许发送的帧，这些帧就处于发送窗口内。

  

Receiving window 接收窗口：

• 接收方也会维护一个接收窗口，代表着允许接收的帧的序号，只有落在接收窗口中的帧才会被接收，窗口之外的帧会被丢弃或暂存。

  

For full-duplex (双全工) data transmission:

• Use two separate(独立) communciation channels and use each one for simplex (单向) data traffic(数据传输).
• Use the same circuit(电线) for data in both directions.

Piggybacking ACK 捎带确认

• When a data frame arrives, instead of immediately sending a separate control frame, the receiver restrains(抑制) itself and waits until the network layer passes it the next packet.
• ACK is attach to the outgoing data frame(using the ack field in the frame header)
• 当接收到一个帧时，接收方不会立刻发送一个单独的ACK帧，而是等待网络层传来下一个数据包，然后将ack填充在数据帧的头部，减少了单独控制帧的发送，提高了传输效率。

Protocol 4 : Sliding Window of Size 1

• 发送窗口最大值为1
• 接收窗口最大值为1
• $W_S = W_R = 1$ 序号空间0，1

发送方

1. 初始化

ack_expected =0;	//发送的ack的序号
frame_expected = 0;	//作为接收方时，期望下一个收到的帧序号
next_frame_to_send = 0;	//作为发送方时，下一个即将发送的帧序号

2. 从网络层接收分组，放入相应的缓冲区，构造帧，物理层发送， 开始计时器
3. 等待确认帧到达，从物理层接收一个帧，判断确认号是否正确，正确则停止计时器，并从网络层接收新的分组
4. 发送新的帧，跳转到3.

接收方

1. 初始化：

   ack_expected =0;	//发送的ack的序号
   frame_expected = 0;	//作为接收方时，期望下一个收到的帧序号
   next_frame_to_send = 0;	//作为发送方时，下一个即将发送的帧序号

2. 等待帧到达，从物理层接收一个帧，校验和计算，并判断收到的帧序号是否正确，正确则交给网络层处理，frame_expected++

3. 返回确认帧，跳转至2

在此协议中，链路是双全工的，接收双方的代码一致，所以不再区分发送方和接收方的代码。

现在我们将接收方和发送方进行了合并，但是信道的利用率仍然很低，我们采用流水线机制提升传输效率：

我们增加发送窗口的数量，同时选择增大接收窗口的数量，可以一次发送多个帧，同时返回多个ACK

Protocol 5 :GO Back N(GBN)

协议5中，我们先增大发送窗口，而将接收窗口的大小仍然为1

• Use window to control number of outsranding frames
• If receiver detacts error, discard(丢弃) that frame and all future frames until error frame recevied correctly
• Transmitter must go back and retransmit that frame and all subsequent(后续的) frames

Cumulative ACK 累计确认

不必对收到的分组逐个发送确认，而是对按序到达的最后一个分组发送确认

接下来我们介绍实际情况下的用例，当用3 bit来存储接收窗口和发送窗口时，总共可用的序号有：8个

由于需要避免发送窗口与接收窗口重叠:

• 发送窗口为0~6，大小为7
• 接收窗口只有一个大小

遇到错误时的Go-Back-N

情景：

现在发送方连续发送一个发送窗口中的所有帧，序号为0~6，全部都正常到达了。

接收方先后收到序号为0~6的所有帧，并且依次发送了ACK(0)到ACK(6)

1. 发送过程中数据包3丢失/错误

   • 接收方先后收到帧0到2，然后发送ACK(0)到ACK(2)，然后收到帧4到6，但是由于没有收到帧3，所以收到后续帧后依然发送ACK(2)
   • 发送方经过一段时间后，定时器确认超时没有收到后续的ACK，所以将重新发送帧3到6

2. 接收方返回的ACK(3)丢失

   • 接收方收到帧0~6 并且返回ACK(0)到ACK(6)，ACK(3)丢失后，发送可以通过ACK(6)确定接收方已经正确收到了所有的帧。不再进行重复发送

Protocol 6:Selective Repeat 选择重传(SR)

Sender:

• Only Rejected frames are retransmitted

Receiver:

• Subsequent frames are accepted by the receiver and buffered, must maintain large enough buffer(缓冲区)

接收窗口和发送窗口的大小都为序列号范围大小的一半

$$
W_S = W_r = 2^{n-1}
$$

ACK timer

• 启动机制 ：当一个按序到达的数据帧抵达后，会通过 “start_ack_timer” 启动 ACK 定时器 。
• 发送确认帧条件 ：如果在该定时器到期之前没有反向流量(reverse traffic)，就会发送一个单独的 ACK 帧。
• 停止机制 ：一旦出现反向流量，ACK 定时器就会停止。
• 时间特性 ：与 ACK 定时器相关的超时时间明显短于用于数据帧超时计时的定时器。

NAK(negative acknowledge)

NAK frame is a request for retransmission

Two cases when the receiver should be suspicious：

• A damaged frame has arriver
• A frame other than the expected one arrived

避免给同一帧发送重复的重传请求，接收器跟踪是否已经为给定帧发送了NAK

SR summary

基本原理：

• 在如果一个数据帧计时器超时或者收到NAK，就认为该帧丢失或者被破环，只重传NAK指定的帧(由NAK帧中ack序号推断)或计时器超时的数据帧
• 在接收端，只把出错的帧丢弃(并向发送端回复NAK)；如果落在窗口内的帧从未接受过并且没有出错，则存储起来，等比它序号小的所有帧都正确接收后，按次序交付给网络层

协议六：SR协议代码

例题：数据链路层采用GBN协议,发送方已经发送了编号为0-7的帧,当计时器超时时,若发送方只收到0,2,3号帧的确认,则发送方需要重发的帧是?

GBN采用累计确认的方式，若能够收到3号帧的确认，则表明已经正确收到0，1，2，3号帧。则发送方只会重传4，5，6，7 号帧。

例题：数据链路层采用SR协议，发送方已经发送了编号0-7的帧，当计时器超时时，若发送方收到了0，2，3号帧的确认，则发送方需要重发的帧是？

SR协议的每个确认帧与其他帧没有关系，发送方只会发送定时器超时的帧和收到NAK的帧，所以哪个帧的定时器超时就会重发哪个帧。如果最后1，4，5，6，7帧的定时器都超时的化，则会重发1，4，5，6，7号帧。

Performance of Protocols

Basis

• Bandwidth-delay product(时延带宽积)：传播时延 * 带宽
• 时延带宽积：表示管道中填满时由多少bit数据
  • 发送端连续发送数据，则在发送的第一个bit即将到达终点时，发送端就已经发送了时延带宽积个bit，这些bit都在链路上向前移动。

协议的性能评价：传输数据的时间/总时间

常规情况下：从一帧被发送到下一帧发送的时间间隔为一个帧的周期 $T_{frame}$

$$
T_{frame} = t_{prop} + t_{frame} + t_{proc} + t_{prop} + t_{ack} + t_{proc}
$$

• $t_{prop}$ ：传播时延
• $t_{frame}$：1帧的传输时延
• $t_{proc}$：处理时延(很小，在题目不提及时一般忽略)
• $t_{ack}$：ack的传输时延(很小，题目不提及忽略)

停等协议(Stop-and-wait)的传输效率：

$$
T = n(t_{frame} + t_{prop} + t_prop)
$$

链路利用率U：

$$
U = \frac{n \times t_{\text{frame}}}{n(2t_{\text{prop}} + t_{\text{frame}})} = \frac{t_{\text{frame}}}{2t_{\text{prop}} + t_{\text{frame}}}
$$

公式转换

一个特殊的中间值：

1. 参数 a:定义为传播时间与帧传输时间的比值。

   $$
   a = \frac{t_{\text{prop}}}{t_{\text{frame}}}
   $$

   这个参数 $a$ 反映了传播延迟相对于传输延迟的大小。

   将我们之前得到的U的公式上下同时除以$t_{frame}$，再以a代换得到：

   $$
   U =\frac{1}{1 + 2a}
   $$

2. 基本参数定义:

   • 信道容量 (Channel Capacity): $B$ bits/sec (表示信道每秒可以传输多少比特)
   • 帧大小 (Frame Size): $I$ bits (表示每个数据帧包含的比特数)
   • 单向传播时间 (Propagation Time): $R$ sec (表示信号从发送端传播到接收端所需的时间，图中也用 $t_{\text{prop}}$ 表示，即 $t_{\text{prop}} = R$)

3. 帧传输时间 (Frame Transmission Time): $t_{\text{frame}} = I/B$ (表示将一个完整的帧发送到信道上所需的时间)

4. 传播时间：$t_{prop} = R$

5. 用参数 B, I, R 的最终形式: 将 $a = BR/I$ 代入上式：

$$
U = \frac{1}{1 + 2BR/I}
$$

滑动窗口协议(Sliding window)的传输效率

公式：

$$
U = \begin{cases}
1 & W \ge 2a + 1 \
\frac{W}{2a + 1} & W < 2a + 1
\end{cases}
$$

• W为发送方的窗口大小

1. 当 $W \ge 2a + 1$ 时: 这意味着发送窗口足够大，可以在第一个帧的确认信息返回之前，持续不断地发送数据，填满整个“往返管道”。发送方永远不会因为等待确认而空闲，因此信道可以被 100% 利用，即 $U = 1$。
2. 当 $W < 2a + 1$ 时: 这意味着发送窗口不够大，发送方在发送完 W 个帧后，即使信道还有能力传输更多数据，也必须停下来等待确认信息。在这种情况下，信道利用率受限于窗口大小。在一个完整的发送周期（时间约为 $2t_{\text{prop}} + t_{\text{frame}}$，对应于 $2a + 1$ 个帧的传输时间），发送方实际只发送了 W 个帧。因此，利用率是实际发送的帧数 W 与理论上可以发送的最大帧数 $2a + 1$ 的比值，即 $U = \frac{W}{2a + 1}$。

Stop-and-wait with error

再次定义几个新的变量：

• $N_r$ : number of transmission
• P：Probility of Frame Error

最终传输效率公式：

$$
U = \frac{1 - P}{1 + 2\alpha}
$$

Error-free sliding window with piggybacking(捎带确认)

$$
U = \frac{W}{2+2a}
$$

解释为何分母变为2+2a:

• 此时要求为捎带确认，返回的ack会封装在回传的数据帧中
• 回传的数据帧也需要时间为$t_{frame}$的传输时间
• $$
  T = 2t_{frame} + 2t_{prop}
  $$

Protocol examples:HDLC/SLIP/PPP

HDLC(High-Level Data Link Control)

基本概念：

• Primary station(主站)

  • 负责控制整个数据链路的操作。

  • 它发出的帧（数据包）被称为 命令 (Commands)。

  • 尤其在多点配置中）负责维护与每一个从站之间的独立逻辑连接。

    

• Secondary station(从站)

  • 运行在主站的控制之下。

  • 它发出的帧被称为 响应 (Responses)，通常是回应主站发来的命令。

    

• Combined station(复合站)

  • 这种站既可以发送命令，也可以发送响应。

  • 它结合了主站和从站的功能，通常用于平衡配置（例如两个对等站之间的点对点通信）。

    

HDLC帧的基本格式

采用bit填充(Bit stuffing)的方式

HDLC的三种帧

三种不同类型的帧的控制信号在Control信息段中

• I-frame 信息帧:An information frame (INFO)
• S-frame 监控帧：A supervisory frame (RR/RNR/REJ/SREJ)
• U-frame 无序号帧: An unnumbered frame (SABM/UA/DISC/FRMR)

I-frame

I-frame 的第一个bit为0：

S-frame

S-frame 的前两个bit为 10

RR：Reveiver Ready

• ACK frame used to indicate(表示) the N(R) frame expected
• 这个帧主要用于没有反向流量(reverse traffic)可以捎带(piggybacking)时。

RNR：Reveiver Not Ready

• 这个帧确认收到的所有帧，但是不包括N(R)，同时告诉发送方停止发送。

REJ：Reject 拒绝接收

• REJ 表示检测到传输错误。
• 其中的 N (R) 字段指示没有被正确接收的第一个帧，也就是需要重传的帧。
• 发送方需要重传从 N (R) 开始的所有未确认帧。

SREJ: Selective Rejective 选择性拒收

• SREJ 意为仅要求重传由 N (R) 指定的帧。

U-frame

U-frame 开头两个bit为 11，用于控制链路本身，如呼叫、确认和断开连接等控制。

PPP protocol 点对点协议

本章重点