3. 介质访问控制

传输数据使用的两种链路：

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

总线型 & 星型

总线型缺点：如果某一处出现故障，所有主机都不能通信
星型刚好避免了总线型的缺点

数据链路层要解决的问题：如果 A 主机和 B 主机通信，A 发送信息，同时 B 也发送信息，在传输过程中会造成干扰。想一个办法（介质访问控制）使两个节点在通信时不会相互干扰。

1. 介质访问控制

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

2. 信道划分介质访问控制

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

多路复用技术：把多个信号组合在一条物理信道上进行传输，使得多个计算机或终端设备共享信道资源，提高信道利用率。

把一条广播信道，逻辑上分为几条用于两个节点之间通信的互不干扰的子信道，实际就是把广播信道转变为点对点信道。

2.1 频分多路复用 FDM

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

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

2.2 时分多路复用 TDM

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

频分复用：并行；时分复用：并发

缺点：如果 A、B、C 全部没有工作，为休息状态，那么对于 D 来说，只能发送一段时间，需要等待三个时间段才能再次发送数据，这样信道利用率就会极低。

2.3 统计时分复用 STDM

改进时分多路复用的缺点，信道利用率低的情况。

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

2.4 波分多路复用 WDM

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

2.5 码分多路复用 CDM

码分多址（CDMA）是码分复用的一种方式。

1 个比特分为多个码片/芯片（chip），每一个站点被指定一个唯一的 m 位芯片序列；发送 1 时发送芯片序列（通常把 0 写成 -1），发送 0 时发送芯片序列反码。

分离数据的方法：

多个站点同时发送数据的时候，要求各个站点芯片序列互相正交，规格化内积为0
两个向量到了公共信道上，线性相加
数据分离：合并的数据和源站点规格化内积

3. 动态分配信道

静态划分信道：在用户通信前，就规定好了信道的使用规则，已经固定好了信道的分配。

相比于静态划分信道，动态分配信道并非用户通信时固定分配给用户的。

4. ALOHA 协议

分类：

纯 ALOHA 协议
时隙 ALOHA 协议

4.1 纯 ALOHA 协议

思想：不监听信道，不按时间槽发送，随机重发。想发就发

冲突如何检测？

如果发送冲突，接收方会检测出差错，然后不予确认，发送方在一定时间内收不到就判断发生冲突

冲突如何解决？

超时后等待一随机时间再重传

4.2 时隙 ALOHA 协议

思想：把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等到下一个时间片开始时刻再发送。（控制想发就发的随意性）

两者比较：

纯 ALOHA 比时隙 ALOHA 吞吐量更低，效率更低
纯 ALOHA 想发就发，时隙 ALOHA 只有在时间片段开始时才能发

5. CSMA 协议

全称：载波监听多路访问协议 CSMA（Carrier Sense Multiple Access）

CS：载波监听/侦听，每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据。

当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。当一个站监测到的信号电压摆动值超过一定门限值时，就可以认为总线上至少有两个站同时在发送数据，表明产生了碰撞，即发生了冲突。

MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。

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

5.1 1-坚持 CSMA

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

1-坚持 CSMA 思想：

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

优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失

缺点：假如有两个或两个以上的站点有数据要发送，冲突就不可避免

5.2 非坚持 CSMA

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

非坚持 CSMA 思想：

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

优点：采用随机的重发延迟时间可以减少冲突发生的可能性

缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低

5.3 p-坚持 CSMA

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

p-坚持 CSMA 思想：

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

优点：既能像非坚持算法那样减少冲突，又能像 1-坚持算法那样减少媒体空闲时间的这种方案

缺点：发生冲突后还要坚持把数据帧发送完，造成了浪费

5.4 总结对比

举例：

6. CSMA/CD 协议

全称：载波监听多点接入/碰撞检测CSMA/CD（Carrier Sense Multiple Access With Collision Detection）

CS：载波监听/侦听，每一个站在发送数据之前以及发送数据时都要检测一下总线上是否有其他计算机在发送数据。

MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。（总线型网络）

CD：碰撞检测（冲突检测），“边发送边监听”，适配器边发送数据边检测信道上信号电压的变化情况，以便判断自己在发送数据时其他站是否也在发送数据。（半双工网络）

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

可能由于主机之间的距离较远，导致检测不到信道中的有其他计算机在发送数据，其实是有的，只不过还没有传过去而已。

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

截断二进制指数规避算法

确定基本退避（推迟）时间为征用期 $2\tau$
定义参数 k，它等于重传次数，但 k 不超过 10，即 k = min[重传次数，10]。当重传次数不超过 10 时，k 等于重传次数；当重传次数大于 10 时，k 就不再增大而一直等于10
从离散的整数集合 $[0, 1, \cdots , 2^k - 1]$ 中随机取出一个数 r，重传所需要退避的时间就是 r 倍的基本退避时间，即 $2r \tau$
当重传达 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} 选；
......

若连续多次发生冲突，就表明可能有较多的站参与争用信道。使用此算法可使重传需要推迟的平均时间随重传次数的增大而增大，因而减小发生碰撞的概率，有利于整个系统的稳定。

6.3 最小帧问题

情况：A 站发送了一个很短的帧，但发生了碰撞，不过帧在发送完毕后才检测到发生碰撞，没法停止发送，因为发完了。

帧的传输时延至少要大于等于两倍的信号在总线中的传播时延

最小帧长 = 总线传播时延 x 数据传输速率 x 2 = $2 \tau$ x 数据传输速率

以太网规定最短帧长为 64B，凡是长度小于 64B 的都是由于冲突而异常终止的无效帧

6.4 知识脑图

7. CSMA/CA 协议

全称：载波监听多点接入/碰撞避免 CSMA/CA（Carrier Sense Multiple Access With Collision Avoidance）

为什么要有 CSMA/CA ?

前面的 CSMA/CD 适用于总线型网络
而 CSMA/CA 适用于无线局域网

无线局域网的局限：

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

7.1 CSMA/CA 协议工作原理

发送数据前，先检测信道是否空闲

空闲则发送 RTS（request to send），RTS 包括发射端的地址，接收端的地址，下一份数据将持续发送的时间等信息；信道忙则等待

接收端收到 RTS 后，将响应 CTS（clear to send）

发送端收到 CTS 后，开始发送数据帧（同时预约信道：发送方告知其他站点自己要传多久数据）

接收端收到数据帧后，将用 CRC 来检验数据是否正确，正确则响应 ACK 帧

发送方收到 ACK 就可以进行下一个数据帧的发送，若没有则一直重传至规定重传次数为止（采用二进制指数退避算法来确定随机的推迟时间）

7.2 CSMA/CD & CSMA/CA 比较

相同点：

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

不同点：

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