《基于TCP拥塞控制的改进Backpressure算法》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

基于TCP拥塞控制的改进Backpressure算法

范文

占庆杰韩韧周好生

摘 ?要：本文研究了无线网络中在Backpressure算法路由调度下TCP数据流的性能表现，发现该算法无法有效提高网络吞吐量，原因是Backpressure算法基于队列差值的路由调度与TCP的拥塞控制机制之间的不匹配造成的。本文提出了一种适应于TCP数据流调度的改进Backpressure算法（T-BP），并从理论上证明了T-BP算法具有throughput-optimal 性能。仿真结果表明，在多种网络拓扑结构下，与传统BP算法相比，TCP数据流在吞吐量和公平性方面的性能得到了有效的提高。

关键词： Backpressure算法;TCP;最优吞吐量;公平性

中图分类号： TP393.03 ? ?文献标识码： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.013

本文著录格式：占庆杰，韩韧，周好生. 基于TCP拥塞控制的改进Backpressure算法[J]. 软件，2019，40（4）：6773

【Abstract】： In this paper， we discuss the performance of backpressure algorithm for TCP flows in wireless networks. We found that the algorithm cannot efficiently improve the network throughput. The reason is that there exists a conflict between the congestion control mechanism in TCP and the queue backlog differences in the backpressure algorithm. Consequently， we propose an improved backpressure algorithm that is efficient for TCP flows. Moreover， we prove that T-BP achieves the performance of throughput-optimal in theory. Simulation results confirm that T-BP has better throughput and fairness performance than the traditional backpressure algorithm in various network topologies.

【Key words】： Backpressure algorithm; TCP; Throughput-optimal; Fairness

0 ?引言

Backpressure算法（以下简称BP算法）是由Tassiulas和Ephremides提出的一種可以实现网络路由和调度的算法，能够动态高效的分配带宽资源[1]。网络中的每个节点会为经过该节点的数据流维持一个队列，通过计算得出各个网络节点与相邻可通信节点之间的最大队列差值，并把它赋为该对相邻节点之间的链路权值，再根据链路权值和干扰模型，进一步得出具有最大权值和的可行链路集，从而实现数据包的路由转发[2]。研究表明BP算法具有throughput-optimal的性能优势，当BP算法与数据流控制相结合时，无线网络可以达到效用最大化[3]。

BP算法可以有效提高网络吞吐量，因此引起了研究者的兴趣，但仍有许多问题需要解决，如集中控制模型的复杂度问题、延迟性能差等。目前为止，已经有大量的文献为解决这些问题提出了各种有效的方法，来改进BP算法。文献[4]使用shadow队列值来计算链路权值，shadow队列值由虚拟的队列长度和真实的队列长度决定，这样就可以减少每个节点维持的真实队列长度，达到改善延迟的作用。文献[5]将惩罚函数来决定路由调度，队列里数据包采用后进先出的方法，改善了延迟性能。文献[6，7]研究了单跳网络下链路调度延迟性能的改善，采用相邻节点队头延迟差代替队列长度差作为链路权值，提高了延迟性能。文献[8]采用基于每个邻居队列的路由调度的方法，在每个时隙只激活调度一个链路，在一定程度上降低了复杂度，但是却增加了延迟。文献[9]在延迟容忍网络中使用了基于集群的两级队列结构，有效地降低了节点的排队复杂度。

传输控制协议（Transmission Control Protocol）是一种面向连接的、可靠的、基于字节流的传输层通信协议，在当今Internet上占主导地位，在未来一段时间内也会一直保持这种地位[10]。因此BP算法在TCP网络中有效使用，充分利用二者各自的性能优势是一个值得研究的问题，人们针对这个问题提出了一些解决方法。Ajit Warrier， Sankararaman Janakiraman[11]等人针对无线网络的拥塞控制，结合BP算法的路由调度，提出了一种效用最优的无线多跳网络拥塞控制算法。文献[12]中对TCP拥塞控制和BP算法之间的协作方式进行了研究，提出了一种新的链路调度方法，并提出了一种新的网络编码方式，提高了网络吞吐量。这些文章解决了TCP与BP算法结合在一起使用时的一些问题，但他们都对TCP协议做出了一定的改动，同时忽略了TCP数据流在传输机会上的公平性，本文提出了一种新的BP算法，并在不对TCP协议做修改的前提下改善了网络吞吐量和传输公平性。

本文通过研究TCP拥塞控制下的数据流在BP算法路由调度下的性能表现，深入分析了其网络吞吐量性能较差的原因，研究发现在BP算法的路由调度下，数据队列较短的数据流一直得不到传输机会，而长队列数据流可以一直得到传输，进而提出了一种改进BP算法（T-BP），对传统BP算法的链路权重计算方法进行了改进，让短队列数据流也可以传输，提高了TCP数据流的吞吐量和传输公平性，同时证明了其具有throughput-optimal性能。

如果节点上的数据流的长度很小，T-BP算法使用公式（2）计算队列差，则数据流依然有可能得到传输。如图1（b）中所示，假设在时隙处，数据流1和2的队列队列长度分别为和。T-BP算法中的取值为10，则调度策略为 ? 。因为，则这两个数据流都有公平的机会得到传输，两个TCP数据流的拥塞窗口大小会随着时间而变化，TCP数据流可以传输它们的数据包。经过一段时间后，若此时数据流队列大小分别为和，则数据流1的数据包又得不到机会传输，因此确定值的大小十分重要。数据流1和2的队列长度分别和，设 0，则此时只有数据流2中的数据包得到传输。假设数据队列1和2在开始时就需进行队列长度差计算，则其队头延迟忽略不计，又因为，由公式可得缓冲区大小，现在已用的缓冲区大小为，这意味着节点的缓冲区即将溢出，这将導致第二个数据流的回退，即来自最大队列的包将被删除。因此，第二个数据流的流速率和队列大小将减少，则第一个流获得传输机会。若短队列数据流在一段时间内得不到传输，其队头延迟增大，则其值会比长队列数据流大，因而短队列数据流可以更快的得到传输机会，在一段时间后二者传输机会相等，此时数据流的队头延迟也相等。

2.3 ?T-BP算法throughput-optimal性能证明

3 ?仿真结果及分析

本章实验采用MATLAB仿真工具，针对T-BP算法和传统BP算法分别仿真了在其路由调度下的TCP数据流的吞吐量变化。

本文实验场景描述如下：信道模型采用的是随机的瑞利衰减信道模型，仿真时间设为200秒，TCP拥塞控制算法采用TCP-RENO算法，即基于丢包的拥塞控制，在仿真开始的前5秒内TCP数据流随机调度，5秒后由T-BP算法或者BP算法路由调度。信道容量设为2Mbps，每个节点上的缓冲区大小设为100个数据包，每个数据包大小为1000B。

为了体现T-BP算法相比于传统BP算法对于TCP数据流传输性能的改善，本文在两种不同的网络拓扑结构中进行了仿真，如图4所示。

在树状拓扑结构中，节点A是数据流源节点，其上有两个TCP数据流和（以下简称流1和流2），流1和流2的目的节点分别是B和D，故流1的路由路径是A->B，流2的路由路径是A->C->D。

在网状拓扑结构中，节点S是数据流源节点，产生四个数据流，分别是、、和，目的节点分别为、、和，它们通过中间节点传输数据到目的节点，为防止数据流传输包含长路径和循环路径，以及最后包问题，我们为其设置路由跳数限制。

数据包到达目的节点后直接传递到更高的层，不再停留在网络中，故我们以每一秒离开网络的数据包的数量作为吞吐量，通过观察流1和流2的吞吐量变化来对比T-BP算法和传统BP算法的性能。

如图5所示，在传统BP算法路由调度下的流1和流2的吞吐量在仿真时间开始5s后产生了两级分化，如上文分析所述，短队列TCP数据流在传统BP算法的路由调度下一直得不到任何传输机会，故流2的吞吐量始终为0，而长队列数据流1可以一直传输，最终吞吐量稳定在一个常值附近。

本文提出的T-BP算法改善了短队列数据流得不到传输机会的情况，如图6所示，流1和流2在仿真时间开始5s后吞吐量上下交替波动，二者传输机会均等，证明了本文所提出的T-BP算法是行之有效的，对传统BP算法路由调度下TCP数据流传输机会不均等的情况进行了改善。

如图7所示，在网状拓扑结构中，传统BP算法路由调度下的流1仿真5s时的队列长度大于其余三条数据流，则流1可以得到传输，故它的拥塞窗口大小在TCP拥塞控制算法的控制下增加，流1的数据队列也会有更多的数据包传入;而流2、流3和流4则得不到传输机会，拥塞窗口无变化，数据队列无数据包进入。流1占据了所有的传输机会，而其他数据流无传输机会。

如图8所示，四个数据流的吞吐量曲线变化在一个常值附近上下波动交替，即四个数据流都得到了传输机会，这四个数据流的传输机会相等。

综上所述，我们展示了T-BP与传统BP路由调度下TCP数据流的性能对比，并证明了T-BP算法支持网络中的所有TCP流的传输，而在传统BP算法中一些TCP数据流无法得到传输机会。仿真结果表明了：（1）传统BP算法和TCP数据流之间存在兼容性问题。（2）T-BP算法消除了了TCP数据流在传统BP算法路由调度下的兼容性问题，其吞吐量性能和传输公平性得到了的提升。

4 ?结语

本文提出了T-BP算法，以解决TCP和传统BP算法的兼容性问题。通过分析传统BP算法路由调度下TCP数据流的工作机制，在不对TCP协议做更改的情况下，对传统BP算法的链路权重计算方法进行改进，改善了短队列数据流得不到传输机会的情况。MATLAB中的仿真表明，T-BP算法提高了TCP流的吞吐量，让所有的TCP数据流得到了公平传输的机会。

参考文献

[1] Tassiulas L， Ephremides A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multi-hop radio networks[J]. IEEE Trans on Automatic Control， 1992， 37（12）： 1936-1948.

[2] 胡雪晴，周继鹏，陈晓霞. Ad hoc网络中Backpressure调度算法延迟性能的改进[J]. 计算机应用研究， 2017， 34（6）： 1812-1816.

[3] M. J. Neely， E. Modiano， C. Li. Fairness and optimal stochastic control for heterogeneous networks [J]. IEEE/ ACM Transactions on Networking， 2008， 16（2）： 396-409.

[4] Bui L， Srikant R， Stolyar A. A novel architecture for reduction of delay and queueing structure complexity in the backpressure algorithm[J]. IEEE/ACM Transactions on Networking， 2011， 19（6）： 1597-1609.

[5] Moeller S， Sridharan A， Krishnamachari B， et al. Routing without routes： the backpressure collection protocol[C]// Proc of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. New York： ACM Press， 2010： 279-290.

[6] Liu Shihuan， Ekici E， Lei Ying. Scheduling in multihop wireless networks without back-pressure[J]. IEEE/ACM Trans on Networking， 2014， 22（5）： 1477-1488.

[7] Mekkittikul A， Mc Keown N. A starvation-free algorithm for achieving 100% throughput in an input queued switch[C]// Proc of ICCCN. 1996： 226-231.

[8] E. Athanasopoulou et al. Back-Pressure-Based Packet-by-Packet Adaptive Routing in Communication Networks [J]. IEEE/ACM Transactions on Networking， 2013， 21（1）： 244-257.

[9] Jung Ryu， Lei Ying， Sanjay Shakkottai. Back-Pressure Routing for Intermittently Connected Networks [C]. 2010 Proceedings IEEE INFOCOM， 2010： 1-5.

[10] K Thompson， G J Miller， R Wilder. Wide-area Internet Traffic Patterns and characteristics[J]. IEEE Network， 1997， 11（6）： 10-23.

[11] A. Warrier， S. Janakiraman， S. Ha， I. Rhee. DiffQ： Practical differential backlog congestion control for wireless networks [C]. IEEE INFOCOM 2009， 2009： 262-270.

[12] Hulya Seferoglu， Eytan Modiano. TCP-Aware Backpressure Routing and Scheduling[J]. IEEE Transactions on Mobile Computing，2016，15（7）： 1783-1796.

[13] Bui L， Srikant R， Stolyar A. A novel architecture for reduction of delay and queueing structure complexity in the back- pressure algorithm [J]. IEEE/ACM Trans on Networking， 2011， 19（6）： 1597-1609.

[14] Eleni Stai， Symeon Papavassiliou， John S. Baras. Performance- Aware Cross-Layer Design in Wireless Multihop Networks Via a Weighted Backpressure Approach[J]. IEEE/ACM Transactions on Networking， 2016， 24（1）： 245-258.

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。