基于历史流量的单向FAST TCP公平性改进算法研究

陈常晖 曾凌静

摘  要：FAST TCP传输延时的估计是一个有待解决的问题。针对这些开放性问题，根据FAST TCP的单向加速应用特点，本文提出了一种新的传输层两层算法。一个活动的FAST TCP流的历史信息，如启动时间、运行时间等，在底层被记录下来。当新的FAST TCP流到达时，上层算法可以根据最早的FAST TCP流提供瓶颈链路的当前队列延时。传播延时的计算是以当前估测的最小往返延时与传播延时之差作为瓶颈链路的排队延时。最后，NS-2仿真结果验证了改进的两层算法的有效性。

关键词：FAST TCP;传播延时;公平;历史流量信息

中图分类号：TP339     文献标识码：A

Abstract：It is an open problem for the FAST TCP to estimate the true propagation delay.Aiming at these open problems，according to unilateral accelerated application characteristic of FAST TCP，a new two-layer algorithm is proposed.In the lower layer，the history information of the active FAST TCP flows，such as the startup time and the running time etc.，are recorded.When new FAST TCP flows arrive，the upper layer algorithm can provide the current queue delay of the bottleneck link based on the earliest FAST TCP flow.For the first time in the calculation propagation delay，the lower layer FAST TCP algorithm estimates the accurate propagation delay based on the current round trip delay minus the queuing delay provided through the upper algorithm.Finally，the NS-2 simulation results verify the effectiveness of this improved two-layer algorithm.

Keywords：FAST TCP;propagation delay;fairness;historic flow information

1   引言（Introduction）

FAST TCP[1-3]是针对高速长延时网络提出的一种新的传输控制协议，它的目标是使网络运行更加稳定、高效、公平，它采用排队延时来估计网络拥塞状态。与丢包概率相比，排队延时提供了更好的拥塞估计，并能根据网络容量进行扩展。利用排队时延，确定窗口调整策略，使FAST TCP在高速长时延网络中实现高吞吐量。但众所周知，它们的均衡传输速率对估测的往返传播延时的精度和估计的排队延时都非常敏感[4-7]。FAST TCP的源发送窗口更新操作依赖于BaseRTT的参数，该参数用来估计往返传播延时（RTPD），是目前观察到的最小往返传输延时（RTT）。由于有时路由器队列永远不会清空，因此FAST TCP可能无法准确估计实际的传输延时，从而导致不公平性。然而，目前对FAST TCP公平性的研究还没有深入展开，这仍然是一个有待解决的问题。

2   现状分析（Current situation analysis）

在文献[4]中，Linasheng Tan解释了这种不准确估测导致FAST中的不公平性，并表明，通过在每个流优先级中给出第一个包来改进这种估测，可以提高公平性并减少排队变化。在文献[5]中，只有在每个流对其真正的传播延时进行准确估计时，FAST才能实现公平性。除非有网络支持，比如允许探测包绕过队列，否则获得真正传播延时的唯一方法是让队列清空。因此，Tony Cui建议对每个新启动的流进行简单的节流以清空队列，从而获得传播延时的可靠估计。在文献[6]中，Miguel发现这种方法并不总是有效的。Miguel表明，只有当竞争低值的往返传播延时超过文献[6]中的下限时，这种速率降低方法才有效，并且不能完全耗尽瓶颈队列，因此无法获得精确的传播延时拥塞。

于是，Miguel提出了一种新的解决方案，它不依赖于直接測量传播延时。相反，通过调整传输速率，源端能够计算出估计往返传输延时的误差，从而与其他FAST流均匀地共享链路。然而，在文献[7]中表明，这种方法只有在新的FAST到达时才有效。因为FAST对往返传播延时的估计不准确，当多个FAST到达一个瓶颈链路时，会出现不公平现象。虽然FAST不能直接通信，但该改进算法充分利用源端信息，获得同步回退时钟和最小回退因子，然后通过该算法使新旧流同时降低发送速率。最后，链路缓冲区队列快速变为空队列，从而快速估计真实的传播延时。通过这种改进后的方法，能够获得了较高的传播延时估计精度和较好的新老流之间的公平性，但是这种方法需要牺牲FAST系统的一些稳定性。

综上所述，对于FAST的开放性问题，目前还没有很好的解决方案。因此，我们希望通过FAST TCP商业应用找到解决这一开放问题的方法。

FASTSoft公司成立于2006年，是由美国国家科学基金会、美国国防高级研究计划局（DARPA）和思科公司资助，它在加州理工学院（Caltech）开发的一种突破性的网络优化技术，名为FAST TCPTM。FASTSoft的产品提高了网站和web应用程序的性能，并在不需要客户端软件或浏览器插件的情况下，加快了视频和其他数字内容在互联网上的分发速度。如图1所示，FASTSoft的E系列软件安装在现成的Dell服务器上，在没有客户端软件或浏览器插件的情况下，提供了最高级别的Internet性能和TCP加速。它使网络和应用程序透明地运行，并且安装迅速，因为不需要修改服务器或重写代码。从发送器到任意多个接收器的加速度是单向的。

针对FAST单向加速的特点，本文提出了一种新的传输层双层算法。在底层，以较小的时间尺度动态记录FAST TCP流的启动时间、运行时间等历史信息。当新的FAST TCP流到达时，上层算法根据最早活动FAST的传播延时，在没有外部测量设备参与和网络支持的情况下，实现了高精度的传播延时估计。由于采用了以上算法，解决了FAST不能同时收敛的问题[8]。

3   FAST TCP单向加速系统描述（Description of the FAST TCP unilateral accelerating system）

根据实际的网络模型，我们可以构建如图2所示的网络拓扑。图2中，假设S1为信源主机节点，D1、D2、…、DM为信宿主机节点。中间节点L1、L2构成瓶颈环节。信源主机、若干个相连接的链路和信宿主机组成一条路由。例如，S1- L1-L2-D1是一条路由。

对于FAST连接i，有：：发送端拥塞窗口大小（包）;：传播时延;：队列时延;：RTT，（s）;：速率（数据包/秒）;;：协议参数（数据包）;：协议参数;：链路容量（数据包/秒）;：窗口更新周期（秒）。

4   不公平性验证（Demonstration of unfairness）

考虑到FIFO调度下的FAST TCP流，我们在图2所示的网络拓扑上运行以下NS2仿真。链路容量和传播时延如图2所示。使用一个FAST TCP发送器和三个接收器（S1-D1，S1-D2，S1-D3），每对创建10个具有不同活动周期的FAST TCP流，如图3所示。

从图4可见，在150（s）和400（s）中，延迟连接的FAST TCP流高估了它的传播延迟，因为它的所有包都经历了显著的排队延迟，因此它的baseRTT太高。因此，对于早期加入FAST TCP流，它低估了排队延迟，这使得延迟连接流更具攻击性，从而获得更高的吞吐量。在600（s）中，当FAST TCP流离开路由2时，队列占用率下降，因此现有的FAST TCP流都得到真实的传播延迟，并获得瓶颈链路带宽的相等份额。

5  改进后的两层算法（Improved two-layer algorithm）

根据以上仿真结果，为了快速准确地估计传播延时，分析如下：

如图2所示，单向FAST TCP网络拓扑结构只有一个信源主机节点S1，因此所有活动的FAST TCP都可以相互通信，延时连接流可以充分利用历史流信息，快速准确地估测传播延时。

在底层，FAST TCP增加了启动时间和运行时间两个参数。当FAST到达时，每个参数都记录它的流启动时间并计算它的运行时间。上层算法总是为最早活动的FAST保存历史信息。当新的FAST到达时，上层算法可以为当前队列延时提供最早的启动时间和运行时间。在计算传播延时时，下层FAST算法首次没有用最小的往返估计传播延时，而是根据当前的往返延时减去上层算法提供的排队延时来估计准确的传播延时。改进后的算法实现如下：

6   虚拟仿真（Simulation）

将图4与图5进行比较，在150（s）和400（s）中，延迟连接的FAST TCP流用算法1估算精确的传播延迟，可以得到瓶颈链路带宽的相等份额。在600（s）中，当FAST TCP流离开路由2时，队列占用率下降，因此现有的FAST TCP流都得到真正的传播延迟，并获得瓶颈链路带宽的相等份额。

7   结论（Conclusion）

根据FAST的单向加速应用特点，提出了一种新的传输层两层算法。在底层，以较小的时间尺度收集活动的FAST的历史信息，如启动时间、运行时间等。當新的FAST到达时，上层算法可以根据最早的FAST提供瓶颈链路的当前队列延时。传播延时是以当前估测的最小往返延时与传播延时之差作为瓶颈链路的排队延时。仿真结果表明，在没有外部测量设备参与和网络支持的情况下，该算法可以提高TCP系统的公平性。

参考文献（References）

[1] 梁伟，张顺颐，宁向延，等.基于稳定性的FASTTCP参数γ调整[J].通信学报，2010，31（7）：53-59.

[2] David X.Wei，Cheng Jin，S.H.Low.FAST TCP：motivation，architecture， algorithms，performance[J].IEEE/ACM Transactions on Networking，2006，14（6）：1246-1259.

[3] Chen Xiao-long，Zhang Yun.Less conservative global stability for nonlinear FAST TCP system with time-varying time-delay[J].Control Theory & Applications，2012，29（4）：477-485.

[4] Liansheng Tan，Cao Yuan，Mosh Z.FAST TCP：Fairness and Queueing Issues[J].IEEE Communications Letters，2005，9（8）：762-764.

[5] Tony Cui，Lachlan，Liansheng Tan.Improving the Fairness of FAST TCP to New Flows[J].IEEE Communications Letters，2006，10（5）：414-416.

[6] Migule R，Sergio H.Achieving Fair Network Equilibria with Delay-based Congestion Control Algorithms[J].IEEE  Communications Letters，2008，12（7）：535-537.

[7] 陈晓龙，张云.基于历史特征的FAST TCP公平性改进算法[J].解放军理工大学学报，2010，27（4）：5-9.

[8] 陈静，郑明春.基于历史流量及其性能分析的拥堵控制算法[J].计算机研究与发展杂志，2003，40（10）：1470-1475.