指数退避算法 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. 用处

作为避免网络堵塞的一部分，用于数据块的重发策略。

3. 名词定义

争用期：即基本退避时间，它是总线上的单程端到端传播时延，记为 x，以太网的端到端往返时间2x。以太网把争用期定为51.2us。对于10Mb/s以太网，在争用期内可发送512bit，即64字节。也可以说争用期是512比特时间。1比特时间就是发送1比特所需要的时间。所以这种时间单位与数据率密切相关。

4. 算法流程

1.确定基本退避时间，一般为端到端的往返时间为2t，2t也成为冲突窗口或争用期。

定义参数k，k与冲突次数有关，规定k不能超过10，即 $k=Min[冲突次数，10]$ 。在冲突次数大于10，小于16时，k不再增大，一直取值为10。（即取一个threshold做截断）
从离散的整数集合[0,1,2，……，( $2^k-1$ )]中随机的取出一个数r，等待的时延为r倍的基本退避时间 $r \cdot 2t$ 。r的取值范围与冲突次数k有关，r可选的随机取值为 $2^k$ 个，这也是称为二进制退避算法的起因。

4.当冲突次数大于10以后，都是从 $0$ ~ $2^{10}-1$ 个2t中随机选择一个作为等待时间。

当冲突次数超过16次后，发送失败，丢弃传输的帧，发送错误报告。

5. 工程应用

Envoy、AWS的重试机制使用指数退避算法。