基于TCP擁塞控制的改進(jìn)Backpressure算法

占慶杰 韓韌 周好生

摘 ?要： 本文研究了無線網(wǎng)絡(luò)中在Backpressure算法路由調(diào)度下TCP數(shù)據(jù)流的性能表現(xiàn)，發(fā)現(xiàn)該算法無法有效提高網(wǎng)絡(luò)吞吐量，原因是Backpressure算法基于隊(duì)列差值的路由調(diào)度與TCP的擁塞控制機(jī)制之間的不匹配造成的。本文提出了一種適應(yīng)于TCP數(shù)據(jù)流調(diào)度的改進(jìn)Backpressure算法（T-BP），并從理論上證明了T-BP算法具有throughput-optimal 性能。仿真結(jié)果表明，在多種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，與傳統(tǒng)BP算法相比，TCP數(shù)據(jù)流在吞吐量和公平性方面的性能得到了有效的提高。

關(guān)鍵詞： Backpressure算法;TCP;最優(yōu)吞吐量;公平性

中圖分類號： TP393.03 ? ?文獻(xiàn)標(biāo)識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.013

本文著錄格式：占慶杰，韓韌，周好生. 基于TCP擁塞控制的改進(jìn)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提出的一種可以實(shí)現(xiàn)網(wǎng)絡(luò)路由和調(diào)度的算法，能夠動(dòng)態(tài)高效的分配帶寬資源[1]。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)會(huì)為經(jīng)過該節(jié)點(diǎn)的數(shù)據(jù)流維持一個(gè)隊(duì)列，通過計(jì)算得出各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)與相鄰可通信節(jié)點(diǎn)之間的最大隊(duì)列差值，并把它賦為該對相鄰節(jié)點(diǎn)之間的鏈路權(quán)值，再根據(jù)鏈路權(quán)值和干擾模型，進(jìn)一步得出具有最大權(quán)值和的可行鏈路集，從而實(shí)現(xiàn)數(shù)據(jù)包的路由轉(zhuǎn)發(fā)[2]。研究表明BP算法具有throughput-optimal的性能優(yōu)勢，當(dāng)BP算法與數(shù)據(jù)流控制相結(jié)合時(shí)，無線網(wǎng)絡(luò)可以達(dá)到效用最大化[3]。

BP算法可以有效提高網(wǎng)絡(luò)吞吐量，因此引起了研究者的興趣，但仍有許多問題需要解決，如集中控制模型的復(fù)雜度問題、延遲性能差等。目前為止，已經(jīng)有大量的文獻(xiàn)為解決這些問題提出了各種有效的方法，來改進(jìn)BP算法。文獻(xiàn)[4]使用shadow隊(duì)列值來計(jì)算鏈路權(quán)值，shadow隊(duì)列值由虛擬的隊(duì)列長度和真實(shí)的隊(duì)列長度決定，這樣就可以減少每個(gè)節(jié)點(diǎn)維持的真實(shí)隊(duì)列長度，達(dá)到改善延遲的作用。文獻(xiàn)[5]將懲罰函數(shù)來決定路由調(diào)度，隊(duì)列里數(shù)據(jù)包采用后進(jìn)先出的方法，改善了延遲性能。文獻(xiàn)[6，7]研究了單跳網(wǎng)絡(luò)下鏈路調(diào)度延遲性能的改善，采用相鄰節(jié)點(diǎn)隊(duì)頭延遲差代替隊(duì)列長度差作為鏈路權(quán)值，提高了延遲性能。文獻(xiàn)[8]采用基于每個(gè)鄰居隊(duì)列的路由調(diào)度的方法，在每個(gè)時(shí)隙只激活調(diào)度一個(gè)鏈路，在一定程度上降低了復(fù)雜度，但是卻增加了延遲。文獻(xiàn)[9]在延遲容忍網(wǎng)絡(luò)中使用了基于集群的兩級隊(duì)列結(jié)構(gòu)，有效地降低了節(jié)點(diǎn)的排隊(duì)復(fù)雜度。

傳輸控制協(xié)議（Transmission Control Protocol）是一種面向連接的、可靠的、基于字節(jié)流的傳輸層通信協(xié)議，在當(dāng)今Internet上占主導(dǎo)地位，在未來一段時(shí)間內(nèi)也會(huì)一直保持這種地位[10]。因此BP算法在TCP網(wǎng)絡(luò)中有效使用，充分利用二者各自的性能優(yōu)勢是一個(gè)值得研究的問題，人們針對這個(gè)問題提出了一些解決方法。Ajit Warrier， Sankararaman Janakiraman[11]等人針對無線網(wǎng)絡(luò)的擁塞控制，結(jié)合BP算法的路由調(diào)度，提出了一種效用最優(yōu)的無線多跳網(wǎng)絡(luò)擁塞控制算法。文獻(xiàn)[12]中對TCP擁塞控制和BP算法之間的協(xié)作方式進(jìn)行了研究，提出了一種新的鏈路調(diào)度方法，并提出了一種新的網(wǎng)絡(luò)編碼方式，提高了網(wǎng)絡(luò)吞吐量。這些文章解決了TCP與BP算法結(jié)合在一起使用時(shí)的一些問題，但他們都對TCP協(xié)議做出了一定的改動(dòng)，同時(shí)忽略了TCP數(shù)據(jù)流在傳輸機(jī)會(huì)上的公平性，本文提出了一種新的BP算法，并在不對TCP協(xié)議做修改的前提下改善了網(wǎng)絡(luò)吞吐量和傳輸公平性。

本文通過研究TCP擁塞控制下的數(shù)據(jù)流在BP算法路由調(diào)度下的性能表現(xiàn)，深入分析了其網(wǎng)絡(luò)吞吐量性能較差的原因，研究發(fā)現(xiàn)在BP算法的路由調(diào)度下，數(shù)據(jù)隊(duì)列較短的數(shù)據(jù)流一直得不到傳輸機(jī)會(huì)，而長隊(duì)列數(shù)據(jù)流可以一直得到傳輸，進(jìn)而提出了一種改進(jìn)BP算法（T-BP），對傳統(tǒng)BP算法的鏈路權(quán)重計(jì)算方法進(jìn)行了改進(jìn)，讓短隊(duì)列數(shù)據(jù)流也可以傳輸，提高了TCP數(shù)據(jù)流的吞吐量和傳輸公平性，同時(shí)證明了其具有throughput-optimal性能。

如果節(jié)點(diǎn) 上的數(shù)據(jù)流 的長度 很小，T-BP算法使用公式（2）計(jì)算隊(duì)列差，則數(shù)據(jù)流 依然有可能得到傳輸。如圖1（b）中所示，假設(shè)在時(shí)隙 處，數(shù)據(jù)流1和2的隊(duì)列隊(duì)列長度分別為 和 。T-BP算法中的 取值為10，則調(diào)度策略為 ? 。因?yàn)?，則這兩個(gè)數(shù)據(jù)流都有公平的機(jī)會(huì)得到傳輸，兩個(gè)TCP數(shù)據(jù)流的擁塞窗口大小會(huì)隨著時(shí)間而變化，TCP數(shù)據(jù)流可以傳輸它們的數(shù)據(jù)包。經(jīng)過一段時(shí)間后，若此時(shí)數(shù)據(jù)流隊(duì)列大小分別為 和 ，則數(shù)據(jù)流1的數(shù)據(jù)包又得不到機(jī)會(huì)傳輸，因此確定 值的大小十分重要。數(shù)據(jù)流1和2的隊(duì)列長度分別 和 ，設(shè) 0，則此時(shí)只有數(shù)據(jù)流2中的數(shù)據(jù)包得到傳輸。假設(shè)數(shù)據(jù)隊(duì)列1和2在開始時(shí)就需進(jìn)行隊(duì)列長度差計(jì)算，則其隊(duì)頭延遲忽略不計(jì)，又因?yàn)?，由公式 可得緩沖區(qū)大小 ，現(xiàn)在已用的緩沖區(qū)大小為 ，這意味著節(jié)點(diǎn) 的緩沖區(qū)即將溢出，這將導(dǎo)致第二個(gè)數(shù)據(jù)流的回退，即來自最大隊(duì)列的包將被刪除。因此，第二個(gè)數(shù)據(jù)流的流速率和隊(duì)列大小將減少，則第一個(gè)流獲得傳輸機(jī)會(huì)。若短隊(duì)列數(shù)據(jù)流在一段時(shí)間內(nèi)得不到傳輸，其隊(duì)頭延遲增大，則其 值會(huì)比長隊(duì)列數(shù)據(jù)流大，因而短隊(duì)列數(shù)據(jù)流可以更快的得到傳輸機(jī)會(huì)，在一段時(shí)間后二者傳輸機(jī)會(huì)相等，此時(shí)數(shù)據(jù)流的隊(duì)頭延遲也相等。

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

3 ?仿真結(jié)果及分析

本章實(shí)驗(yàn)采用MATLAB仿真工具，針對T-BP算法和傳統(tǒng)BP算法分別仿真了在其路由調(diào)度下的TCP數(shù)據(jù)流的吞吐量變化。

本文實(shí)驗(yàn)場景描述如下：信道模型采用的是隨機(jī)的瑞利衰減信道模型，仿真時(shí)間設(shè)為200秒，TCP擁塞控制算法采用TCP-RENO算法，即基于丟包的擁塞控制，在仿真開始的前5秒內(nèi)TCP數(shù)據(jù)流隨機(jī)調(diào)度，5秒后由T-BP算法或者BP算法路由調(diào)度。信道容量設(shè)為2Mbps，每個(gè)節(jié)點(diǎn)上的緩沖區(qū)大小設(shè)為100個(gè)數(shù)據(jù)包，每個(gè)數(shù)據(jù)包大小為1000B。

為了體現(xiàn)T-BP算法相比于傳統(tǒng)BP算法對于TCP數(shù)據(jù)流傳輸性能的改善，本文在兩種不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中進(jìn)行了仿真，如圖4所示。

在樹狀拓?fù)浣Y(jié)構(gòu)中，節(jié)點(diǎn)A是數(shù)據(jù)流源節(jié)點(diǎn)，其上有兩個(gè)TCP數(shù)據(jù)流 和 （以下簡稱流1和流2），流1和流2的目的節(jié)點(diǎn)分別是B和D，故流1的路由路徑是A->B，流2的路由路徑是A->C->D。

在網(wǎng)狀拓?fù)浣Y(jié)構(gòu)中，節(jié)點(diǎn)S是數(shù)據(jù)流源節(jié)點(diǎn)，產(chǎn)生四個(gè)數(shù)據(jù)流，分別是 、 、 和 ，目的節(jié)點(diǎn)分別為 、 、 和 ，它們通過中間節(jié)點(diǎn)傳輸數(shù)據(jù)到目的節(jié)點(diǎn)，為防止數(shù)據(jù)流傳輸包含長路徑和循環(huán)路徑，以及最后包問題，我們?yōu)槠湓O(shè)置路由跳數(shù)限制。

數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)后直接傳遞到更高的層，不再停留在網(wǎng)絡(luò)中，故我們以每一秒離開網(wǎng)絡(luò)的數(shù)據(jù)包的數(shù)量作為吞吐量，通過觀察流1和流2的吞吐量變化來對比T-BP算法和傳統(tǒng)BP算法的性能。

如圖5所示，在傳統(tǒng)BP算法路由調(diào)度下的流1和流2的吞吐量在仿真時(shí)間開始5s后產(chǎn)生了兩級分化，如上文分析所述，短隊(duì)列TCP數(shù)據(jù)流在傳統(tǒng)BP算法的路由調(diào)度下一直得不到任何傳輸機(jī)會(huì)，故流2的吞吐量始終為0，而長隊(duì)列數(shù)據(jù)流1可以一直傳輸，最終吞吐量穩(wěn)定在一個(gè)常值附近。

本文提出的T-BP算法改善了短隊(duì)列數(shù)據(jù)流得不到傳輸機(jī)會(huì)的情況，如圖6所示，流1和流2在仿真時(shí)間開始5s后吞吐量上下交替波動(dòng)，二者傳輸機(jī)會(huì)均等，證明了本文所提出的T-BP算法是行之有效的，對傳統(tǒng)BP算法路由調(diào)度下TCP數(shù)據(jù)流傳輸機(jī)會(huì)不均等的情況進(jìn)行了改善。

如圖7所示，在網(wǎng)狀拓?fù)浣Y(jié)構(gòu)中，傳統(tǒng)BP算法路由調(diào)度下的流1仿真5s時(shí)的隊(duì)列長度大于其余三條數(shù)據(jù)流，則流1可以得到傳輸，故它的擁塞窗口大小在TCP擁塞控制算法的控制下增加，流1的數(shù)據(jù)隊(duì)列也會(huì)有更多的數(shù)據(jù)包傳入;而流2、流3和流4則得不到傳輸機(jī)會(huì)，擁塞窗口無變化，數(shù)據(jù)隊(duì)列無數(shù)據(jù)包進(jìn)入。流1占據(jù)了所有的傳輸機(jī)會(huì)，而其他數(shù)據(jù)流無傳輸機(jī)會(huì)。

如圖8所示，四個(gè)數(shù)據(jù)流的吞吐量曲線變化在一個(gè)常值附近上下波動(dòng)交替，即四個(gè)數(shù)據(jù)流都得到了傳輸機(jī)會(huì)，這四個(gè)數(shù)據(jù)流的傳輸機(jī)會(huì)相等。

綜上所述，我們展示了T-BP與傳統(tǒng)BP路由調(diào)度下TCP數(shù)據(jù)流的性能對比，并證明了T-BP算法支持網(wǎng)絡(luò)中的所有TCP流的傳輸，而在傳統(tǒng)BP算法中一些TCP數(shù)據(jù)流無法得到傳輸機(jī)會(huì)。仿真結(jié)果表明了：（1）傳統(tǒng)BP算法和TCP數(shù)據(jù)流之間存在兼容性問題。（2）T-BP算法消除了了TCP數(shù)據(jù)流在傳統(tǒng)BP算法路由調(diào)度下的兼容性問題，其吞吐量性能和傳輸公平性得到了的提升。

4 ?結(jié)語

本文提出了T-BP算法，以解決TCP和傳統(tǒng)BP算法的兼容性問題。通過分析傳統(tǒng)BP算法路由調(diào)度下TCP數(shù)據(jù)流的工作機(jī)制，在不對TCP協(xié)議做更改的情況下，對傳統(tǒng)BP算法的鏈路權(quán)重計(jì)算方法進(jìn)行改進(jìn)，改善了短隊(duì)列數(shù)據(jù)流得不到傳輸機(jī)會(huì)的情況。MATLAB中的仿真表明，T-BP算法提高了TCP流的吞吐量，讓所有的TCP數(shù)據(jù)流得到了公平傳輸?shù)臋C(jī)會(huì)。

參考文獻(xiàn)

[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網(wǎng)絡(luò)中Backpressure調(diào)度算法延遲性能的改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用研究， 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.