DCQCN 公式推导

Posted on 2026-04-08 In Networking

我一直觉得 DCQCN 里的流体模型是鸡肋（包括 PowerTCP 里的 Lyapunov 稳定性），就纯为了凑论文字数糊上去的，说是做了分析但也就是让人看着觉得确实分析了罢了（虽然我自己的文章也是这样），除了给 Reviewer 心理安慰让他给过之外也没啥作用。最近老师让看 DCQCN 的公式推导，所以系统记录一下这个过程。

DCQCN 的流体模型来源于 SIGMETRICS ’11 的 Stability Analysis of QCN: The Averaging Principle 这篇文章，在这届会议中同样还有分析 DCTCP 的稳定性的文章（Analysis of DCTCP: stability, convergence, and fairness，出自同一人之手）。总之可以互相参考着看。

DCQCN 文章中有一些更详细的公式推导在 CoNEXT ’16 的 ECN or Delay: Lessons Learnt from Analysis of DCQCN and TIMELY，其中还有关于 TIMELY 的稳定性分析，但本文并不关心 TIMELY。

符号表

符号	意义
	当前发送速率
	目标速率，即恰好在最后一个反馈消息到来前的发送速率
	减速因子，初值为
	队列长度
	时间
	ECN 标记所用参数
	论文里没有描述，但其是一个移动平均因子
	瓶颈处的流条数
	瓶颈链路的带宽
	快速恢复的阶段数
	速率增长中所用的字节计数器
	速率增长中所用的计时器
	速率增长的幅度（固定为 40Mbps）
	控制回路的延迟
	更新的时间周期
	CNP 的生成周期

前提假设

分析时，假设有条贪心流（指如果有空闲带宽就会抢占）通过单个容量为的瓶颈链路。

但最重要的假设是 DCQCN 一定在 PFC 前起作用。

长距场景下上面的假设非常鸡肋，不满足 PFC 后于 DCQCN 触发的情况很多。

流体模型

公式 5

这个公式描述的是拥塞时给包打 ECN 标记的概率随出队列长度变化的变化情况。图象是非常经典的三段，如果你做网络的话应该是刻 DNA 里了所以就不贴图了。

这个公式本身也没什么好说的，意思就是我们认为以下的队列是合理的，因为统计复用系统避免不了排队。但是大于的时候可能是拥塞的预兆，这时做 RED，但是不丢包，而是随机打标记。如果大于则认为是真拥塞了，每个包都打拥塞标记。

公式 6

假设所有流的速率都相等，这个公式描述了队列长度随时间变化的情况。等式左边是队列变化率，右边是队列入速率减出速率，就是一个水槽放水的问题，也没什么大不了的。但是需要注意这个公式十分理想，现实情况下至少应写作，并且这也没考虑传输时延的影响。

后面说他可以放宽所有流的速率都相等的假设，但是说实话我没看懂他是怎么放宽的。

公式 7

这是一个十分困难的公式，但是这个类型和 8 与 9 类似。

这个公式考虑随时间的变化的情况。根据 DCQCN 算法，当收到一个 CNP 时，会进行一次「向更新」，也就是，然后重置更新计时器。当触发更新计时器时，会进行一次「向更新」，也就是。因此，对于「向更新」，变化量为，对于「向更新」，变化量为。

这里的「向更新」和「向更新」是我自己造的，区分的是更新后会往哪儿移动。「向更新」是一种 EWMA，标准的 EWMA 是，这里就是，就是，是，因此在移动混合过程中会逐渐消解而过渡到。「向更新」很 trivial，假设更新次，值变成，而，因此，基础微积分。

但是，是否收到 CNP 是取决于是否有 ECN 标记的包，而 ECN 标记是依概率的，因此是一个随机变量，是一个随机过程。

从道理来说，是一个一维随机游走，不应该这么定义变化率。

考虑到设计时，CNP 的生成周期是小于的更新周期的。因此，在一个的时间窗口内，要么收到了一个 CNP 后进行「向更新」，之后更新计时器被重置，但假设不重置的情况下，在这个时间窗口内仍只会有这一个 CNP；要么一直没有收到 CNP，到窗口末期进行「向更新」。因此，一个时间窗口内，最多进行一次「向更新」，如果没进行「向更新」，则进行一次「向更新」。

这里文章的符号是乱的，我自己采用了新的符号。（后文还会出现）在文章里是，上下文符号不一致，第一次出现的符号是。

为了计算的变化率，我们首先需要承认如下近似。

强行解释就是我们希望计算在时间内的平均变化率，而是一个极小量，然后变化量期望代表着平均变化量，一除就是平均变化率了，反正不是的话也推不出后面的东西。严格来说这么写都是错的，不可导，应该写成类似 Ito 积分的形式，虽然选了应用随机过程但已经过了四年（但好像讲的时候 Ito 积分也就提了一嘴，没细讲），现在啥也不会了。

设在时间窗口内没有 CNP 的概率为，那么

则

比照给出的公式，发现。我们仅考虑一个时间窗口内的变化。由于网络存在控制回路延迟，当前时刻收到的反馈，对应的是时刻的发送状态。因此，如果这个窗口内无 CNP，发送的总数据量为

为了使这个窗口无 CNP，就不能被 ECN 打标记，因此在这一窗口内所有数据都不被 ECN 标记的概率是

由此得证。

但为什么是这样是很无厘头的。首先不是所有的发送数据都形成队列，假设这些数据都形成队列了，虽然 ECN 是根据队列长度变化的，但是按理说这个概率应该和包个数有关，而不是字节数。然后是打 ECN 标记的时间并非控制回路延迟，综合起来这公式混合了不同时刻发生的事情，虽然差距很小但还是有差距，但是数据中心内这点差距也不算啥，数学是天体物理老师教的，就只能感性理解，不要用它来计算。长距链路上带入这个显然就是错的了。

公式 9

由于的更新相对简单，我们先看公式 9。

由于降速还是升速取决于是否有 CNP，还是一个随机过程，因此仍然仿照公式 7 推导，写出

但是这里降速周期和升速周期并不一样，降速周期是但是升速周期受字节计数器和升速计时器限制，所以我们拆开分析

这里用到，我们把除法也放进去就好了。

降速过程

当收到 CNP 时会降速，而 CNP 每时间生成一个，因此在这里我们以为时间窗口分析。降速过程中的变化量，同样根据公式 7 中推导已知，时间内最多产生一个 CNP，并且在时间内产生至少一个 CNP 的概率是，所以

升速过程

升速过程受字节计数器和计时器限制。先看一次升速产生的变化量，虽然 DCQCN 中有 FastRecovery，AdditiveIncrease 和 HyperIncrease 三种状态，但是更新的方法都是同一种，即，因此。并且无论取值多少，都会这样更新，所以推导中不会出现。

再看多长时间才能进行一次升速，首先看字节计数器影响的升速。网卡要发送个字节且期间不收到任何 CNP，才能触发一次提速。我们要求的就是期望发送多少数据，才能出现连续发送个字节均不被标记。这是一个 Markov 链经典问题（QCN 稳定性论文中也有提及，但并没有做推导），答案是

那么进行一次字节计数器导致的升速所需的期望时间为

同理，对于计时器，网卡要发送个字节且期间不收到任何 CNP，才能触发一次提速，重新带入即可。

然后

就是原式了。

综合如上两部分原式得证。

公式 8

公式 8 的大致思路和公式 9 是一样的，只是换了一下参数而已。

在降速阶段，由于进行了，因此，剩下的讨论同公式 9。

在升速阶段，虽然 DCQCN 中 AdditiveIncrease 和 HyperIncrease 两种升速所用的不同，但是为了方便起见公式中用的是一样的。由此。

与更新不同的是，至少更新次后才会更新，即 FastRecovery 不会更新，而是在 Increase 阶段才更新。因此，公式 9 字节计数器升速时讨论的「网卡要发送个字节且期间不收到任何 CNP，才能触发一次提速」就变成了「网卡要发送个字节且期间不收到任何 CNP，才能触发一次提速」，对于计时器升速同理，指数部分多乘个就是了。

综合起来原式得证。

稳定性

DCQCN 论文中并没有直接证明稳定性，而是依赖 QCN 的稳定性证明。QCN 也没有直接证明稳定性，而是通过如下路径来证明：

QCN 利用了 Average Principle（似乎没有对应的汉语翻译）；
AP 在线性控制系统中和 PD（比例微分）控制器代数意义上等价，即给 AP 和 PD 等价的输入，它们的输出是等价的；
PD 具有稳定性，那么 AP 也具有稳定性；
所以 QCN 是稳定的。

至于证明已经完全不想看了。

用处

那么到最后 DCQCN 用这个流体模型干什么了呢？

不动点

这部分内容在 CoNEXT ’16 文章中的 3.2 节。

首先置公式 6 左式为，即也就是说，如果 DCQCN 存在一个不动点，则必须满足

因为不动点处一定有队列长度不变，说明速率收敛了

在任一不动点处，设的值为，所有流都共享此值。此时，队列长度的不动点与每条流的的不动点可以由公式 5 和 7 确定。

假设流收敛在队列长度为到之间（其原因并没有说明）。则直接将带入公式 5，得到队列长度的不动点对于的不动点，仍然置公式 7 左式为 0，即由于，因此只能是后面括号内部为 0，则可解得

有一个没什么意义的推导。如果发送端每隔时间就收到一个 CNP，也是收敛的。设，在等待下一个 CNP 的时间内，衰减次。因此在下一个 CNP 刚好到达前，衰减到：因为当前处于稳态，所以有，令稳态，则有解得考虑更新的递推式为了方便计算，我们令一个衰减常数。将上式展开并整理，得到一个标准的一阶线性递推数列：

已知该数列的最终收敛稳态为，我们可以利用稳态值将递推式改写为：

不断向下递推，可以得到第次迭代后的与初始值的关系：

如果进入稳态，则对任意给定，存在正整数使得对于都有成立。

将上面的通项公式代入：

两边同时取自然对数（注意，所以是负数，除以负数时不等号要变号）：

化简得但由于不可能一直收到 CNP，这意味着拥塞一直不缓解，并且有时进入收敛态的可能很大，所以计算这个确实没什么意义。

接下来我们需要证明存在，并且被唯一确定。

为了简单需要确定五个代换变量置公式 8 左式为 0，得到则置公式 9 左式为 0，得到则解得带入公式 8 得到的结果，有移项得为 CoNEXT 论文中公式 11。

此处，由于我们已经是考虑稳态中情况了，实际上为一常数，可以根据上式求解。

下面我们要考虑不动点是否只有一个，也就是求解上式是否可以唯一确定。可以发现，当时，左式是关于的单调递增函数。这部分证明论文没写，虽然我猜他们是猜的，但是确实是单调递增的。

考虑左式拆为如果这三部分均关于在上单调递增，那么在上单调递增。

首先，，两部分都是关于的多项式函数，因为指数部分都是常数。考虑（为一常数）在上单调递减，则在上单调递增成立，因此第一部分在上单调递增成立。

第二部分和第三部分形式类似。对于第二部分，考虑的倒数和的倒数考虑函数其中，我们想知道它在上的单调性。

对求导其中，在上恒成立，考虑在上的取值，继续求导。在上恒成立，因此在上单调增，也就是成立，因此在上恒成立，在上单调增。因此和在上均单调增。

那么由于和均单调增，那么它们的并联函数也单调增，因此第二部分也单调增。

设和均为单调增函数，且和均不为，现在考虑它们的并联函数求导由于和均单调增，那么和均大于，因此成立，即单调增。

对于第三部分，类似考虑的倒数和的倒数都把分母中的部分除上去，得到类似下面的函数其中。由于求导十分麻烦，因此在处对分子 Taylor 展开则观察前系数，分奇偶讨论，可以得出系数均为正。因此对展开式求导，可知大于 0 恒成立。

考虑函数求导得到分析当时的各项符号：

由于的取值范围是，当时，所有的都是负数。

在的求和公式中，每一项都是从个负数因子中抽掉了一个，因此每一项恰好是个负数的乘积。

因此，当为偶数时，恒成立，函数在负半轴上单调递增。当为奇数时，恒成立，函数在负半轴上单调递减。

类似第二项分析并联函数，第三项同样单调递增。至此，可以证明原式单调递增。

回顾原式当取时，左式小于右式，取时，左式大于右式，因此在上有唯一不动点，这使得队列长度也存在唯一不动点。

在收敛性一节中证明了每条流的不动点是，接下来估计的大小。由于通常非常接近 0，因此考虑在处 Taylor 展开，忽略。

实际上只展开了到忽略的是。原论文大小还打错了。

考虑，因此

由于非常接近 0，因此同样忽略了和中的部分（指某个常数）。

代入原式化简代入，化简得

收敛性

收敛性的详细证明在 CoNEXT 论文的 3.3 节，是分析多次一次降速后的多次升速过程，通过证明任意两条流之间的速率差随时间指数级别减小来说明多条流可以收敛，最后推导出收敛至公平。但是需要特别注意的是，分析过程中仅存在计时器引导的升速，而不存在字节计数器引导的升速。

需要注意的是，字节计数器引导的升速是乘性增。根据前面的公式是可以算出关于的关系的，但由于我已修为尽失所以只能问 Gemini。

考虑不触发 CNP 且仅有字节计数器影响时，每发送字节触发一次升速，两次触发升速之间的时间为，对和类似求导上下两式相除，得这是一个一阶线性常微分方程，求解得到由于，因此后一项趋近于 0，因此。那么考虑速率从开始上升这一过程，实际上在最初主要起作用的是计时器，因为速率很低，升速计时器触发时发送字节数还没有达到，因此在最初还是进行加性增，直到一计时器时间间隔内发送数据量大于等于，则此时开始的发送速率为，之后的增速由字节计数器驱动，因此后面的增速过程可以表达为

也就是说这个乘性增只在增速到一定程度后才起作用，此时可能网络空闲带宽很多，需要快速探测带宽，这样的设计倒也是有其合理性。

问题

我一直觉得流体模型不适用网络分析，分析一般流体（比如水流）的时候是可以微分的，但是分析网络数据的时候，分析对象没办法对时间微分，因为数据都是以包为单位传输的，这样在求极限的时候显然就爆炸了，比如在时间内即使就发了一个包，求出的所谓「速率」也是一个极吊诡的值，是没有物理意义的。说到底，所有的发送速率都是一种平均速率，在微观层面分析的时候只有两个包之间的发送间隔是有意义的，但是对于整体分析并无帮助。在选择符号方面，应该避免使用微分，而应该选择平均速率，变化率等表达，并且不能求极限。

那网络分析应该怎么分析，包传输过程是量子化的，但量子理论里似乎也没啥可借鉴的东西。所以与其微积分不如简单一点，用平均变化率表达，这样符号也对物理意义也有，但是能分析出啥就不知道了。