一種適合有線/無線混合網絡的自適應擁塞控制方法
2023-05-04 14:07:21 1
專利名稱：一種適合有線/無線混合網絡的自適應擁塞控制方法
技術領域：
本發明涉及計算機網絡傳輸技術領域，特別是一種適合有線/無線混合網絡的自適應擁塞控制方法，是傳輸控制協議TCP的擁塞控制方法，尤其是一種基於有線/無線混合網絡的能夠區分不同丟包原因的自適應TCP擁塞控制方法。
背景技術：
傳輸控制協議(TCP)經歷了從TCP Tahoe到當前廣泛使用的TCPNewReno多個版本的改進之後，其不斷優化的擁塞控制方法保證了端到端的可靠的數據流傳輸服務。最初在TCP Tahoe中實現的擁塞控制機制包括兩個部分慢啟動和擁塞避免。TCP Reno進一步引入了快速重傳和快速恢復算法，根據發送方收到的重複確認即可斷定數據包丟失，不必像TCP Tahoe那樣需等待丟失數據包的重傳定時器超時。Newreno在Reno基礎上又做了補充，使得在發生連續丟包的情況下，發送方能夠更有效地進行擁塞控制。
這一系列的優化都是針對有線網絡的。重複確認、超時所標識的數據包丟失均被解釋為網絡擁塞，通過啟動擁塞控制機制進行流量控制加大重發間隔、縮小發送窗口來適應網絡擁塞。這種方法對於鏈路質量良好的有線環境是合適的。
然而在無線網絡中擁塞已不再是數據丟失的唯一原因。無線鏈路的高誤碼率導致大部分丟包都是由於鏈路出錯造成的。如果TCP仍然遵循丟包必然是由擁塞引起的原則，盲目減小發送速率，就勢必降低帶寬利用率，導致TCP性能惡化。
現有為改善TCP在無線環境下性能的改進方法主要可分為三類(1)端到端方案(End-to-End)只修改TCP連接兩端的協議，而不需要中間節點的支持，保證從發送方到接收方TCP連接的完整性。此類研究有TCP Westwood、TCP-Real等。在這些協議中性能最好的是TCPWestwood，該協議通過一個濾波器來估測鏈路的可用帶寬，實時調整慢啟動的門限值及擁塞窗口，從而顯著提高TCP利用帶寬的能力。其不足之處在於與傳統TCP協議共存時，就會霸佔其他協議流帶寬，破壞了不同協議流之間的友好性(friendliness)。
(2)分段連接方案(Split Connection)與端到端方案不同，傳輸層連接在基站分成兩段，對TCP發送方完全屏蔽了無線鏈路。無線部分可以另外使用其它的擁塞控制技術如SACK等。這類方案對移動主機和中間節點的TCP軟體都要做修改而不必更改發送端的TCP實現。但是它破壞了端對端的TCP連接語義，因為在數據實際沒有傳送到接收方之前，偽造的確認就被送給發送方。
(3)本地鏈路層方案(Localized Link Layer)介於端到端和分段連接之間，它使用可靠鏈路層協議在鏈路層進行重傳從而對發送端屏蔽與鏈路有關的丟包。但是由於鏈路層協議和高層協議都有獨立的差錯控制功能，這些功能有一定的重複性，因此鏈路層和傳輸層的重發功能相互競爭的結果會降低無線信道的有效利用率，導致端到端吞吐量下降。
發明內容
本發明的目的是提出一種適合有線/無線混合網絡的自適應擁塞控制方法，適合於傳輸層擁塞控制方法。它能夠自適應地根據鏈路狀況，區分丟包的不同原因，並採取相應的恢復措施。同時保持已有的有線網絡的傳輸協議語意和端到端語義完整性，即只對發送方的TCP協議進行少量的修改，而不改變中間節點的TCP協議，並且修改只涉及到傳輸層，與其它層協議無關。
技術方案一種適合有線/無線混合網絡的自適應的擁塞控制方法，根據確認包(Acknowledgments，以下簡寫為ACK)的相對單向延遲變化趨勢來判斷鏈路的擁塞狀況，進而區分丟包是因為鏈路擁塞引起的還是因為無線鏈路出錯導致，自適應地根據不同的丟包原因採取不同的恢復機制，其特徵在於，主要步驟如下步驟1計算相對單向延遲；步驟2估測相對單向延遲的變化趨勢；步驟3區分丟包原因；
步驟4恢復措施。
本發明的技術解決方案是提供一種能夠區分對待不同丟包原因的擁塞控制方法。基本思想是根據包的延遲變化趨勢來判斷鏈路的擁塞狀況，進而區分丟包是因為鏈路擁塞引起的還是因為無線出錯導致，自適應地根據不同的丟包原因採取不同的恢復機制。其中的關鍵點是包的延遲如何反映鏈路的擁塞狀況。
包在網絡中的延遲可以分為四個部分介質訪問延遲、傳播延遲、傳輸延遲和每個中間路由器內部的排隊延遲。其中介質訪問延遲取決於網絡媒體的特性；傳播延遲指電信號從鏈路的一端傳播到另一端所需要的時間，通常為5us/1km；傳輸延遲取決於每個連接所分配的帶寬；排隊延遲指包在路由器中排隊所造成的延遲，它與路由器本身的特性、鏈路擁塞狀況等較為相關。對於一個實際運行的有線/無線異構網絡，傳播延遲和介質訪問延遲主要反映了路徑本身的物理特徵，即組成路徑的各條鏈路的長度、介質等，是端到端延遲的不變部分合稱固有延遲；傳輸延遲和排隊延遲組成延遲的可變部分，合稱動態延遲，它主要由每條連接搶佔的帶寬和在網絡轉發節點中的排隊造成，反映了網絡的繁忙程度。因此我們可以根據延遲變化也即動態延遲的變化趨勢來估測網絡的擁塞情況。
當網絡瓶頸部分接收到的數據包超過了它所能處理的容量，新到的數據包由於不能發送出去，將不斷插入緩存隊列中，造成隊列長度的增長，數據包的延遲將呈增加趨勢。如果隊列長度超出了瓶頸路由器的緩存能力，分組就會被丟棄。可見延遲增加是擁塞導致丟包的顯著特徵。如果只是因為無線鏈路突發性鏈路出錯使得分組丟失，而數據流並沒有造成鏈路超載，也就不會有不斷增加的積壓隊列，延遲序列也就不會表現出明顯增加趨勢。另一種不可避免的情況是如果在網絡輕度擁塞的同時無線鏈路出錯導致丟包，根據延遲的變化我們可能會將它誤判為擁塞丟包，但是這種誤判是可以接受的，畢竟此時端系統向網絡輸出的負載已經逼近網絡資源容量和處理能力的極限。總之，我們可以根據延遲的變化來判斷鏈路狀況從而採取更有效的擁塞控制機制。
本發明基於發送方收到的ACK包來計算相對單向延遲。每收到一個ACK包，發送方記錄下當前的時間戳時鐘ai，在該ACK包中還攜帶著接收方發送它的時間戳si。根據ai和si這兩個時間，可以得到每個ACK包i的相對延遲(RODRelative One-way Delay)Di＝ai-si，Di實際上是從發送方到接收方的絕對延遲加上/減去一個偏移量θ，θ是兩個端系統間的時鐘偏差。由於在下一步的統計分析中只關注延遲的相對量，因此這種測量方法不需要進行時鐘同步。
將樣本值Di存入數組rod_arr中，顯然只有最近的N個ROD的變化趨勢才反映網絡的當前狀況，因此可以把數組大小設置為固定值N(N取經驗值100)，使其成員隨時間推移不斷變化。
一旦收到丟包標識，發送方根據此前採樣的延遲序列的變化趨勢來作為區分不同丟包的判據。統計方法如下1)預處理把K個樣本{D1，D2，...，Dk}分成=K]]>組，每組有Γ個連續的樣本，求出每組的中值 然後使用以下兩種統計方法來檢測數據流的變化趨勢；2)PCT(Pairwise Comparison Test)SPCT=k=2I(D^k>D^k-1)-1]]>I(X)若X成立，I(X)＝1，否則為0，PCT測量的是相鄰兩個呈增加趨勢的樣本在所有樣本中佔的比例，0≤SPCT≤1，如果兩個樣本是不相關的，那麼SPCT的期望值是0.5；如果有很強的增加趨勢，那麼應該接近1；如果SPCT＞0.66，即判為增加趨勢；如果SPCT＜0.54判為不增加趨勢；否則即為不確定趨勢；3)PDT(Pairwise Difference Test)SPDT=D^-D^1k=2|D^k-D^k-1|]]>PDT量化了相對於樣本值的絕對變化其首尾變化的程度，其中-1≤SPDT≤1。如果樣本是不相關的，那麼SPDT的期望值為0；如果有很強的增長趨勢，SPDT接近1；如果SPDT＞0.55時，為增加趨勢；如果SPLDT＜0.45判為不增加趨勢；否則，即為不確定趨勢；4)綜合PCT和PDT如果PCT/PDT之一為增加趨勢，另一個為增加或者不確定趨勢，那麼即可判為ROD呈增加趨勢，否則ROD不呈現明顯的增加趨勢。
區分丟包的判據是根據前面PCT和PDT綜合判斷的結果，如果ROD呈增加趨勢，可知三次重複ACK或超時所反映的丟包情況就是由於鏈路擁塞導致的，反之丟包是因為無線鏈路出錯引起的。
以此作為區分丟包原因的判據，即可針對不同原因導致的丟包做出合適的恢復策略如果延遲呈明顯增加趨勢，即可判為丟包是因為網絡擁塞所致，那麼仍然按照傳統TCP的擁塞控制策略，降低分組進入網絡的傳輸速率，並重傳丟失的報文段；否則，丟包可認為是無線鏈路出錯造成的，此時只需重傳而不必改變發送速率。
這種自適應地擁塞控制方法可以直接應用於有線/無線混合網絡發送方的TCP實現中。
圖1是本發明的自適應擁塞控制方法的流程圖，主要包括如下步驟(1)等待ACK包到達；一旦ACK包到達，則進入步驟(2)；否則如果在等待過程中未收到ACK包而重傳定時器超時，則轉到步驟(3)；(2)計算該ACK包的相對單向延遲(ROD)記錄當前發送方的時間戳時鐘ai，以及該ACK包中攜帶的接收方發送它的時間戳si。根據ai和si這兩個時間，可以得到該ACK包i的相對延遲Di＝ai-si。將樣本值Di存入數組rod_arr中，數組rod_arr的大小N取經驗值100。發送方判斷該ACK包是否是第三個重複ACK包，如果是則轉入步驟(3)，否則繼續傳統TCP協議的相應操作；(3)估測相對單向延遲的變化趨勢根據前文所述的PCT、PDT統計方法估測最近的N個ROD樣本的變化趨勢，作為區分丟包的判據，進入步驟(4)；(4)區分丟包原因如果ROD呈增加趨勢，可知三次重複ACK或超時所反映的丟包情況是由於鏈路擁塞導致的，接著執行步驟(5.1)反之丟包是因為無線鏈路出錯引起的，轉入步驟(5.2)；(5)恢復措施(5.1)如果丟包是擁塞所致，仍然按照有線TCP的擁塞控制策略減小擁塞窗口並重傳丟失的數據包；(5.2)如果丟包是無線鏈路出錯所致，只需重傳丟失的數據包而不必減小擁塞窗口。
優點本發明能夠明確區分網絡擁塞導致的丟包和無線鏈路出錯造成的丟包，對不同原因造成的丟包採用相應的恢復策略，從而避免了傳統TCP協議調整擁塞窗口的盲目性。對於有線/無線混合網絡這種擁塞控制方法能夠明顯提高吞吐量同時有很好的公平性和友好性表現。另外，由於它只是對發送端的TCP協議進行了少量修改，而不改變中間節點的TCP協議，並且修改只涉及到傳輸層，與其它層協議無關。保持了已有的有線網絡的傳輸協議語意和端到端語義完整性。
權利要求
1.一種適合有線/無線混合網絡的自適應的擁塞控制方法，根據確認包ACK的相對單向延遲變化趨勢來判斷鏈路的擁塞狀況，進而區分丟包是因為鏈路擁塞引起的還是因為無線鏈路出錯導致，自適應地根據不同的丟包原因採取不同的恢復機制，其特徵在於，主要步驟如下步驟1計算相對單向延遲；步驟2估測相對單向延遲的變化趨勢；步驟3區分丟包原因；步驟4恢復措施。
2.根據權利要求1所述的自適應擁塞控制方法，其特徵在於，其中步驟1中所述的相對單向延遲ROD，是發送端根據收到的ACK包攜帶的時間戳ai和發送端的當前時間si得到Di＝ai-si。
3.根據權利要求1所述的自適應擁塞控制方法，其特徵在於，其中步驟2所述的估測相對單向延遲變化趨勢，採用的方法如下1)預處理把K個樣本{D1，D2，...，Dk}分成=]]>組，每組有Γ個連續的樣本，求出每組的中值 然後使用以下兩種統計方法來檢測數據流的變化趨勢；2)PCTSPCT=k=2I(D^K>D^k-1)-1]]>I(X)若X成立，I(X)＝1，否則為0；如果SPCT＞0.66，即判為增加趨勢；如果SPCT＜0.54判為不增加趨勢；否則即為不確定趨勢；3)PDTSPDT=D^-D^1k=2|D^k-D^k-1|]]>如果SPDT＞0.55時，為增加趨勢；如果SPDT＜0.45判為不增加趨勢；否則，即為不確定趨勢；4)綜合PCT和PDT如果PCT/PDT之一為增加趨勢，另一個為增加/不確定趨勢，那麼即可判為ROD呈增加趨勢，否則ROD不呈現明顯的增加趨勢。
4.根據權利要求1所述的自適應擁塞控制方法，其特徵在於，其中步驟3中所述的區分丟包的判據是根據前面PCT和PDT綜合判斷的結果，如果ROD呈增加趨勢，可知三次重複ACK或超時所反映的丟包情況就是由於鏈路擁塞導致的，反之丟包是因為無線鏈路出錯引起的。
5.根據權利要求1所述的自適應擁塞控制方法，其特徵在於，其中步驟4中所述的恢復措施如下1)如果丟包是擁塞所致，仍然按照有線TCP的擁塞控制策略減小擁塞窗口並重傳丟失的數據包；2)如果丟包是無線鏈路出錯所致，只需重傳丟失的數據包而不必減小擁塞窗口。
全文摘要
本發明涉及計算機網絡傳輸控制協議TCP的擁塞控制技術領域，是一種基於有線和無線混合網絡的能夠區分不同丟包原因的自適應的TCP擁塞控制方法。其步驟計算相對單向延遲；估測相對單向延遲的變化趨勢；區分丟包原因；恢復措施。本發明的特點是根據確認包ACK的相對單向延遲變化趨勢來判斷鏈路的擁塞狀況，進而區分丟包是因為鏈路擁塞引起的還是因為無線出錯導致，自適應地根據不同的丟包原因採取不同的恢復機制。它只對發送方的TCP協議進行少量的修改，而不改變中間節點的TCP協議，並且修改只涉及到傳輸層，與其它層協議無關。保持了已有的有線網絡的傳輸協議語意和端到端語義完整性。
文檔編號H04Q3/64GK1487698SQ03155730
公開日2004年4月7日 申請日期2003年9月1日 優先權日2003年9月1日
發明者葛鴿, 張國清, 葛 鴿 申請人:中國科學院計算技術研究所