EE6223-P1_2-Data-Link-Layer

引入

这一章节，主要讨论数据链路层的帧（frames）

数据链路层的主要作用是将一帧数据从一个节点传输到另一个临近的节点，它是物理层之上的一层逻辑，为网络层提供服务。链路层通常在网络适配器（NIC，网卡）中实现，比如以太网网卡、PCMCIA 卡等硬件设备。

在数据链路层中，有两种信道：点对点（Point-to-Point）和广播（Broadcast）。

链路层的核心功能有：

成帧（Framing）：将网络层传递下来的数据报（datagram）封装成帧（frame），并添加必要的头部（header）和尾部（trailer）开销。

流量控制（Flow control）：调节相邻发送节点和接收节点之间的发送速率，避免接收方缓冲区溢出，导致数据丢失。

差错控制（Error control）：接收方检测帧中是否存在传输错误。如果检测到错误，接收方会通过信号通知发送方重传该帧，或者直接丢弃出错的帧。

链路访问（Link access）：由介质访问控制（MAC）协议规定，解决多个节点共享同一通信信道时的访问规则问题。例如：以太网的 CSMA/CD、WiFi 的 CSMA/CA，都是典型的 MAC 协议。

成帧（framing）和填充

HDLC

高级数据链路控制（High-Level Data Link Control ，HDLC)是一种在计算机网络中广泛使用的数据链路层协议，由 国际标准化组织（ISO） 制定，是面向比特的同步数据链路控制协议的代表。本小节以HDLC为范例，介绍数据链路层。

HDLC 帧的首尾都是 Flag：01111110，中间是地址、控制、信息和校验字段。标志位被用来标记帧的开始和结束。

Flag	Address（8bit）	Control（8/16 bit）	Information	FCS(16/32 bit)	Flag

但问题来了：如果帧内部的数据恰好也出现了和 Flag 一样的比特序列，接收方就会误以为帧提前结束，导致解析错误。填充（Stuffing）就是为了避免这种歧义：发送方在数据中 “插入” 额外的比特 / 字节，破坏 Flag 的模式。接收方收到后，再把这些插入的部分 “移除”，恢复原始数据。

• 发送方：在数据（Address+Control+Info+FCS）中每遇到连续 5 个1，就自动插入一个0。
• 接收方：检测到连续 5 个1后，若下一位是0则删除该0；若下两位是10则判定为 Flag。

例如：模拟数据0110 1111 1111 1100的Stuffing

首先填充头尾flag，然后按照规则在Data中填0：0111110 0110 1111 1011 1110 00 0111110

例如：模拟数据0111 1110 0001 1101 1111 0111 1101 1001 1111 10 的Receiveing

0111,1110是Falg，移除，得到Data：0001 1101 1111 0111 1101 10

找到中间有0001 1101 1111 0 111 1101 10两组连续5个1后接0，因此移除0，得到：0001 1101 1111 1111 1110

PPP

PPP（Point-to-Point Protocol，点对点协议）是一种在数据链路层广泛使用的协议，主要用于在两个节点之间建立直接的连接，以字节为单位进行传输和处理，实现比 HDLC 更简单，兼容性更好。

同HDLC一样，PPP 帧的首尾由 Flag 0x7E（01111110）界定。但是由于PPP是面向字节操作的，因此不能简单补0，它的填充规则是：

1. 使用0x7D作为跳过控制符（Control Escape），数据中包含0x7E或0x7D需要被替换
2. 当数据中出现0x7E(0111 1110)或0x7D(0111 1101)时，先插入0x7D，再将原字节与0x20异或。
3. 检测到0x7D时，丢弃它，并将下一字节与0x20 (0010 0000)异或，恢复原始数据。

例题：对 0x41 0x7D 0x42 0x7E 0x50 0x70 0x46进行填充操作

观察到数据内包含一个0x7D和一个0x7E，0x7D(0111 1101) XOR 0x20(0010 0000) = 0x5D(0101 1101)，0x7E(0111 1110) XOR 0x20(0010 0000) = 0x5E(0101 1110)。

因此在其前方插入0x7D，再使用异或结果替换原值，得到：0x41 0x7D 0x5D 0x42 0x7D 0x5E 0x50 0x70 0x46

例题：接收到了0x7E 0x7D 0x5E 0x7D 0x5D 0x5E 0x7E恢复未填充数据

首先去除头尾flag0x7E，数据为0x7D 0x5E 0x7D 0x5D 0x5E。遇到0x7D就丢弃，并将下一byte与0x20异或，得到：0x7E 0x7D 0x5E

HDLC协议详解

两种工作模式

HDLC 定义了两种主要的操作模式，用于不同的网络拓扑和通信需求。在连接建立（connection establishment）阶段确定使用哪种模式。

响应模式（Response Mode）

• 主站（Primary）：负责发起通信、发送命令（Commands），并控制整个链路。
• 次站（Secondary）：只能在主站轮询时，才能发送响应（Responses）。

主站依次向每个次站发送轮询，次站收到后才回传数据，是一种半双工的、主从式的通信。

异步平衡模式（Asynchronous Balanced Mode, ABM）

该模式用于全双工点对点链路（full-duplex point-to-point links）。通信的双方都可以是主站或次站，即每个节点都可以主动发起命令和响应，地位平等。双方可以同时双向传输数据，无需等待轮询，效率更高。

控制信息

控制字段是 HDLC 的核心，它定义了三种不同类型的帧，每种帧的控制字段结构不同：

信息帧（Information Frame, I-frame）

如果Control被字段第一位为0，则表明该帧时信息帧，information字段内为用户数据。

信息帧的Control字段用于用户数据传输管理：

• N(S)：发送序列号（Send Sequence Number），用于流量控制和顺序控制。
• P/F：轮询 / 终止位（Poll/Final bit），用于主站和次站之间的交互。主站发送时，这一位被称为P位；次站发送时，这一位被称为F位。
• N(R)：接收序列号（Receive Sequence Number），用于捎带确认（piggybacked ACK）。

HDLC使用滑窗协议进行流控和差错控制，而信息帧的控制字段就是用来支撑滑窗协议的。

• 序列号：每个 I 帧都包含一个发送序列号 N(S) 。序列号可以是 3 位或 7 位。
• 捎带确认（Piggybacked ACK）：当一个节点发送某一帧时，可以在 N(R) 字段中捎带对之前收到的帧进行确认。N(R) 表示期望接收的下一个帧的序号，这意味着它确认了所有序号小于 N(R) 的帧都已正确接收。举个例子，例如，N(R)=3时，表明编号为2的之前帧已经被正确接收，下一次接收端希望接收编号为3的帧。
• P/F 位的作用：主站通过设置 P=1 来轮询次站；次站在响应的最后一个帧中设置 F=1 表示传输结束。

监控帧（Supervisory Frame, S-frame）

如果Control被字段前两为为10，则该帧为监控帧。监控帧用于差错控制和流量控制，不携带用户数据。

• SS：监控功能位（Supervisory Function Bits），定义了 4 种监控帧类型。
• P/F：轮询 / 终止位。
• N(R)：接收序列号，用于确认或请求重传。

SS位的4种监控类型为：

• 接收就绪（Receive Ready, RR, SS=00）：当无法捎带确认时，使用 RR 帧来确认所有序号小于 N(R) 的帧已正确接收，并表示已准备好接收更多数据。
• 拒绝（REJ, SS=01）：发送否定确认，表示序号为 N(R) 的帧未被正确接收，要求对方从 N(R) 开始重传所有后续帧。
• 接收未就绪（Receive Not Ready, RNR, SS=10）：确认所有序号小于 N(R) 的帧，但告知对方本地缓冲区已满，暂时无法接收更多数据。
• 选择性拒绝（Selective REJECT, SREJ, SS=11）：发送否定确认，仅要求对方重传序号为 N(R) 的那个特定帧，提高了重传效率。

无编号帧（Unnumbered Frame, U-frame）

如果Control被字段前两为为11，则该帧为无编号帧。其用于链路管理，如建立、断开连接，以及传输控制信息。在本节内容中不要求掌握。

• M：无编号功能位（Unnumbered Function Bits），定义了多种链路控制命令和响应。
• P/F：轮询 / 终止位。

HDLC通信示例

正常通信

看下图情况，图中I表示Infomation，是用户数据。

1. A首先发送N(S)=0,N(R)=0来对B说：我现在给你发送的是我的第0个帧，信息为I，我请求你给我发第0帧。
2. B发送N(S)=0,N(R)=1回复A：我现在给你发送的是我的第0个帧，信息为I，第0帧已经接收，我希望下次收到帧1。
3. A连续两次发送给B，帧序号为1和2；同时给B表明我正准备接收你的帧1，你给我的帧0已经接收。
4. B发送帧1给A，并回复N(R)=3来表明我已经正确接收了1和2。

忙情况

对于下图A的Buffer满了的情况：

1. B给A发送信息I，帧序号为3，准备好接收A发送帧0。
2. A的Buffer满了，回复Receive Not Ready，并确认帧3已成功接收，预计接收帧4。
3. B回复Receive Ready来试探A是否准备好了再次接收，同时应答已经成功接收了A发送的帧4之前的数据。同时，B将Polling Bit置1，表示请求A务必对自己的RR进行应答。
4. A的Buffer还是满的，继续回复RNR，同时将Final Bit置1，表示自己的应答已经结束。
5. B重复尝试，这次A回复RR，表示已准备好接收，B继续正常发送消息。

流控机制（Flow Control）

停等流控（Stop & Wait）

停等流控的机制

停等流控的步骤是：

1. 发送端发送一帧数据
2. 接收端收到数据后进行处理，等它准备好接受下一次消息时，返回ACK消息
3. 发送端收到ACK消息后，再发送下一帧消息

停等流控的link利用率（Utilization）

记$t_{prop}$为传播时延，$t_{frame}$为数据帧传输时延，$t_{proc}$为数据处理时延，$t_{ack}$为应答帧传输时延。则停等流控造成的总延迟如下图：

总传输时间$T_D=2t_{prop}+t_{frame}+t_{ack}+2t_{Proc}$

停等流控的效率是用$帧传输时间/总传输时间$得到的。则根据上图可以知道停等效率$U$为（$t_{proc}$为处理延迟未在上图体现）:

$$U=\frac{t_{frame}}{T_D}=\frac{t_{frame}}{2t_{prop}+t_{frame}+t_{ack}+2t_{Proc}}$$

忽略$t_{ack}$和$t_{proc}$计算效率

因为$t_{ack}$和$t_{proc}$很短，假设其可以忽略不计则有：

$$U=\frac{t_{frame}}{2t_{prop}+t_{frame}}$$

定义$a=\frac{t_{prop}}{t_{frame}}$，称其为传播-传输时间比，则可以得到：

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

$a$还可以进一步推导（其中d表示传播距离，V表示信号传播速度，L表示信息长度，R表示信息传输速率）：

$$a=\frac{t_{prop}}{t_{frame}}=\frac{d/V}{L/R}=\frac{Rd}{LV}$$

SW流控的有效信道利用率$R_{eff}$

有效传输速率（Effective Transmission rate）的定义是$R_{eff} = \frac{L_{frame}}{T_D}$，即，信道在这种协议下，单位时间内真实的速率。

进一步地，信道的利用率还可以使用$U=\frac{R_{eff}}{R}$表示，即，真实传输速率/理论传输速率。

也可以通过U计算有效传输效率$R_{eff}=U\cdot R$

例题

（1）一条链路的数据速率为4Mbps，距离为1000公里。传播延迟为5us/km。一个1000字节的帧到达链路另一端需要多长时间？

传播时延$t_{prop}=1000\times 5us=5ms$；传输时延$t_{trans}=1000\times8/(4\times10^6)=2ms$

总延迟：$T_D=t_{prop}+t_{trans}=7ms$。

将（1） 中的值 $a = t_{prop}/t_{frame} $与另一个数据速率较低的1 Mbps信道的值进行比较

在例1中，传播/传输 时间比为$a=5/2=2.5$，此时的信道利用率$U=\frac{1}{1+2a}=\frac{1}{6}$。

如果换成1Mbps的信道，传输时间变为$1000\times8/(1\times 10^6)=8ms$，$a=5/8=0.625$，$U=\frac{1}{1+2a}=\frac{4}{9}$

可以看到，$a$越小，信道利用率越高。

如果帧大小从1000字节增加到5000字节，会怎么样？

$$t_{frame}=5000\times 8/(4\times 10^6)=10ms$$ $$U=\frac{t_{frame}}{t_{frame}+2t_{prop}}=5/7\approx0.714$$

通过上述例子，可以看出：对于停等流控，帧传输时间相较于传播时间的占比越大，信道效率越高。停等流控适合一次发较大的数据

滑窗流控（Sliding Window）

滑窗流控机制

停等流控下，如果帧长度不够长，那么信道利用率将会很低。因此引入滑窗流控。在滑窗流控中，发送端被允许在还未收到ACK的情况下，发送多个帧。

在滑窗流控中，发送方最多可连续发送 W 个未被确认的帧，每个帧都有自己的编号，编号满足模 (2^k) （如 3 位序号时，编号为 0-7，循环使用）

ACK 携带 “期望下一个帧的编号为 i”，记为$RRi$。采用累积ACK机制，若收到$RRi$，表示前 (i-1) 号帧已全部正确接收。接收方可发送特殊 ACK，暂时阻止发送方继续发帧；需后续正常 ACK 才能恢复传输。

滑窗流控在发送端和接受端都有一个“窗”，这个窗的头被称为leading edge，尾被称为trailing edge。以下图这个容量为7的窗为例：

1. 发送端可以在没有ACK的情况下发送窗内的数据
2. 接收端会择机进行ACK，一旦进行ACK，接收端的窗向前增加。以下图为例，接收端已收到6、7，那么将应答RR0表示自己0之前的已经妥善接受，准备接受0
3. 发送端一旦受到ACK，更新自己的窗口。例如下图发送端收到RR0这个ACK时，将会让自己的窗向前移2，变成0123456。
4. 等待ACK信号的同时可能发送端还在继续发送数据，例如发送端发送6 7之后接收端回复RR0，在RR0到达发送端期间它继续发送了0 1。那么此时可发送的数据为 2 3 4 5 6（仍被限制在窗内）。

如此操作，就无需及时的应答，因此ACK数据包可以随其他必要的通信包一起发送，无需为了ACK单独发信一次。

滑窗流控的link利用率

记：

• (t_{\text{frame}})：发送一帧的时间，设为 1（单位可自定义，方便推导）。
• (t_{\text{prop}})：信号单程传播时间，定义 (a = \frac{t_{\text{prop}}}{t_{\text{frame}}})（即传播时间与传输时间的比值）。
• $W$：滑动窗口的发送窗口大小（发送方可连续发送的最大未确认帧数）。
• $W \times t_{\text{frame}}$：把窗发完所需要的时间

1.ACK能在窗发完之前被收到的情况

考虑这样的一个情景，现在W为7，如果RR0可以在发送第4个包时收到，那么窗就会向前步进1；在第五个包时，会收到RR1，第六个包时，会收到RR2…以此类推，那么窗就会一直往前走，发送端可以一直发消息，信道利用率就是100%。

也就是说，只要RR0能在当前窗被发完之前收到，这个窗就可以一直往前走，一直持续不断得发消息不需要停下来等ACK，如下图所示。

而RR0能在当前窗被发完之前收到可以被数学表达为$W \times t_{\text{frame}}\geq2t_{\text{prop}}+t_{\text{frame}}$，即，发完窗的时间 $\geq$ 从发送第一个frame开始到收到第一个ACK的时间。改写一下：

$$W\geq2\frac{t_{\text{prop}}}{t_{\text{frame}}}+1=2a+1$$

即，如果$W\geq 2a+1$，则信道利用率为100%

2.ACK不能在窗发完之前被收到的情况

如果W为3，而RR0需要再第4个窗口被收到，那么在发送完窗之后，就需要等1帧的时间收到RR0，才能继续发送。在收到RR0，RR1，RR2会每间隔一帧被收到，因此发送端此时可以连续传输3帧。但是这次传输了3帧之后，又要再等一帧收到下一次ACK才能传输。如此周期往复。

即，若$W< 2a+1$，每个周期内发送方仅在前 $W \times t_{\text{frame}}$ 时间内发送数据，周期时长为收到第一次ACK的时长，即为$2t_{\text{prop}}+t_{\text{frame}}$，因此信道利用率为：

$$U = \frac{W \times t_{\text{frame}}}{2t_{\text{prop}}+t_{\text{frame}}}=\frac{W}{2a+1}$$

3.通式

综上所述，滑窗流控的信道利用率可以被总结为：

$$U = \begin{cases} 1 & W \geq 2a+1 \quad \text{frame 1 ack reaches A before window exhausted} \\ \dfrac{W}{2a+1} & W < 2a+1 \quad \text{window exhausted at } t=W \text{ out of } 2a+1 \text{ period} \end{cases}$$

下图是不同W与不同a下，信道利用率的关系。

例题

考虑一个无误差的 64 kbps 卫星信道用于单向发送 512 字节的数据帧，并在另一方向发送很短的确认信号（ACK）。当窗口大小为 1、7、15 和 128 时，最大利用率是多少？往返传播延迟为 540 毫秒。

题目已告知$2t_{prop}=540ms$，计算可得$t_{trans}=\frac{512\times 8 }{64\times 10^3}=64ms$，$t_{prop}=270ms$

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

• 当$W=1$，$W<2a+1$，$U=\frac{W}{2a+1}=\frac{16}{151}\approx10.6\%$，$R_{eff}=U\times R=211.92kbps$
• 当$W=7$，$W<2a+1$，$U=\frac{W}{2a+1}=\frac{112}{151}\approx74.17\%$，$R_{eff}=U\times R\approx1.483Mbps$
• 当$W=15$和$W=128$时，$W\geq 2a+1$，因此$U=100\%$，$R_{eff}=2Mbps$

错误检测机制（Error Detection）

分组码（Block Code）

分组编码的核心是通过增加冗余信息来检测传输错误，具体分为两步：

• 发送端（Sender）：
  1. 把原始消息切分成等长的小块，称为数据块（Dataword / Information），长度为 k 比特。
  2. 为每个数据块附加 r 比特的冗余位（Redundancy / Checkbits），生成长度为 n=k+r 比特的码字（Codeword）。
• 接收端（Receiver）：
  1. 接收到码字后，先提取出原始的 k 比特数据。
  2. 再通过校验器（Checker）检查整个码字是否合法。如果不合法，就判定为传输错误并丢弃。

一个简单的例子是简单地复制数据作为校验位。原始消息：11 10 01 00经过编码后得到1111 1010 0101 0000，传输中发生错误，变成：1011 1010 1101 0000接收端发现 1011 不是任何有效码字的前 4 位，因此判定为无效，可以检测到错误。但是，如果1111变成了1010，那么它就没办法检测到错误。

对于上述例子的这种情况，多项式码可以将无法检测的错误图案缩得更少。

多项式码：CRC（Polynomial Codes）

引入

多项式码不仅考虑每个字节的数值（value），还考虑数值的顺序（order）。它用多项式（Polynomials）而非向量表示码字，用多项式算术而非校验和进行运算。

多项式码也称循环冗余校验（ cyclic redundancy check CRC）码，是多数数据通信标准采用的错误检测方式，同时也是强大的错误纠正方法的基础。

在数据链路层，CRC依赖于硬件计算电路（移位寄存器电路（shift-register circuits）），因此可以以非常快的速度对CRC进行计算和校验。

CRC的生成的数据如下图所示，对于长度为(n+1)的数据位，生成长度为(n+k+1)的序列（帧或数据包）传输。其中，在数据后附加k位的帧校验序列（FCS, Frame Check Sequence）。

加上FCS之后的码字（code word）（即，n+k+1位的序列）的二进制多项式(T(x))，能被一个选择的多项式(C(x))（生成多项式）整除。通过校验是否整除来检错，若有余数，则认为帧中有一个或多个错误。下面是详细讲解

引入-二进制多项式算数法则

1. 二进制向量映射法则：

一个二进制的向量$(i_k, i_{k-1}, \dots, i_1, i_0)$可被映射为多项式(i_kx^k + i_{k-1}x^{k-1} + \dots + i_1x + i_0)（系数(i_j)为 0 或 1）。例如10101101可以被表示为$x^7+x^5+x^3+x^2+x^0$

2. 二进制多项式加法

按模 2 运算（即异或，XOR）对对应次数的系数相加。例如：

$$(x^7 + x^6 + 1) + (x^6 + x^5) = x^7 + (1\oplus1)x^6 + x^5 + 1 = x^7 + x^5 + 1$$

模2运算下，减法等价于加法

3. 二进制多项式乘法

乘法是按分配律展开后，再对系数进行模 2 运算。例如：

$$(x+1)(x^2 + x + 1) = x^3 + x^2 + x + x^2 + x + 1 = x^3 + (1\oplus1)x^2 + (1\oplus1)x + 1 = x^3 + 1$$

4. 二进制多项式除法

与十进制除法一样，遵循“被除数（dividend） = 商（quotient） × 除数（divisor） + 余数（remainder）” 的逻辑，只是运算基于模 2 多项式算术。最终余数的次数小于除数时就停止。例如下面这个例子

每一步的核心都是 “消去最高次项”：每用除数的最高次项匹配被除数的最高次项。

1. 被除数是$x^6+x^5$，除数是$x^3+x+1$，此时为了匹配最高次，第一个商是$x^3$，余数是$x^6+x^5-x^6-x^4-x^3=x^5+x^4+x^3$（模2运算减法等价于加法）
2. $x^5+x^4+x^3$中，最高次是$x^2$，因此第二个商是$x^3$，余数是$x^5+x^4+x^3-x^5-x^3-x^2=x^4+x^2$
3. (x^4+x^2)中，最高次是(x^4)，因此第三个商是x（(x^4 \div x^3 = x)），余数是(x^4+x^2 - (x^4+x^2+x) = x)（次数小于除数次，停止）

因此，$x^6+x^5/x^3+x+1=x^3+x^2+x…x$，可以反过来计算验证一下：

$$(x^3+x^2+x)\times(x^3+x+1)+x=x^6+x^4+x^3+x^5+x^3+x^2+x^4+x^2+x+x=x^6+x^5$$

5. 二进制多项式的算术性质

整除性性质：如果多项式(C(x))能整除多项式(B(x))，那么(B(x))的次数（最高次幂）大于或等于(C(x))的次数，即(\text{Degree}(B(x)) \geq \text{Degree}(C(x)))

模 2 加减的等效性：在模 2 运算下，对多项式(B(x))减去或加上多项式(C(x))，等价于对(B(x))和(C(x))的每一对对应系数进行异或（XOR）操作。

二进制多项式除法的性质以及其如何被CRC使用

现在我们来看这么个情况：记商是$A(x)$，除数是$C(x)$，被除数是$M(x) \cdot x^k$，余数是$R(x)$。

根据除法的性质，$M(x) \cdot x^k=C(x)A(x)+R(x)$。

对这个式子变形：$M(x) \cdot x^k-R(x)=C(x)A(x)$

由于模2运算减和加等价：$M(x) \cdot x^k+R(x)=C(x)A(x)$

如果我们把$M(x) \cdot x^k+R(x)$记作传输码字（Transmit Code Word）$T(x)$，在传输之后变成$T’(x)$

在接收端，我们把$T’(x)$再次除以$C(x)$：

• 若(T’(x) \div C(x))的余数为 0，说明(T’(x) = T(x))（传输过程中无错误），因为(T(x) = C(x)A(x))能被(C(x))整除。
• 若(T’(x) \div C(x))的余数不为 0，说明(T’(x) \neq T(x))（传输过程中存在错误），因为错误导致(T’(x))不再能被(C(x))整除

这就是CRC校验的原理。$C(x)$被称为生成多项式，$R(x)$就是CRC校验位

CRC的计算方式：

1. 将消息表示成n次多项式
2. 选择一个k次多项式$C(x)$作为生成多项式
3. 将原始码字的后$k$位空出来，补0，留给CRC校验位，即变成$M(x)\cdot x^k$
4. 通过模2除法，算出$M(x)\cdot x^k/C(x)$的余数，填在补0的k位上，码字变成$M(x) \cdot x^k+R(x)$

除了通过常规的多项式写法之外，使用二进制写法更直观更好写

举个例子：需要发送1100，选择C(x)=1011作为生成多项式

由于生成多项式是3次的，因此将信息bit整体上移3位（乘$ x^3 $），被除数就是$1100000$，或者用多项式表示就是$x^6+x^5$。

$C(x)=1011=x^3+x^1+1$，针对这一组除数和被除数，用多项式的写法前面已经有介绍。这里介绍二进制的写法。

最后，计算出来余数是10，最后3bit是留给CRC的，因此最后的传输码字就是1100010

第二个例子：需要发送110111,选择101作为生成多项式

由于生成多项式是2次的，因此将信息bit整体上移2位（乘$x^2$）。最后计算如下：

因此最后校验位填入01，传输码字为11011101

假设收到的数据无误，使用11011101再次除以C(x)

最后余数是0，证明消息正确

假设收到消息为11001101, bit4发生了翻转

最后余数不是0，表示消息错误。

CRC检测的局限性

在前面，我们已经介绍了CRC检测的原理，它通过除法的特性来检测是否有比特错误。

记发送的码字多项式为(T(x))，接收的码字多项式为(T’(x))，则错误图案（error pattern）(E(x) = T(x) - T’(x))。其中，(E(x))的每一项对应传输中被翻转的比特。

根据模2运算的法则移项，我们可以认为：在传输过程中，$T(x)$与错误的比特$E(x)$相加，就构成了$T’(x)$，即$T’(x)=T(x)+E(x)$。

举个例子，假设传输的$T(x)$是1100010，bit1出现了错误，$E(x)$是0000010，其中bit1位置上的1表示这个地方发生了错误。接收到的$T’(x)$就是1100000，等于$T(x)+E(x)$

那么，根据CRC检测的原理，如果生成多项式(C(x))同时整除(T(x))和(T’(x))，则错误不可检测。$C(x)$能同时整除意味着(C(x))可以整除(E(x))。

例如，生成多项式是110，而错误图案恰好也是110，那这个错误就无法检测。

典型的生成多项式

• CRC-8：(x^8 + x^2 + x + 1)，用于 ATM（异步传输模式）。
• CRC-16：(x^{16} + x^{15} + x^2 + 1)（或因式分解为((x+1)(x^{15} + x + 1))），用于 Bisync（二进制同步通信）。
• CCITT-16：(x^{16} + x^{12} + x^5 + 1)，用于 HDLC（高级数据链路控制）。
• CCITT-32：(x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1)，用于 IEEE 802（以太网等标准）。

差错控制机制（Error Control）

在物理层传输中，传输的帧（Frame）可能被破坏或丢失（比如噪声突发会损坏帧）。因此，数据链路层需要执行差错检测（Error Checking）和重传（Retransmission），以确保两个系统之间 “无差错的分组（Packet）传输”。

差错控制有两种基本方法：

• ARQ（Automatic Repeat reQuest 自动重传请求）：检测到错误后重传（本课程核心，属于 “检错重传” 思路）。
• FEC（Forward error correction 前向纠错）：直接在接收端纠正错误（本课暂不深入）。

对于ARQ，其本质是基于前面介绍的停等和滑窗这样的流控机制。

Stop & Wait ARQ

停等工作机制

S&W ARQ是基于停等流控协议的。它的流程如下：

1. 发送端在发送一帧数据后，启动一个Timer开始计时
2. 等待接收端接受到数据后，发送ACK。接收端收到ACK后再发送下一帧。
   • 如果timer超时了还没收到ACK，则发送端重传该帧，并重置timer
   • 如果传输的数据在路上损坏，则接收端忽略它（不发送ACK），使发送端timer超时来触发重传
   • 如果ACK信号在路上损坏，发送端还是重传该帧，并重置timer（这会导致接收方收到重复帧，需通过序号避免，即，给帧交替标记0 和 1，回复时恢复ACK0请求标记为0的帧，ACK1请求标记为1的帧）。

停等流控性能建模

对于引入了差错控制之后的性能建模，其核心是计算 “每成功传输一帧的期望传输次数 (N_r)”。成功传输一帧的时间期望是 (N_r \times T_D)（因为每帧平均重传 (N_r) 次）。信道利用率修正为：

$$U = \frac{t_{\text{frame}}}{N_r \cdot T_D} = \frac{1}{N_r (1 + 2a)}$$

同时，信道的有效传输速率为：

$$R_{eff}=\frac{L_{frame}}{N_rT_D},\quad T_D=t_{\text{frame}} + 2t_{\text{prop}}$$

那么如何计算$N_r$呢？

1.使用单帧错误概率进行计算

假设 “单个帧出错的概率为 p”，且将模型简化为ACK/NAK 不会出错。

第 i 次传输才成功的概率为 (\Pr[i] = p^{i-1}(1-p))（前 (i-1) 次出错，第 i 次成功），则期望为：

$$N_r = \sum_{i=1}^{\infty} i \cdot \Pr[i] = \sum_{i=1}^{\infty} i \cdot p^{i-1}(1-p)= (1-p) \cdot \frac{1}{(1-p)^2} = \frac{1}{1-p}$$

将$N_r$代入$U$的计算公式：

$$U=\frac{1}{N_r (1 + 2a)}=\frac{1-p}{1 + 2a}$$

2.使用信道BER进行计算

假设帧正确传输的概率为$P_{frame-succes}$，出现ACK正确传输的概率为$P_{ACK-success}$，那么不重传的概率为：

$$P_{success}=P_{frame-succes}\times P_{ACK-success}$$

假设这个信道上的Bit Error Rate（BER）已知，$P_{frame-succes}=(1-BER)^{L_{frame}}$，其中$L_{frame}$表示frame的比特长度。同理，$P_{ACK-succes}=(1-BER)^{L_{ACK}}$

那么，对于一个帧，其被正确传输并正确收到ACK，传输次数的期望就是$N_r=\frac{1}{P_{success}}$

如果，还是假设ACK无错误，那么$P_{success}=P_{frame-succes}=(1-BER)^{L_{frame}}$。此时，信道利用率是：

$$U=\frac{1}{N_r (1 + 2a)}=\frac{(1-\text{BER})^{L_{frame}}}{1 + 2a}$$

例题

对于与SW流控例题中相同的系统（数据速率为4Mbps，距离为1000公里。传播延迟为5us/km），如果传输帧的比特错误率分别为 $p = 10^{-4}$ 和 $10^{-5}$，比较帧大小为1000字节和5000字节时的链路效率。

$t_{prop}=1000\times 5us=5ms$， $t_{trans-1000}=1000\times 8 /(4\times 10^6)=2ms$，$t_{trans-5000}=5000\times 8 /(4\times 10^6)=10ms$

当$p = 10^{-4}$时：

1000字节的$N_r=\frac{1}{(1-10^{-4})^{1000\times8}}\approx2.2256$，5000字节的$N_r=\frac{1}{(1-10^{-4})^{5000\times8}}\approx54.6091$

信道利用率分别为

$$U_{1000}=\frac{t_{trans-1000}}{2.2256\times(2t_{prop}+t_{trans-1000})}=0.0748$$ $$U_{5000}=\frac{t_{trans-5000}}{54.6091\times(2t_{prop}+t_{trans-5000})}=0.0092$$

当$p = 10^{-5}$时：

1000字节的$N_r=\frac{1}{(1-10^{-5})^{1000\times8}}\approx1.0833$，5000字节的$N_r=\frac{1}{(1-10^{-5})^{5000\times8}}\approx1.4918$

$$U_{1000}=\frac{t_{trans-1000}}{1.0833\times(2t_{prop}+t_{trans-1000})}=0.1539$$ $$U_{5000}=\frac{10ms}{1.4918(10ms+20ms)}\approx0.3352$$

还有一种算法，是使用Error Free时的信道利用率乘上折损。

以$p = 10^{-4}$时1000byte为例：

$$U_{error-free}=\frac{t_{trans}}{2t_{prop}+t_{trans}}=\frac{2ms}{12ms}=\frac{1}{6}$$ $$U=(1-10^{-4})^{1000\times 8}\times U_{error-free}\approx0.0748$$

考虑一个系统，其中A使用SW-ARQ向B发送一条包含N帧的消息。考虑一个系统，其中A使用停止-等待ARQ向B发送一条包含N帧的消息。对于上述的系统，如果我们现在假设确认应答（ACK）也可能出错。且A正确传输给B的概率为P，B的ACK正确到达A的概率为$P_A$，那么结果（即A需要发送的帧的平均次数）将会是多少？

$$P_{success}=P\times P_A$$

成功传输一帧的传输次数期望是：

$$N_r=\frac{1}{P_{success}}=\frac{1}{P\times P_A }$$

此时有N帧，那么传输期望就是：$\frac{N}{P\times P_A}$

Go Back N ARQ

Go-Back-N 机制

GBN ARQ基于滑窗流控。发送端维护一个窗，允许在无ACK时发送窗内的内容。

若接收端接收数据无差错，则正常发送，则会发送RR(Receive Ready)作为ACK 确认。若某帧出错，收方会丢弃该帧及后续所有帧，并回复 “拒绝 NAK 或 REJ(reject)”；发送方收到 NAK或超时后，回退并重传该帧及所有后续帧。

详细来说，需要重传有以下三种情况：

• 损坏的帧（Damaged frame）：发送方 A 发帧i，接收方 B 检测到错误并丢弃。若 A 继续发帧(i+1)，B 收到乱序的(i+1)后发 NAK；A 超时后，重传帧i及后续所有帧。
• 损坏的 ACK（Damaged ACK）：B 收到帧i后发 ACK(i+1)，但 ACK 丢失。由于 ACK 是累积的，A 可能后续收到其他 ACK来确认帧i已被接收，但若超时则重传帧i及后续所有帧。
• 损坏的 NAK（Damaged NAK）：NAK 丢失后，A 会因超时重传帧i及后续所有帧

下图是一个GNB ARQ的例子：

• 第一次出现了损坏的帧：frame4损坏，当后续收到frame5时，B发现接收的帧缺了4，因此立马发送REJ4。A在收到REJ4之后，将4及之后的帧重传
• 第二次出现了损坏的ACK：RR7损坏，A继续发送帧，此时A中负责接收ACK的时钟继续计数，当超时时，A发送一个 Poll bit为1的帧，B会将此帧作为一个命令处理，B在接收后必须立马发送一个ACK。由于现在frame0已被成功接收，因此B直接回复RR1，表示所有之前的帧都已被接收

Go-Back-N 性能建模

GNB ARQ 的特点是：某一帧出错时，需重传该帧及后续的帧，共K帧（K是重传的帧数量）。我们需要计算 “成功传输一帧所需的期望总传输帧数(N_r)”。

记$f(i)$是指如果原始帧必须传输 i 次时传输的总帧数。例如，$f(1)=1$，原始帧在传输第一次就成功，无需重传。$f(2)=1+K$，即，第一次传输失败，由于这个失败，第二次重成功，在第二次重传时需要重传后续的K帧。$f(3)=1+2K$，即，第一次传输失败，第二次重传（传输数量为K帧）也失败，第三次重传（又重传K帧）才成功。

那么，设 “单个帧出错的概率为p”，则第i次尝试才成功传输该帧的概率为(p^{i-1}(1-p))。 “成功传输一帧所需的期望总传输帧数(N_r)”就可以写为：

$$N_r = \sum_{i=1}^{\infty} f(i) \cdot p^{i-1}(1-p)$$

从前面的例子不难看出，$f(i)$是一个等比数列，$f(i)=(1-K)+Ki$，将其代入$N_r$化简：

$$\begin{align} N_r &= \sum_{i=1}^{\infty} [(1-K)+Ki] \cdot p^{i-1}(1-p)\\ &=(1-K)(1-p) \sum_{i=1}^{\infty} p^{i-1} + K(1-p) \sum_{i=1}^{\infty} i \cdot p^{i-1}\\ \end{align}$$

$\sum_{i=1}^{\infty} p^{i-1}$是一个等比数列，用求和公式可以算出：

$$\sum_{i=1}^{\infty} p^{i-1} = \frac{1}{1-p}$$

对于(\sum_{i=1}^{\infty} i \cdot p^{i-1})，我们知道等比级数的和为 (\sum_{k=1}^{\infty} p^{k-1} = \frac{1}{1-p})，对其两边关于 p 求导：$\frac{d}{dp} \left( \sum_{k=1}^{\infty} p^{k-1} \right) = \frac{d}{dp} \left( \frac{1}{1-p} \right)$

左边求导后为 (\sum_{k=1}^{\infty} (k-1) \cdot p^{k-2})，令 (i = k-1)，则级数变为 (\sum_{i=0}^{\infty} i \cdot p^{i-1})；右边求导后为 (\frac{1}{(1-p)^2})。注意到当 (i=0) 时，项 (0 \cdot p^{-1} = 0)，因此 (\sum_{i=0}^{\infty} i \cdot p^{i-1} = \sum_{i=1}^{\infty} i \cdot p^{i-1})，即：

$$\sum_{i=1}^{\infty} i \cdot p^{i-1} = \frac{1}{(1-p)^2}$$

带回原式：

$$N_r = (1 - K) + \frac{K}{1-p} = \frac{(1 - K)(1-p) + K}{1-p} = \frac{1 - p + Kp}{1-p}$$

而需要重传的帧数K与窗大小和传播时延有关：

1. 如果$W\geq 2a+1$，即，发送端会源源不断地发送帧的情况下，$K=2a+1$，因为ACK在$2a+1$帧后出现；
2. 如果$W<2a+1$，即，发送端会把窗发完然后等ACK的情况下，$K=W$。

当无差错时，利用率由窗口大小W和a决定：

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

当有差错时，每传输(N_r)帧，仅 1 帧是 “有效” 的，因此利用率修正为：

$$U = \frac{1}{ N_r} \times U_{\text{error-free}}$$

那么，将$N_r$代入：

• 在$W\geq 2a+1$时：

$$U=\frac{1}{\frac{1 - p + (2a+1)p}{1-p}}\times 1=\frac{1-p}{1+2ap}$$

• 在$W < 2a+1$时：

$$U=\frac{1}{\frac{1 - p + Wp}{1-p}}\times \frac{W}{2a+1}=\frac{W(1-p)}{(2a+1)(1-p+Wp)}$$

综上：

$$U = \begin{cases} \frac{1 - p}{1 + 2ap} & W \geq 2a+1 \\ \frac{W(1 - p)}{(2a+1)(1 - p + Wp)} & W < 2a+1 \end{cases}$$

Selective-Reject ARQ

S-R ARQ 机制

Selective-Reject ARQ 与 GBN ARQ类似，也基于滑窗流控，但它仅重传被 NAK 拒绝或超时的帧，最小化重传量。

• 在SR ARQ模式下，当错误出现时，B会发送”Selective Reject （SREJ）”，并将后续收到的帧存在自己的缓存中。则是SR-ARQ与Go-Back-N的核心区别。
• A收到SREJ后，立马重发SREJ指定的帧，重发之后继续发送滑窗内剩下的内容。
• B收到更正后，会立马发送一次ACK来更新A的窗。
• 若ACK信号丢失，处理机制和Go-Back-N一致。

S-R ARQ下，发送方和接收方都需要缓冲区存储未确认 / 缓冲的帧，且逻辑更复杂，因此应用不如回退 N 帧广泛；但在卫星链路（传播延迟大）场景中很有用，因为可避免大量不必要的重传。

下图是一个S-R ARQ的例子：

• Frame错误情况：当 A 发送Frame 4时错误，B 检测到错误后不丢弃后续帧，而是缓冲Frame 5,6...，并发送SREJ 4，表示请求重传Frame 4。A 收到SREJ 4后，仅重传Frame 4，然后就接着发了。
• ACK错误情况：当A传输frame 0后，RR1丢失，A在Timer超时前未收到RR，因此发送一次RR请求，让P bit=1。B在收到P bit=1后，立即重新发送RR。

S-R ARQ性能建模

设 “单帧出错概率为 p”，则：第 i 次尝试才成功传输该帧的概率为 (\Pr[i] = p^{i-1}(1-p))（前 (i-1) 次出错，第 i 次成功）。

对于S-R ARQ，若某一帧出错了，只需要单独重传某一帧，则期望传输次数 (N_r) 就和停等ARQ一样，是 “尝试次数的期望”，即：

$$N_r = \sum_{i=1}^{\infty} i \cdot \Pr[i] = \sum_{i=1}^{\infty} i \cdot p^{i-1}(1-p)= (1-p) \cdot \frac{1}{(1-p)^2} = \frac{1}{1-p}$$

同GBN一样，当无差错时，利用率由窗口大小W和a决定：

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

当有差错时，每传输(N_r)帧，仅 1 帧是 “有效” 的，因此利用率修正为：

$$U = \frac{1}{ N_r} \times U_{\text{error-free}}$$

代入$N_r=\frac{1}{1-p}$，即可得到：

$$U = \begin{cases} 1 - p & W \geq 2a+1 \\ \frac{(1-p)W}{2a+1} & W < 2a+1 \end{cases}$$

错误对几种ARQ机制信道利用率的影响

上图是假设帧出错概率 (p = 10^{-3})时，各种ARQ机制信道利用率与传播 - 传输时间比$a$的关系。

• 对于停等ARQ，利用率随 a 增大急剧下降。因为停等 ARQ 每次只发 1 帧，传播延迟期间链路完全空闲，所以当 a 较大（传播延迟远大于传输时间）时，利用率几乎为 0，性能极差。
• 对于GBN ARQ，由于 “出错时重传后续所有帧”，因此窗口越大，重传的 “无效开销” 越大，受到错误影响的衰减更高（上图W=7的信道利用率几乎与无差错一致，但是W=127出现了明显衰减）。
• S-R ARQ未见明显衰减，因为它的重传只重传单帧，利用率受错误影响有限。

真实协议中的应用：

• SW-ARQ：RFC 1350协议、UDP简单传输协议
• GBN-ARQ：HDLC
• SR-ARQ：TCP协议（使用变种SR）

介质访问控制

两个设备间的通信，有两种链路。一种是Point-to-Point链路，此时两个设备的通信独占整个物理介质。还有一种是共享物理介质的链路，例如下图这样的情况。

对于共享介质的链路，为了避免通信冲突，就需要介质访问控制（MAC）。

要实现物理介质访问控制，有以下几种方法：

• 信道分割（Channel Partitioning）：将信道通过时隙、频率、码等等复用技术分为不同的片段，给不同设备分配不同的片段。
• 控制接入（Controlled Access）：使用一个中央节点，来管理其他节点的传输权限。每个节点必须要被告知可以传输后才能传输数据。
• 随机接入（Random Access）：任意节点都可以随意传输数据，这可能会导致碰撞，当碰撞发生时，调用协议对应的碰撞处理机制来进行处理。这是最简单的。

本小节术语

吞吐量 (Throughput, S)

定义：吞吐量是指单位时间内成功传输的、无差错的数据量，通常以 bps (bits per second) 为单位。

$$S=\frac{\text{data transmitted (bits)}}{\text{elapsed time (s)}}$$

S/R 这个比值被称为归一化吞吐量。归一化吞吐量在数值上等于效率（或利用率）。这意味着，当我们说网络效率是 80% 时，也等同于说吞吐量达到了网络最大容量的 80%。

利用率 (Utilization, U)

定义：利用率是指网络用于传输有效数据的时间占总时间的比例，通常以百分比（%）表示。

$$U=\frac{\text{frame transmision time (s)}}{\text{elapsed time (s)}}$$

它反映了信道的繁忙程度。例如，利用率为 50% 意味着在统计时间内，信道有一半的时间在真正传输数据，另一半时间则处于空闲或处理开销（如冲突、等待、协议交互等）的状态。

术语	符号	核心含义	与其他量的关系
吞吐量	S	实际传输的有效数据速率 (bps)	$S=U\times R$
利用率	U	信道用于传输的时间比例 (%)	$U=S/R$
效率	ρ	网络容量的有效利用比例 (%)	$ρ=U=S/R$

ControlAccess: Token Ring

Token Ring是典型的Control Access，通过一个在网络中循环传递的 令牌（token） 来控制对信道的访问权。只有持有令牌的站点才有权发送数据。

工作流程

1. 令牌传递：一个特殊的 “令牌帧” 在网络中按顺序从一个站点传递到下一个站点。
2. 获取权限：当一个站点有数据要发送时，它会等待令牌到来，然后 “抓住” 令牌，获得发送权。
3. 数据传输：持有令牌的站点发送数据帧。
4. 释放令牌：数据发送完毕后，站点将令牌释放，使其继续在网络中传递，供下一个站点使用。
5. 无数据时：如果站点没有数据要发送，它会直接将令牌传递给下一个站点。

例题

一个令牌环网络有 S 个等间距的站点。它以 R Mbps 的数据速率运行。假设一个帧在整个网络中传输所需的传播延迟为 D 秒。如果每个站在接收到令牌时都会传输一个 F Bytes的帧，那么令牌环网络的吞吐量和效率是多少？（你可以假设，当帧的第一个比特在绕环一周后到达发送站时，令牌会被释放（这意味着 D 大于帧传输延迟）。）

由于一个帧传播一圈需要D秒，当主机发送的数据帧回到主机自身时，它开始传递令牌。传递令牌时，由于有S个主机等距分布，令牌传递时间就是$D/S$。那么，一次完整的传输过程（传递数据+传递令牌到下一个主机）所耗费的时间是$T_D=D+\frac{D}{S}$

在周期时间内，传递了$8\times F (bits)$的有效数据，因此吞吐量是：

$$S=\frac{8F}{D+\frac{D}{S}}=\frac{8FS}{D(S+1)}\ bps$$

网络的传输能力是RMbps，因此效率为：

$$\rho=U=\frac{S}{R\times 10^6}=8\times 10^{-6}\times\frac{FS}{DR(S+1)}$$

ALOHA协议

ALOHA 是一种分布式共享广播信道的接入协议（无中央仲裁者），最初用于夏威夷大学主校区与远程校区的无线数据传输。

标准ALOHA

协议机制

标准的ALOHA非常简单，它是一个竞争协议。其流程如下：

1. 当传输点有数据需要传送的时候，它会立即向通讯频道传送。
2. 接收站通过检查帧校验序列字段来确定传入帧的正确性
   • 如果正确，接收方发送ACK。传输站点等待ACK的时间是2倍传播时延+一个小小的增量。
   • 如果这个包在传输过程中遭遇了碰撞或是错误，则无ACK，会发生超时，两个站点会各自等待一段随机退避时间（backoff time）后，再次尝试发送。

性能分析

首先定义一些基本的符号：

• $F$：帧传输时间（假设为常数）。
• $S$：吞吐量（平均每秒成功传输的帧数）。
• $G$：负载（平均每F时间内总传输尝试数，包括首次传输和重传）。
• $P_{success}$：单个帧传输成功的概率。

考虑下面这样一个情景：我要发送一帧数据（下图红色）。我发送的时刻记为$t_c$。一旦有其他主机在我发送的$t_c-F$的时间内发送数据（下图A），他们它会和我发生碰撞。一旦有其他主机在我发送的$t_c+F$内发送数据，也会和我碰撞。因此，称ALOHA的脆弱期（Vulnerable period）是2F

ALOHA 协议通常假设帧到达服从泊松过程：平均到达率为$\lambda$ 帧 / 秒；到达间隔服从指数分布，均值为$\frac{1}{\lambda}$

$$P[k\text{ arrivals in t (s)}] = \frac{(\lambda t)^k}{k!} e^{-\lambda t}$$

假设帧的到达服从泊松分布，$G$是平均每F时间内到达的帧平均数，在时长为$2F$的时间单元（脆弱期）内，到达$K$个帧的概率为：

$$P[k\text{ arrivals in } 2F] = \frac{(2G)^k}{k!} e^{-2G}$$

只有在2F时间单元内没有其他帧到达时，当前帧才不会碰撞。即$K=0$时的概率：

$$P_{\text{success}} = e^{-2G}$$

将其代入吞吐量：$S=G\times P_{success}=Ge^{-2G}$。可以看到，系统吞吐量现在被表示为了一个和负载$G$相关的函数。当负载从0开始增加，吞吐量也应该是增加的，直到吞吐量不增了，说明到它的极限了。因此，通过导数等于0来寻找$S$停止增长的点。

$$\frac{dS}{dG} = e^{-2G} - 2G \cdot e^{-2G} = 0$$

解出$G=\frac{1}{2}$。将其代入吞吐量公式，得最大吞吐量：

$$S_{\text{max}} = \frac{1}{2} \cdot e^{-2 \times \frac{1}{2}} = \frac{1}{2e} \approx 0.184$$

下图是负载（x轴）与吞吐量（y轴）的关系。

这意味着纯 ALOHA 的最大信道利用率仅为 18.4%，当每秒平均尝试传输0.5帧时到达峰值。

Slotted ALOHA

协议机制

Slotted ALOHA 与 ALOHA的机制几乎一样，唯一的区别是：时间被划分为了不同的时隙，所有主机都只能在时隙开始时进行传输。

性能分析

考虑下面这个情景，因为被划分为了不同的时隙，因此帧A和B都无法回下图红色构成威胁。唯一会构成威胁的只有与红色帧在一个时隙的帧C。因此，称Slotted ALOHA的脆弱期从2F变成了F。部分碰撞在slotted ALOHA里面不存在了，只有无碰撞和完全碰撞两种情况

与前面的分析一样，假设为泊松分布，可以求得吞吐量表达式：

$$P_{success}=P[0\text{ arrivals in } F] = \frac{(G)^0}{0!} e^{-G}=e^{-G}$$ $$S=GP_{success}=Ge^{-G}$$

对G求导，使得导数为0，寻找最大点：

$$e^{-G}-e^{-G}G=0,\quad G=1$$

因此在$G=1$时，吞吐量有最大值，为36.8%

一些终端使用时隙ALOHA协议通过一个2400 bps的公共信道与主机计算机通信。每个终端平均每两分钟发送一次200位的信息。使用该信道的最大终端数量是多少？

$$2400\times36.8\%=883.2bps$$ $$883.2/(200/120)\approx530$$

最大支持530台终端。

例题

一个纯ALOHA网络在速率为400 kbps的共享信道上发送400-bit的帧。如果系统（包括所有站点及重传）每秒产生1000帧，那么吞吐量是多少帧/秒？吞吐量以bps计算是多少？

一帧所需的时间是$F=400bits/400Kbps=1ms$。那么$G=1000\times \frac{1ms}{1s}=1$

$$S=Ge^{-2G}\approx0.135$$

即，吞吐量为每F时间$0.135frame$，换算成秒就是$135$帧/秒。换算成bits是$0.135\times 400k=54kbps$

如果这是一个时隙ALOHA系统，吞吐量是多少？

$$S=Ge^{-G}\approx0.368$$

即，吞吐量为每F时间$0.368frame$，换算成秒就是$368$帧/秒。换算成bits是$0.368\times 400k=147.2kbps$

CSMA协议

纯CSMA

协议机制

CSMA的全称是载波侦听多路存取（Carrier Sensing Multiple Access）。

在ALOHA中，每个人都不顾及他人，如果每个人能在发之前先听听是不是有人正在传输，如果有人传输就避让，那碰撞概率就可以大大降低，这就是载波侦听（Carrier Sensing ）。

在进行避让动作时，有三种不同的执行方式：

• 1-persistent CSMA：最 “贪婪”，信道一空闲，立即开始传输。这种方式低时延但效率低（因为多个站点同时等待信道空闲时，极易发生碰撞，碰撞后又需退避，陷入 “碰撞 - 退避 - 再碰撞” 的循环）
• Non-persistent CSMA：最 “不贪婪”，信道忙时，先等待一个随机的退避时间（遵循某种概率分布），之后再重新感知信道。优势：高效率（碰撞概率低）；缺陷：时延高（因为退避时间是随机的，可能等待较长时间）。
• p-persistent CSMA：可调节的 “贪婪度”， 信道空闲时，以概率p立即传输；以概率(1-p)等待一个微时隙（时长为(t_{\text{prop}})）后再重新感知。其可在 “时延” 和 “效率” 之间做平衡（通过调整p的值实现）。

脆弱期

考虑下面这个场景：A与B之间的信号传播需要经过$t_{prop}$的时间。如果A想给C发消息，记帧开始发送的时间为$t_s$，在$t_s+t_{prop}$的时间之后这个帧就传到了B那里，此时B可以听到信道中有人在传输，因此进行避让，不会发生碰撞（下图上）。然而，如果在$t_s+t_{prop}$时间内，即，A发送的帧还没有传播到B那里，B就想发消息，此时B往信道一听，没人发，那我发。这样，AB的消息就会发生碰撞（下图下）。

因此，称CSMA的脆弱期是$t_{prop}$。

一旦发生碰撞，整个帧持续的时间都将作废，因为CSMA的传输“一发不可收拾”，只要开始发了，就算碰撞，它也得发完。

CSMA/CD协议

协议机制

在纯CSMA中，只在自己说话之前听一听别人有没有在说话。CSMA/CD 是对 CSMA 的进一步改进，核心机制是 “边说边听（listen while talking）”：站点在传输过程中持续监听信道，检测是否发生冲突，这就是CD的含义：Collision Detection（碰撞检测）。

CSMA/CD 的工作过程可分为三种状态：

• 竞争（Contention）：多个站点争夺信道使用权的阶段。
• 传输（Transmission）：单个站点成功占用信道，传输完整帧的阶段。
• 空闲（Idle）：信道无数据传输的阶段。

工作流程：

1. 持续监听：站点不断感知信道状态。
2. 空闲则发：如果信道空闲，立即开始发送帧；如果信道忙，则持续监听直到空闲。
3. 冲突处理：如果在发送过程中检测到冲突：中止当前的帧传输。立即发送一个短的干扰信号（jamming signal），确保所有站点都知道发生了冲突。
4. 退避重传：干扰信号发送后，等待一段随机的退避时间（backoff time），然后从步骤 1 重新开始。

冲突浪费的优化：在纯 CSMA 中，冲突会浪费 “整个帧的传输时间”；而 CSMA/CD 只需浪费 “检测冲突并中止传输的时间”，大幅减少了资源浪费。

CSMA/CD的性能分析

考虑下图这样一个情况：

• A想跟C发消息，B也想，A在$t_s$时刻发送了消息，然而，在$t_s+t_{prop}$之内（A的消息还没传播到B），B看到信道空闲，也开始发消息了，这个时间点记为$t_b$（$t_b<t_s+t_{prop}$）。那么这条消息会发生碰撞，如下图(a)所示。
• 由于B在发送时一直在监听，在$t_s+t_{prop}$时刻A的消息传播过来了，发现了碰撞，于是立马停止传输。
• B已经发送的消息传播到A还需要$t_b+t_{prop}$，由于$t_b<t_s+t_{prop}$，因此A发现碰撞的时间就是$t_s+t_{prop}$到$t_s+2t_{prop}$之间的一个时间。
• 即，通信双方都侦测到碰撞，开始停止发消息，最多需要$2t_{prop}$，在这$2t_{prop}$之内，信道被碰撞了的废信息占用。

因此，我们不妨假设竞争期被划分为时长为(2t_{\text{prop}})的时隙。假设有n个忙碌的站点，每个站点在每个竞争时隙内传输的概率为p。竞争期结束后（某站点成功占用信道），传输一帧需要F时间；下一个竞争期开始前有(t_{\text{prop}})的间隔。

成功传输的概率(P_{\text{success}} = np(1-p)^{n-1})（n个站点中，某一个传输、其余(n-1)个不传输的概率）。

通过导数等于0来寻找成功传输概率的最大值：求导可得，当(p = 1/n)时，(P_{\text{success}})最大，最大值为(P_{\text{success}}^{\text{max}} \approx \frac{1}{e})（e为自然常数，约 2.718）。

则，成功传输一帧数据需要的时隙期望为：(1/P_{\text{success}}^{\text{max}} \approx e)，每个时隙时长为(2t_{\text{prop}})，所以平均竞争期为(2t_{\text{prop}} \cdot e)。

当一个主机成功占用信道时，其会占用帧传输时间$F$+最长传播时间$t_{prop}$秒的信道。而在最大吞吐量下，信道总是在被占用-竞争-被占用-竞争之间交替，如下图。

那么，成功传输一个传输时长为$F$的帧，所需要的平均总周期时间就是传输F占用的时间+竞争平均时间，即$F + t_{\text{prop}} + 2e t_{\text{prop}}$。

由此可得，最大吞吐量效率(\rho_{\text{max}})是 “帧传输时间” 与 “总周期时间” 的比值：

$$\rho_{\text{max}} = \frac{F}{F + t_{\text{prop}} + 2e t_{\text{prop}}} = \frac{1}{1 + (2e + 1)a} = \frac{1}{1 + (2e + 1)\frac{Rd}{VL}}$$

其中：

• (a = t_{\text{prop}}/F)（传播时延与帧传输时间的比值）。
• (t_{\text{prop}} = d/V)（d为系统直径，V为信号传播速度）。
• (2e + 1 \approx 6.44)（由(e \approx 2.718)推导而来）。

下图是各CSMA机制的 信道利用率 与 传播/传输时间比（$a=\frac{t_{\text{prop}}}{t_{frame}}$） 的关系。

根据假设的概率模型不同，这个公式可能略有差异。

练习题：现有一个网络，电缆长度2.5 km，传输速率：10 Mbps，帧长：620 字节，信号传播速度 (V = 2 \times 10^8 \, \text{m/s})，在这个网络中CSMA/CD 协议的效率是多少？

传输单帧帧长是$F=\frac{620\times8}{10^7}=4.96\times10^{-4}s$

单次传播时延是$t_{prop}=\frac{2.5\times 10^3}{2\times 10^8}=1.25\times 10 ^{-5}s$

效率：

$$\rho_{\text{max}}=\frac{F}{F+t_{prop}+2et_{prop}}\approx0.8604=86.04\%$$

因此，在10Mbps的信道中，有效传输速率为8.604Mbps。

以太网中的CSMA/CD

以太网（Ethernet）是 CSMA/CD 协议的典型应用。早期以太网中：

• 采用1-persistent CSMA避让机制
• 规定时隙长度为512个bit的时间。例如在10Mbps的网络中，时隙长度为$512\times\frac{1}{10\times 10 ^6bps}$
• 采用截断二进制指数退避（Truncated Binary Exponential Backoff）：第n次冲突后，退避时间从(\{0, 1, \dots, 2^k - 1\})中随机选择，其中(k = \min(n, 10))（避免退避时间无限制增长）。

以太网是无连接、不可靠的通信：

• 无连接（connectionless）：发送和接收网卡（NIC）之间没有握手过程，直接传输帧。
• 不可靠（unreliable）：接收方不会向发送方发送确认（ACK）或否定确认（NACK）。若帧丢失，需依赖上层协议（如 TCP）来恢复（如 TCP 的重传机制）。

下图是以太网中CSMA/CD的流程图：

1. 载波侦听（Carrier-sense）：网卡从网络层接收数据报（datagram），封装成以太网帧。若网卡检测到信道空闲，立即开始传输帧；若信道忙，则等待信道空闲后再传输。
2. 碰撞检测（Collision Detection）：网卡开始逐个bit传输帧数据，每传输一次，都检查一下有没有发生碰撞。
   • 如果没有全程没有检测到碰撞，则成功传输
   • 如果检测到了碰撞，则传输32bit的Jam Signal（部分参考书说是48bit，总之它很短）。在以太网中，最短的数据帧是64bits，而这个Jam Signal看起来特别短，因此很好识别。
3. 截断二进制指数退避（Truncated Binary Exponential Backoff）：所有收到Jam Signal的设备都将进入截断二进制指数退避阶段。
   • 如果传输碰撞次数小于16，第n次冲突后，退避时间从(\{0, 1, \dots, 2^k - 1\})中随机选择，其中(k = \min(n, 10))
   • 如果传输碰撞数大于16，网卡会放弃这个帧的传输。

以太网比ALOHA的效率高很多。它适合于很长的帧传输（长时占用效率更高）。然而，在节点更多，数据包更小时，冲突和仲裁可能更频繁。还有链路过长时，脆弱期较大。

CSMA/CA协议

无线网络基础

在无线通信中，有两种模式：

• 基础设施模式（infrastructure mode）：基站将无线主机接入有线网络；当无线主机移动时，需执行 “切换（handoff）” 以更换基站，保持网络连接。
• 自组织模式（ad hoc mode）：无基站，节点间直接通信；节点只能向通信范围内的其他节点传输，需自行组织成网络并完成路由。

而下面介绍的CSMA/CA就是基于基础设施模式模式的。即，有接入点（Access Point），所有通信都是与AP之间进行通信，设备之间不直接通信。

而在无线局域网中，存在一个隐藏节点问题：节点 C 在节点 A 的通信范围外，但在节点 B 的通信范围内（A 和 B 能互相通信，B 和 C 能互相通信，但 A 和 C 无法通信）。此时：A 向 B 传输时，C 若同时向 B 传输，会在 B 处引发冲突，但 A 和 C 互相 “隐藏”，无法感知对方的传输，导致冲突无法避免。这种问题会降低网络利用率。

因此，在无线网络中，碰撞检测是很难的。需要从另一个思路切入：碰撞避免（Collision Avoidance）。这就是CSMA/CA中CA的意思。

CSMA/CA机制

CSMA/CA的核心思想是：允许发送者预留某一信道，而不是纯粹地随机接入。这样来避免长数据帧时发生冲突（短的预留包即使冲突，浪费也很小）。

1. 发送方发 RTS：发送方先发送短的请求发送包（RTS Request To Sent）给接入点（AP），RTS 包含数据帧的长度等信息。（RTS 可能与其他 RTS 冲突，但因 RTS 很短，冲突损失小）
2. AP回复CTS：AP收到 RTS 后，广播允许发送包（CTS Clear To Sent），CTS 包含与 RTS 对应的长度信息。
3. 所有节点感知 CTS：CTS 被广播范围内所以节点接收，这会 “预留” 信道给发送方。
4. 发送方发数据帧并收 ACK：发送方传输数据帧，接收方收到后返回确认包（ACK）。

例题

计算以下网络中 CSMA/CD 协议的效率：
- 2.5 公里总线拓扑
- 10 Mbps 传输速率
- 620 字节帧
- 信道传播速度：V = 2x10^8 m/s

$$t_{prop}=2500/(2\times 10^8)=1.25\times 10^{-5}s$$ $$t_{frame}=620\times 8/(10\times 10^6)=4.96\times 10^{-4}s$$ $$a=\frac{t_{prop}}{t_{frame}}=0.0252$$ $$\rho_{max}=\frac{1}{1 + (2e + 1)a}\approx86.04\%$$