从FAST TCP到POWERTCP

 POWERTCP[1]的拥塞窗口控制规则是从FAST TCP[2]发展来的，有一些不错的理论分析。
 本博客涉及的公式，来自不同的论文，在不同的语境下，相同的符号含义不同。
 根据论文[2]的分析，AIMD的拥塞窗口的动态变化，可以总结为：
$$\dot{w}(t)=k_i(t)(1-\frac{q_i(t)}{u_i(t)})\text{\hspace{1em}(1)}$$

• $k_i(w_i,T_i)$描述的是算法的响应性——窗口的增长速度（the choice of the gain function determines the dynamic properties such as stability and responsiveness, but does not affect the equilibrium properties）。
• $u_i(w_i,T_i)$描述的算法的收敛特性（ the choice of the marginal utility function determines equilibrium properties such as the equilibrium rate allocation and its fairness）。
• $q_i$是算法使用的拥塞控制信号（in the absence of explicit feedback, the choice of congestion measure $q_i$ s limited to loss probability or queueing delay）。
   博客[3]推导了AIMD算法的随机微分方程（$I=\frac{1}{w},D=\frac{w}{2}$）。
  x ˙ = 1 r t t Δ w Δ t = w r t t 2 { I ( 1 − p ) − D p } = x r t t { I ( 1 − p ) − D p } (2) \dot x=\frac{1}{rtt}\frac{\Delta w}{\Delta t}=\frac{w}{rtt^2}\{I(1-p)-Dp\}=\frac{x}{rtt}\{I(1-p)-Dp\}\tag{2} x˙=rtt1​ΔtΔw​=rtt2w​{I(1−p)−Dp}=rttx​{I(1−p)−Dp}(2)
   整理为公式(1)的形式($1-p\approx 1$)：
  $$\dot{w}=\frac{\Delta w}{\Delta t}=\frac{w}{rtt}(I-Dp)=\frac{wI}{rtt}(1-\frac{Dp}{I})$$
   当$\dot{x}=0$,即$I(1-p)\approx Dp$,可以求得算法在均衡点的吞吐量：
  $$x=\frac{1}{rtt}\sqrt{\frac{1-p}{p}}\text{\hspace{1em}(3)}$$
   FAST TCP的拥塞控制规则：
  w ( t + δ t ) ← min ⁡ { 2 w ( t ) , ( 1 − γ ) w ( t ) + γ ( b a s e R T T R T T w ( t ) + α ) } (4) w(t+\delta t)\gets \min\{2w(t),(1-\gamma)w(t)+\gamma(\frac{baseRTT}{RTT}w(t)+\alpha)\}\tag{4} w(t+δt)←min{2w(t),(1−γ)w(t)+γ(RTTbaseRTT​w(t)+α)}(4)
   先不考虑$2w(t)$的约束项，整理一下上式：
  $$w(t+\delta t)\leftarrow w(t)+\gamma (\alpha -\frac{RTT-baseRTT}{RTT}w(t))\text{\hspace{1em}(5)}$$
   其中$q=RTT-baseRTT$描述的链路的缓冲区占用情况。当q较小的时候，$\alpha -\frac{q}{RTT}w(t)\ge 0$，FAST TCP增加窗口值。当q较大的时候，FAST TCP减少窗口值。当$\alpha -\frac{q}{RTT}w(t)=0$，求得算法在均衡点达到的理论吞吐量：
  $$x=\frac{\alpha }{q}\text{\hspace{1em}(6)}$$
   FAST TCP和Vegas在均衡点的理论吞吐量相同（ FAST TCP has the same equilibrium properties as TCP Vegas）[4][5]。博客[4]中的$\alpha$的单位是毫秒，本文的$\alpha$的单位是数据包增量。
   公式(5)可以不太严谨地整理为公式(1)的形式。
  $$\dot{w}=\frac{w(t+\delta t)-w(t)}{\delta t}=\frac{\gamma \alpha }{\delta t}(1-\frac{q}{\alpha \times rtt/w})\text{\hspace{1em}(7)}$$
   POWERTCP的拥塞控制规则，是FAST TCP的扩展：
  $$w_i(t+\delta t)\leftarrow \gamma (w_i(t)\frac{e}{f(t)}+\alpha )+(1-\gamma )w_i(t)\text{\hspace{1em}(8)}$$
   $f(t)$是从网络中获取的拥塞信号，$e$是某种常量（拥塞控制算法意图靠近的值）。将其整理为公式(1)的形式：
  $$\dot{w}=\frac{w(t+\delta t)-w(t)}{\delta t}=\frac{\gamma \alpha }{\delta t}(1-\frac{f(t)-e}{\alpha \times f(t)/w})\text{\hspace{1em}(9)}$$
   论文在附录中有几个论断：
• 当$e=B\times T，f(t)=q_{len}+B\times T$，当$\gamma =1$的时候，公式(8)反映的是HPCC[6]的拥塞控制规则（不完全相同，缺少$\eta$）。
• 当 $e=1，f(t)=\frac{\dot{q}}{B}+1$，即算法采用时延梯度作为网络拥塞信号。公式(8)可以重写为$w_i(t+\delta t)\leftarrow w(1-\frac{\gamma }{\dot{q}+B}\dot{q})+\gamma \alpha$。忽略分母中的$\dot{q}$项，公式(8)大致反映的是TIMELY[7]的拥塞控制规则。
   根据拥塞控制信号的不同，作者将现有的拥塞控制算法划分为两类：voltage-based CC和current-based CC。voltage-based CC的拥塞信号是网络中的绝对值（loss，delay，ECN），而current-based CC的拥塞信号是网络中的梯度值（rtt gradient）。网络的电压值定义为BDP和缓冲区长度的和，电流值与网络中流速率 ($\lambda$) 相关。网络缓冲区占用长度可以表示为$\dot{q}=({\sum }_i{\lambda }_i)-B=\lambda -B$。
   论文中给出了一个表格。

 PowerTCP就是一种基于功率的拥塞控制算法，定义$\Gamma$函数作为网络拥塞信号。
$$f(t)=\underset{\text{Power}}{\underbrace{\Gamma (t)}}=\underset{\text{Voltage}}{\underbrace{(q+B\times \tau )}}\times \underset{\text{Current}}{\underbrace{\lambda }}\text{\hspace{1em}(10)}$$

 算法定义$e=B^2\tau$。PowerTCP定义的拥塞信号需要网络路由设备反馈信息，是一种应用于数据中心的拥塞控制算法。而其扩展版本$\theta -PowerTCP$可以不依赖这些信息。
$$\frac{e}{f}=\frac{B^2\tau }{(q+B\times \tau )\times (\dot{q}+B)}=\frac{\tau }{(q/B+\tau )\times (\dot{q}/B+1)}\text{\hspace{1em}(11)}$$
其中，$RTT(t)=\frac{q(t)}{B}+\tau$，对其求导，可得$\dot{R}TT(t)=\frac{\dot{q}(t)}{B}$。RTT和RTT的梯度可以在终端侧估计。
 效果如何？我没有做仿真实验，不做评价。

Reference
[1] POWERTCP: Pushing the Performance Limits of Datacenter Networks
[2] FAST TCP: motivation, architecture, algorithms, performance
[3] AIMD吞吐量公式的推导
[4] tcp拥塞控制vegas的数学分析
[5] 漫谈TCP Vegas如何收敛到公平
[6] HPCC: high precision congestion control
[7] TIMELY: RTT-based Congestion Control for the Datacenter