RED(Random Early Detection)算法旨在将队列的平均长度保持在较低的值，同时，允许一定量的突发报文。在发生拥塞期间，RED以一定的概率通知（丢包或者ECN机制）某个连接减低窗口值，此概率大致上与该连接占用的带宽份额成比例。RED设计用来与传输层协议如TCP等一起使用。另外，RED还可避免过多的连接同时减低窗口的现象发生。

RED使用一个带有EWMA（Exponential Weighted Moving Average）的LPF（Low-Pass Filter）低通滤波器来计算平均队列长度。平均队列长度avg与最小和最大两个阈值（minth和maxth）相比较，当平均队列长度小于minth时，不对报文进行标记处理（ECN或者丢弃）；当平均队列长度大于maxth时，每个接收到的报文都进行标记处理，如果报文最终被丢弃，或者所有的发送端都能够对检测到的拥塞标记进行适当处理（降低发送速率），那么平均队列长度将不会超过maxth过多。

当平均队列长度位于minth和maxth阈值之间时，每个到达的报文按照一定的概率（pa）被标记，pa根据平均队列长度推倒而来。并且，某个特定连接中的报文被标记的概率大致与此连接占用的带宽成比例。以下是一个简单的RED算法框架：

for each packet arrival
    calculate the average queue size _avg_
    if minth <= avg > maxth
	    calculate probability _pa_
        with probability _pa_ :
            mark the arriving packets
    else if maxth <= avg
        mark the arriving packets

RED由两个独立的算法组成，a)计算平均队列长度，决定了可接收的报文突发量；b）计算报文的标记概率，决定标记报文的频率，给出当前的拥塞级别。总的目标是公平的标记报文，避免同步丢失（global synchronization）的发生，并且，标记足够的报文以控制平均队列长度。

RED计算平均队列长度时，考虑了队列的空闲时长，假设在空闲阶段可传输m数量的小报文，在空闲结束之后，RED假定在此段时间内空队列接收了m个报文，以此计算平均队列长度。

当平均队列长度avg位于minth和maxth之间时，报文标记概率pb的取值位于线性空间：[0, maxp]，其中maxp为设定的最大标记概率:

$p_{b} \leftarrow \frac{max_{p}\left ( avg-min_{th} \right )}{\left ( max_{th}-min_{th} \right )}$

最终的报文标记概率pa，由以上计算的概率pb，和自上一次标记报文到当下处理的报文数量count，两个变量计算而得：

$p_{a} \leftarrow \frac{p_{b}}{\left ( 1-count*p_{b} \right )}$

这样pa将随着平均队列长度的增加，以及报文数量的增加，而增长，RED可及时的对报文进行标记。

另外，除了以报文为单位，RED还可以字节为单位计算队列的长度，这种情况下，平均队列长度可以更准确的反应时延情况。对RED算法需要修改以保证报文的标记概率与以字节为单位的报文大小成比例，使用如下公式修正pb概率：

$p_{b} \leftarrow p_{b}*\frac{PacketSize}{MaximumPacketSize}$

完整的RED算法如下：

Initialization:
    avg <- 0
    count <- -1
for each packet arrival
    calculate new avg. queue size _avg_ :
        if the queue is nonempt
		    avg <- (1 - Wq)avg + Wq * q 
        else
            m <- f(time - q_time)
            avg <- (1 - Wq)**m * avg
    if minth <= avg < maxth
        increment count
        calculate probability _pa_ :
            pb <- maxp(avg - minth)/(maxth - minth)
            pa <- pb/(1 - count * pb)
        with probability _pa_ :
            marking the arriving packet
            count <- 0
    else if maxth <= avg
        marking the arriving packet
        count <- 0
when queue becomes empty
    q_time <- time

参数说明：

Saved Variables:
**avg**    : 平均队列长度 average queue size
**q_time** : 队列空闲开始时间戳 start of the queue idle time
**count**  : 自上次报文标记后，处理的报文数量 packets since last marked pkt.

Fixed parameters:
**Wq**     : 队列权重 queue weight
**minth**  : 队列最小长度阈值 minimum threshold for queue
**maxth**  : 队列最大长度阈值 maximum threshold for queue
**maxp**   : pb的最大值 maximum value for pb

Other:
**pa**    : 当前报文标记概率 current pkt-marking probability
**q**     : 当前队列大小 current queue size
**time**  : 当前时间 current time
**f(t)**  : a linear function of the time

1 平均队列长度

由于RED使用LPF计算平均队列长度avg，突发报文引起的队列短期增长，以及暂时的拥塞，都不会引起平均队列长度的剧烈变化。LPF使用如下的EWMA（Exponential Weighted Moving Average）公式实现：

$EWMA(t) = aY(t) + (1-a)EWMA(t-1)，t = 1,2,.....,n；$

其中，EWMA(t) 表示t时刻的估计值；Y(t) 表示t时刻的测量值；n 表示所观察的总的时间；a(0 < a <1)表示历史测量值权重系数。之所以称之为指数加权，是因为加权系数a是以指数式递减的，即各指数随着时间而指数式递减。用n表示加权系数为a = 2/(n+1)。转化为RED使用的形式如下：

$avg \leftarrow \left ( 1-w_{q} \right )avg+w_{q}q$

其中，权重值wq决定了LPF的加权系数，如果wq过大，将不能过滤短时的拥塞情况，如果wq过小，将不能及时反映平均队列长度的变化，无法检测即将到来的拥塞状况。

1.1 权重wq上限

假设队列初始为空，并且平均队列长度为零，当接收到L个报文之后，队列长度由零增长到L，平均队列长度avgL计算如下：

$avgL=\sum_{i=1}^{L}iw_{q}\left ( 1- w_{q}\right )^{L-i} = w_{q}\left ( 1- w_{q}\right )^{L}\sum_{i=1}^{L}i\left ( \frac{1}{1-w_{q}} \right )^{i}$

依据以下等式，

$\sum_{i=1}^{L}ix^{i}=\frac{x+\left ( Lx-L-1 \right )x^{L+1}}{\left ( 1-x \right )^{2}}$
求解avgL：

$avgL=L+1+\frac{\left ( 1-w_{q} \right )^{L+1}-1}{w_{q}}$
假设给定一个最小的队列长度minth，并且允许L数量的突发报文，如果要达到avg<minth（不标记报文），wq需要满足以下要求：

$L+1+\frac{\left ( 1-w_{q} \right )^{L+1}-1}{w_{q}} < min_{th}$

例如，minth等于5，L=50，wq的值需要小于等于0.0042。

1.2 权重wq下限

假设队列由空变为1个报文长度，之后，如果报文的到达和离开保持相同的速率，那么队列始终维持1个报文长度。更进一步假设初始时，平均队列长度avg为零，在这种情况下，avg要增长到0.63=1-1/e，需要接收到-1/ln(1-wq)数量的报文。对于wq=0.001的情况，这需要1000个报文；对于wq=0.002，需要500个报文；对于wq=0.003，需要333个报文。

wq值太小，将导致平均队列长度avg对于实际队列长度的变化，反应过慢，典型的使用wq=0.002的值。

1.2 minth和maxth的设置

minth和maxth的设置取决于期望的平均队列长度avg。如果网络中以突发流量为主，minth应设置较大值，以保证带宽的有效利用，容许突发流量。maxth的值取决于可接受的最大平均时延。

RED建议maxth-minth的差值应大于一个RTT周期内平均队列长度的增加值。一般设置maxth大于minth的2倍值。

2 报文标记概率

最初的标记概率pb由平均报文长度组成的线性方程计算而来，如下：

$p_{b} \leftarrow \frac{max_{p}\left ( avg-min_{th} \right )}{\left ( max_{th}-min_{th} \right )}$

如果直接使用pb做为最终的标记概率，在平均队列长度不变的情况下，在两个被标记的报文之间，每个接收到的报文的标记概率都为pb，假设此时间间隔为X，那么第n个报文被标记的概率为：
$Prob\left [ X=n \right ]=\left ( 1-p_{b} \right )^{n-1}p_{b}$
可见，X为一个几何随机变量，其期望值为E[X]=1/pb。

对于不变的平均队列长度，目标是要以平均的间隔标记报文，如果标记的报文聚集，或者相隔太大都不是理想的情况，将引起多个连接同时降低窗口的发生。故不能直接使用概率pb。

因此，根据要求，X应为一个均匀分布(矩形分布)的随机变量：{1,2,…,1/pb}。那么，每个到来的报文的标记概率应为：pb/(1-count*pb)可满足均匀分布的要求：

$Prob\left [ X=n \right ]=\frac{p_{b}}{1-\left ( n-1 \right )p_{b}}\prod_{i=0}^{n-2}\left ( 1-\frac{p_{b}}{1-ip_{b}} \right )$
在1<= n <= 1/qb时：
$Prob\left [ X=n \right ]= p_{b}$
当n>1/pb时，
$Prob\left [ X=n \right ]=0$

此时期望值E[X]=1/(2pb)+1/2。