用于CSMA/CD协议的退避算法

先决条件 –CSMA/CD的基本原理, CSMA/CD中的碰撞检测

“后退算法”是一种……碰撞解决这种机制被用于随机访问MAC协议中（即CSMA/CD协议）。 该算法通常用于以太网中，用于在发生冲突后安排数据的重新传输。 如果两个站点之间发生了碰撞，那么这两个站点可以在碰撞发生后尽快重新开始传输数据。 这总会引发又一次碰撞，从而形成一个无休止的循环，最终导致系统陷入死锁状态。 为了避免出现这种情况，会采用回退算法来防止类似的情况发生。 让我们考虑这样一种情况：有两个站点A和B，它们正在传输一些数据。

在发生碰撞之后，时间会被划分为多个独立的时段。T插槽其长度等于 2t，其中 t 表示网络中最大的传播延迟。 参与这次碰撞的站点会从集合K中随机选择一个整数，即{0, 1}中的一个数字。 这个集合被称为“争用窗口”。 如果由于选择了相同的整数而导致资源再次发生冲突，那么争用窗口的大小将会翻倍，变为{0, 1, 2, 3}。 现在，参与第二次碰撞的各方会随机从集合{0, 1, 2, 3}中选择一个整数，然后等待该数量的时隙过后，才会再次尝试。 在尝试传输之前，他们会先监听该频道的情况。只有当频道处于空闲状态时，他们才会进行传输。 这样一来，在争用窗口中选择了最小整数的那个源节点，就能够成功传输其帧了。 因此，Back-off算法定义了一个……与碰撞相关的各个站点之间的等待时间也就是说，该电台需要等待多长时间才能重新进行传输。

等待时间 = 退避时间
设 n 为碰撞次数或重传序列号。
那么，
等待时间 = K * T插槽
其中，K = [0, 2]n– 1 ]

示例 – 案例1：假设有2个站点A和B同时开始传输数据（即数据包1）。此时，会发生碰撞。因此，这两个站点传输的数据（即数据包1）的碰撞次数均为1。现在，这两个站点各自从集合K中随机选择一个整数，即{0, 1}中的一个整数。

• 当A和B都选择K = 0时等待时间A等于0 * T插槽= 0 等待时间B = 0 * T插槽因此，两个站点会同时发送信号，从而导致信号冲突。
• 当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插槽因此，B会发送该数据包，而A则等待时间T。插槽因为进行了传输，所以B获胜。
• 当A和B都选择K = 1时等待时间A等于1 * T。插槽= T插槽B的等待时间等于1 * T。插槽= T插槽因此，两者都会等待相同的时间T。插槽然后，数据会被传输出去。因此，就会发生冲突的情况。

A获胜的概率 = 1/4
B获胜的概率 = 1/4
碰撞的概率 = 2/4

案例2：假设在案例1中，A成功发送了它的数据（数据包1）。现在，当B发送其数据包1之后，A立即发送其数据包2。因此，就会发生冲突。此时，A的数据包2的冲突次数变为1，而B的数据包1的冲突次数则变为2。对于A的数据包2来说，K = {0, 1}；而对于B的数据包1来说，K = {0, 1, 2, 3}。

A获胜的概率 = 5/8
B获胜的概率 = 1/8
碰撞的概率 = 2/8

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

以下是该产品的一些主要特点：

当发生碰撞时，发送设备会等待一段随机的时间，然后再重新发送数据包。这种随机延迟有助于防止多个设备同时重新发送数据包，从而避免再次发生碰撞。

随机延迟时间是通过指数退避算法来确定的。延迟时间从最小值开始，每次发生碰撞后都会翻倍，直到达到最大值。通常，最大延迟时间被设定为1024个时隙时间。这里所说的“时隙时间”指的是信号从网络段的一端传输到另一端所需的时间。

这种回退算法是通过每个设备的网络接口卡上的硬件来实现的。当检测到冲突时，网络接口卡会生成一个介于0到2^n-1之间的随机数，其中n表示已经发生的冲突次数。然后，网络接口卡会将这个随机数乘以一个固定的时间值，从而确定重新传输之前的延迟时间。

如果达到了最大重传次数 yet仍然无法成功传输数据，那么该设备就会放弃尝试，并报告传输失败。

优势/好处

• 碰撞概率呈指数级下降。
• 提升了网络性能：回退算法能够减少冲突和重传的次数，从而提升整个网络的性能。
• 提高通道的利用率通过减少碰撞的次数，回退算法能够提高信道的利用率，从而更有效地利用网络资源。
• 减少延迟：通过减少碰撞的次数，回退算法能够缩短每次传输尝试之间的等待时间，从而降低延迟现象。
• 公平性：这种回退算法确保了网络中的所有节点都有平等的机会来访问信道，从而提升了网络资源分配的公平性。
• 适应能力：该回退算法能够适应不断变化的网络状况。当网络处于繁忙状态时，它会增加重传尝试前的等待时间；而当网络处于空闲状态时，则会减少等待时间。这样就能确保网络资源的有效利用。
• 可扩展性：这种回退算法具有可扩展性，因为它可以应用于各种规模的网络中——无论是小型本地网络还是大型广域网络。
• 能源效率：通过减少碰撞次数和重传次数，退避算法能够降低网络节点的能耗。这一点对于手机、物联网设备等依赖电池供电的设备来说尤为重要。
• 鲁棒性：这种回退算法非常可靠，因为它能够应对大量节点同时尝试访问同一通道的情况，而不会导致网络崩溃或性能下降。

缺点/不利之处 –

• 捕获效果：获胜的队伍会一直保持胜利的状态。
• 仅适用于2个站点或主机。
• 运营成本增加“回退算法”会在网络中引入额外的开销，因为需要等待一段随机的时间之后才能重新发送数据包。
• 复杂性“Back-off算法”是一种复杂的算法，其实现过程需要极高的复杂性。
• 容易受到攻击的弱点这种回退算法容易受到某些攻击的影响，比如服务拒绝攻击。在这种攻击中，攻击者可以操纵随机时间间隔，从而导致网络无法正常运行。
• 有限性能：虽然这种延迟算法能够在低到中等负载的情况下提升网络性能，但在高负载情况下却可能效果不佳。因为在高负载情况下，试图访问网络的节点数量会非常多，此时该算法的效果就会大打折扣。
• 在需要高度及时性的应用中效率低下：这种延迟算法可能并不适合那些对时间敏感的应用场景，比如实时视频流传输或IP语音通信等。在这些应用中，哪怕只有一点点延迟，都可能引发严重的问题。
• 可扩展性有限：虽然这种回退算法可以应用于任何规模的网络中，但在那些节点数量非常多、同时试图访问该通道的节点数量也相当多的大型网络中，这种算法的效果可能会有所下降。
• 对距离和干扰的敏感性：这种退避算法对距离和干扰非常敏感。因为，那些在物理上相距较近的节点，发生碰撞的概率会更高，因此可能需要更长的随机等待时间。
• 对服务质量的支持有限：该回退算法并不支持服务质量(QoS)方面的处理。而QoS功能对于许多网络应用来说非常重要，比如视频流传输、IP语音通信以及在线游戏等。

GATE模拟试题 –

1. GATE-CS-2004 | 问题90
2. GATE-CS-2016（第2套试题）| 问题34
3. GATE-IT-2004 | 问题85