详解数据链路层-介质访问控制【王道计算机网络笔记】

数据传输使用的两种链路

• 点对点链路：两个相邻结点通过一个链路相连，没有第三者。 应用：PPP协议，常用于广域网。例如打电话
• 广播式链路：所有主机共享通信介质。 应用：早期总线以太网、无线局域网，常用于局域网。例如同一个频道的对讲机 典型拓扑结构：总线型、星型（逻辑总线型）

类似广播式链路的对讲机，很容易出现对话冲突的情况，也就是两个人想同时说话，但是对讲机只能让一个人说完，另一个人才能再说

介质访问控制的内容就是采取一定的措施，使得两对节点之间的通信不会发生相互干扰的情况

静态划分信道-信道划分介质访问控制

信道划分介质访问控制：将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备

多路复用技术：把多个信号组合在一条物理信道上进行传输，使得多个计算机或终端设备共享信道资源，提高信道利用率 这里的共享信道就可以看做广播信道。把一条广播信道逻辑上分成几条用于两个节点之间通信的互不干扰的子信道，实际就是把广播信道转变为点对点信道

频分多路复用FDM

用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。频分复用的所有用户在同样的时间占用不同的带宽（频率带宽）资源

充分利用传输介质带宽，系统效率较高；由于技术比较成熟，实现也比较容易

时分多路复用TDM

将时间划分为一段段等长的时分复用帧（TDM帧）。每一个时分复用的用户在每一个TDM帧中占用固定序号的时隙，所有用户轮流占用信道

TDM帧是在物理层传送比特流所划分的帧，标志一个周期

频分复用类似于并行 时分复用类似于并发

改进的时分复用——统计时分复用STDM

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

波分多路复用WDM

波分多路复用就是光的频分多路复用，在一根光纤中传输多种不同波长（频率）的光信号，由于波长（频率）不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来

码分多路复用CDM

码分多址（CDMA）是码分复用的一种方式。1个比特分为多个码片/芯片（chip），每一个站点被指定一个唯一的m位芯片序列，发送1时发送芯片序列（通常把0写作-1）

我们指定A的芯片序列为00011011，用向量S表示这个芯片序列；B的芯片序列为00101110，用向量T表示这个芯片序列

1. 多个站点同时发送数据的时候，要求各个站点芯片序列相互正交，规格化内积为0。、 例如此处 $$S \cdot T=\frac{1}{m}\sum\limits_{i=1}^{m}S_{i}T_{i}=0$$ 比特1就发送芯片序列，比特0就发送芯片序列的反码
2. 两个向量到了公共信道上，线性相加。 例如这里A发1，B发0，则有 $$S-T=\begin{pmatrix}0 & 0 & -2 & 2 & 0 & -2 & 0 & 2\end{pmatrix}$$
3. 数据分离：合并的数据和源站规格化内积 例如收到A的，若要看发送的是什么需要 $$S \cdot (S-T)=S^{2}-S \cdot T = 1-0=1$$ 类似地B $$T \cdot (S-T)=T \cdot S - T^{2}=0-1=-1$$ 因此A站点发送的数据为1，B站点发送的数据为0

动态划分信道-随机访问介质访问协议

这里动态媒体介入控制/多点接入的特点：信道并非在用户通信时固定分配给用户

随机访问介质访问信息也就是所有用户可随机发送信息，发送信息时占全部带宽

ALOHA协议

纯ALOHA协议

纯ALOHA协议思想：不监听信道，不按时间槽发送，随机重发，想发就发

$T_{0}$指的是发送时间，即传输时间+传播时间 如果发生冲突，接收方就会检测出差错，然后不予确认，发送方在一定时间内收不到就判断发生冲突 解决冲突方法：超时后等一随机时间再重传

时隙ALOHA协议

时隙ALOHA协议的思想：把时间分成若干个相同的时间片（槽），所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等到下一个时间片开始时刻再发送 两个站的时隙ALOHA协议的工作原理示意图。时隙的长度$T_{0}$，使得每个帧正好在一个时隙内发送完毕。每个帧在到达后，一般都要在缓存中等待一段小于$T_{0}$的时间，然后才能发送出去。在一个时隙内有两个或两个以上的帧到达时，在下一个时隙将产生碰撞。碰撞后重传的策略与纯ALOHA的情况是相似的。

碰撞后重传的策略与纯ALOHA的情况是相似的，但依旧遵守在时隙开始时才能重传

关于ALOHA要知道的事

• 纯ALOHA比时隙ALOHA吞吐量更低，效率更低 吞吐量指的是单位时间内发送的帧数
• 纯ALOHA想法就发，时隙ALOHA只有在时间片段开始时才能法

载波监听多路访问CSMA协议

CS：载波侦听/监听，每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据 当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（相互叠加）。当一个站检测到的信号电压摆动值超过一定门限值时，就认为总线上至少有两个站同时在发送数据，表名产生了碰撞，即发生了冲突 MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上（逻辑上是一个总线型的）

协议思想：发送帧之前，监听信道 监听结果

• 信道空闲：发送完整帧
• 信道忙：推迟发送

1-坚持CSMA

坚持指的是对于监听信道忙之后的坚持

1-坚持CSMA思想：

• 如果一个主机要发送消息，那么它先监听信道，空闲则直接传输，不必等待
• 忙则一直监听，知道空闲马上传输
• 如果有冲突（一段时间内未收到肯定恢复），则等待一个随机长的时间再监听，重复上述过程

优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失 缺点：假如有两个或两个的站点有数据要发送，冲突就不可避免

非坚持CSMA

非坚持指的是对于监听信道忙之后就不继续监听

非坚持CSMA思想：

• 如果一个主机要发送消息，那么它先监听信道，空闲则直接传输，不必等待
• 忙则等待一个随机的时间之后再进行监听

优点：采用随机的重发延迟时间可以减少冲突发生的可能性 缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低

p-坚持CSMA

p-坚持指的是对于监听信道空闲的处理

p-坚持CSMA思想：

• 如果一个主机要发送消息，那么它先监听信道
• 空闲则以p概率直接传输，不必等待；1-p的概率等待到下一个时间槽再传输
• 忙则持续监听直到信道空闲再以p概率发送
• 若冲突则等到下一个时间槽开始再监听并重复上述过程

优点：既能想非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间的这种方案 缺点：发生冲突后还是要坚持把数据帧发送完，造成了浪费

载波监听多点接入/碰撞检测CSMA/CD协议

CS：载波侦听/监听，每一个站在发送数据之前以及发送数据时都要检测一下总线上是否有其他计算机在发送数据 MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上（逻辑上是一个总线型的） CD：碰撞检测（冲突检测），“边发送边监听”，适配器边发送数据边检测信道上信号电压的情况，以便判断自己在发送数据时其他站是否也在发送数据（用于半双工网络）

传播时延对载波监听的影响

由于传播时延的存在，导致A已经在信道上发送数据，但是还没有到B，就导致了B认为信道是空闲的

最迟两倍的总线端到端的传播时延$2 \tau$才能知道自己发送的数据没和别人发送的数据碰撞，这个时间也叫总线的端到端往返传播时延、征用期、冲突窗口、碰撞窗口 因此只要经过$2\tau$时间还没有检测到碰撞，就能肯定这次发送不发生碰撞

如何确定碰撞后的重传时机

截断二进制指数规避算法

1. 确定基本退避（推迟）时间为征用期$2\tau$
2. 定义参数k，它等于重传次数，但k不超过10，即$k=\min [重传次数,10]$。k等于重传次数；当重传次数大于10时，k就不再增大而一直等于10
3. 从离散的整数集合$[0,1,\cdots ,2^{k}-1]$中随机取出一个数r，重传所需要退避的时间就是r倍的基本退避时间，即$2r \tau$
4. 但重传达16次仍不能成功时，说明网络太拥挤，认为此帧永远无法正确发出，抛弃此帧并向高层报告出错

例如：

• 第一次重传，k=1，r从{0,1}选： 重传推迟时间为0或$2\tau$,在这两个时间中随机选一个；
• 若再次碰撞，则在第二次重传时，k=2，r从{0,1,2,3}选： 重传推迟时间为0或2$\tau$或4$\tau$或6$\tau$，在这四个时间中随机选一个：
• 若再次碰撞，则第三次重传时，k=3，r从{0,1,2,3,4,5,6,7}选……

最小帧长

帧的传播时延至少要两倍于信号在总线中的传播时延 $$ \begin{aligned} \frac{帧长}{数据传输速率}&\geq 2 \times 总线传播时延\最小帧长&=总线传播时延 \times 数据传输速率 \times 2=2 \tau \times 数据传输速率\end{aligned} $$ 以太网规定最短帧长为64B，凡是长度小于64B的都是由于冲突而异常终止的无效帧

载波监听多点接入/碰撞避免CSMA/CA协议

CSMA/CD协议常用于有线局域网环境 CSMA/CA协议常用于无线局域网环境

• 前者无法做到306°全面检测碰撞
• 存在隐蔽站问题。当A和C都检测不到信号，认为信道空闲时，同时向终端B发送数据帧，就会导致冲突

CSMA/CA协议工作原理

• 发送数据前，先检测信道是否空闲
• 空闲则发出RTS（request to send），RTS包括发送端的地址、接收端的地址、下一份数据将持续发送的时间等信息；信道忙则等待
• 接收端收到RTS后，将响应CTS（clear to send）
• 发送端收到CTS后，开始发送数据帧，同时预约信道，发送方告知其他站点自己要传多久数据
• 接收端收到数据帧后，将用CRC来检验数据是否正确。正确则响应ACK帧
• 发送方收到ACK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止（采用二进制指数退避算法来确定随机推迟时间）

其中RTS、CTS帧可以没有

CSMA/CD与CSMA/CA

相同点： CSMA/CD与CSMA/CA机制都从属于CSMA的思路，其核心是先听再说。换言之，两个在接入信道之前都须要进行监听。当发现信道空闲后，才能进行接入。

不同点：

• 传输介质不同：CSMA/CD用于总线式以太网【有线】，而CSMA/CA用于无线局域网【无线】。
• 载波检测方式不同：因传输介质不同，CSMA/CD与CSMA/CA的检测方式也不同。CSMA/CD通过电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化；而CSMA/CA采用能量检测(ED)、载波检测(CS)和能量载波混合检测三种检测信道空闲的方式。
• CSMA/CD检测冲突，CSMA/CA避免冲突，二者出现冲突后都会进行有上限的重传。

动态划分信道-轮询访问介质访问控制

轮询协议

主节点轮流邀请从属结点发送数据

问题：

• 轮询开销
• 等待延迟，尤其是靠后的主机，例如123都不发送数据，4发送，但按顺序要等很久
• 单点故障，若接收端故障则发送端不会收到邀请

令牌传递协议

在令牌传递协议中，一个令牌在各结点间以某个固定次序交换。令牌是由一组特殊的比特组合而成的帧。当环上的一个站希望传送帧时，必须等待令牌。一旦收到令牌，站点便可启动令牌上的发送帧。帧中包括目的站的地址，以标识哪个站应接收此帧。帧在环上传送时，不管该帧是否是发给本站点的，所有站点都进行转发，直到该帧回到它的始发站，并由该始发站撤销该帧。帧的目的站除转发帧外，应针对该帧维持一个副本，并通过在帧的尾部设置“响应比特”来指示已收到此副本。站点在发送完一帧后，应释放令牌，以便让其他站使用。 当计算机都不需要发送数据时，令牌就在环形网上游荡，而需要发送数据的计算机只有在拿到该令牌后才能发送数据帧，因此不会发送冲突（因为令牌只有一个）。

每个结点都可以在一定的时间内（令牌持有时间）获得发送数据的权利，并不是无限制的持有令牌

问题：

1. 令牌开销
2. 等待延迟
3. 单点故障，导致断路

通常应用于令牌环网（物理星型拓扑，逻辑环型拓扑）

采用令牌传送方式的网络常用于负载较重、通信量较大的网络中