EE1608-Computer-Networks-Topic2-Data-Link-Layer

引入-数据链路层

数据链路层的主要作用是将一帧数据从一个节点传输到另一个临近的节点，这两个节点将位于同一个广播域中。因此数据链路层还会针对一个广播域提供差错控制、流控等服务。

数据链路层是服务于网络层的。一个数据包从一个网络层传输到另一个网络层，可能跨越多个不同的广播域，这些广播域可能使用不同的链路层协议，这是可行的。

数据链路层在IEEE802标准中可以细分为两个子层：

• 介质访问控制（Medium Access Control，MAC）：将载荷编码为帧；进行执行地址识别和错误检测；
• 链路逻辑控制（Link Logic Control，LLC）：为高层协议提供接口；提供流控与差错控制；

流控机制（Flow Control）

停等流控（Stop & Wait）

停等流控的机制

停等流控的步骤是：

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

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

记$t_{prop}$为传播时延，$t_{frame}$为数据帧传输时延，$t_{ack}$为应答帧传输时延。则停等流控造成的总延迟如下图，$T_D=2\times t_{prop}+t_{frame}+t_{ack}$：

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

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

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

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

$$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}$$

上图是$a$与传播时延、传输时延之间的关系。如果$a<1$，则传输时延远大于传播时延，此时信道利用率更高，这是停等流控所喜欢的情况。

进一步表示：有效信道利用率$R_{eff}$

如果我们将$2t_{prop}+t_{frame}$，即，传播所需要的时间记为$T_D$。那么$U=\frac{L_{frame}/R}{T_D}$，其中R是信道标称传输速率

引入新的变量：有效传输速率（Effective Transmission rate）$R_{eff} = \frac{L_{frame}}{T_D}$。

通过信道利用率$U=\frac{R_{eff}}{R}$可以看出，$R_{eff}$代表信道实际的传输速率，且$R_{eff}=U\cdot R$。

例题1：计算停等流控的帧大小-利用率关系

一个信道的速率为4Kbps, 传播时延为20ms，信道使用停等流控。如果要使得信道利用率为50%，那么对应的帧大小是多少？

$$U=\frac{t_{frame}}{2t_{prop}+t_{frame}}=50\%$$ $$t_{frame}=0.5\times(2\times20ms+t_{frame}), \ \ \ t_{frame}=40ms$$ $$Size/4\times10^3=40\times10^{-3}, \ \ \ Size=160 bits$$

例题2：计算链路效率与实际吞吐量

一个信道的比特率为 1Gbps，传播延迟为 15ms。若帧大小为 1000 字节，那么停等协议下的链路效率是多少？吞吐量（以 bps 为单位）又是多少？

$$t_{frame}=1000\times 8 bits/1\times10 ^ 9bps=8us$$ $$U=\frac{t_{frame}}{2t_{prop}+t_{frame}}=\frac{8us}{30ms+8us}=0.0267\%$$ $$R_{eff}=U\cdot R=267 kbps$$

滑窗流控（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下，信道利用率的关系。

例题

考虑一个无误差的 2Mbps 卫星信道，用于单向发送 16KB 的数据帧，另一方向的 ACK 非常短（可忽略）。 在窗口大小分别为 1、7、15 和 128 的情况下，最大吞吐量是多少？ 往返传播延迟为 540 毫秒。

根据题目，$2t_{prop}=540ms, t_{prop}=270ms$，发送16KB的数据，$t_{frame}=\frac{16\times 8\times10^3}{2\times10^6}=64ms$

$$a=\frac{t_{prop}}{t_{frame}}=\frac{270}{64}, \quad 2a+1=\frac{151}{16}=9.4375$$

• 当$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 Control）

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

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

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

Stop & Wait ARQ

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

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

停等流控性能建模

在停等流控中，有需要重传（有差错）和无需重传（无差错）两种情况。

对于无差错的情况，传播单帧所需要的时间是$T_D = t_{\text{frame}} + 2t_{\text{prop}}$，因此信道利用率是：

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

再考虑有差错的情况，由于发送方需要重传（且重传了还有可能错），因此需引入 “每成功传输一帧的期望传输次数 (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$

假设帧正确传输的概率为$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}}$

PPT的方法计算$N_r$

假设 “单个帧出错的概率为 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}$$

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未见明显衰减，因为它的重传只重传单帧，利用率受错误影响有限。。

错误检测机制（Error Detection）

当一个比特（bit）在传输和接收之间被改变时，称发生了错误 —— 比如发送 1 接收 0，或发送 0 接收 1。

错误被分为独立比特错误（Independent bit errors）和突发错误（Burst errors）两种：

• 独立比特错误（Independent bit errors）：一帧数据中，某一个比特错误的概率与其他比特相互独立。
• 突发错误（Burst errors）：由于信道噪声产生了干扰，在一个长度为B的序列中，其第一个比特、最后一个比特以及任意数量的中间比特都会出错

常见的错误检测原理为：发送方向数据中添加额外的错误检测码（error detecting code）接收方基于接收到的码字（code word），重新计算该检测码，再与发送方的校验位比对。

奇偶校验（Parity Check）

单奇偶校验（Single Parity Check）

发送方添加 1 个额外比特（奇偶校验位，parity bit） 用于错误检测。

• 如果是偶（even）校验，则通过添加的校验位使得最终码字中1的个数为偶数。
• 如果是奇（odd）校验，则通过添加的校验位使得最终码字中1的个数为奇数。

例如信息位为1100110，其中有4个1，因此校验位为0，保持码字1的个数是偶数。码字为11001100

若接收方收到码字11011100，统计 1 的个数为5（奇数），则判定存在错误。

在计算机中，偶校验的是否存在错误可以通过模2运算来计算。例如5%2=1，则有错。4%2=0，则无错

局限性：单奇偶校验无法检测偶数个比特错误，例如上述码字若有 2 个比特错误，变为11010100，1 的个数仍为偶数，接收方会误认为无错。仅能检测奇数个比特错误的模式。

冗余度（Redundancy）：每k个信息位添加 1 个冗余位，开销（overhead）为(\frac{1}{k+1})。

错误概率分析：假设信道中每个比特出错的概率为p（且(p < 0.5)，即单比特错误比多比特错误更可能发生）。

不可检测的错误模式是偶数个比特错误，其概率为：

$$P[\text{undetectable error}] = \sum_{i=2,4,\dots}^n \binom{n}{i} p^i (1-p)^{n-i}$$

例如当(n=32)，(p=10^{-3})时，$P[\text{undetectable error}]\approx4.96 \times 10^{-4}$即大约每 2000 个错误中，有 1 个无法被检测

二维奇偶校验（Two-Dimensional Parity Check）

二维奇偶校验将信息排列成块，为每一行和每一列都添加校验位。如下图：

对于二维奇偶校验，错误小于3个时，一定可以被检测出。对于4bit错误时，大多数情况都可以被检出，除了下图这样的2个错误在一行，2个错误在一列的情况。

冗余度（Redundancy）：冗余度与编码的块大小有关。在上面的例子中，20bits的信息需要10bits的校验码，冗余度非常高。因此编码效率很低。

网络检验和（Internet Checksum）

诸如IPv4, TCP/UDP等协议使用校验和来检测错误。

• IPv4：仅检测 IP 头部的错误；
• TCP/UDP：端到端检测传输层头部（包含网络层和传输层信息）及有效载荷数据的错误。

对于IP头部的校验和，每经过一次路由器都会重新计算一次。本课对于校验和这里使用IP Checksum作为例子。IP的校验和有16bit。

校验和的二进制计算方式

1. 将原始数据按照块大小（IP中为16字节）划分，记为(b_0, b_1, b_2, \dots, b_{L-1})；（每个字段遵循big-endian）
2. 计算这些 16 位字的和，对(2^{16}-1)（即 65535）取模。这一步等效于使用二进制加法将每个块相加。若最高位发生进位，将溢出的高位加回到低位（称为回卷（end-around carry））
3. 记和为$x$，计算$-x \mod (2^{16}-1)$，这一步等效于二进制下取结果的反码，

取模运算的计算方式：

计算 23 mod 5：$23/5=4…3$。所以结果是：23 mod 5 = 3

计算 -7 mod 4 （不同于取余，取模需要向负无穷取整，即$-7/4=-1.72$，这里要取-2，余正数）$-7 / 4 = -2 余 1$，所以结果是：-7 mod 4 = 1

校验和的验算方式

在计算完校验和后，会把它插入到原来码字中，在接收端，接收机接收数据之后把接收的所有块都加起来记为$S$（即，把信息分割成块相加，再加上插进去的校验和），需要满足(S \mod (2^{16}-1) = 0)，或在二进制下满足累加结果全为1。

例题1：计算以下数据的Checksum：1000(8), 1010(10), 0000(0), 1001(9)。块大小为4bits

十进制计算方式：

$$8+10+0+9=27$$ $$27\ mod(2^4-1)=12$$ $$Checksum=-12\ mod(2^4-1)=3$$

二进制计算方式：

$$1000+1010=0010+10000$$

因为发生了进位，将进位加到LSB（回卷），因此结果是$0010+1=0011$

$$0011+0=0011, 0011+1001=1100$$

$1100$取反等于$0011$（十进制是3）

来试试进行十进制的校验操作：$8+10+0+9+3=30$，$30\mod (2^4-1)=0$。结果为0，无错误。

例题2：计算以下数据的Checksum：10001010（138），00001001（9）。块大小为8bits

十进制的计算方式：

$$(138+9)\mod(2^8-1)=147\mod 255=147$$ $$Checksum=-147\mod(255)=108$$

二进制的计算方式

$$10001010+00001001=10010011\quad \text{无进位，不回卷}$$ $$\sim10010011=01101100=108$$

来试试进行二进制的校验操作：$10001010+00001001+01101100=11111111$，累加结果全为1，正确。

多项式码（Polynomial Code）/ 循环冗余码（CRC）

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

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

通常来说，Checksum用软件来计算和验算，但CRC依赖于硬件计算电路（移位寄存器电路（shift-register circuits））。

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检测的局限性，我们来更详细地讨论各种情况：

1. 奇数个比特错误的检测

若(C(x))包含因子((x+1))，则所有奇数个比特错误的模式均可检测。因为奇数个比特错误的(E(x))项数为奇数，而((x+1))仅能整除项数为偶数的多项式（模 2 运算下的特性），因此这类错误必然可检测。

2. 双比特错误的检测

若(C(x))不整除任何(x^m + 1)（其中(m < n)，n是码字的比特数），则所有双比特错误均可检测。双比特错误的(E(x))形式为(x^i + x^j)（(i \neq j < n)），若(C(x))不整除这类多项式，则双比特错误可被检测。

3. 突发错误的检测（连续k个bit段内集中出现错误）

若(C(x))的次数为k，则所有长度≤k的突发错误均可检测。长度为k或更短的突发错误，其(E(x))的次数≤(k-1)，而(C(x))的次数为k，因此(C(x))无法整除这类(E(x))，错误可被检测。

4. 单比特错误的检测

生成多项式必须至少包含两个非零项（即不是单项式），即可检测所有单比特错误。如果生成多项式有至少两个非零项，那么它永远不能整除单项式 $x^i$，因此所有单比特错误都能被检测出来。

不难看出，生成多项式决定了CRC纠错的能力。不同通信标准采用了特定的生成多项式(C(x))，以下是链路层中CRC生成多项式的典型示例：

• 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（以太网等标准）。

x次余数表

任意一个生成多项式都有一个余数表，下面是$C(x)=x^4+x^2+1$的余数表。在Dividend-Bin/Poly这一栏中，表示对应位置的比特出现错误，Remainder - Bin中的数字表示这个错误出现时，使用生成多项式去检测的余数。

通过这个表可以快速看出哪些比特的错误组合不能被这个生成多项式检出，例如，$ x^0 $和$ x^7 $的余数都是1，那么如果错误图案是$ x^7+x^0 $时，余数就会相消，无法检出错误。

Dividend - Bin	Dividend - Poly	Remainder - Bin
1	( x^0 )	1
10	( x^1 )	10
100	( x^2 )	100
1000	( x^3 )	1000
10000	( x^4 )	0101
100000	( x^5 )	1010
1000000	( x^6 )	1
10000000	( x^7 )	10
100000000	( x^8 )	100
1000000000	( x^9 )	1000
10000000000	( x^{10} )	0101

这个的计算非常简单：

• 例如$C(x)=x^4+x^2+1$的次数为4，那么小于4次的（$x^0,x^1,x^2,x^3$）余数就是它本身。
• 从4次开始，需要计算余数。但是这个计算非常快，只需要算出一个之后在后面补零继续写即可（建议实操试试就知道了）
• 如果算到后面出现了与前面重复的余数，就可以停止计算了，余数表会这样一直重复下去。例如上表，算到$ x^6 $又出现了1，就说明后面都是前面的余数一直循环了。

介质访问控制（Medium Access Control）

概述

为何需要介质访问控制

在计算机网络中，常出现多个设备连接在一条总线，或是他们共享同一种介质进行通信的情况。此时称为这些计算机在一个碰撞域内，需要对他们对传输介质进行管理，否则可能有很多设备同时发信，最终谁也听不清。这就是介质访问控制（Medium Access Control，MAC）

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

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

随机接入介质访问控制

随机接入易于实现，无需复杂计算和昂贵组件，但其需要解决碰撞问题，因此称站点会为共享介质的时间竞争（即 “contention”）。随机接入的MAC协议旨在规范如何检测随机访问时的数据碰撞，以及如何对损毁的数据进行重传。

在IEEE 802.3以太网标准中，采用的 CSMA/CD进行随机接入MAC。而CSMA/CD 的前身是ALOHA、slotted ALOHA、和CSMA。这将在下面的内容中详细介绍。

ALOHA协议

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

标准ALOHA

协议机制

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

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

性能分析

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

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

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

如果系统每秒尝试传输$G$个帧，其中每个帧传输成果的概率是$P_{success}$，那么，系统的吞吐量就是：

$$S=GP_{success}$$

而需要重传的概率就是$1-P_{success}$，重传数为$G(1-P_{success})$

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

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

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

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

将其代入吞吐量：$S=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帧时到达峰值。

练习题：多个终端通过纯 ALOHA 协议与主计算机通信，信道速率 2400 bps；每个终端平均每 2 分钟发一次 200 比特的消息。求最多支持多少个这样的终端？

对于标准ALOHA，信道利用率为18.4%，因此2400bps的信号，吞吐量为：

$$2400\times18.4\%=441.6bps$$

每个终端每120秒发送200bits消息，每秒平均$200/120\approx1.6667bis/s$

$$441.6/1.6667\approx265个$$

因此，最多支持265个这样的终端。

Slotted ALOHA

协议机制

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

性能分析

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

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

$$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台终端。

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. 若检测到冲突，所有涉及的站点立即停止传输，规划随机退避时间后重新尝试传输。

冲突浪费的优化：在纯 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）。

网络设备

在网络中，大致有4类设备：集线器 / 中继器（Hubs/Repeaters）、网桥 / 交换机（Bridges/Switches）、路由器（Routers）。

多数网络设计者逐渐摒弃集线器，主要使用交换机和路由器 —— 这是因为集线器的性能局限（如共享冲突域），而交换机在效率、隔离冲突域等方面优势更明显。

集线器 / 中继器（Hubs/Repeaters）

集线器和中继器都是工作在物理层的设备，核心作用是信号再生与多端口扩展。它不识别任何地址，只是简单地将接收到的数据再发出去。

中继器负责将衰减了的数字信号重新识别，再生一次，让数字信号可以传播更远。

集线器是一种 “多端口中继器”，接某一信号后再生（regenerate），然后朝着所有端口都发出去。

当主机A想要向主机B发送数据时，集线器会将数据从除了接收端口以外的所有端口广播出去。这意味着，尽管主机B确实收到了数据，但主机C和C也会收到这些数据，然后它们会忽略这些不属于自己的数据。

同时，A发东西时如果C也开始发东西，他们会产生物理层的碰撞，因此，一个HUB内的设备都位于一个碰撞域（collision domain）

网桥 / 交换机（Bridges/Switches）

网桥和交换机都是工作在物理层 + 数据链路层的设备，他们会基于 MAC 地址智能转发，同时，也能在物理层再生数字信号，让它传播得更远。

交换机的每个端口对应一个独立碰撞域（collision domain）（端口下的设备碰撞仅局限在本端口，不会影响其他端口）。网桥就像是只有2个端口的交换机。

正因为碰撞域的隔离，二层设备快速代替了HUB和中继器。

交换机的自学习机制

交换机可以检查链路层的头部

1. 当交换机收到一帧数据的时候，它会检查这个数据的发送者MAC地址，将这个MAC地址与对应的端口记录在自己的Switching Table中
2. 接着交换机会检查目的地MAC地址
   • 如果目的地MAC地址和发送者一致（他们处于同一个物理碰撞域内），则交换机直接丢弃该帧。因为不需要交换机参与转发到其他碰撞域。
   • 如果目的地MAC在自己的Switching Table中，则直接朝着对应端口转发
   • 如果目的MAC地址在何端口未知，则朝着收到帧的端口以外的所有端口泛洪（flood）

例如上图这个例子：

• （a）：首先交换机的交换表是空的
• （b）：在A尝试给D发送一个消息之后，交换机学习到A的MAC在Port1，并把这个帧消息在2 3 4端口上转发
• （c）：B C D都收到这个消息，但是BC发现不是给自己的，丢弃。D回复A消息，这次通过D的回复，交换机学习到了D的MAC在自己的Port4，并把这个消息转发到Port 1单播给A
• 后续过程同理

因为在不知道对应主机的MAC地址时，交换机会进行广播数据帧，因此称交换机连接的范围为一个广播域（Broadcast Domain）

生成树协议（Spanning Tree Algorithm）

广播风暴（Broadcast Strom）

考虑下图这个例子：有两个网桥$\alpha$和$\beta$（2口交换机），他们的交换表在一开始时空的。记下方的端口是1，上方的端口是0

• 此时A尝试给B发送一个消息，$\alpha$和$\beta$都收到了这个消息，他们首先学到A在我的下方，即，学习到(A’s MAC, Port 1)，然后把这个消息朝着上方（端口2）发出去。
• 而$\alpha$和$\beta$的端口2都会收到被对方转发的帧，这时候，他们各自都重新学习到了A在我的上方，即(A’s MAC, Port 2)，然后把这个消息朝着下方（端口1）发出去。
• 端口1这边又进行重新学习，学到(A’s MAC, Port 1)，然后把这个消息朝着上方（端口2）发出去。
• 如此往复，他们就在自我学习中反复横跳，根本不干活了。这就是广播风暴。

为了解决广播风暴，需要生成树算法（Spanning Tree Algorithm）

生成树算法（Spanning Tree Algorithm）

生成树算法遵循以下几个步骤，来确认谁负责转发哪个LAN的消息，避免大家都转发形成回路：

1. 选择根网桥（root bridge）：在所有网桥中，选择网桥 ID 最小的作为根网桥（网桥 ID 由优先级和 MAC 地址组成，优先级默认相同，因此通常是 MAC 地址最小的网桥）。
2. 为每个非根网桥确定根端口（root port）：跟端口是非根网桥中，到根网桥路径成本最低的端口，记录为R。路径成本由链路的 “开销” 决定（例如经过一个LAN，开销为1）
3. 为每个 LAN 选择指定网桥+端口：对于每个 LAN，选择到根网桥路径成本最低的端口，记录为D。（例如经过一个其他LAN，开销为1）
4. 阻塞无用端口：如果存在端口既不是R也不是D，则在逻辑上将他们阻塞。就像是断开连接了一样，任何数据都不从这个端口收发。

举个例子：

1. 选择根网桥：上图中，B1是路由ID最小的，那么B1就是MAC地址最小的，它被选择为根路由。
2. 为网桥选择根端口R：现在我们要为B2，B3，B4，B5选择根端口。
   • 对于B2，它的1和2端口到B1都经过一个LAN，因此开销相同，选择编号低的1号端口作为根端口
   • 对于B3，它的1号端口到B1只经过一个LAN，开销最低，因此选1号。
   • 对于B4，它的1号端口到B1只经过一个LAN，开销最低，因此选1号。
   • 对于B5，它的1号端口到B1需要经过2个LAN（LAN3+LAN2），二号端口也需要经过2个LAN（LAN4+LAN1），因此选择编号小的1。
3. 为LAN选择网桥+端口D：
   • 对于LAN1，它到B1最近的端口是B1的（1），cost为0
   • 对于LAN2，它到B1最近的端口是B1的（2），cost为0
   • 对于LAN3，它到B1最近的端口是B3的（2），cost为1
   • 对于LAN4，它到B1最近的端口是B3的（3），cost为1
4. 选择的D和R如下图所示，将既不是D也不是R的端口阻塞掉（下图虚线）

此时拓补内就没有环路了，也就杜绝了广播风暴的存在。

三层设备与VLAN

三层设备通常是路由器，也有部分三层交换机。

前面提到，二层设备隔绝了碰撞域，连接了广播域，而三层设备可以隔绝广播域：路由器的每个接口对应一个独立广播域，从根本上避免了广播风暴的跨域传播。

路由器不依赖 MAC 地址（数据链路层标识），而是根据目的网络地址（如 IP 地址）转发流量。它会维护路由表，记录 “目标网络 - 出接口” 的映射关系，从而实现不同网络间的通信。

路由器至少有两个不同的网络接口，用于连接两个或多个逻辑子网（这些子网没有共同的网络地址）。

而三层设备与数据链路层有关的就是VLAN了，VLAN 是 “通过软件配置的逻辑局域网”，打破了 “物理布线决定组网” 的限制。即使设备位于不同物理 LAN，也可通过 VLAN 逻辑上属于同一网络，从而提升组网灵活性、安全性（隔离不同部门的流量）和资源利用率。

这段话用人话讲就是，虽然大家都连在一个交换机上，但是可以通过这个交换机设置VLAN，把大家从一个广播域分开。又可以通过路由器或三层交换机，在网络层让大家选择性地联通。从而避免一个广播域内的广播风暴、ARP攻击、抓包监听等等。