CSMA/CD采用二进制指数退避算法,又称为二元指数后退算法。退避算法是以冲突窗口大小为基准的,每个节点有一个冲突计数器C。退避的时间与冲突次数具有指数关系,冲突次数越多,退避的时间就可能越长,若达到限定的冲突次数,该节点就停止发送数据。
定义
二进制退避技术(Binary Exponential Back off). 指在遇到重复的冲突时,站点将重复传输,但在每一次冲突之后,随着时延的平均值将加倍。二进制指数退避算法提供了一个处理重负荷的方法。尝试传输的重复失败导致更长的退避时间,这将有助于负荷的平滑。如果没有这样的退避,以下状况可能发生:两个或多站点同时尝试传输,这将导致冲突,之后这些站点又立即尝试重传,导致一个新冲突。
应用
在CSMA/CD协议中,一旦检测到冲突,为降低再冲突的概率,需要等待一个随机时间,然后再使用CSMA方法试图传输。为了保证这种退避维持稳定,采用了二进制指数退避算法的技术,其算法过程如下:
确定基本退避时间,一般为端到端的往返时间为2t,2t也称为冲突窗口或争用期。
定义参数k,k与冲突次数有关,规定k不能超过10,k=Min[冲突次数,10]。在冲突次数大于10,小于16时,k不再增大,一直取值为10。
从离散的整数集合[0,1,2,……,(2^k-1)]中随机的取出一个数r,等待的时延为r倍的基本退避时间,等于r x 2t。r的取值范围与冲突次数k有关,r可选的随机取值为2^k个、这也是称为二进制退避算法的起因。
当冲突次数大于10以后,都是从0—2^10-1个2t中随机选择一个作为等待时间。
当冲突次数超过16次后,发送失败,丢弃传输的帧,发送错误报告。
举例
如果第二次发生碰撞:
n = 2
k = MIN(2,10) = 2
R = {0, 1, 2, 3)
延迟时间 = R * 512 * Bit-time
其中:Bit-time = 1 / Debit
例如:
对于传输速率Debit = 10 Mbit/s,
那么Bit-time = 0.1 us
延迟时间={0, 51.2 us, 102.4 us, 153.6 us} 其中任取一