截断二进制指数退避算法

在以太网中，每一个站在自己发送数据之后的一小段时间内，存在着遭遇碰撞的可能性，因此以太网不能保证某一时间之内一定能够把自己的数据帧成功的发送出去。以太网的这一特点为发送的不确定性。如果希望在以太网上发生碰撞的机会很小，必须使整个以太网的平均通信量远小于以太网的最高数据率。

总线上的单程端到端传播时延记为，以太网的端到端往返时间2称为争用期。这是因为一个站在发送完数据后，只有通过争用期的“考验”，即经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。截断二进制指数退避（truncated binary exponential backoff）算法就是是用来解决以太网碰撞问题的一种算法。

截断二指数退避算法并不复杂。具体的退避算法如下：

1. 确定基本退避时间，它就是争用期。以太网把争用期定为51.2us。对于10Mb/s以太网，在争用期内可发送512bit，即64字节。也可以说争用期是512比特时间。1比特时间就是发送1比特所需要的时间。所以这种时间单位与数据率密切相关。
2. 从离散的整数集合[0,1,…,]中随机取出一个数，记为r。重传应推后的时间就是r倍的争用期。上面的参数k按下面的公式计算：k=Min[重传次数，10]可见当重传次数不超过10时，参数k等于重传次数;但当重传次数超过10时，k就不在增大而一直等于10。
3. 当重传达16次仍不能成功时(这表明同时打算发送的数据站太多，以致连续发生冲突)，则丢弃该，并向高层报告。例如，在第1次重传时，k=1，随机数r从整数{0,1}中选一个数。因此重传推迟的时间是0或争用期，在这两个时间中随机选择一个。

若再发生碰撞，则重传时，k=2，随机数r就从整数{0,1,2,3}中选一个数。因此重传推迟的时间是在0,2,4和6这4个时间中随机抽取一个。

同样，若在发生碰撞，则重传时k=3，随机数r就从整数{0,1,2,3,4,5,6,7}中选一个数。以此类推。

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

我们还注意到，适配器每发送一个新的帧，就要执行一次CMSA/CD算法。适配器对过去发生过的碰撞并无记忆功能。因此，当好几个适配器正在执行指数退避算法时，很可能有某一个适配器发送的新帧能够碰巧立即成功插入到信道中，得到了发送权。

我们可以看出，以太网在发送数据时，如果帧的前64字节之内没有发生冲突，那么后续的数据就不会发生冲突。换句话说，如果发生冲突就立即中止发送，这时已经发送出去的数据一定小于64字节，因此以太网规定了最短有效的帧长为64字节，凡长度小于64字节的帧都是由于冲突而异常中止的无效帧。收到了这种无效帧就应当立即丢弃。^[1]