截斷二進制指數退避算法

在以太網中，每一個站在自己發送數據之後的一小段時間內，存在着遭遇碰撞的可能性，因此以太網不能保證某一時間之內一定能夠把自己的數據幀成功的發送出去。以太網的這一特點為發送的不確定性。如果希望在以太網上發生碰撞的機會很小，必須使整個以太網的平均通信量遠小於以太網的最高數據率。 ^[2] 

總線上的單程端到端傳播時延記為

，以太網的端到端往返時間2

稱為爭用期。這是因為一個站在發送完數據後，只有通過爭用期的“考驗”，即經過爭用期這段時間還沒有檢測到碰撞，才能肯定這次發送不會發生碰撞。如概述圖所示，傳輸的數據幀發生碰撞。以太網使用截斷二進制指數退避（truncated binary exponential backoff）算法來解決碰撞問題。 ^[2] 

截斷二進制指數退避算法，具體的算法是： ^[1] 

（1）當站點發送的數據包衝突時，站點的退避延時取值範圍(競爭窗口，CW)按2的指數增大，即k=2^i，i是衝突站點的重發次數（i=1,2,3,...）。 ^[1] 

（2）衝突站點取（1,2^i）中的一個隨機整數作為其退避時間。若再次發生衝突，則使i=i+1，並重覆上述延遲過程，直到衝突分解成功。 ^[1] 

（3）為保證信道利用效率，算法規定i的最大值為10，即最大時隙窗口為1024。 ^[1] 

（4）算法規定最大重複次數為16，當衝突站點的分解次數超過16次仍然存在衝突站點時就認為分解失敗，後幾次衝突分解的窗口大小保持1024不變。 ^[1] 

當重複次數達16，仍未能成功發送時，就丟棄該幀，並向高層報告。 ^[1] 

例如，在第1次重傳時，k=1，隨機數r從整數{0,1}中選一個數。因此重傳推遲的時間是0或爭用期，在這兩個時間中隨機選擇一個。 ^[2] 

若再發生碰撞，則重傳時，k=2，隨機數r就從整數{0,1,2,3}中選一個數。因此重傳推遲的時間是在0,2

,4

和6

這4個時間中隨機抽取一個。 ^[2] 

同樣，若在發生碰撞，則重傳時k=3，隨機數r就從整數{0,1,2,3,4,5,6,7}中選一個數。以此類推。 ^[2] 

截斷二進制指數退避算法容易實現。 ^[3]  若連續多次發生衝突，就表明可能有較多的站參與爭用信道。使用截斷二進制指數退避算法可使重傳需要推遲的平均時間隨重傳次數而增大（這也稱為動態退避），因而減小發生碰撞的概率，有利於整個系統的穩定。 ^[2] 

當網絡負載重時，尤其是在實時性要求較高的網絡中，信道的利用率就比較低，時延較大並且抖動較嚴重，不能有效處理動態網絡中業務的突發性。 ^[1]  影響系統的短期吞吐量和長期延遲方差。 ^[3]