概述
截斷二進制指數退避（truncated binary exponential backoff）算法是用來解決乙太網碰撞問題的一種算法。這種算法讓發生碰撞的的站在停止傳送數據後，不是等待信道變為空閒後就立即在傳送數據，而是推遲（這叫做退避）一個隨機的時間。這樣做是為了重傳是再次發生衝突的機率減小。
基本介紹
- 中文名：截斷二進制指數退避算法
- 外文名：truncated binary exponential backoff
簡介,算法過程,
簡介
在乙太網中，每一個站在自己傳送數據之後的一小段時間內，存在著遭遇碰撞的可能性，因此乙太網不能保證某一時間之內一定能夠把自己的數據幀成功的傳送出去。乙太網的這一特點為傳送的不確定性。如果希望在乙太網上發生碰撞的機會很小，必須使整個乙太網的平均通信量遠小於乙太網的最高數據率。
匯流排上的單程端到端傳播時延記為
，乙太網的端到端往返時間2稱為爭用期。這是因為一個站在傳送完數據後，只有通過爭用期的“考驗”，即經過爭用期這段時間還沒有檢測到碰撞，才能肯定這次傳送不會發生碰撞。截斷二進制指數退避（truncated binary exponential backoff）算法就是是用來解決乙太網碰撞問題的一種算法。
算法過程
截斷二指數退避算法並不複雜。具體的退避算法如下：
- 確定基本退避時間，它就是爭用期。乙太網把爭用期定為51.2us。對於10Mb/s乙太網，在爭用期內可傳送512bit，即64位元組。也可以說爭用期是512比特時間。1比特時間就是傳送1比特所需要的時間。所以這種時間單位與數據率密切相關。
- 從離散的整數集合[0,1,…,]中隨機取出一個數，記為r。重傳應推後的時間就是r倍的爭用期。上面的參數k按下面的公式計算：
k=Min[重傳次數，10]
可見當重傳次數不超過10時，參數k等於重傳次數;但當重傳次數超過10時，k就不在增大而一直等於10。 - 當重傳達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位元組的幀都是由於衝突而異常中止的無效幀。收到了這種無效幀就應當立即丟棄。
