解析二進(jìn)制指數(shù)退避算法的過程

CSMA/CD采用二進(jìn)制指數(shù)退避算法，又稱為二元指數(shù)后退算法。退避算法是以沖突窗口大小為基準(zhǔn)的，每個(gè)節(jié)點(diǎn)有一個(gè)沖突計(jì)數(shù)器C。退避的時(shí)間與沖突次數(shù)具有指數(shù)關(guān)系，沖突次數(shù)越多，退避的時(shí)間就可能越長，若達(dá)到限定的沖突次數(shù)，該節(jié)點(diǎn)就停止發(fā)送數(shù)據(jù)。

二進(jìn)制退避技術(shù)（Binary Exponential Back off）. 指在遇到重復(fù)的沖突時(shí)，站點(diǎn)將重復(fù)傳輸，但在每一次沖突之后，隨著時(shí)延的平均值將加倍。二進(jìn)制指數(shù)退避算法提供了一個(gè)處理重負(fù)荷的方法。嘗試傳輸?shù)闹貜?fù)失敗導(dǎo)致更長的退避時(shí)間，這將有助于負(fù)荷的平滑。如果沒有這樣的退避，以下狀況可能發(fā)生：兩個(gè)或多站點(diǎn)同時(shí)嘗試傳輸，這將導(dǎo)致沖突，之后這些站點(diǎn)又立即嘗試重傳，導(dǎo)致一個(gè)新沖突。

在CSMA/CD協(xié)議中，一旦檢測到?jīng)_突，為降低再沖突的概率，需要等待一個(gè)隨機(jī)時(shí)間，然后再使用CSMA方法試圖傳輸。為了保證這種退避維持穩(wěn)定，采用了二進(jìn)制指數(shù)退避算法的技術(shù)，其算法過程如下：

1.確定基本退避時(shí)間，一般為端到端的往返時(shí)間為2t，2t也成為沖突窗口或爭用期。

2. 定義參數(shù)k，k與沖突次數(shù)有關(guān)，規(guī)定k不能超過10，k=Min[沖突次數(shù)，10]。在沖突次數(shù)大于10，小于16時(shí)，k不再增大，一直取值為10。

3. 從離散的整數(shù)集合[0,1,2，……，(2^k-1)]中隨機(jī)的取出一個(gè)數(shù)r，等待的時(shí)延為r倍的基本退避時(shí)間，等于r x 2t。r的取值范圍與沖突次數(shù)k有關(guān)，r可選的隨機(jī)取值為2^k個(gè)、這也是稱為二進(jìn)制退避算法的起因。

4.當(dāng)沖突次數(shù)大于10以后，都是從0—2^10-1個(gè)2t中隨機(jī)選擇一個(gè)作為等待時(shí)間。

5. 當(dāng)沖突次數(shù)超過16次后，發(fā)送失敗，丟棄傳輸?shù)膸?，發(fā)送錯(cuò)誤報(bào)告。

舉例

如果第二次發(fā)生碰撞：

n = 2

k = MIN(2,10) = 2

R = {0, 1, 2, 3)

延遲時(shí)間 = R * 512 * Bit-time

其中：Bit-time = 1 / Debit

例如：

對于傳輸速率Debit = 10 Mbit/s,

那么Bit-time = 0.1 us

延遲時(shí)間={0, 51.2 us, 102.4 us, 153.6 us} 其中任取一