数据链路层 III（介质访问控制）【★★★★★】

（★★）代表非常重要的知识点，（★）代表重要的知识点。

介质访问控制所要完成的主要任务是：为使用介质的每个结点隔离来自同一信道上其他结点所传送的信号，以协调活动结点的传输。

下图所示是广播信道的通信方式，结点 A 、B 、C 、D 、E 共享广播信道，假设 A 要与 C 发生通信， B 要与 D 发生通信，由于它们共用一条信道，如果不加控制，那么两对结点间的通信可能会因为互相干扰而失败。

介质访问控制的内容是：采取一定的措施，使得两对结点之间的通信不会发生互相干扰的情况。用来决定广播信道中信道分配的协议属于数据链路层的一个子层，称为介质访问控制（Medium Access Control, MAC）子层。

常见的介质访问控制方法有信道划分介质访问控制（不发生冲突）、随机访问介质访问控制（可能发生冲突）和轮询访问介质访问控制（不发生冲突）。其中前者是 静态划分信道 的方法，而后两者是 动态分配信道 的方法。

一、信道划分介质访问控制

信道划分介质访问控制将使用同一传输介质的多个设备的通信隔离开来，把时域和频域资源合理地分配给这些设备，因此不存在冲突。信道划分介质访问控制通过复用技术实现。

所谓复用（multiplexing），是指在发送端把多个发送方的信号组合在一条物理信道上进行传输，在接收端把收到的复用信号分离出来，并发送给对应的接收方。

如下图所示。当传输介质的带宽超过传输单个信号所需的带宽时，可以通过在一条介质上传输多个信号来提高传输系统的利用率。

在进行通信时，复用器（multiplexer）总是和分用器（demultiplexer）成对地使用。在复用器和分用器之间是用户共享的高速信道。分用器的作用正好和复用器相反，它把高速信道传送过来的数据进行分用，分别送交到相应的用户。

信道划分的实质是通过分时、分频、分码等方法，将原来的一个广播信道，逻辑上分为几个用于在两个结点之间进行通信的互不干扰的子信道，即将广播信道转变为若干个点对点信道。信道划分介质访问控制分为：频分复用（FDM）、时分复用（TDM）、波分复用（WDM）和码分复用（CDM），下面分别详细介绍它们：

1. 频分复用（FDM）

频分复用（Frequency Division Multiplexing, FDM）是指将信道的总频带（整个带宽）划分为多个子频带，每个子频带作为一个子信道，每个用户或信号分配一个独立的子信道进行通信，如下图所示。通过这种方式，不同的信号可以同时在同一介质上进行传输，每个信号在属于自己的频带中进行传输，从而避免了信号之间的干扰。

用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带（即 FDM 的所有用户在同样的时间占用不同的带宽资源）。每个子信道分配的频带可不相同，但它们的总和不能超过信道的总频带。在实际应用中，为了防止子信道之间互相干扰，相邻信道间还要加入“隔离频带”。

频分复用的优点在于充分利用了传输介质的带宽，系统效率较高，实现也较容易。
【注意】：上面所述的“ 带宽” 指的是频率带宽而不是数据的发送速率。

2. 时分复用（TDM）

时分复用（Time Division Multiplexing, TDM）又称同步时分复用，是指将信道的传输时间划分为一段段的等长的时间片，称为 TDM 帧，每个用户在每个 TDM 帧中占用固定序号的时隙，且每个用户所占用的时隙周期性地出现（其周期就是 TDM 的长度），因此 TDM 信号也称为等时（isochronous）信号。如下图所示，所有用户在不同的时间占用同样的信道资源（即频带宽度）。

TDM 帧是一段固定长度的时间。需要注意它与数据链路层的帧不是同一个概念。

从某个时刻来看，时分复用信道上传送的仅是某对用户之间的信号；从某段时间来看，传送的是按时间分割的复用信号。

因为时分复用是按固定次序给用户分配时隙的，当用户在某段时间暂无数据传输时，其他用户也无法使用这个暂时空闲的线路资源，所以时分复用后的信道利用率不高。下图所示为时分复用可能会造成线路资源的浪费。

统计时分复用（StatisticTDM, STDM）又称异步时分复用，它是对 TDM 的一种改进，能明显地提高信道的利用率。 STDM 帧与 TDM 帧不同，它并不固定分配时隙，而按需动态分配时隙，当用户有数据要传送时，才会分配到 STDM 帧中的时隙，因此可以提高线路的利用率。

例如，假设线路的数据传输速率为 6000b/s，3 个用户的平均速率都为 2000b/s，当采用 TDM 方式时，每个用户的最高速率为 2000b/s；而在 STDM 方式下，每个用户的最高速率可达 6000b/s 。

频分复用和时分复用这两种复用方法的优点是技术比较成熟，但缺点是不够灵活。根据 FDM 和 TDM 的工作原理可以得出：频分复用 FDM 适合传输模拟信号，时分复用 TDM 则更适合数字信号的传输。

时分复用 TDM 在发送端将不同用户的信号互相交织在不同的时间片内，沿同一个信道传输，在接收端再将各个时间片内的信号提取出来，还原成原始信号。为了实现 TDM，必须满足如下条件：
① 介质的位速率（即每秒传输的二进制位数）大于单个信号的位速率；
② 介质的带宽（即所能传输信号的最高频率与最低频率之差）大于结合信号的带宽（即所有信号经过调制后形成的复合信号的带宽）。

3. 波分复用（WDM）

波分复用（Wavelength Division Multiplexing, WDM）即光的频分复用，它在一根光纤中传输多种不同波长（频率）的光信号，因为波长不同，各路光信号互不干扰，最后用光分用器将各路波长分解出来。因为光波处于频谱的高频段，有很大的带宽，所以可以实现多路的波分复用。下图为波分复用的概念示意图。

【拓展】：最初，人们只能在一根光纤上复用两路光载波信号，这种复用方式称为波分复用（WDM）。随着技术的发展，在一根光纤上复用的光载波信号的路数越来越多。现在已能做到在一根光纤上复用几十路或更多路数的光载波信号，于是就使用了密集波分复用（Dense Wavelength Division Multiplexing, DWDM）这一名词。
例如，每一路的数据率是 40 Gbit/s, 使用 DWDM 后，如果在一根光纤上复用 64 路，就能够获得 2.56 Tbit/s 的数据率。

4. 码分复用（CDM）

码分复用（Code Division Multiplexing, CDM）是采用不同的编码来区分各路原始信号的一种复用方式。与 FDM 和 TDM 不同，它既共享信道的频率，又共享时间。

实际上，更常用的名词是码分多址（Code Division MultipleAccess, CDMA），其原理是：将每个比特时间再划分成 m 个短的时间槽，称为码片（Chip），通常 m 的值是 64 或 128 ，下例中为简单起见，设 m 为 8 。每个站点被指派一个唯一的 m 位码片序列（chip sequence），发送 1 时，站点发送它的码片序列；发送 0 时，站点发送该码片序列的反码。当两个或多个站点同时发送时，各路数据在信道中线性相加。为了从信道中分离出各路信号，要求各个站点的码片序列相互正交。

简单理解就是，A 站向 C 站发出的信号用一个向量来表示，B 站向 C 站发出的信号用另一个向量来表示，两个向量要求相互正交。向量中的分量，就是所谓的码片。由于各用户使用经过特殊挑选的不同码型，因此各用户之间不会造成干扰。

下面举例说明 CDMA 的原理：

1）向量 S 与向量 T 的关系

令向量 S 表示 A 站的码片向量，T 表示 B 站的码片向量。
假设 A 站的码片序列被指派为 00011011 ，则 A 站发送 00011011 就表示发送比特 1 ；发送 11100100 就表示发送比特 0 。为了方便计算，将码片中的 0 写为 -1 ，将 1 写为 +1 ，因此 A 站的码片向量 S = (-1 -1 -1 +1 +1 -1 +1 +1) 。
同时，令 B 站的码片向量 T = (-1 -1 +1 -1 +1 +1 +1 -1) 。

【拓展】：现假定 N 站要发送信息的数据率为 b bit/s 。由于每一个比特要转换成 m 个比特的码片，因此 N 站实际上发送的数据率提高到 mb bit/s，同时 N 站所占用的频带宽度也提高到原来数值的 m 倍。这种通信方式是扩频（spread spectrum）通信中的一种。
扩频通信通常有两大类。一种是直接序列扩频（Direct Sequence Spread Spectrum, DSSS）；另一种是跳频扩频（Frequency Hopping Spread Spectrum, FHSS）。上述的使用码片序列属于直接序列扩频。

CDMA 系统的一个重要特点就是这种体制给每一个站分配的码片序列不仅必须各不相同，并且还必须互相正交（orthogonal）（在实用的系统中是使用伪随机码序列）。
两个不同站的码片序列正交，即向量 S 和 T 的规格化内积（inner product）为 0：

已知 S = (-1 -1 -1 +1 +1 -1 +1 +1) ，T = (-1 -1 +1 -1 +1 +1 +1 -1) 。
得到 S’ = (+1 +1 +1 -1 -1 +1 -1 -1) ，T’ = (+1 +1 -1 +1 -1 -1 -1 +1) （这里的 S’ 代表 S 的二进制反码，T’ 代表 T 的二进制反码），满足 S ⋅ T = 0，S ⋅ S = T ⋅ T = 1，S ⋅ S’ = T ⋅ T’ = -1 。

2）发送方对数据进行叠加

当 A 站向 C 站发送数据 1 时，就发送了向量 S = (-1 -1 -1 +1 +1 -1 +1 +1) ；
当 B 站向 C 站发送数据 0 时，就发送了向量 T’ = (+1 +1 -1 +1 -1 -1 -1 +1) 。
两个向量在公共信道上叠加（实际上是线性相加），得到 S + T’ = (0 0 -2 2 0 2 0 2) 。

3）接收方对数据进行分离

到达 C 站后，进行数据分离，若要得到来自 A 站的数据，则 C 站就必须知道 A 站的码片序列，让 S 与 S + T’ 进行规格化内积。根据叠加原理，其他站点的信号都在内积的结果中被过滤掉（其内积的相关项都是 0），而只剩下 A 站发送的信号，得到：
S ⋅ (S + T’) = S ⋅ S + S ⋅ T’ = 1 + 0 = 1 ，所以 A 站发出的数据是 1 。
同理，若要得到来自 B 站的数据，则：
T ⋅ (S + T’) = T ⋅ S + T ⋅ T’ = 0 + (-1) = -1 ，所以 B 站发送过来的信号向量是一个反码向量，代表 0 。

下图为码分复用的原理示例图：

码分复用技术具有频谱利用率高、抗干扰能力强、保密性强、语音质量好等优点，还可以减少投资及降低运行成本，主要用于无线通信系统，特别是移动通信系统。

二、随机访问介质访问控制（★★）

在随机访问协议中，不采用集中控制方式解决发送信息的次序问题，所有用户都能根据自己的意愿随机地发送信息，占用信道的全部速率。

在总线形网络中，当有两个或多个用户同时发送信息时，就会产生帧冲突（也称碰撞），导致所有冲突用户的发送均以失败告终。为了解决随机访问发生的冲突，每个用户需要按照一定的规则反复地重传它的帧，直到该帧无冲突地通过，这些规则就是随机访问介质访问控制协议，其核心思想是：胜利者通过争用获得信道，进而获得信息的发送权。因此，随机访问介质访问控制协议又称争用型协议。需要注意的是随机访问介质访问控制协议在发送过程中可能会发生冲突。

可见，若采用信道划分机制，则结点之间的通信要么共享空间，要么共享时间，要么共享空间和时间；而若采用随机访问控制机制，则结点之间的通信既不共享时间，又不共享空间。因此，随机介质访问控制实质上是一种将广播信道转换为点到点信道的机制。如下图所示。

1. ALOHA协议

ALOHA（Additive Link On-line HAwaii system）协议分为纯 ALOHA 协议和时隙 ALOHA 协议两种。

1）纯ALOHA协议

纯 ALOHA 协议的基本思想是：当总线形网络中的任何站点需要发送数据时，可以不进行任何检测就发送数据。若在一段时间内未收到确认，则该站点就认为传输过程中发生了冲突。发送站点需要等待一段时间后再发送数据，直至发送成功。

下图表示一个纯 ALOHA 协议的工作原理。每个站均可自由地发送数据帧，假定所有帧都是定长的，帧长不用比特而用发送这个帧所需的时间来表示，图中用 T₀ 表示这段时间。

在上图的例子中，当站 1 发送帧 1 时，其他站都未发送数据，所以站 1 的发送必定是成功的。但随后站 2 和站 N - 1 发送的帧 2 和帧 3 在时间上重叠了一部分（即发生了冲突）。

发生冲突的各站都必须进行重传，但并不能马上进行重传，因为这样做必然导致继续发生冲突。因此，纯 ALOHA 协议采用的重传策略是让各站等待一段随机的时间，然后进行重传。若再次发生冲突，则需要再等待一段随机的时间，直到重传成功为止。

图中其余一些帧的发送情况是，帧 4 发送成功，而帧 5 和帧 6 发生冲突。

纯 ALOHA 网络的吞吐量很低，为了克服这个缺点，人们在原始的纯 ALOHA 协议的基础上进行改进，产生了时隙 ALOHA 协议。

2）时隙ALOHA协议

时隙 ALOHA 协议同步各站点的时间，将时间划分为一段段等长的时隙（Slot），规定站点只能在每个时隙开始时才能发送帧，发送一帧的时间必须小于或等于时隙的长度。这样做避免了用户发送数据的随意性，降低了产生冲突的可能性，提高了信道的利用率。

下图表示两个站的时隙 ALOHA 协议的工作原理。每个帧到达后，一般都要在缓存中等待一段小于时隙 T₀ 的时间，才能发送出去。当在一个时隙内有两个或两个以上的帧到达时，在下一个时隙将产生冲突。冲突后重传的策略与纯 ALOHA 协议的情况相似。

2. CSMA协议

时隙 ALOHA 系统的效率虽然是纯 ALOHA 系统的两倍，但每个站点都是随心所欲地发送数据的，即使其他站点正在发送也照发不误，因此 ALOHA 网络发生冲突的概率很大。

若每个站点在发送前都先监听公用信道，发现信道空闲后再发送，则会大大降低冲突的可能性，从而提高信道的利用率，载波监听多路访问（Carrier SenseMultiple Access, CSMA）协议依据的正是这一思想。

CSMA 协议是在 ALOHA 协议基础上提出的一种改进协议，它与 ALOHA 协议的主要区别是多了一个载波监听装置。根据监听方式和监听到信道忙后的处理方式的不同，CSMA 协议分为：1-坚持 CSMA、非坚持 CSMA 和 p-坚持 CSMA 。

1）1-坚持 CSMA

1-坚持 CSMA（1-persistent CSMA）的基本思想是：当站点要发送数据时，首先监听信道：若信道空闲，则立即发送数据；若信道忙，则继续监听直至信道空闲。

“坚持”的含义是：监听到信道忙时，继续坚持监听信道；“1” 的含义是监听到信道空闲时，立即发送的概率为 1 。

传播延迟对 1-坚持 CSMA 协议的性能影响较大。结点 A 开始发送数据时，结点 B 也正好有数据要发送，但这时结点 A 发出数据的信号还未到达结点 B，结点 B 监听到信道空闲，于是立即发送数据，结果必然导致冲突。

即使不考虑延迟，1-坚持 CSMA 协议也可能产生冲突。例如，结点 A 正在发送数据时，结点 B 和 C 也准备发送数据，监听到信道忙，于是坚持监听，结果当结点 A 发送完毕，结点 B 和 C 就会立即发送数据，同样导致冲突。

2）非坚持 CSMA

非坚持 CSMA（Non-persistent CSMA）的基本思想是：当站点要发送数据时，首先监听信道：若信道空闲，则立即发送数据；若信道忙，则放弃监听，等待一个随机的时间后，再重新监听。

非坚持 CSMA 协议在监听到信道忙时就放弃监听，因此降低了多个站点等待信道空闲后同时发送数据导致冲突的概率，但也增加了数据在网络中的平均时延。可见，信道利用率的提高是以增加数据在网络中的延迟时间为代价的。

3） p-坚持 CSMA

p-坚持 CSMA（p-persistent CSMA）只适用于时分信道，其基本思想是：当站点要发送数据时，首先监听信道：若信道忙，则持续监听（即等到下一个时隙再监听），直至信道空闲；若信道空闲，则以概率 p 发送数据，以概率 1 - p 推迟到下一个时隙再继续监听；直到数据发送成功。

I、p-坚持 CSMA 检测到信道空闲后，以概率 p 发送数据，以概率 1 - p 推迟到下一个时隙继续监听的目的是：降低 1-坚持 CSMA 中多个站点检测到信道空闲时同时发送帧的冲突概率；
II、采用坚持“监听”的目的是：克服非坚持 CSMA 中因随机等待造成的延迟时间较长的缺点。

因此，p-坚持 CSMA 协议是非坚持 CSMA 协议和 1-坚持 CSMA 协议的折中。

4）三种 CSMA 协议的比较

三种不同类型的 CSMA 协议比较如下图所示：

3. CSMA/CD协议——冲突检测机制

1）CSMA/CD协议的特点

载波监听多路访问/冲突检测（CSMA/CD）协议是 CSMA 协议的改进方案，适用于 总线形网络或半双工网络 环境，许多计算机以多点接入的方式连接在一根总线上。对于全双工网络，因为全双工采用两条信道，分别用来发送和接收，在任何时候，发收双方都可以发送或接收数据，不可能产生冲突，所以不需要 CSMA/CD 协议。CSMA/CD 协议的实质是“载波监听”和“冲突检测”。

① 载波监听是指每个站点在发送前和发送过程中都必须不停地检测信道。在发送前检测信道是为了获得发送权；在发送过程中检测信道是为了及时发现发送的数据是否发生冲突。

② 站点要在发送数据前先监听信道，只有信道空闲时才能发送。冲突检测（Collision Detection）就是边发送边监听的，若监听到了冲突，则立即停止数据发送，等待一段随机时间后，重新开始尝试发送数据。

CSMA/CD 的工作流程可简单地概括为：“先听后发，边听边发，冲突停发，随机重发”。
I、发送前的措施：发送前先监听，闲则发送，忙则等待；
II、发送时的措施：边发送边监听；
III、冲突时的措施：冲突则停发，随机退避重传。

2）信道发生冲突时的最长时间分析

电磁波在总线上的传播速率总是有限的。因此，当某时刻发送站检测到信道空闲时，信道不一定空闲。如下图所示为传播时延对载波监听的影响。

设 τ 为单程传播时延。

当 t = 0 时，A 站发送数据。
当 t = τ - δ 时，A 站发送的数据还未到达 B 站，因为 B 站检测到信道空闲而发送数据。
经过时间 δ / 2 后，即当 t = τ - δ / 2 时，A 站发送的数据和 B 站发送的数据发生冲突，但这时 A 站和 B 站都不知道。
当 t = τ 时，B 站检测到冲突，于是停止发送数据。
当 t = 2τ - δ 时，A 站检测到冲突,也停止发送数据。

显然，CSMA/CD 中的站不可能同时进行发送和接收（但必须边发送边监听信道），因此采用 CSMA/CD 协议的以太网只能进行半双工通信。

从下图不难看出，A 站在开始发送数据后最多经过时间 2τ（端到端传播时延的 2 倍）就能知道有没有发生冲突（当 δ → 0 时)。因此，把以太网的端到端之间往返传输的时间 2τ 称为争用期（contention period）（又称冲突窗口 [collision window]）。每个站在自己发送数据后的一小段时间内，存在发生冲突的可能性，只有经过争用期这段时间还未检测到冲突时，才能确定这次发送不会发生冲突。

3）最短帧长的分析

现在考虑一种情况：某站发送一个很短的帧，但在发送完之前并未检测出冲突。假定这个帧在继续向前传播到达目的站之前和别的站发送的帧发生了冲突，因此目的站将收到有差错的帧（当然会把它丢弃）。然而，发送站却不知道发生了冲突，因此不会重传这个帧。

注意：假设现在传了一个帧，还未到往返时延就发送完毕，而且在中途出现冲突，这样就检测不出错误；如果中途发生冲突，且这个帧还未发送
完，则可以检测出错误。因此，要保证 CSMA/CD 正常工作，就必须使帧的发送时间（传输时延）大于或等于来回往返时延（即争用期 2τ ）。

为了避免发生这种情况，以太网规定了一个最短帧长（即争用期 2τ 内可发送的数据长度）。在争用期内若检测到冲突，则站就停止发送，此时已发送出去的数据一定小于最短帧长，因此凡长度小于这个最短帧长的帧，就都是因为冲突而异常中止的无效帧。最短帧长的计算公式为：

最短帧长 = 总线传播时延 × 2 × 数据传输速率 = 争用期 × 数据传输速率

例如，对于 10Mb/s 的以太网（即传统以太网），按规定它的争用期长度 2τ 为 51.2μs，因此它在争用期内可发送 512bit 即 64B 的数据帧。当传统以太网发送数据时，若前 64B 未发生冲突，则后续数据也不会发生冲突（表示已成功抢占信道）。换句话说，若发生冲突，则一定在前 64B 。

因为一旦检测到冲突就立即停止发送，所以这时发送出去的数据一定小于 64B 。于是，以太网规定最短帧长的值为 64B ，凡长度小于 64B 的帧，就都是因为冲突而异常中止的无效帧，收到这种无效帧时应立即丢弃。

若只发送小于 64B 的帧，如 40B 的帧，则需要在 MAC 子层中于数据字段的后面加一个整数字节的填充字段，以保证以太网的 MAC 帧的长度不小于 64B 。
【1s(秒) = 10³ms(毫秒) = 10⁶μs(微秒) = 10⁹ns(纳秒) = 10¹²ps(皮秒)】
【10Mbit/s 的以太网，争用期 2τ 为 51.2μs；100Mbit/s 的以太网，争用期 2τ 为 5.12μs。】

CSMA/CD 协议要求：发送帧的时间 ≥ 争用期的时间（即信号在最远两个端点之间往返传输的时间）。因此，当数据传输率提高时，发送帧的时间就缩短，此时可通过增加最短帧长来增加发送帧的时间，或缩短电缆的长度来减少争用期的时间。

4）二进制指数退避算法

除检测冲突外，CSMA/CD 还能从冲突中恢复。

一旦发生冲突，参与冲突的两个站点紧接着再次发送就没有意义，若坚持这样做，则将导致无休止的冲突。CSMA/CD 采用截断二进制指数退避（truncated binary exponential backoff）算法来确定冲突后重传的时机，它让发生冲突的站点在停止发送后，推迟一个随机的时间再重新发送。算法精髓如下：

① 确定基本退避时间，一般取 2 倍的总线端到端的传播时延 2τ（即争用期）。
② 定义参数 k，它等于重传次数，但 k 不能超过 10，即参数 k = min[重传次数, 10]。可见当重传次数不超过10 时，参数 k 等于重传次数；但当重传次数超过 10 时，k 就不再增大，而一直等于 10 。
② 从离散的整数集合 [0, 1, … , (2^k - 1)] 中随机取出一个数，记为 r，重传所需推迟的时间就是 r 倍的争用期，即 2rτ 。
③ 当重传达 16 次仍不成功时，说明网络太拥挤，认为该帧永远无法正确发出，抛弃该帧并向高层报告出错。

假设适配器首次试图传送一帧，且在传送过程中检测到冲突。

当发生第 1 次重传时（k = 1），随机数 r 从整数集合 {0, 1} 中选择，可选的重传推迟时间是 0 或 2τ 。
若再次发生冲突，则第二次重传时（k = 2），随机数 r 从整数集合 {0, 1, 2, 3} 中选择，因此重传推迟时间是在 0, 2τ, 4τ, 6τ 这四个时间中随机选取的一个。
同样，若再次发生冲突，则第三次重传时（k = 3），随机数 r 从整数集合 {0, 1, 2, 3, 4, 5, 6, 7} 中选择一个数，……，以此类推。

使用截断二进制指数退避算法可使重传需要推迟的平均时间随重传次数的增大而增大（也称动态退避），因此能降低发生冲突的概率，有利于整个系统的稳定。

5）CSMA/CD协议冲突检测机制的总结

① 准备发送：适配器（adapter）从网络层获得一个分组，封装成帧，放入适配器的缓存。
② 检测信道：若信道空闲，则开始发送该帧；若信道忙，则持续检测直至信道空闲。
③ 在发送过程中，适配器仍然持续检测信道。这里只有如下两种可能：

发送成功：在争用期内一直未检测到冲突，该肯定能发送成功。
发送失败：在争用期内检测到冲突，此时立即停止发送，适配器执行指数退避算法，等待一段随机时间后返回到步骤 ② 。若重传 16 次仍不能成功，则停止重传并向上报错。

【拓展】CSMA/CD 还包括帧间间隔 96 比特时间，碰撞后发送强化干扰信号等规定。

4. CSMA/CA协议——冲突避免机制

CSMA/CD 协议已成功用于使用有线连接的局域网，但在无线局域网环境下不能简单地搬用 CSMA/CD 协议，特别是冲突检测部分，主要有两个原因：

① 接收信号的强度往往远小于发送信号的强度，且在无线介质上信号强度的动态变化范围很大，因此若要实现冲突检测，则硬件上的花费会过大。
② 在无线通信中，并非所有站点都能够听见对方，即存在“隐蔽站”问题。

为此，802.11 标准定义了广泛用于无线局域网的 CSMA/CA 协议，它对 CSMA/CD 协议进行修改，将冲突检测改为冲突避免（Collision Avoidance，CA）。“冲突避免”并不是指协议可以完全避免冲突，而是指协议的设计要尽量降低冲突发生的概率。因为 802.11 无线局域网不使用冲突检测，一旦站点开始发送一个帧，就会完全发送该帧，但冲突存在时仍发送整个帧（尤其是长数据帧）会严重降低网络的效率，所以要采用冲突避免技术来降低冲突的概率（并不能完全避免冲突）。

802.11 的冲突避免机制采用以下几种措施：
I、载波监听：发送前必须先监听信道，包括物理载波监听和虚拟载波监听；
II、帧间间隔：信道空闲后必须等待帧间间隔，优先级越高的帧等待的帧间间隔越短；
III、随机退避：帧间间隔结束后，还必须进行随机退避，退避结束后才能发送。

1）载波监听

CSMA/CA 规定发送前必须进行载波监听，用以检查传输介质是否已被占用。802.11 的载波监听包括两种方式，分别为：物理载波监听和虚拟载波监听。物理载波监听和虚拟载波监听是同时执行判断的，只有两种方式都认为信道空闲时，才判定信道空闲。

① 物理载波监听（Physical Carrier Sense）：

通常基于能量和波形识别，这种功能也称为空闲信道评估，用于了解介质当前是否繁忙。

② 虚拟载波监听（Virtual Carrier Sense）：

执行虚拟载波监听的每个站维持一个称为网络分配向量（Network Allocation Vector, NAV）的本地计数器，用来评估信道将处于繁忙状态的时间。虚拟载波监听机制检查每个帧中持续时间字段（用于指示一个数据帧在无线网络中传输所需的时间），并据此更新 NAV 变量，NAV 变量是基于本地时钟递减的，只要 NAV 变量不为 0，则信道就会被认为处于繁忙状态。

总之，虚拟载波监听机制根据 NAV 的值，判断信道是否繁忙。后续还会提到有关帧的持续时间字段以及 NAV 的概念。

2）帧间间隔

因为无线信道的通信质量远不如有线信道，所以 802.11 标准使用链路层确认/重传（ARQ）方案，即站点每通过无线局域网发送完一帧，就要在收到对方的确认帧后才能继续发送下一帧。可见，802.11 标准无线局域网采用的停止 - 等待协议是一种可靠传输协议。

为了尽量避免冲突，802.11 标准规定，移动站监听到信道空闲时，不能立即发送数据，而是需要等待一段很短的时间（继续监听）才能发送下一帧。这段时间称为帧间间隔（InterFrameSpace, IFS）。帧间间隔的长短取决于该站要发送的帧的类型。802.11 标准使用了下列三种 IFS ：

SIFS（短 IFS）：最短的 IFS，高优先级，用来分隔属于一次对话的各帧，使用 SIFS 的帧类型有 ACK 帧、CTS 帧、分片后的数据帧，以及所有回答 AP 探询的帧等。
PIFS（点协调 IFS）：中等长度的 IFS，在 PCF 操作中使用。
DIFS（分布式协调IFS）：最长的 IFS，普通优先级，用于异步帧竞争访问的时延，使用 DIFS 的帧类型有 RTS 帧、数据帧等。

注：高优先级的帧等待较短的帧间间隔。

举例：ACK 帧在 SIFS 后发送，数据帧在 DIFS 后发送。

3）随机退避

CSMA/CA 的退避算法与 CSMA/CD 的稍有不同。当信道从忙态变为空闲时，移动站等待一个 DIFS 后，仍然不能立即发送数据帧，还需要执行随机退避算法，从而降低冲突发生的概率。

当且仅当检测到信道空闲且需要发送的数据是本站的的第一帧时，才不使用退避算法，其他所有情况都必须使用退避算法，具体为：
① 在发送第一个帧之前检测到信道忙；
② 每次重传；
③ 每次成功发送后要发送下一帧。

WLAN 采用二进制指数退避算法。退避时间等于一个随机数与时隙的乘积。其中：

时隙依赖物理层标准不同，通常是几十微妙。
随机数是在区间 [0, CW] 中随机选择的一个整数，其中 CW 代表竞争窗口，是一个整数。CW 的值从物理层指定的常数 aCWmin 开始，随着重传次数增加，直到 aCWmax 为止。
直接序列扩频 DSSS 规定的 aCWmin = 31，aCWmax = 1023 。
正交频分多路复用 OFDM 规定的 aCWmin = 15，aCWmax = 1023 。

下图为数据帧经过多次重传后，CW 的变化：

下面详细介绍随机退避的规则：

随机退避计时器是无线站点发送数据帧之前的最后一个计数器，当信道从忙转闲，并持续空闲 DIFS 时间后，随机退避计时器开始计时。在退避过程中，每经过一个时隙，站点就会监听一次信道：

若信道空闲：随机退避计时器的值减 1；
若信道繁忙：挂起随机退避计时器，直到信道再次从忙转闲，并持续 DIFS 时间后，计时器恢复计时。

直到站点的随机退避计时器倒数至 0 时，意味着站点竞争获得了信道，就可以发送数据帧了。

举例：

B 站与 C 站相继产生数据，需要竞争信道进行发送，它们首先推迟至信道空闲，然后等待 DIFS 时间。在 DIFS 时间内，信道保持空闲状态，然后 B 站和 C 站进入随机退避过程。
B 站与 C 站分别从各自的竞争窗口 CW 中选择一个随机数，作为其随机退避计时器的值。假设 B 站选择了 8，C 站选择了 3 。
经过 3 个时隙后，B 站的随机退避计时器从 8 递减至 5，而 C 站的随机退避计时器从 3 递减至 0 。于是 C 站获得信道，并开始发送数据帧。
C 站发送的数据帧到达接收站后，检验通过，接收站在一个 SIFS 时间后发送确认帧 ACK 给 C 站。
C 站发送数据帧和接收 ACK 的过程中，B 站监听（虚拟载波监听）到介质忙，于是将随机退避计时器挂起，直到信道再次空闲。随后，B 站等待 DIFS 时间后，继续倒数计时。
又经过几个时隙后，B 站的随机退避计时器递减至 0 。于是 B 站获得信道，并开始发送数据帧。

4）CSMA/CA协议冲突避免机制的总结

① 若站点最初有数据要发送（而非发送不成功再进行重传），且检测到信道空闲，那么在等待时间 DIFS 后，就发送整个数据帧。
② 否则，站点执行 CSMA/CA 退避算法，选取一个随机退避值。一旦检测到信道忙，退避计时器就保持不变。只要信道空闲，退避计时器就进行倒计时。
③ 当退避计时器减至 0 时（这时信道只可能是空闲的），站点就发送整个帧并等待确认。
④ 发送站若收到确认，就知道已发送的帧被目的站正确接收。这时要发送第二帧，就要从步骤 ② 开始，执行 CSMA/CA 退避算法，随机选定一段退避时间。若发送站在规定时间（由重传计时器控制）内未收到确认帧 ACK ，就必须重传该帧，再次使用 CSMA/CA 协议争用该信道，直到收到确认，或经过若干次重传失败后放弃发送。

5）确认重传机制

CSMA/CA 采用了停止 - 等待协议，利用确认重传机制，在数据链路层实现可靠传输。当 WLAN 中接收站正确收到数据帧时，它等待一个短帧间间隔 SIFS ，然后发回一个 ACK 帧。如果发送站没有收到 ACK 帧，就认为发送失败，应重传该数据帧。

802.11 的停止 - 等待协议是在直接发送站和直接接收站之间实现的（它们的发送是面向特定目标的，即从 A 到 B 或 B 到 A ）。

6）处理隐蔽站问题：RTS和CTS（信道预约机制）

在下图左图中，无线站 A 和站 B 都在 AP（Access Point, 无线接入点）的覆盖范围内，但站 A 和站 B 相距较远，并不在对方的无线电信号传播范围内，因此无法通过载波监听的方法发现对方正在发送数据。当站 A 和站 B 检测到信道空闲时，都向 AP 发送数据，就会导致冲突发生，这就是隐蔽站（hidden station）问题。

CSMA/CA协议进行信道预约：

为了避免隐蔽站带来冲突的可能，802.11 标准允许发送站采用 RST（Request To Send）帧和 CTS（Clear To Send）帧对信道进行预约，如上图右图所示。

① 源站要发送数据帧之前，先监听信道，若信道空闲，则等待时间 DIFS 后，向接收站 AP 发送一个很短的请求发送 RTS 控制帧，它包括源地址、目的地址和这次通信所需的持续时间（用持续时间字段指示传输数据帧和确认帧需要的总时间）。

② 若接收站 AP 正确收到 RTS 帧，且信道空闲，则等待时间 SIFS 后，向源站发送一个允许发送 CTS 控制帧作为响应，它也包括这次通信所需的持续时间。

CTS 帧有两个目的：
I、给源站明确的发送许可；
II、指示其他站在预约期内（即持续时间内）不要发送数据。

③ 在此过程中，AP 覆盖范围内的其他站点会监听到 RTS 和 CTS 的信号。如果它们接收到 CTS 信号，说明源站正在准备发送数据，因此它们将在 CTS 帧中指明的时间内抑制发送数据，以避免产生冲突。

④ 源站收到接收站 AP 发送的 CTS 帧后，再等待时间 SIFS，就可发送数据帧。

⑤ 若 AP 正确收到了源站发来的数据，则等待时间 SIFS 后，就向源站发送确认帧 ACK ，表明数据已经成功发送。

⑥ 如果源站在发送过程中未收到 ACK，就说明可能出现了冲突或数据丢失，此时源站会根据可能的重传策略（如采用指数退避算法）选择等待一段随机时间后重新进行上述的过程。

RST 帧、CTS 帧和确认帧 ACK 的发送是面向特定目标的，那么其他站点是如何知道信道是否已被预约的？
答：严格来说，RST 帧、CTS 帧和确认帧 ACK 都是点对点的请求和应答，但由于无线通信的特性，它们在同一信道上的其他设备能够“监听”到这些帧，以得知无线信道的状态，从而具备了广播的效果。这种机制可以确保其他站点在数据传输期间避免与源站和目标站的通信发生冲突，从而提高了网络的效率和数据传输的可靠性。
如果其他站点监听到 ACK，这并不代表任何特别的操作，因为 ACK 只是对特定数据帧的确认，只有源站需要关注 ACK 的接收。

下图为含信道预约的 CSMA/CA 协议流程图：

NAV 值的概念：

需要说明的是，源站在 RTS 帧中填写的所需占用信道的持续时间，是从 RTS 帧发送完毕后，到目的站最后发送完 ACK 帧为止的时间，即 “SIFS + CTS + SIFS + 数据帧 + SIFS + ACK” ；而 AP 在 CTS 帧中填写的所需占用信道的持续时间，是从 CTS 帧发送完毕，到目的站最后发送完 ACK 帧为止的时间，即 “SIFS + 数据帧 + SIFS + ACK”。如下图所示：

虽然站 B 检测不到站 A 发送给 AP 的 RTS 帧，但却能检测到 AP 发送给站 A 的 CTS 帧，站 B 根据 CTS 帧中的持续时间设置自己的网络分配向量（NAV），NAV 指出了信道忙的持续时间，意味着站 A 和 AP 以外的站点都不能在这段时间内发送数据。

使用 RTS 帧和 CTS 帧会使网络的通信效率有所下降，但这两种帧都很短，与数据帧相比开销不算大。相反，若不使用这种控制帧，则一旦发生冲突而导致数据帧重发，浪费的时间会更多。信道预约不是强制性规定，一般情况下，802.11 协议的实现会提供一个称为 RTS 阈值的配置选项，各站可自行决定使用或不使用。只有当数据帧长超过某个数值时，使用 RTS 帧和 CTS 帧才比较划算。

5. CSMA/CD与CSMA/CA的区别

CSMA/CD 与 CSMA/CA 主要有如下区别:

① CSMA/CD 可以检测冲突，但无法避免；CSMA/CA 发送数据的同时不能检测信道上有无冲突，本结点处没有冲突并不意味着在接收结点处就没有冲突，只能尽量避免。

② 传输介质不同。CSMA/CD 用于总线形以太网；CSMA/CA 用于无线局域网 802.11a/b/g/n 等。

③ 检测方式不同。CSMA/CD 通过电缆中的电压变化来检测；而 CSMA/CA 采用能量检测、载波检测和能量载波混合检测三种检测信道空闲的方式。

总结：CSMA/CA 在发送数据帧之前先广播告知其他站点，让其他站点在某段时间内不要发送数据帧，以免发生冲突。CSMA/CD 在发送数据帧之前监听，边发送边监听，一旦发生冲突，就立即停止发送。

三、例题

① 在某 CSMA/CD 局域网中，使用一个 Hub 连接所有站点，且限定站点到 Hub 的最长距离为 100m，信号的传播速率为 200000km/s，则站点的最长冲突检测时间是（ A ）。
A. 2 μs
B. 2 ms
C. 1 μs
D. 1 ms
【限定站点到 Hub 的最长距离为 100m，则两个站点之间的最长距离为 200m，最长冲突检测时间等于信号在两个最远站点之间的往返传输时间，即 2 × 200m ÷ 200000km/s = 2 μs.】

② 【2009 统考真题】在一个采用 CSMA/CD 协议的网络中，传输介质是一根完整的电缆，传输速率为 1Gb/s，电缆中的信号传播速率是 200000km/s 。若最小数据帧长度减少 800 比特，则最远的两个站点之间的距离至少需要（ D ）。
A. 增加 160 m
B. 增加 80 m
C. 减少 160 m
D. 减少 80 m
【令最小数据帧长度为 t，最远的两个站点之间的距离为 L，则有：t / (1 × 10⁹) = (2 × L) / (2 × 10⁸)，推出 t = 10L 。设最小数据帧长度减少 800 比特后，最远的两个站点之间的距离改变了 x 米，则有：(t - 800) / (1 × 10⁹) = 2 × (L + x) / (2 × 10⁸)，推出 t - 800 = 10L + 10x ，又因为 t = 10L ，得到 x = -80 。】

有关最短帧长的题需要抓住两个公式来分析：① 发送帧的时间 ≥ 争用期的时间；② 最短帧长 = 数据传输速率 × 争用期的时间。

③ 【2011 统考真题】下列选项中，对正确接收到的数据帧进行确认的 MAC 协议是（ D ）。
A. CSMA
B. CDMA
C. CSMA/CD
D. CSMA/CA
【ACK 帧是 CSMA/CA 避免冲突的机制之一，只有当发送方收到接收方发回的 ACK 帧时，才确认发出的数据已正确到达目的地。】

④ 【2013 统考真题】下列介质访问控制方法中，可能发生冲突的是（ B ）。
A. CDMA
B. CSMA
C. TDMA
D. FDMA

⑤ 【2014 统考真题】站点 A、B、C 通过 CDMA 共享链路， A、B、C 的码片序列分别是 (1, 1, 1, 1)、（1, -1, 1, -1) 和 (1, 1, -1, -1)。若 C 从链路上收到的序列是 (2, 0, 2, 0, 0, -2, 0, -2, 0,
2, 0, 2) ，则 C 收到 A 发送的数据是（ B ）。
A. 000
B. 101
C. 110
D. 111
【把收到的序列分成每 4 个数字一组，即 (2, 0, 2, 0), (0, -2, 0, -2), (0, 2, 0, 2) ，然后把这三组数据与 A 站的码片序列 (1, 1, 1, 1) 做内积运算，结果分别是 (2, 0, 2, 0) ⋅ (1, 1, 1, 1) / 4 = 1、(0, -2, 0, -2) ⋅ (1, 1, 1, 1) / 4 = -1、(0, 2, 0, 2) ⋅ (1, 1, 1, 1) / 4 = 1。所以 C 接收到的 A 发送的数据是 101 。】

⑥ 【2015 统考真题】下列关于 CSMA/CD 协议的叙述中，错误的是（ B ）。
A. 边发送数据帧，边检测是否发生冲突
B. 适用于无线网络，以实现无线链路共享
c. 需要根据网络跨距和数据传输速率限定最小帧长
D. 当信号传播延迟趋近 0 时，信道利用率趋近 100%
【CSMA/CD 适用于有线网络， CSMA/CA 则广泛应用于无线局域网。】

⑦ 【2016 统考真题】如下图所示，在 Hub 再生比特流的过程中会产生 1.535μs 延时（Switch 和 Hub 均为 100Base-T 设备），信号传播速率为 200m/μs，不考虑以太网帧的前导码，则 H3 和 H4 之间理论上可以相距的最远距离是（ B ）。

A. 200 m
B. 205 m
C. 359 m
D. 512 m
【最短帧的传输时延为：(64 × 8b) / (100 × 10⁶b/s) = 5.12μs，则单程总时延应该为 5.12μs / 2 = 2.56μs 。已知 Hub 产生的转发时延为 1.535μs ，那么单程的传播时延为：2.56μs - 1.535μs = 1.025μs ，则 H3 和 H4 之间理论上可以相距的最远距离为：200m/μs × 1.025μs = 205m 。】

⑧ 【2018 统考真题】IEEE 802.11 无线局域网的 MAC 协议 CSM/CA 进行信道预约的方法是（ D ）。
A. 发送确认帧
B. 采用二进制指数退避
C. 使用多个 MAC 地址
D. 交换 RTS 与 CTS 帧
【一台主机想要发送信息时，先向无线站点发送一个 RTS 帧，说明要传输的数据及相应的时间。无线站点收到 RTS 帧后，会广播一个 CTS 帧作为对此的响应，既给发送端发送许可，又指示其他主机不要在这个时间内发送数据，从而预约信道，避免碰撞。发送确认帧的目的主要是保证信息的可靠传输。】

⑨ 【2019 统考真题】假设一个采用 CSMA/CD 协议的 100Mb/s 局域网，最小帧长是 128B，则在一个冲突域内两个站点之间的单向传播延时最多是（ B ）。
A. 2.56 μs
B. 5.12 μs
C. 10.24 μs
D. 20.48 μs
【最小帧长的传输时延 = (128 × 8b) / (100 × 10⁶b/s) = 10.24μs，则 RTT 最多为 10.24μs，那么两个站点之间的单向传播延时最多为 5.12μs 。】

⑩ 【2020 统考真题】在某个 IEEE 802.11 无线局域网中，主机 H 与 AP 之间发送或接收 CSMA/CA 帧的过程如下图所示。在 H 或 AP 发送帧前等待的帧间间隔时间（IFS）中，最长的是（ A ）。

A. IFS1
B. IFS2
C. IFS3
D. IFS4

(11)【2023 统考真题】已知 10BaseT 以太网的争用时间片为 51.2μs 。若网卡在发送某帧时发生了连续 4 次冲突，则基于二进制指数退避算法确定的再次尝试重发该帧前等待的最长时间是（ C ）。
A. 51.2 μs
B. 204.8 μs
C. 768 μs
D. 819.2 μs
【发生第 4 次冲突时，随机数从整数集合 {0, 1, 2, 3, … , 15} 中选择，所以最长的等待时间为：15 × 51.2μs = 768 μs 。】

四、轮询访问：令牌传递协议（了解即可）

在轮询访问中，用户不能随机地发送信息，而要通过一个集中控制的监控站，以循环方式轮询每个结点，再决定信道的分配。典型的轮询访问控制协议是令牌传递协议。

在令牌传递协议中，一个令牌（Token）沿着环形总线在各站之间依次传递。令牌是一个特殊的控制帧，它本身并不包含信息，仅控制信道的使用，确保同一时刻只有一个站独占信道。当环上的一个站希望发送帧时，必须等待令牌。站点只有取得令牌后才能发送帧，因此令牌环网络不会发生冲突（因为令牌只有一个）。站点发送完一帧后，应释放令牌，以便让其他站使用。因为令牌在网环上是按顺序依次传递的，所以对所有入网计算机而言，访问权是公平的。

令牌环网络中令牌和数据的传递过程如下：

当网络空闲时，环路中只有令牌帧在循环传递。
令牌传递到有数据要发送的站点时，该站点就修改令牌中的一个标志位，并在令牌中附加自己需要传输的数据，将令牌变成一个数据帧，然后将这个数据帧发送出去。
数据帧沿着环路传输，接收到的站点一边转发数据，一边查看帧的目的地址。若目的地址和自己的地址相同，则接收站就复制该数据帧，以便进一步处理。
数据帧沿着环路传输，直到到达该帧的源站点，源站点收到自己发出去的帧后便不再转发。同时，通过检验返回的帧来查看数据传输过程中是否出错，若出错则重传。
源站点传送完数据后，重新产生一个令牌，并传递给下一站点，交出信道控制权。

令牌传递协议非常适合负载很高的广播信道，即多个结点在同一时刻发送数据概率很大的信道。若这样的信道采用随机介质访问控制，则发生冲突的概率很大，而采用令牌传递协议则可以很好地满足各站点间的通信需求。令牌传递协议既不共享时间，又不共享空间；它实际上在随机访问介质访问控制的基础上，限定了有权发送数据的结点只能有一个。

即使是广播信道也可通过介质访问控制机制，使广播信道变为逻辑上的点对点信道，所以说数据链路层研究的是“点到点”之间的通信。

令牌传递协议的一些要点：

① 令牌环网路的拓扑结构为环状，有一个令牌不停地在环中流动，只有获得了令牌的结点才能发送数据，因此不存在冲突。
② 令牌环网络是一种半双工通信方式，同一时刻只能有一个结点发送数据，其它结点只能接收或转发数据。
③ 令牌环网络中的所有结点都连接到同一个信道上，共享整个信道的带宽。
④ 在令牌环网络中，数据从一个结点到另一结点的时间可根据环上经过的结点数、传输速率和数据帧长来计算。
⑤ 令牌环网络使用令牌在各个结点之间传递来分配信道的使用权，每个结点都可在一定的时间内（令牌持有时间）获得发送数据的权限，而并非无限制的持有令牌，在令牌传递过程中，没有数据要发送的结点收到令牌后将立刻传递下去而不能持有。
⑥ 令牌环网在逻辑上采用环状控制结构，因为令牌总沿着逻辑环单向逐站传送，所以结点总可在确定的时间内获得令牌并发送数据。在最坏情况下，即所有结点都要发送数据，一个结点获得令牌的等待时间等于逻辑环上所有其他结点依次获得令牌，并在令牌持有时间内发送数据的时间总和。