前置知识 – CSMA/CD 基础, CSMA/CD 中的冲突检测
退避算法是一种用于随机访问 MAC 协议（如 CSMA/CD）的冲突解决机制。该算法通常用于以太网中，以规划冲突发生后的重传时间。让我们设想一下，如果两个站点之间发生了冲突，它们可能会在冲突结束后立即尝试重新开始传输。这将不可避免地导致再次发生冲突，从而陷入无限循环，最终导致死锁。为了防止这种情况，我们引入了退避算法。让我们考虑一个包含两个站点 A 和 B 正在传输数据的场景：
在发生冲突后，时间被划分为离散的时隙（Tslot），其长度等于 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} 中随机选择一个整数。!image
- 当 A 和 B 都选择 K = 0 时 –> A 的等待时间 = 0 * T slot = 0
B 的等待时间 = 0 * T slot = 0
因此，两个站点将同时传输，从而导致冲突发生。
- 当 A 选择 K = 0 且 B 选择 K = 1 时 –> A 的等待时间 = 0 * T slot = 0
B 的等待时间 = 1 * T slot = T slot
因此，A 传输数据包，B 等待时间 T slot 以便传输，因此 A 获胜。
- 当 A 选择 K = 1 且 B 选择 K = 0 时 –> A 的等待时间 = 1 * T slot = T slot
B 的等待时间 = 0 * T slot = 0
因此，B 传输数据包，A 等待时间 T slot 以便传输，因此 B 获胜。
- 当 A 和 B 都选择 K = 1 时 –> A 的等待时间 = 1 * T slot = T slot
B 的等待时间 = 1 * T slot = T slot
因此，两者都会等待相同的时间 T slot 然后传输。因此，会发生冲突。
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 相比，冲突的概率降低了。
以下是它的一些关键特性：
当发生冲突时，传输设备会等待一段随机的时间，然后重新传输数据包。这种随机延迟有助于防止多个设备同时重传数据包从而导致再次冲突。
随机延迟时间是通过指数退避算法确定的。延迟时间从一个最小值开始，并在每次冲突后加倍，直到达到最大值。最大延迟时间通常设置为 1024 个时隙时间，其中一个时隙时间是信号从网络段的一端传输到另一端所需的时间。
退避算法是在每个设备的网络接口卡（NIC）的硬件中实现的。当检测到冲突时，NIC 会生成一个介于 0 和 2^n-1 之间的随机数，其中 n 是已发生的冲突次数。然后，NIC 将该随机数乘以时隙时间，以确定重传前的延迟时间。
如果达到最大重传次数后仍未成功传输，设备将放弃尝试。