【二进制指数退避算法】

二进制指数退避算法一、概念二、原理一、概念1.二进制指数退避算法是以太网退避算法是 CSMA/CD 里处理冲突后重发的核心规则。2.发生冲突后不立刻重发而是随机等一段时间再试。3.冲突次数越多随机等待的范围就越大避免再次撞车网络负载越重退避时间越长。4.因为等待的时间范围是2的冲突次数次方每次冲突等待区间翻倍扩大所以叫二进制指数退避。二、原理1.发生冲突发送干扰信号。2.进入退避算法记当前冲突次数为n计算退避指数k min(n, 10)最多只取 10防止等待时间无限变大从 0 ~ 2ᵏ − 1 中随机选一个整数 r等待时间r*512比特时间设传输速率为R1比特时间1/R。3.等待结束后重新监听信道尝试重发。4.如果重发又冲突n1重复上述步骤。5.最多重试 16 次还失败就丢弃帧并向上层报错。第 1 次冲突k1 → 0~ 1 中随机选第 2 次冲突k2 → 0~ 3 中随机选第 3 次冲突k3 → 0~ 7 中随机选……第 10 次冲突k10→ 0~ 1023 中随机选第 11~16 次冲突k 不再增加保持 10例题1某以太网采用10Mbps速率使用二进制指数退避算法当某个帧发生第 3 次冲突时。求1.此次退避的时间范围2.若随机选中 r5求实际等待时间①传输速率R10Mbps10^6bps1比特时间1/R1/10 ^610 ^-70.1μs则退避时间等待时间5120.1μs51.2μsr3则k[0,2 ^3-1][0,7]退避时间范围051.2μs-751.2μs0-358.4μs。②若r5则等待时间551.2μs256μs。