CSMA/CD的退避算法

先决条件—— CSMA/CD基础知识 , CSMA/CD中的碰撞检测 退避算法是一种 冲突解决 用于随机访问MAC协议（CSMA/CD）的机制。这种算法通常在以太网中用于在冲突后安排重新传输。

如果两个电台之间发生碰撞，它们可能会在碰撞后尽快重新启动传输。这总是会导致另一次碰撞，并形成一个无限循环的碰撞，从而导致死锁。为了防止这种情况，使用了退避算法。

让我们考虑2个站A和B发送一些数据的情景：

碰撞后，时间被划分为离散的时隙( T _狭槽 )其长度等于2t，其中t是网络中的最大传播延迟。

参与碰撞的站从集合K中随机选取一个整数，即{0，1}。这一组被称为竞争窗口。如果源因为选取了相同的整数而再次发生冲突，则争用窗口大小将加倍，并变为{0,1,2,3}。现在，参与第二次碰撞的源从集合{0，1，2，3}中随机选取一个整数，并等待该时间段的数量，然后重试。在他们尝试传输之前，他们会监听该频道，并仅在该频道空闲时进行传输。这会导致在争用窗口中选取最小整数的源成功传输其帧。

所以，退避算法定义了 发生碰撞的车站等待时间 ，即站点应等待多长时间才能重新传输。

Waiting time = back–off time
Let n = collision number or re-transmission serial number. 
Then, 
Waiting time = K * Tslot
where K = [0, 2n – 1 ]  

例如——

案例1： 假设两个站点A和B同时开始传输数据（数据包1），则发生冲突。因此，两个数据（数据包1）的冲突数n=1。现在，两个站从集合K中随机选取一个整数，即{0，1}。

• 当A和B都选择K=0时 –>等待A=0*T的时间 _狭槽 = 0 等待B=0*T的时间 _狭槽 = 0

  因此，两个站将同时传输，因此会发生碰撞。

• 当A选择K=0，B选择K=1时 –>等待A=0*T的时间 _狭槽 = 0 等待B=1*T的时间 _狭槽 =T _狭槽

  因此，A发送分组，B等待时间T _狭槽 用于传输，因此A获胜。

• 当A选择K=1，B选择K=0时 –>等待A=1*T的时间 _狭槽 =T _狭槽 等待B=0*T的时间 _狭槽 = 0

  因此，B发送分组，A等待时间T _狭槽 用于传输，因此B获胜。

• 当A和B都选择K=1时 –>等待A=1*T的时间 _狭槽 =T _狭槽 等待B=1*T的时间 _狭槽 =T _狭槽

  因此，两者都将等待相同的时间T _狭槽 然后传输。因此，会发生碰撞。

Probability that A wins = 1/4
Probability that B wins = 1/4
Probability of collision  = 2/4

案例2： 假设A在案例1中获胜，并传输其数据（数据包1）。现在，只要B发送其数据包1，A就发送其数据包2。因此，会发生碰撞。现在，A的数据包2的冲突号n变为1，B的数据包1的冲突号n变为2。 对于A的数据包2，K={0，1} 对于B的数据包1，K={0，1，2，3}

Probability that A wins = 5/8
Probability that B wins = 1/8
Probability of collision  = 2/8

因此，与情况1相比，碰撞概率降低。

优势——

• 碰撞概率呈指数下降。

缺点——

• 捕获效果： 谁赢了，谁就赢。
• 仅适用于2个电台或主机。

大门练习题-

1. 问题-12490
2. GATE-CS-2016（第2组）|问题34
3. GATE-IT-2004 |问题85