真是难以置信,一有全都有。
刚说过,只要有不混部的条件,就不要混部不同的拥塞控制算法,能隔离 capacity-seeking\text{capacity-seeking}capacity-seeking 协议就隔离它,但我手欠,贱到不自觉就想让 DIPCC\text{DIPCC}DIPCC 和 AIMD\text{AIMD}AIMD 之间保持公平。
这事想着不难,既然时延是定值,那么发现时延增加就可以直接变身 AIMD\text{AIMD}AIMD 了,多么纯粹,一开始简单,后面全都不难。
但我还是想让 DIPCC\text{DIPCC}DIPCC 先往 AIMD\text{AIMD}AIMD 靠一下,结果,没想到更简单,只在原 ppp 跟踪基础上加一个乘性丢包衰减 β\betaβ,然后共同调 (β,p0,K)(\beta,p_0,K)(β,p0,K) 这个耦合三元组就够了,看一个 buffer=250\text{buffer=250}buffer=250 时的仿真结果(其它参数建议值见正文):

下面解释 why\text{why}why.
先简单回顾纯 DIPCC\text{DIPCC}DIPCC 的不动点。纯 DIPCC\text{DIPCC}DIPCC 流 iii 的窗口更新方程为:
wi(t+1)=(1−K)wi(t)+Kαp(t)+p0w_i(t+1) = (1-K) w_i(t) + \dfrac{K\alpha}{p(t)+p_0}wi(t+1)=(1−K)wi(t)+p(t)+p0Kα
稳态条件 wi(t+1)=wi(t)=w∗w_i(t+1)=w_i(t)=w^*wi(t+1)=wi(t)=w∗ 给出:
w∗=αp∗+p0,Nw∗=Cw^*=\dfrac{\alpha}{p^*+p_0}, \qquad N w^*=Cw∗=p∗+p0α,Nw∗=C
所有 DIPCC\text{DIPCC}DIPCC 流收敛到同一窗口 w∗w^*w∗,且 Q∗=Nw∗=CQ^*=Nw^*=CQ∗=Nw∗=C 对应的排队时延 p∗=Q∗T0Cp^*=\dfrac{Q^*T_0}{C}p∗=CQ∗T0 满足 Q∗<BQ^*<BQ∗<B,即固定时延,零丢包,这是纯 DIPCC\text{DIPCC}DIPCC 自身的稳定不动点。
现在考虑加入 Reno\text{Reno}Reno 后发生的事。
设瓶颈中有 DDD 条 DIPCC\text{DIPCC}DIPCC 流和 RRR 条 Reno\text{Reno}Reno 流,Reno\text{Reno}Reno 的更新规则为:
wr(t+1)={wr(t)+1,无丢包0.5 wr(t),有丢包w_r(t+1)=\begin{cases}w_r(t)+1, & \text{无丢包}\\0.5\,w_r(t), & \text{有丢包}\end{cases}wr(t+1)={wr(t)+1,0.5wr(t),无丢包有丢包
Reno\text{Reno}Reno 等 AIMD\text{AIMD}AIMD 必然周期性把 buffer\text{buffer}buffer 打满产生丢包,最终 Q>BQ>BQ>B 总会溢出。
设稳态下每 RTT\text{RTT}RTT 发生丢包的概率为 λ\lambdaλ,纯 DIPCC\text{DIPCC}DIPCC 对丢包无记忆,它便要抢占 AIMD\text{AIMD}AIMD 丢包后腾出的 buffer\text{buffer}buffer,现为其引入一个响应因子 β\betaβ,即丢包后,DIPCC\text{DIPCC}DIPCC 的窗口为 β⋅w\beta\cdot wβ⋅w,以此分析。
如果 DIPCC\text{DIPCC}DIPCC 不响应丢包,即 β=1\beta=1β=1,它的窗口只由 ppp 决定,对 DIPCC\text{DIPCC}DIPCC 流取期望,即对丢包事件取平均:
E[Δwd]=(1−λ)K(wd∗−wˉd)+λ(β−1)wˉd⏟=0whenβ=1=0\mathrm{E}[\Delta w_d] = (1-\lambda)K(w_d^*-\bar{w}_d)+\underbrace{\lambda(\beta-1)\bar{w}_d}_{=0 \text{when}\beta=1}=0E[Δwd]=(1−λ)K(wd∗−wˉd)+=0whenβ=1λ(β−1)wˉd=0
解得:
wˉd=wd∗=αp+p0\bar{w}_d = w_d^* =\dfrac{\alpha}{p+p_0}wˉd=wd∗=p+p0α
对 Reno\text{Reno}Reno 流 jjj 同理:
E[Δwr]=(1−λ)⋅1+λ(0.5−1)wˉr=0\mathrm{E}[\Delta w_r] = (1-\lambda)\cdot 1 + \lambda(0.5-1)\bar{w}_r=0E[Δwr]=(1−λ)⋅1+λ(0.5−1)wˉr=0
wˉr=2(1−λ)λ≈2λ(λ≪1)\bar{w}_r=\dfrac{2(1-\lambda)}{\lambda} \approx \dfrac{2}{\lambda} \quad (\lambda \ll 1)wˉr=λ2(1−λ)≈λ2(λ≪1)
由于 DIPCC\text{DIPCC}DIPCC 的 wˉd\bar{w}_dwˉd 只取决于当前排队时延 ppp,而 ppp 是队列水平的函数,当 Reno\text{Reno}Reno 溢出 buffer\text{buffer}buffer 丢包时,队列被截断到 BBB,p=BT0Cp=\dfrac{BT_0}{C}p=CBT0 确实高,wd∗w_d^*wd∗ 下降,但丢包后队列开始快速排空,ppp 迅速下降,DIPCC\text{DIPCC}DIPCC 的 wd∗w_d^*wd∗ 回升,这就是 DIPCC\text{DIPCC}DIPCC 对拥塞没记忆。
而 $\text{Reno} 每次丢包后窗口降到一半,需要 wˉr\bar{w}_rwˉr 轮增长才恢复,这段恢复期内 DIPCC\text{DIPCC}DIPCC 一直占着高位窗口,wˉdwˉr≈1.3∼1.5\dfrac{\bar{w}_d}{\bar{w}_r}\approx 1.3 \sim 1.5wˉrwˉd≈1.3∼1.5,DIPCC\text{DIPCC}DIPCC 多占 30%–50%30\%–50\%30%–50%.
现在定量分析一般 β\betaβ 时的情形,DIPCC\text{DIPCC}DIPCC 的更新规则为:
wi(t+1)={(1−K)wi(t)+Kαp(t)+p0,无丢包β wi(t),有丢包w_i(t+1)=\begin{cases}(1-K)w_i(t) + \dfrac{K\alpha}{p(t)+p_0}, & \text{无丢包} \\[6pt]\beta\, w_i(t), & \text{有丢包}\end{cases}wi(t+1)=⎩⎨⎧(1−K)wi(t)+p(t)+p0Kα,βwi(t),无丢包有丢包
对 DIPCC\text{DIPCC}DIPCC 流取期望平衡:
E[Δwd]=(1−λ)K(wd∗−wˉd)+λ(β−1)wˉd=0\mathrm{E}[\Delta w_d] = (1-\lambda)K(w_d^* - \bar{w}_d) + \lambda(\beta-1)\bar{w}_d = 0E[Δwd]=(1−λ)K(wd∗−wˉd)+λ(β−1)wˉd=0
解得:
wˉd=(1−λ)K(1−λ)K+λ(1−β)⋅αp+p0\bar{w}_d = \dfrac{(1-\lambda)K}{(1-\lambda)K + \lambda(1-\beta)} \cdot \dfrac{\alpha}{p+p_0}wˉd=(1−λ)K+λ(1−β)(1−λ)K⋅p+p0α
当 β=1\beta = 1β=1 时,即无丢包响应:
wˉd=(1−λ)K(1−λ)K⋅wd∗=wd∗\bar{w}_d =\dfrac{(1-\lambda)K}{(1-\lambda)K}\cdot w_d^* = w_d^*wˉd=(1−λ)K(1−λ)K⋅wd∗=wd∗
DIPCC\text{DIPCC}DIPCC 完全不受丢包影响,只跟随 ppp,恢复过快会对 AIMD\text{AIMD}AIMD 不公平。
当 β=0.5\beta = 0.5β=0.5 时:
wˉd=(1−λ)K(1−λ)K+0.5λ⋅wd∗\bar{w}_d = \dfrac{(1-\lambda)K}{(1-\lambda)K + 0.5\lambda}\cdot w_d^*wˉd=(1−λ)K+0.5λ(1−λ)K⋅wd∗
λ≈0.05\lambda \approx 0.05λ≈0.05 为典型混合场景丢包率,设 K=0.08K=0.08K=0.08:
(0.95)(0.08)(0.95)(0.08)+0.5(0.05)=0.0760.101≈0.75\dfrac{(0.95)(0.08)}{(0.95)(0.08)+0.5(0.05)}=\dfrac{0.076}{0.101} \approx 0.75(0.95)(0.08)+0.5(0.05)(0.95)(0.08)=0.1010.076≈0.75
DIPCC\text{DIPCC}DIPCC 被压到目标窗口的 75%75\%75%,可能被 Reno\text{Reno}Reno 压制,而且,β=0.5\beta=0.5β=0.5 导致深度退避,队列排空,p→0p\to0p→0 ,wd∗w_d^*wd∗ 跑飞而自激振荡。
当 β=0.85\beta = 0.85β=0.85 时,这是一个更加温和的退避:
1−β=0.15,(1−λ)K(1−λ)K+0.15λ=0.0760.076+0.0075≈0.911-\beta = 0.15, \quad \dfrac{(1-\lambda)K}{(1-\lambda)K + 0.15\lambda}=\dfrac{0.076}{0.076+0.0075} \approx 0.911−β=0.15,(1−λ)K+0.15λ(1−λ)K=0.076+0.00750.076≈0.91
DIPCC\text{DIPCC}DIPCC 平均窗口约为目标窗口的 91%91\%91%,即:
wˉd≈0.91⋅αp+p0\bar{w}_d \approx 0.91 \cdot \dfrac{\alpha}{p+p_0}wˉd≈0.91⋅p+p0α
这情况下,Reno\text{Reno}Reno 流的平均窗口:
wˉr=2(1−λ)λ\bar{w}_r=\dfrac{2(1-\lambda)}{\lambda}wˉr=λ2(1−λ)
混部时的总负载平衡:
D wˉd+R wˉr=CD\,\bar{w}_d + R\,\bar{w}_r = CDwˉd+Rwˉr=C
将 wˉd\bar{w}_dwˉd 和 wˉr\bar{w}_rwˉr 代入:
D⋅(1−λ)K(1−λ)K+λ(1−β)⋅αp+p0+R⋅2(1−λ)λ=CD\cdot\dfrac{(1-\lambda)K}{(1-\lambda)K+\lambda(1-\beta)}\cdot\dfrac{\alpha}{p+p_0}+R\cdot\dfrac{2(1-\lambda)}{\lambda}=CD⋅(1−λ)K+λ(1−β)(1−λ)K⋅p+p0α+R⋅λ2(1−λ)=C
其中 p=QT0Cp=\dfrac{Q T_0}{C}p=CQT0,而 Q≈Dwˉd+Rwˉr−CQ \approx D\bar{w}_d + R\bar{w}_r - CQ≈Dwˉd+Rwˉr−C 为队列积累量。
wˉd\bar{w}_dwˉd 和 wˉr\bar{w}_rwˉr 都隐式依赖于 λ\lambdaλ,而 λ\lambdaλ 由总负载决定。通过选择 β=0.85\beta=0.85β=0.85,DIPCC\text{DIPCC}DIPCC 的退避因子 (1−β)=0.15(1-\beta)=0.15(1−β)=0.15 和 Reno\text{Reno}Reno 的退避因子 0.50.50.5 间建立了匹配:
- Reno\text{Reno}Reno 每次丢包损失 50%50\%50% 窗口,但恢复靠加性增长,慢但无限冲破缓冲区;
- DIPCC\text{DIPCC}DIPCC 每次丢包损失 15%15\%15% 窗口,但恢复靠比例跟踪 K(wd∗−wd)K(w_d^*-w_d)K(wd∗−wd),快但有约束;
DIPCC\text{DIPCC}DIPCC 的负反馈是,恢复得越快,队列积累越多,ppp 越高,wd∗w_d^*wd∗ 越低,趋向一个本身就随拥堵程度下调的目标。β\betaβ 不需匹配 Reno\text{Reno}Reno 的恢复速度,其核心是弥补比例跟踪太慢。
下面是一个 buffer=850\text{buffer}=850buffer=850 时的仿真结果:

无法获得更好的参数了,我暂时无法证明算法的不动点本身在哪怕一组参数下的稳定性,准备后面用 AI\text{AI}AI 协助一下。
只见更大的缓冲区破坏了公平性,reno\text{reno}reno 的平均窗口由于 λ\lambdaλ 决定,间接就是缓冲区大小决定,因此 DIPCC\text{DIPCC}DIPCC 被压制。
α\alphaα 决定队列深度,Q=NαT0−p0CT0Q=\dfrac{N\alpha}{T_0}-\dfrac{p_0 C}{T_0}Q=T0Nα−T0p0C, 混部场景下 ppp 由 Reno\text{Reno}Reno 推高,要让 wd∗≈CNw_d*\approx \dfrac{C}{N}wd∗≈NC 公平值,需要调 α\alphaα。
此外,期望平衡中 DIPCC\text{DIPCC}DIPCC 平均窗口为 wˉd=(1−λ)K(1−λ)K+λ(1−β)wd∗\bar{w}_d = \dfrac{(1-\lambda)K}{(1-\lambda)K+\lambda(1-\beta)} w_d^*wˉd=(1−λ)K+λ(1−β)(1−λ)Kwd∗,β=0.85\beta=0.85β=0.85 时 DIPCC\text{DIPCC}DIPCC 被拉低,因此需要调高 β\betaβ,才使结果更接近公平目标。
下面是一个比 250250250 更小缓冲区的仿真结果:

总之,调参规律是,α∝p\alpha\propto pα∝p,buffer\text{buffer}buffer 越大,排队时延越高,需要越大的 α\alphaα 让 w∗=αp+p0w^*=\dfrac{\alpha}{p+p_0}w∗=p+p0α 维持在合理窗口,β∝(1−λ)\beta\propto (1 - \lambda)β∝(1−λ),buffer\text{buffer}buffer 越小丢包越频繁,β\betaβ 越要接近 Reno\text{Reno}Reno 的 0.50.50.5,大 buffer\text{buffer}buffer 低丢包时 β\betaβ 可以高到 0.9x\text{0.9x}0.9x。
不管怎样,在一个全局可控尺度的网络,如 DCN\text{DCN}DCN,这一切都是确定的,经理一句话,就可以全网统一。
DIPCC\text{DIPCC}DIPCC 加入 β<1\beta<1β<1 后仍需验证稳定性。
DIPCC\text{DIPCC}DIPCC 的不动点方程为:
f(w)=(1−λ)K (αp(w)+p0−w)−λ(1−β)w=0f(w)=(1-\lambda)K\!\left(\dfrac{\alpha}{p(w)+p_0}-w\right)-\lambda(1-\beta)w=0f(w)=(1−λ)K(p(w)+p0α−w)−λ(1−β)w=0
其中 p(w)=Dw+RwrCT0p(w)=\dfrac{D w + R w_r}{C}T_0p(w)=CDw+RwrT0 是关于 www 的增函数。
对 www 在不动点处求导:
f′(w)=(1−λ)K (−α(p+p0)2T0C−1)−λ(1−β)f'(w) = (1-\lambda)K\!\left(-\dfrac{\alpha}{(p+p_0)^2}\dfrac{T_0}{C} - 1\right) - \lambda(1-\beta)f′(w)=(1−λ)K(−(p+p0)2αCT0−1)−λ(1−β)
两项均负,系统的稳定性由离散更新方程 wt+1=wt+f(wt)w_{t+1} = w_t + f(w_t)wt+1=wt+f(wt) 的雅可比矩阵决定,要求 ∣1+f′(w∗)∣<1|1+f'(w^*)| < 1∣1+f′(w∗)∣<1。
由于 f′(w∗)<0f'(w^*) < 0f′(w∗)<0,且 ∣f′(w∗)∣|f'(w^*)|∣f′(w∗)∣ 的量级为 K≈0.08K \approx 0.08K≈0.08,远小于 111,∣1+f′(w∗)∣≈1−0.08<1|1+f'(w^*)| \approx 1-0.08 < 1∣1+f′(w∗)∣≈1−0.08<1,这算法本质上就是一个一阶负反馈,系统自动稳定。
结论很简洁,即在纯 DIPCC\text{DIPCC}DIPCC 的比例跟踪基础上,仅增加乘性丢包衰减:
wi←β wi(丢包时)w_i \leftarrow \beta\, w_i \quad (\text{丢包时})wi←βwi(丢包时)
选择 β∈(0.8,0.9)\beta \in (0.8, 0.9)β∈(0.8,0.9),即可使混部 DIPCC+Reno\text{DIPCC}+\text{Reno}DIPCC+Reno 系统收敛到近似公平的稳态,且纯 DIPCC\text{DIPCC}DIPCC 子系统保持零振荡。
依旧不需要流间通信,不需要知道 NNN,不需要路由器反馈,甚至不需要区分同构异构流,每个 DIPCC\text{DIPCC}DIPCC 流只测量自己的 RTT\text{RTT}RTT,检测丢包,执行一个简单方程,就自动完成了公平收敛。
再看下算法外,所有流整体的链路利用率,稳态时队列稳定 Q(t+1)=Q(t)Q(t+1)=Q(t)Q(t+1)=Q(t),故:
Q−C+Nw∗=Q ⟹ Nw∗=CQ - C + N w^* = Q \implies N w^* = CQ−C+Nw∗=Q⟹Nw∗=C
即:
∑iwi∗=C=120\sum_i w_i^*=C=120∑iwi∗=C=120
结合代价关系 p∗=Q∗CT0=Nw∗⋅T0Cp^* = \dfrac{Q^*}{C}T_0 = N w^* \cdot \dfrac{T_0}{C}p∗=CQ∗T0=Nw∗⋅CT0,代入不动点:
w∗=αNw∗T0C+p0w^* = \dfrac{\alpha}{\dfrac{N w^* T_0}{C} + p_0}w∗=CNw∗T0+p0α
整理得二次方程:
NT0C(w∗)2+p0w∗−α=0\dfrac{N T_0}{C}(w^*)^2 + p_0 w^* - \alpha = 0CNT0(w∗)2+p0w∗−α=0
唯一正解:
w∗=−p0+p02+4αNT0/C2NT0/Cw^* = \dfrac{-p_0 + \sqrt{p_0^2 + 4\alpha N T_0 / C}}{2 N T_0 / C}w∗=2NT0/C−p0+p02+4αNT0/C
验证仿真参数,α=5000, p0=30, T0=100, C=120\alpha=5000,\; p_0=30,\; T_0=100,\; C=120α=5000,p0=30,T0=100,C=120,理论和实际值均可接近 C=120C=120C=120。
裤衩子锁着边儿,而且绣着花儿。
算法比之前的 v1\text{v1}v1 版多个分支罢了:
测量 RTT_i
if 收到丢包信号:
w[i] = beta * w[i]
else:
RTT_min[i] = min(RTT_min[i], RTT_i)
p = RTT_i - RTT_min[i]
w_target = alpha / (p + p0)
w[i] = w[i] + K * (w_target - w[i])
w[i] = max(2, w[i])
当然,还有一种更加非学术的算法与 AIMD\text{AIMD}AIMD 共存,即用一个低通滤波器约束的 RTT\text{RTT}RTT 测量,发现升高即变身为 AIMD\text{AIMD}AIMD,这里的隐式假设是,纯 DIPCC\text{DIPCC}DIPCC 流的 RTT\text{RTT}RTT 不变。
浙江温州皮鞋湿,下雨进水不会胖。
转载自 CSDN-专业IT技术社区



