计算机网络——数据链路层介质访问控制

---

前言

本文的主要内容是计算机网络中数据链路层的介质访问控制，包括介质访问控制概述、信道划分介质访问控制中的四种多路复用方式、随机访问介质访问控制中的 ALOHA 协议和 CSMA 协议以及轮询访问介质访问控制中的轮询协议和令牌传递协议。

---

一、介质访问控制概述

传输数据时通常使用两种链路，即点对点链路和广播式链路。
点对点链路指的是两个相邻节点通过一个链路相连，没有第三者，其应用包括 PPP 协议，常用于广域网。
广播式链路指的是所有主机共享通信介质，其应用包括早期的总线以太网、无线局域网，常用于局域网。 它的典型拓扑结构有总线型和星型(逻辑总线型)。
介质访问控制的内容是采取一定的措施，使得两对节点之间的通信不会发生互相干扰的情况。 介质访问控制分为静态划分信道和动态分配信道。
静态划分信道就是信道划分介质访问控制，其包括频分多路复用(FDM)、时分多路复用(TDM)、波分多路复用(WDM)、码分多路复用(CDM)。
动态分配信道包括轮询访问介质访问控制和随机访问介质访问控制，其中轮询访问介质访问控制包括令牌传递协议；随机访问介质访问控制包括ALOHA 协议、CSMA 协议、CSMA/CD 协议以及 CSMA/CA 协议。
介质访问控制的划分图如下图所示。

---

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

信道划分介质访问控制是指将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备。
多路复用技术是把多个信号组合在一条物理信道上进行传输，使得多个计算机或终端设备共享信道资源，提高信道利用率。
多路复用技术其实就是把一条广播信道，逻辑上分成几条用于两个节点之间通信的互不干扰的子信道，实际就是把广播信道转变为点对点信道。其简单的示意图如下图所示。

信道划分介质访问控制包括频分多路复用(FDM)、时分多路复用(TDM)、波分多路复用(WDM)以及码分多路复用(CDM)。

1、频分多路复用(FDM)

频分多路复用(FDM，Frequency Division Multiplexing)技术是指用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带，频分复用的所有用户在同样的时间占用不同的频率带宽资源。 频分多路复用的简单示意图如下图所示。

频分多路复用技术的优点：能够充分利用传输介质带宽，系统效率较高；由于技术比较成熟，实现也比较容易。

2、时分多路复用(TDM)

时分多路复用(TDM，Time Division Multiplexing)技术是将时间划分为一段段等长的时分复用帧(TDM 帧)，其中每一个时分复用的用户在每一个 TDM 帧中占用固定序号的时隙，所有用户轮流占用信道。时分多路复用的简单示意图如下图所示。

频分复用相当于“并行”，时分复用相当于“并发”。
这种情况下对于信道的利用率不是很高，因为每个用户只有在属于自己的“时间片”内才能发送数据，但实际情况下有的用户需要多发，有的用户需要少发，因此就有了在时分复用基础上改进的方法——统计时分复用(STDM，Statistic Time Division Multiplexing)。
统计时分复用的简单示意图如下图所示。

每一个 STDM 帧中的时隙数小于连接在集中器上的用户数，各用户有了数据就随时发往集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的输入数据放入STDM 帧中，一个 STDM 帧满了就发出。STDM 帧不是固定分配时隙，而是按需动态分配时隙。

3、波分多路复用(WDM)

波分多路复用(WDM，Wavelength Division Multiplexing)就是光的频分多路复用，在一根光纤中传输多种不同波长(频率)的光信号，由于波长不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来。波分多路复用的简单示意图如下图所示。

波分多路复用和频分多路复用很相似，因为归根结底还是频率的不同。

4、码分多路复用(CDM)

码分多址(CDMA，Code Division Multiple Access)是码分复用的一种方式。
1个比特分为多个码片/芯片，每一个站点被指定一个唯一的 m 位的芯片序列。发送 1 时站点发送芯片序列，发送0时发送芯片序列反码(通常把 0 写成 -1)。
比如 1 的序列为 (+1，-1，+1，-1，+1，-1，+1，-1)，则 0 的序列为 (-1，+1，-1，+1，-1，+1，-1，+1)。
发送数据时如何做到互不影响：多个站点同时发送数据的时侯，要求各个站点芯片序列相互正交。
比如序列 (+1，-1，+1，-1，+1，-1，+1，-1) 和 (+1，+1，+1，+1，+1，+1，+1，+1)就是正交的。
如何合并：各路数据在信道中被线性相加(对应位直接相加形成一个新的序列)。
比如要发送的序列分别是(+1，-1，+1，-1，+1，-1，+1，-1) 和 (+1，+1，+1，+1，+1，+1，+1，+1)，则合并后的序列就是 (+2，0，+2，0，+2，0，+2，0)。
如何分离：合并的数据和源站规格化内积(合并后新的序列分别和多路原序列做规格化内积，也就是最终的内积结果除以原序列模长)。
序列 (+1，-1，+1，-1，+1，-1，+1，-1) 和合并后的序列 (+2，0，+2，0，+2，0，+2，0) 做规格化内积后的结果是：$\frac{2\times 1+2\times 1+2\times 1+2\times 1}{8}$ = 1 ，即发送 1 比特。
序列 (+1，+1，+1，+1，+1，+1，+1，+1) 和合并后的序列 (+2，0，+2，0，+2，0，+2，0) 做规格化内积后的结果是：$\frac{2\times 1+2\times 1+2\times 1+2\times 1}{8}$ = 1 ，即发送 1 比特。
信道划分介质访问控制基于多路复用技术划分资源，在网络负载重时共享信道的效率高且公平，在网络负载轻时共享信道的效率低。

---

三、随机访问介质访问控制

介质访问控制中的动态分配信道特点是：信道并非在用户通信时固定分配给用户。随机访问介质访问控制指的是所有用户可随机发送信息，且发送信息时占全部带宽。

1、ALOHA 协议

ALOHA 协议分为纯 ALOHA 协议和时隙 ALOHA 协议。

⑴纯 ALOHA 协议

纯 ALOHA 协议的思想是不监听信道，不按照时间槽发送，且随机重发。
纯 ALOHA 协议发送数据的示意图如下图所示。

冲突的检测：如果发生冲突，接收方在就会检测出差错，然后不予确认，发送方在一定时间内收不到就判断发生冲突。
冲突的解决：超时后等待随机时间后再重传。

⑵时隙 ALOHA 协议

时隙 ALOHA 协议的思想是把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等到下一个时间片开始时刻再发送。
时隙 ALOHA 协议发送数据的示意图如下图所示。

时隙 ALOHA 协议下控制了纯 ALOHA 协议想发就发的随机性，它只有在时间片开始的时候才能传数据，发生冲突也只能从时间片一开始就发生冲突。
纯 ALOHA 协议比时隙 ALOHA 协议的吞吐量更低，效率也更低。

2、CSMA 协议

CSMA(Carrier Sense Multiple Access) 协议全称是载波监听多路访问协议。
CS 指的是载波侦听/监听，每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据。当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大。当一个站检测到的信号电压摆动值超过一定门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞，即发生了冲突。
MA 指的是多点接入，表示许多计算机以多点接入的方式连接在一根总线上。
CSMA 协议的思想是在发送帧之前先监听信道。 监听结果分为信道空闲和信道忙，信道空闲就发生完整的帧，信道忙就推迟发送。
后续的处理分为 1-坚持 CSMA、非坚持 CSMA 和 p-坚持CSMA。

⑴1-坚持 CSMA

坚持指的是对于监听到信道忙之后的坚持。
1-坚持 CSMA 的思想：如果一个主机要发送消息，那么它先监听信道，信道空闲则直接传输，不必等待，忙则一直监听，直到信道空闲然后马上传输。 如果有冲突，即一段时间内未收到肯定回复，则等待一个随机长的时间再监听，重复该过程。
1-坚持 CSMA 的优点：只要媒体空闲，站点就可以马上发送，避免了媒体利用率的损失。 1-坚持 CSMA 的缺点：假如有两个或两个以上的站点有数据要发送，冲突就不可避免。

⑵非坚持 CSMA

非坚持指的是对于监听到信道忙之后就不再继续监听。
非坚持 CSMA 的思想：如果一个主机要发送消息，那么它先监听信道，信道空闲则直接传输，不必等待，忙则等待一个随机的时间之后再进行监听。
非坚持 CSMA 的优点：采用随机的重发延迟时间可以减少冲突发生的可能性。
非坚持 CSMA 的缺点：可能存在许多主机都在延迟等待，但这段时间媒体可能处于空闲状态，媒体的使用率会降低。

⑶p-坚持CSMA

不同于上面两种方式，p-坚持指的是对于监听信道空闲的处理。
p-坚持 CSMA 的思想：如果一个主机要发送消息，那么它先监听信道，空闲则以 p 概率直接传输，不必等待，以概率 1-p 等待到下一个时间槽再传输，信道忙则等待一个随机的时间之后再进行监听。
p-坚持 CSMA 的优点：既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间的这种方案。
但是 p-坚持 CSMA 在发生冲突后还是要坚持把数据帧发送完，这样就会造成浪费。
简单总结一下这三种方式，如下表所示。

3、CSMA-CD 协议

CSMA-CD(Carrier Sense Multiple Access with Collision Detection) 协议全称是载波监听多点接入-碰撞检测协议，该协议用于以太网(有线网)。
CS 指的是载波侦听/监听，每一个站点在发送数据之前和发送数据时都要检测一下总线上是否有其他计算机在发送数据。
MA 指的是多点接入，表示许多计算机以多点接入的方式连接在一根总线上，它是总线型网络。
CD 指的是碰撞检测或者冲突检测，它会边发送边监听，适配器/主机边发送数据边检测信道上信号电压的变化情况，以便判断自己在发送数据时其他站点是否也在发送数据。
传播时延对于载波监听也是有影响的，因为在主机 A 向主机 B 发送数据时，信道中会有一定的传播延迟，这样在数据到达主机 B 之前，如果主机 B 也向主机 A 发送数据的话，那么就会产生冲突。
发送端最少需要两倍的单程端到端传播时延 τ 才能知道有没有发生碰撞，示意图如下图所示。

发生碰撞后的重传时机选择采用截断二进制指数规避算法。
截断二进制指数规避算法的流程大致为：
①确定基本退避或者推迟时间为争用期 2τ。
②定义参数 k，它等于重传次数，但 k 不超过10，即 k = min[重传次数，10]，当重传次数不超过 10 时，k 等于重传次数，当重传次数大于10时，k 就不再增大而一直等于10。
③从离散的整数集合{0，1，$2^k-1$}中随机取出一个数 r，重传所需要退避的时间就是 r 倍的基本退避时间，即 2rτ。
④当重传达 16 次仍不能成功时，说明网络太拥挤，认为此帧永远无法正确发出，抛弃此帧并向高层报告出错。
第一次重传，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}选，……
若连续多次发生冲突，就表明可能有较多的站点参与争用信道，使用此算法可使重传需要推迟的平均时间随重传次数的增大而增大，因而减小发生碰撞的概率，有利于整个系统的稳定。
例题：在以太网的二进制回退算法中，在 11 次碰撞之后，站点会在0至多少之间选择一个随机数？
解答：由于重传次数超过了10次，因此 k = 10，取值应在 0 至 $2^{10}-1$之间选择一个随机数，$2^{10}-1$ = 1023。
还有一个问题就是如果帧长太小，那么就会在帧发送完毕之后才会检测到发生了碰撞，这种情况时不能发生的，因此就有了最小帧长的概念。
帧的传输时延至少要两倍于信号在总线中的传播时延，即$\frac{帧长}{数据传输速率}$ ≥ 2τ。
最小帧长 = 2 × 总线传播时延 × 数据传输速率 = 2τ × 数据传输速率
以太网规定的最短帧长为 64 B，凡是长度小于 64 B的都是由于冲突而异常终止的无效帧。

4、CSMA-CA 协议

CSMA-CA(Carrier Sense Multiple Access with Collision Avoidance) 协议全称是载波监听多点接入-碰撞避免协议，该协议用于无线局域网。
CSMA-CA 协议的引入是因为 CSMA-CD 协议无法像检测以太网那样检测无线局域网的碰撞；另一方面是隐蔽展的存在，即当 A，C 都检测不到信号认为信道空闲时，同时给终端 B 发送数据帧，就会导致冲突。
CSMA-CA 协议的工作原理：
①发送数据前先检测信道是否空闲，空闲则发出请求发送信号 (RTS，Request to Send)，RTS 包括发射端的地址、接收端的地址、下一份数据将持续发送的时间等信息，信道忙则等待。
②接收端收到 RTS 后，将响应允许发送信号(CTS，Clear to Send)，CTS 就可以解决隐蔽站的问题。
③发送端收到 CTS 后，开始发送数据帧，同时预约信道，也就是发送方“告知”其他站点自己要传多久数据。
④接收端收到数据帧后，将用循环冗余校验(CRC，Cyclic Redundancy Check)来检验数据是否正确，正确则响应 ACK 帧，发送方收到 ACK 就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止，如果重传则采用二进制指数退避算法来确定随机的推迟时间。
CSMA/CD 与 CSMA/CA 的相同点：CSMA/CD 与 CSMA/CA 机制都从属于 CSMA 的思路，即在接入信道之前都需要先进行监听，当发现信道空闲后，才能进行接入。
CSMA/CD 与 CSMA/CA 的不同点：
①传输介质不同。CSMA/CD 用于总线式以太网(有线)，而 CSMA/CA 用于无线局域网(无线)。
②载波检测方式不同。因传输介质不同，CSMA/CD 与 CSMA/CA 的检测方式也不同。CSMA/CD 通过电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化；CSMA/CA 采用能量检测、 载波检测和能量载波混合检测这三种检测信道空闲的方式。
③CSMA/CD 检测冲突，CSMA/CA 避免冲突，二者出现冲突后都会进行有上限的重传。
随机访问介质访问控制中，用户可以根据意愿随机发送信息，发送信息时可独占信道带宽。在网络负载重时会产生冲突开销，在网络负载轻时共享信道的效率高，单个结点可利用信道的全部带宽。

---

四、轮询访问介质访问控制

前面已经提到，信道划分介质访问控制基于多路复用技术划分资源，在网络负载重时共享信道的效率高且公平，在网络负载轻时共享信道的效率低。随机访问介质访问控制中，用户可以根据意愿随机发送信息，发送信息时可独占信道带宽。在网络负载重时会产生冲突开销，在网络负载轻时共享信道的效率高，单个结点可利用信道的全部带宽。
轮询访问介质访问控制就结合了信道划分介质访问控制和随机访问介质访问控制的优点，也就是既不产生冲突，又要发送时占全部的带宽。

1、轮询协议

轮询协议指的是主结点/主机循环且轮流邀请各从属结点发送数据。其简单的示意图如下图所示。

轮询协议存在的问题主要有：轮询产生的开销；各从属结点的等待延迟；主结点/主机的单点故障。

2、令牌传递协议

令牌是一个特殊格式的介质访问控制(MAC，Media Access Control)控制帧，它不含任何信息。采用令牌传送方式的网络常用于负载较重、通信量较大的网络中。
令牌传递协议应用于令牌环网，令牌环网在物理上是星型拓扑结构，在逻辑上是环型拓扑结构。
令牌环网内无碰撞，即控制信道的使用，确保同一时刻只有一个结点独占信道。
某个主机得到令牌后并不是无限制地持有令牌，它只能在一定的时间内(令牌持有时间，类似于时间片)获得发送数据的权利，到时后该主机的数据还没发送完就要让出令牌，令牌再次轮询各主机，等到下次该主机得到令牌后再接着上次的数据传输。
令牌传递协议的示意图如下图所示。

主机得到令牌之后先修改令牌标志位(由空闲状态改为忙状态)，接着在令牌的控制帧后附上要发送的数据帧，然后将令牌和数据帧发送出去，令牌会按照轮询的方向挨个主机轮询下去，直到找到数据要发送的主机后，接收数据的主机会复制一份令牌上携带的数据帧，然后令牌轮询回到发送方主机。如果数据帧没有出错，主机就回收该数据帧，接着发送其他的数据帧(在令牌持有时间内)；如果发送的数据帧出错，就需要重传该数据帧。令牌的持有时间到了之后，就要修改令牌标志位(由忙状态改为空闲状态)，当前主机让出令牌让其为下个主机服务。
令牌传递协议存在的问题主要有：令牌开销；等待延迟；单点故障。

---

总结

以上就是计算机网络——数据链路层介质访问控制的所有内容了，本文的重点内容是信道划分介质访问控制中的四种多路复用方式、随机访问介质访问控制中的 ALOHA 协议和 CSMA 协议以及轮询访问介质访问控制中的令牌传递协议，重点理解并掌握这些介质访问控制协议。
参考视频：
信道划分介质访问控制
ALOHA 协议
CSMA 协议
CSMA-CD 协议
CSMA-CA 协议
轮询访问介质访问控制