二進制指數退避算法

CSMA/CD採用二進制指數退避算法,又稱為二元指數後退算法。退避算法是以衝突視窗大小為基準的,每個節點有一個衝突計數器C。退避的時間與衝突次數具有指數關係,衝突次數越多,退避的時間就可能越長,若達到限定的衝突次數,該節點就停止傳送數據。

定義

二進制退避技術(Binary Exponential Back off). 指在遇到重複的衝突時,站點將重複傳輸,但在每一次衝突之後,隨著時延的平均值將加倍。二進制指數退避算法提供了一個處理重負荷的方法。嘗試傳輸的重複失敗導致更長的退避時間,這將有助於負荷的平滑。如果沒有這樣的退避,以下狀況可能發生:兩個或多站點同時嘗試傳輸,這將導致衝突,之後這些站點又立即嘗試重傳,導致一個新衝突。

套用

在CSMA/CD協定中,一旦檢測到衝突,為降低再衝突的機率,需要等待一個隨機時間,然後再使用CSMA方法試圖傳輸。為了保證這種退避維持穩定,採用了二進制指數退避算法的技術,其算法過程如下:

1.確定基本退避時間,一般為端到端的往返時間為2t,2t也成為衝突視窗或爭用期。

2. 定義參數k,k與衝突次數有關,規定k不能超過10,k=Min[衝突次數,10]。在衝突次數大於10,小於16時,k不再增大,一直取值為10。

3. 從離散的整數集合[0,1,2,……,(2 -1)]中隨機的取出一個數r,等待的時延為r倍的基本退避時間,等於r x 2t。r的取值範圍與衝突次數k有關,r可選的隨機取值為2 個、這也是稱為二進制退避算法的起因。

4.當衝突次數大於10以後,都是從0—2 -1個2t中隨機選擇一個作為等待時間。

5. 當衝突次數超過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} 其中任取一

相關詞條

熱門詞條

聯絡我們