“RED的到达平均队长与这里的出队驻留时间是不同观测。改变链路速率时，同一队长的等待可显著变化；另一方面，服务机会暂时很少时，本页也只在实际取候选时推进控制，不是每个计划时刻都在后台强制删包。”
缓冲区还没装满，路由器也可能先丢一个包。这样做的目的，是让发送端在长队积累前收到减速信号。RED把这件事分成两个问题：队列是否持续偏大，以及这次选中哪个到达包。一个平均值负责前者，一次概率试验负责后者。
形式陈述
先约定队列和采样事件
考虑固定长度分组组成的FIFO。容量C以包计；q是本次新包加入之前尚在等待的包数，不包括已经交给下游的包。入队、出队按单调整数tick及同刻给定次序执行。每个包最终只能进入队列、被丢弃或已交付，不能因一个通知同时复制成两份。
状态avg是到达采样的平滑平均，初值0；权重0<w≤1。若到达时q>0，先更新
队列变空时记下空闲衰减位置。空闲期间每经过一个约定的参考服务槽，相当于补一个q=0的样本；若已有m个尚未处理的完整槽，就令avg←(1−w)^m avg，再推进衰减位置。附件一tick恰为一槽。连续几次空队列到达不能反复衰减同一段已计时间；参考槽长改变，估计器也随之改变。[1，§4、§6]
这是事件平均，不是时间积分除以观察时长。包长变化时，以包计的q也不能直接换算成字节等待；本页固定包长，避免暗中混用单位。
两个阈值与一份明确计数
参数满足0≤min<max，0<pmax≤1。avg<min时不提前通知；avg≥max时必通知。中间区定义基础概率
令k表示自上次提前通知或低阈值重置后，此前已经处理、仍处中间区而未被选中的到达数。初值0，本次包尚未计入。按原论文§7的这一口径，采用
抽取与既往独立的单位均匀数U，U<pa时选中。选中后k归0；中间区未选中才令k加1；落到低阈值也归0。上阈值强制通知后归0。本页先算概率、后更新k；原论文图2另有到达先增的count写法，不能把它的递增位置和本页k的初值/重置值交叉使用。
这里的k只记录AQM选择器的事件。物理满队列造成的尾丢是另一个容量动作，不计作选择器选中；不能从AQM日志推断所有实际丢包。裁剪处理变化pb时的非正分母，避免把负数当概率。
通知与占位分别结算
主例先检查硬容量：q=C时尾丢；还有空间时，被选中就提前丢弃，未选中才入队。选择器与容量结果分别记录，即使已满，仍可知道平均值是否已到高阈值。被选中事件也可交给经典ECN，把合格包标CE后继续入队；但这不释放一个槽，容量仍要检查。改变丢弃为标记后，后续q和avg必须按新的实际队列重算。
直觉
平滑让短突发和持续积压有所区别
一次大q只贡献wq，其余权重留给旧avg。较小w会削弱单次峰值，同时也使持续增长更晚被看见。假设q连续保持Q，经过j次到达更新，展开递推可得avg_j=Q+(1−w)^j(avg_0−Q)。这条等式直接展示记忆衰减，不是给出所有网络的最佳w。
计数修正让已经等了几次通知的序列更容易被选中。它没有识别流身份：一个流如果贡献更多到达机会，通常也经历更多次试验；这不足以证明不同RTT、不同包长或不合作流量之间严格公平。
例子与边界
七个包，逐项付清队列变化
取C=5、w=1/2、min=2、max=4、pmax=1/2。七包同在0到达，依编号顺序处理，没有穿插出队；所需U依次按表给出。
| 包 | 更新前q | 更新后avg | 概率pa | U | 动作与队列 |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | — | 入队1 |
| 2 | 1 | 1/2 | 0 | — | 入队1,2 |
| 3 | 2 | 5/4 | 0 | — | 入队1,2,3 |
| 4 | 3 | 17/8 | 1/32 | 9/10 | 入队1,2,3,4；k=1 |
| 5 | 4 | 49/16 | 17/47 | 3/10 | 提前丢5；k=0 |
| 6 | 4 | 113/32 | 49/128 | 9/10 | 入队1,2,3,4,6；k=1 |
| 7 | 5 | 273/64 | 1 | — | 高阈值选中；硬满尾丢7；k=0 |
第5包的pb=17/64，故pa=(17/64)/(1−17/64)=17/47。它被丢后q仍4，因此第6包不能按q=5算平均。最后q恰好5，守住容量；表中丢5发生时还没有满。
单独核验衰减子程序：给定输入avg=4，让队列持续空闲三个参考槽，w仍1/2，结果为4×(1/2)^3=1/2。若先经过一槽、再经过两槽，结果应相同；把第二次仍按“离最初变空已三槽”重复衰减，则错误得到1/4。
为什么pa不等于长期丢包率
仅冻结pb=1/4，忽略阈值变化，在刚重置k=0后看下次选中的位置X。前四次条件概率为1/4、1/3、1/2、1。于是
X均匀分布于1..4，均值5/2，而不是几何分布的均值4。基础概率pb不是经过计数修正后的平均通知率。一般pb=1/N且N为正整数时，存活到第j次的概率为(N−j+1)/N，乘本次的1/(N−j+1)得到1/N；这是可复算的望远镜乘积。
如果avg变了，pb也变，这个均匀间距结论就不再直接成立。若使用未修正的固定pb独立选包，间距才是几何型；两种随机过程不能只因都写着RED便共用一张概率表。
提前通知没有取消硬容量
极短突发可以在avg追上前填满缓冲，仍须硬满丢包。即使全部包都能标CE，若发送端不减速，保留所有被标记包也无法在有限内存中承接永久超额到达。发送窗口的响应还隔着传播与ACK时间，不能在标记瞬间假定远端已经停发。
推论与应用
三种保证各有证据
队列占用≤C由每次入队检查保证。0≤avg≤C由凸组合和空闲衰减归纳得到。0≤pa≤1由分段裁剪保证。这些是本状态机对所有合法输入成立的不变量；“延迟很小”“链路利用率高”还依赖到达流量、服务过程和端点反馈，不能从三条不变量中推出。
CoDel直接观察出队等待，并判断高等待是否持续一段时间；本页观察的是到达时队长平均。相同q在不同链路速率下对应不同等待，因而不能把RED阈值包数直接当CoDel的时间阈值。
计算与日志成本
有界字算术和常数时间FIFO下，一次非空到达只做常数次算术及一次队列操作。空闲跳过m槽时，幂运算需要另计；按反复平方计算是O(1+log(m+1))次乘法，不是按每一毫秒唤醒。维护运行字节/包数不能每次扫描整个队列。
附件用精确分数和给定U带复算边界，分子分母会增长，不声称这些任意精度操作是生产常数时间。调试输出若复制完整队列，另付O(1+q)记录成本。概率质量的测试用条件概率乘积，不以有限随机频率代替证明。完整表与改成标记后的迁移见排队与反馈终点。
参考资料
- Sally Floyd、Van Jacobson，Random Early Detection Gateways for Congestion Avoidance，1993，作者双栏稿§4与图2（PDF pp.5–6）、§6（pp.8–10）、§7（pp.10–11）。本页采用§7的此前未标记包计数解释，并明确空闲槽和硬容量接口；不将图2的到达先增count与本页k混用
- RFC3168，§5：提前拥塞通知与满队列丢弃分开，AQM选择方法与ECN编码不是同一层算法