基于多尺度分层改进FAST TCP公平性算法研究

曾凌静

摘  要： FAST TCP传输延时的估计是一个有待解决的问题。针对该关键问题，提出一种多尺度分层改进算法。在第一层，以较小的时间尺度动态记录当前类FAST TCP流的启动时间、运行时间和往返延时等状态信息;在第二层，以较大的尺度计算平均排队延时。当新的FAST TCP流到达时，根据当前往返延时和第二层算法提供的平均排队延时估计本时间周期传播延时，在没有外部测量设备参与和网络支持的情况下，实现高精度的传播延时估计。NS-2仿真结果验证了改进算法的有效性。

关键词： FAST TCP; 传播延时; 公平; 分层; 多尺度

中图分类号： TP393          文獻标志码： A          文章编号： 1671-2153（2019）03-0105-04

0  引言

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

文献[4-5]解释了这种不准确估测导致FAST的不公平性，并表明：通过在每个流优先级中给出第一个包来改进这种估测，可以提高公平性并减少排队变化。文献[6]指出，只有在每个流对其真正的传播延时进行准确估计时，FAST才能实现公平性，除非有网络支持，比如允许探测包绕过队列，但获得真正传播延时的唯一方法是让队列清空。因此，Tony Cui建议对每个新启动的流进行简单的节流以清空队列，从而获得传播延时的可靠估计。文献[7]提出的方法无法保证队列会被清空，所以无法获得精确的传播延时。文献[8]提出了一种新的解决方案，它不依赖于直接测量传播延时;相反，通过调整传输速率，源端能够计算出估计往返传输延时的误差，从而与其他FAST TCP流均匀地共享链路。但文献[7]表明，这种方法只有在新的FAST到达时才有效，因为FAST对往返传播延时的估计不准确，当多个FAST到达一个瓶颈链路时，会出现不公平现象。虽然FAST不能直接通信，但该改进算法充分利用源端信息，获得同步回退时钟和最小回退因子，然后通过该算法使新旧流同时降低发送速率，最后，链路缓冲区队列快速变为空队列，从而快速估计真实的传播延时。通过这种改进后的方法，能够获得较高的传播延时估计精度和较好的新老流之间的公平性，但是这种方法需要牺牲FAST系统的一些稳定性。

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

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

针对FAST单向加速的特点，本文提出了一种新的多尺度分层算法。在第一层，以较小的时间尺度动态记录当前类FAST TCP流的启动时间、运行时间和往返延时等状态信息。在第二层，以较大的尺度计算本尺度周期的平均排队延时。当新的FAST TCP流到达时，根据当前状态的RTT和这个大尺度的平均排队延时估计传播延时，在没有外部测量设备参与和网络支持的情况下，实现了高精度的传播延时估计。

1  FAST TCP单向加速系统描述

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

对于FAST TCP连接i，有：发送端发送拥塞窗口（包）Wi（t）;FAST TCP流传播时延baseRTT di;瓶颈链路L1-L2队列排队延时qi（t）;FAST TCP流往返延时RTT Di（t），其中Di=di+qi（s）;FAST TCP流速率xi（t）（数据包/秒），xi（t）=wi（t）/Di（t）;FAST TCP流协议参数（数据包）αi;比例增益协议参数gi;瓶颈链路L1-L2链路容量（数据包/秒）c;FAST TCP流窗口更新周期T（秒）。

FAST TCP流根据传播延时baseRTT和往返延时定期更新拥塞窗口的伪代码是：

2  不公平性仿真验证

考虑到FIFO（first in first out）调度下的FAST TCP 流发送，在图1所示的网络拓扑上运行NS-2仿真，链路容量和传播时延见图1。如图2所示，使用一个FAST TCP 发送器和三对接收器（S1-D1，S1-D2，S1-D3），每对创建10个具有不同活动周期的FAST流。在0到1000的时间段在S1-D1的链路上创建10个FAST TCP流。在150-600 s在S1-D2链路上创建10个FAST TCP 流，在400 s到1000 s之间在S1-D3链路上创建10个FAST TCP流。

把每个FAST TCP流的协议参数设置为αi=50，增益参数gi=0.5，假设每个包大小设置为1K字节。

假设路由器的缓冲区足够大，可以避免数据包丢失，并且FAST TCP源端总是有数据要发送。仿真结果如图3所示。

从图3可见，在0到150 s，S1-D1先创建的10条FAST TCP流能够准确地估计瓶颈链路L1-L2的传播延时，因此可以公平地分配带宽。在150 s到400 s之间，S1-D2中创建的10条FAST TCP流，在队列无法清空的情况下，无法获得准确的传播延时。从图3看见，后面10条创建的FAST TCP 流估计的传播延时比S1-D1链路的10条连接要大，估计排队延时就小，因此比S1-D1链路的FAST TCP流获得了更多的带宽，从而使得各FAST TCP 流失去了公平性。同理，400 s到600 s之间，S1-D3又产生10条FAST TCP流，参与竞争带宽，同理，后面产生的FAST TCP 流 比前400 s的FAST TCP流获得了更多的带宽。到600 s后，由于S1-D2的FAST TCP流结束了发送包，队列瞬间出现的清空现象，S1-D1和S1-D3的活跃的FAST TCP流有机会估计了准确的传播延时，从而600 s后，活跃的FAST TCP流能够公平的竞争带宽，仿真验证了上述分析的准确性。

3  改进后FAST算法描述

为了快速准确地估计传播延时，根据NS-2仿真结果，对改进后的算法进行分析。

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

在第一层算法，FAST TCP 流增加了启动时间和运行时间两个参数。当FAST TCP到达时，小时间尺度记录每个FAST TCP流启动时间、运行时间、往返延时RTT和传播延时baseRTT。第二层算法，大时间尺度统计这个时间尺度内平均排队延时，即平均排队延时等于往返延时减去传播延时。当有新的FAST到达时，第二层算法可以为当前FAST TCP流提供本时间尺度平均的排队延时。在计算传播延时时，根据当前的往返延时减去第二层算法提供的平均排队延时来估计准确的传播延时。

算法1：

在原有FAST基础上做了如下改进：

第一层算法，对于每个活动的FAST TCP 流i，每小时间尺度，记录当前排队时延qi，now;FAST TCP 流i的建立开始时间ti，start和运行时间ti，time。

根据ti，start判断确定本小时间尺度时间内最早建立的FAST TCP排队延时qi，now作为本小时间尺度瓶颈链路排队延时。

第二层算法，大时间尺度统计瓶颈链路平均排队延时qi，now，平均排队延时等于各个小时间尺度（根据ti，start和ti，time）内统计的各个排队延时的平均值。

当新的FAST TCP流j建立时，按公式（2）计算传播延时。

定理1：在如图1所是的单向加速网络模型，多尺度分层改进的FAST TCP算法1能够使得每个活跃FAST TCP流计算出精确的传播延时。

证明：用数学归纳法证明。

当i=1时，瓶颈链路路由器的队列为空，因此第一个FAST可以获得准确的传播延时。

当i=2，第一个FAST获得准确的传播延时， 第2层算法可以准确计算当前的瓶颈环节排队延时。第二个FAST可以根据根据当前的往返延时减去排队延时，从而计算准确的传播延时。

假设这个结论对于i-1是正确的，现有的i-1个FAST TCP流已經建立了精确的传播延时。

当新的FAST到达时，第2层算法可提供本时间尺度内平均的排队延时。因为之前的传播延时都准确，所以排队延时也是准确的。现有的i-1个FAST已经建立了精确的传播延时qnow，上层算法就可以提供准确的队列延时，因此第i个FAST可以利用算法1计算出精确的传播延时。

4  模拟仿真

以下给出了一组NS-2仿真结果，验证了改进的公平性算法1的有效性。对“不公平性仿真验证”中考虑的相同环境进行了仿真，结果如图4所示。

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

5  结论

根据FAST的单向应用中各FAST TCP具有共享一些信息特点，提出了一种新的多尺度分层算法。在第一层，以较小的时间尺度收集活动的FAST TCP流的历史信息，如启动时间、运行时间、排队延时等。在第二层算法大尺度计算平均排队延时。这样，当有新的FAST到达时，可以根据第二层算法提供的准确排队延时计算传播延时，从而是以当前估测的往返延时与计算的传播延时之差作为瓶颈链路的排队延时。仿真结果表明，在没有外部测量设备参与和网络支持的情况下，该算法可以提高TCP系统的公平性。

参考文献：

[1] 袁晓华，洪小飞. FAST TCP模型的稳定性[J]. 西安文理学院学报（自然科学版），2017，31（5）：53-59.

[2] ZHANG H，CHEN L，BAIREN Y，et al. CODA：Toward Automatically Identifying and Scheduling Coflows in the Dark[C]//Proceedings of the 2016 ACM SIGCOMM Conference. New York：ACM，2016：160-173.

[3] CHEN L，CHEN K，BAI W，et al. Scheduling Mix-flows in Commodity Datacenters with Karuna[C]//Proceedings of the 2016 ACM SIGCOMM Conference. New York：ACM，2016：174-187.

[4] CHEN Xiaolong，ZHANG Yun，LIU Z. Less conservative global stability for nonlinear FAST TCP system with time-varying time-delay[J]. Control Theory & Applications，2012，29（4）：477-485.

[5] TAN L S，YUAN C， ZUKERMAN M. FAST TCP：Fairness and Queueing Issues[J]. IEEE  Communications Letters，2005，9（8）：762-764.

[6] CUI T，ANDREW L L H，ZUKERMAN M，et al. Improving the Fairness of FAST TCP to New Flows[J]. IEEE  Communications Letters，2006，10（5）：414-416.

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

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