37.2° Blog

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

在总线形网络中，当有两个或多个用户同时发送信息时，就会产生帧的冲突（碰撞，即前面所说的相互干扰），导致所有冲突用户的发送均以失败告终。

为了解决随机接入发生的碰撞，每个用户需要按照一定的规则反复地重传它的帧，直到该帧无碰撞地通过。这些规则就是随机访问介质访问控制协议，常用的协议有ALOHA 协议、 CSMA 协议、 CSM/CD 协议和 CSM/CA 协议等，它们的核心思想都是：胜利者通过争用获得信道，从而获得信息的发送权。因此，随机访问介质访问控制协议又称争用型协议。

如果介质访问控制采用信道划分机制，那么结点之间的通信要么共享空间，要么共享时间，要么两者都共享：而如果采用随机访问控制机制，那么各结点之间的通信就可既不共享时间，也不共享空间。所以随机介质访问控制实质上是一种将广播信道转化为点到点信道的行为。

1.ALOHA协议

ALOHA协议是由美国夏威夷大学开发的一种网络协议。处于OSI模型中的数据链路层。它属于随机存取协议（Random Access Protocol）中的一种。它分为纯ALOHA协议和分段ALOHA协议（或时隙ALOHA协议）。

1.1 纯ALOHA协议

（1）思想

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

（2）冲突如何检测

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

（3）冲突如何解决

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

1.2 时隙ALOHA协议

（1）思想

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

（2）特点

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

2.CSMA协议

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

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

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

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

2.1 协议思想

发送帧前，监听信道。

监听结果：

• 信道空闲：发送成功
• 信道忙：
  • 1-坚持CSMA
  • 非坚持CSMA
  • p-坚持CSMA

2.2 1-坚持CSMA

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

1-坚持CSMA思想：如果一个主机要发送消息，那么它先监听信道。

• 空闲则直接传输，不必等待。
• 忙则一直监听，直到空闲马上传输。
• 如果有冲突（一段时间内未收到肯定回复），则等待一个随机长的时间再监听，重复上述过程。

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

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

2.3 非坚持CSMA

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

非坚持CSMA思想：如果一个主机要发送消息，那么它先监听信道。

• 空闲则直接传输，不必等待。
• 忙则等待一个随机的时间之后再进行监听。

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

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

2.4 p-坚持CSMA

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

p-坚持CSMA思想：如果一个主机要发送消息，那么它先监听信道。

• 空闲则以p概率直接传输，不必等待；概率1-p等待到下一个时间槽再传输。
• 忙则持续监听直到信道空闲再以p概率发送。
• 若冲突则等到下一个时间槽开始再监听并重复上述过程。

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

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

2.5 总结

3.CSMA/CD协议

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

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

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

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

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

最多是两倍的总线端到端的传播时延（2τ），又称争用期，冲突窗口，碰撞窗口。

只要经过2τ时间还没有检测到碰撞，就能肯定这次发送不会发生碰撞。

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

截断二进制指数规避算法

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

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

3.3 最小帧长的问题

帧的传世时延至少要两倍于信号在总线中传播时延。

$$\frac {帧长(bit)}{数据传输速率} >= 2τ$$

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

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

为了实现CSMA/CD,需要限定帧的长度。在发送帧的最后一位前，发送站点必须检测冲突，如有任何冲突都要放弃传输。这是因为一旦整个帧被被发送了，站点就无法保留帧的副本并无法掌控线路中的冲突检测。因此，帧的传输时间Tfr必须至少是最长传播时间Tp的2倍。

4.CSMA/CA协议

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

4.1 CSMA/CA协议工作原理

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

4.2 CSMA/CD与CSMA/CA

相同点

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

不同点

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