端點對端點流量控制技術之研究與設計

Abstract

近年來網路技術的進展大幅的提高了傳輸的頻寬，但更多更複雜的應用程式與急速增加的使用者，讓頻寬的提高速度趕不上需求的增加。面對頻寬不足的問題，可經由改進流量控制方法，使其能更有效率的利用網路資源。當流量控制能工作的更有效率，可用的頻寬將形同增加。我們的研究分為兩大部份，第一部份是著眼於壅塞預防技術的改進，而第二部份則發展出能更準確偵測遺失封包的方法並讓壅塞預防機制仍能在此階段充份發揮效能。 TCP的壅塞預防演算法是一種滑動視窗方式的演算法，早期的TCP，利用持續增大視窗的方式去偵測網路的容量。由於此方法會持續加大視窗，所以本身遲早會造成壅塞的發生，也就把封包遺失當做壅塞發生的訊號，因而在高封包遺失率的環境下會有很差的表現。因此TCP Vegas的改良版本導入參考佇列空間的使用量，將其視為壅塞的指標。因為壅塞指標的轉換，Vegas的滑動視窗調整延續了線性調整的概念，依據壅塞指標來線性調整滑動視窗的大小。根據對網路狀態的研究，顯示出可用的頻寬是快速大幅的變動而不是小幅線性的變動，此論文提出了一種虛擬速率TCP演算法，簡化了網路狀態的指標，並提出快速調升與調降滑動視窗的方法。經過分析、證明及模擬，可以驗證此方法能有更高的輸貫量及更公平的頻寬分享。 由於以滑動視窗為基礎的流量控制方法，受到了封包傳送容易爆滿及壅塞預防演算法容易受封包丟失影響的限制，所以改為以速率為基礎的研究，如此，封包的傳輸能更加平順，據此我們提出以速率為基礎的TCP壅塞預防演算法。其中，最適合的傳輸速率不再是靠封包遺失來偵測，而是直接去偵測最佳的傳輸速率。由於在調整傳輸速率的過程中，可能會造成封包大量堆積的現象，因此，本論文也提出了佇列佔有量控制的機制，用以將堆積在佇列的封包迅速疏通掉。經過分析及證明，可以確認本論文所提最佳傳輸速率的偵測機制比現有的機制更為準確，而佇列空間控制的機制也能有效的達到所預期的效果。最後是用系統模擬來比較所提出的演算法及現有的機制，結果可驗證所提出之機制有更好的輸貫量及更佳的公平性。 由於壅塞預防都著重在極低封包遺失率的環境下，能更有效率的利用可用的頻寬，所以目前的壅塞預防演算法在高封包丟失率的環境難有好的輸貫量。探究其原因，是由於以滑動視窗為基礎的壅塞預防機制是以封包丟失來顯示壅塞的發生，所以，在封包遺失並非導因於壅塞的狀況下，以滑動視窗為基礎的壅塞預防機制，會發生有效輸貫量大幅降低的現象。相對的，以速率為基礎的控制機制，先天就不依賴封包遺失來判斷壅塞與否，所以在高封包遺失率的環境下能有較好的表現。而TCP目前的封包遺失判斷方式也會有缺漏之處，所以在遺失重傳階段的演進則是分兩部份處理，其一是要改良遺失的偵測，其二則是基於以佇列空間佔有量來當壅塞的指標時，僅需提供在遺失重傳所需的網路服務速率，即可讓前面提出的演算法在遺失重傳階段有很好的輸貫量。透過系統模擬可以驗證此方法能讓輸貫量有大幅的改進。 由於所提出的滑動視窗為基礎的壅塞預防機制，加上改良過的遺失重傳機制，是屬於不需要下層硬體配合的壅塞預防機制，所以我們將它實作在Linux平台上，並在現有的Internet上測試真實環境下的輸貫量。經長時間的測試結果，驗證了不論網路壅塞與否，所提出之機制皆優於現有的演算法甚多。

Nowadays the advanced communications technology brings up the network bandwidth rapidly, but both numbers of bandwidth hungry applications and Internet users make the network bandwidth demand grow even faster. The problem of bandwidth insufficiency can be improved through enhancing the flow control mechanism so that it can work more efficiently. Therefore, when the flow control mechanism can utilize the network resource more efficiently, the remaining available bandwidth will be increased. In this research, we divide the study of end-to-end flow control algorithm into two stages. In first stage, we focus on the development of congestion avoidance algorithms. While in the second stage, we deal with the error recovery phase. We develop a precise loss detection mechanism and an enhanced congestion avoidance algorithm so that they can work properly and efficiently during this phase. TCP uses the congestion avoidance algorithm based on the sliding window. Early versions of TCP increase the window size to estimate the network capacity. Since the window is increased continuously, this scheme will eventually generate congestion by itself. As a sequel, the packet loss becomes the congestion indication and this characteristic leads to low TCP throughput under high loss rate environments. Therefore, Vegas uses the queue occupancy as the congestion indication and adjusts the window linearly. Since the variation of network traffic is far from linear, we propose the pseudo-rate TCP algorithm to accommodate the more realistic situation. The congestion indication is simplified and the window adjustment becomes faster than Vegas. Through analysis, proof, and simulation, we could observe that pseudo-rate TCP can provide higher throughput and better fairness. The burstness and low throughput under high loss rate environment are characteristics of window-based algorithm, these two characteristics motivate us to study and develop rate-based algorithms. We propose the so-called rate TCP congestion avoidance algorithm, in which the proper transmission rate is estimated through rate probing mechanism. Since the queue occupancy may be kept increasing during rate adjustment, we also propose a queue occupancy control mechanism to constrain the queue occupancy in the network. Through the analysis, we can show that our rate probing mechanism is more precise than the existing mechanisms, and the efficiency of the queue occupancy control is proved, too. We use the simulation to evaluate the performance of the proposed scheme, which shows that our scheme is better than existing ones. Since the packet loss is used as the indication of congestion, the throughput of current algorithms is low under high loss rate environment. On the other hand, the rate-based algorithms do not have this limitation because they do not count on the packet loss to indicate the congestion. Besides, the current loss detection mechanism is unable to detect all kinds of loss. Therefore, we also refine both the loss detection mechanism and the congestion avoidance algorithm. Since the pseudo-rate TCP requires the service rate information to make congestion avoidance algorithm being work properly, our proposed mechanism provides this capability to accomplish the task. We use simulation to evaluate the improvement, which leads to much higher throughput under high loss rate environment. The proposed window-based congestion avoidance algorithm with refined error recovery mechanism does not rely on hardware support. Therefore, we implement the proposed scheme on Linux kernel and evaluate its performance under real-world Internet environment. After a long period of testing, we observe that pseudo-rate TCP has higher throughput than current algorithms no matter the network is congested or not. ABSTRACT IN ENGLISH II ACKNOWLEDGEMENT VI CONTENTS VII LIST OF FIGURES IX LIST OF TABLES XI CHAPTER 1 INTRODUCTION 1 1.1 TCP CONGESTION AVOIDANCE ALGORITHMS 1 1.2 APPROACHES 4 1.3 SIMULATION ENVIRONMENT 6 1.4 ORGANIZATION OF THE THESIS 8 CHAPTER 2 PSEUDO RATE TCP CONTROL ALGORITHM 9 2.1 VIRTUAL QUEUE OCCUPANCY 11 2.2 DIRECT WINDOW DROP 14 2.3 RENEWAL EXPONENTIAL WINDOW INCREMENT 19 2.4 PSEUDO RATE TCP CONTROL ALGORITHM 21 2.5 ANALYSIS OF WINDOW ADJUSTMENT ALGORITHM 25 2.6 SIMULATION NUMERICAL RESULTS 29 CHAPTER 3 RATE TCP 35 3.1 REFINED PACKET-PAIR RATE PROBING 35 3.2 PROBING WITH VARIABLE PACKET SIZE 40 3.3 ANALYSIS OF REFINED PACKET-PAIR PROBING SCHEME 43 3.4 NUMERICAL QUEUE OCCUPANCY REDUCTION 52 3.5 CONGESTION AVOIDANCE ALGORITHM 60 3.6 SIMULATION RESULTS 61 CHAPTER 4 DOUBLE-SCOREBOARD 64 4.1 DOUBLE-SCOREBOARD LOSS DETECTION 67 4.2 CONGESTION AVOIDANCE EXTENSION 74 4.3 SIMULATION RESULTS 75 CHAPTER 5 IMPLEMENTATION 79 5.1 LINUX PACKET FLOW 79 5.2 PSEUDO RATE TCP IMPLEMENTATION 81 5.3 PERFORMANCE EVALUATION 85 CHAPTER 6 CONCLUSION AND FUTURE WORK 93 BIOGRAPHY 94 CURRICULUM VITA 98 PUBLICATION LIST 99