指數(shù)退避算法 Exponential Back-off Algorithm

1. 定義

Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate.

2. 用處

作為避免網(wǎng)絡(luò)堵塞的一部分，用于數(shù)據(jù)塊的重發(fā)策略。

3. 名詞定義

爭用期：即基本退避時間，它是總線上的單程端到端傳播時延，記為 x，以太網(wǎng)的端到端往返時間2x。以太網(wǎng)把爭用期定為51.2us。對于10Mb/s以太網(wǎng)，在爭用期內(nèi)可發(fā)送512bit，即64字節(jié)。也可以說爭用期是512比特時間。1比特時間就是發(fā)送1比特所需要的時間。所以這種時間單位與數(shù)據(jù)率密切相關(guān)。

4. 算法流程

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

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

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

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

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

5. 工程應(yīng)用

Envoy、AWS的重試機制使用指數(shù)退避算法。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容