臺灣博碩士論文加值系統

摘要
在網際網路發達的現代化社會，網路通訊已成為日常生活中重要的一環，越來越多的事情都必須利用網路服務完成；在這樣的環境下，頻寬分配公平性的保證，與網路壅塞的控制，就更顯得重要。近十年來，路由器上對於網路壅塞的控制，已經有超過50種以上不同的設計。這些不同的設計，主要探討如何避免壅塞發生，以及當壅塞發生時如何盡快讓網路恢復穩定，避免封包遺失，減少封包延遲，並提升網路有效使用率。這些不同的設計均以單一壅塞網段為研究標的；在多壅塞區段網路環境，如何有效控制網路壅塞，並確保個別資料流的公平性(Fairness)，目前仍缺乏一套有效的辦法。
本論文探討多重壅塞網路中單一資料流資源匱乏(Starvation)的問題，並提出解決方案。我們結合核心路由器(Core router)、邊境路由器(Edge Router)及主動式佇列管理(AQM，Active Queue Management)運作，簡化核心路由器的工作，將封包分類(Packet Classification)的工作交由邊境路由器負責，而核心路由器則使用多的虛擬佇列(Virtual Queue)，將不同類別的資料流(或叫封包(Packet))分開進行控管，來達到資料流的公平性，同時也可以確保良好的壅塞控制，並有效提高各資料流的傳輸服務品質。
本論文所提出的機制，利用壅塞視窗(Congestion Window)做為關聯，以TCP的ECN欄位記載封包傳輸路徑壅塞相關資訊，並依據此路徑資訊，配合主動式佇列管理機制，調節虛擬佇列控制參數，並進一步利用ECN欄位特性，依通過壅塞網段多寡，更動其優先權(Priority)，據以調整虛擬佇列的控制參數。在此機制設計下，通過越多壅塞網段的封包將可獲得越高的優待可以順利通過網路，同時也不至於對其他資料流造成太大的衝擊。我們藉此改善因為多瓶頸網路造成的資料流公平性問題 (Fairness)，降低網路頻寬浪費，避免網路資源匱乏的情形發生，同時提高網路利用率(Link utilization)及吞吐量(Throughput)，維持佇列穩定度(Queue Stability)。
我們使用眾所周知的網路模擬器NS2，透過實驗設計與數據量測的結果，來驗證本方法的可行性。

abstract
There has been a strong demand for quality of service (QoS) and fairness among flows in the modern day Internet. The assurance of fair bandwidth allocation and effective congestion control have attained a lot of attention. In the past decade, more than fifty different congestion control algorithms have been proposed. Their focus is mainly on congestion avoidance, and fast recoving of network stabilization. Avoiding packets loss, reducing packets delay and enhancing the network utilization are the three most important issues. However, effective control of network congestion and fair bandwidth allocation to individual data flows have not been addressed.
This thesis studies the bandwidth starvation problem in a network with multiple bottlenecks. We propose a solution to this problem. Our new approach includes the operation of core routers and edge routers. In our proposed approach, edge routers are responsible for packets classification and marking, while core routers employ virtual queues to buffer packets from different category for a differentiated congestion control.
Based on the observation of congestion window variation, the new approach inserts congestion information into the ECN field of the packet header. Active queue management mechanism applies this information to retrieve upstream link congestion status and accordingly to regulate control parameters for each virtual queue. Furthermore, we make use of the information in ECN field to vary the number of congestion links that a packet has passed, assign its priority, and adjust the controlled parameter for its virtual queue. We give a higher priority to a packet passing through more congestion links. By carefully adjusting control parameters, we can avoid bandwidth wasted by a long-path flow, and decrease the impact on other data flows. Our new approach can solve the fairness problem causing by multiple bottlenecks. In addition, it can also reduce network bandwidth waste and avoid network resource starvation. Hence, the network link utilization and throughput are increased, and queue stability is maintained as well.
We use ns-2, a well-known network simulator, to verify the feasibility of this method through extensive simulations.

目錄
致謝 i
摘要 ii
abstract iii
圖目錄 viii
表目錄 ix
第１章 導論 1
1.1 簡介 1
1.2 研究動機 2
1.3 研究方向與實做 3
1.4 章節介紹 4
第２章 背景知識及相關研究 5
2.1 背景知識 5
2.1.1 傳送控制協定TCP(Transfer Control Protocol) 5
2.1.2 壅塞控制視窗(Congestion Window) 6
2.1.3 網路壅塞及壅塞網段(Bottleneck) 8
2.1.4 佇列管理機制(Queue Management) 9
2.1.4.1 Drop Tail： 10
2.1.4.2 RED (Random Early Detection)： 10
2.1.5 差別式服務網路(Differentiated Service) 12
2.1.6 延遲(Latency)及抖動率(Jitter) 14
2.1.7 明確壅塞通知(Explicit Congestion Notification) 14
2.2 相關研究 16
第３章 問題與解決方案 19
3.1 問題現象 19
3.1.1 公平性問題 20
3.1.2 效能下降問題 20
3.2 依實驗數據發現問題 21
3.2.1 吞吐量(Throughput) 22
3.2.2 壅塞控制視窗(Congestion Window) 24
3.2.3 封包遺失(Packet loss) 26
3.2.4 封包延遲(Delay) 28
3.3 解決方案 30
3.4 模擬實驗平台—NS2模擬器 32
第４章 模擬結果及分析 36
4.1 網路環境介紹 36
4.1.1 實作模擬環境介紹 36
4.1.2 壅塞感知功能的動態佇列管理機制實作環境 37
4.2實驗數據分析 42
4.2.1 具壅塞感知動態佇列管理機制下(Congestion-Aware AQM scheme)的吞吐量(Throughput) 42
4.2.2 具壅塞感知動態佇列管理機制下(Congestion-Aware AQM scheme)的壅塞控制視窗(Congestion Window)變化 45
4.2.3 具壅塞感知動態佇列管理機制下(Congestion-Aware AQM scheme)的封包遺失(Packet Loss) 48
4.2.4 具壅塞感知動態佇列管理機制下(Congestion-aware AQM scheme)的封包延遲(Delay) 51
4.3 C-A AQM scheme機制下調整佇列捨棄率變化 55
4.3.1 C-A AQM scheme 下佇列調整 55
4.3.2 C-A AQM scheme 下佇列捨棄率為等差狀態 56
4.3.2.1 C-A AQM scheme 下佇列為等差狀態的吞吐量： 56
4.3.2.2 C-A AQM scheme 下佇列為等差狀態的封包捨棄： 58
4.3.2.3 C-A AQM scheme 下佇列為等差狀態的延遲： 59
4.3.3 C-A AQM scheme 下佇列捨棄率為等比狀態 60
4.3.3.1 C-A AQM scheme佇列捨棄率為等比狀態的吞吐量： 60
4.3.3.2 C-A AQM scheme 下佇列為等比狀態的封包捨棄： 62
4.3.3.3 C-A AQM scheme 下佇列為等比狀態的延遲： 63
第５章 結論和未來研究方向 65
References 67
Electronic Resources 69

References
[1] J. Postel, “Transmission Control Protocol,” RFC793, Sep. 1981.
[2] Joerg Widmer, “A Survey on TCP-Friendly Congestion Control,” IEEE Network, June 2001.
[3] Floy S, Jacobson V., “Random Early Detection Gateways for Congestion Avoidance”, IEEE / ACM Transactions on Networkings, 1993.
[4] W. Fang, N. Seddigh and B. Nandy, “A Time Sliding Window Three Color Marker (TSWTCM),” IETF RFC 2859, Jun. 2000.
[5] J. Heinanen, R. Guerin, “A Two Rate Three Color Marker,” IETF RFC 2698, Sep. 1999.
[6] D.D. Clark, W. Fang, “Explicit allocation of Best Effort Packet Delivery Service”,IEEE/ACM Transactions on Networking, August 1998, Vo16. No.4,pp.362-373.
[7] Sally Floyd, “Connection with Multiple Congested Gateways in Packet - Switched Network part I: One-way traffic,”Computer Communication Review, 1991
[8] W. Stevens, “TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms,” RFC2001, Jan.1997.
[9] M. Allman, V.paxson, and W. Stevens. RFC 2581:TCP Congestion Control, April 1999.
[10] K.Fall and S. Floyd. Simulation-based comparisons of Tahoe, Reno, and SACK TCP. ACM computer Communication Review, 26(3):5-21,July 1996.
[11] S.Floyd, S. Ratnasamy, and S. Shenker, “Modifying TCP’s Congestion Control for High Speeds”, - draft, May 2002
[12] Xiaoyang Lin, Xiaolin Chang, and Jogesh K. Muppala, “VQ-RED: An Efficient Virtual Queue Management Approach to Improve Fairness in Infrastructure WLAN”, The IEEE Conference on Nov-2005, pp. 632-638.
[13] Bala, K., Cidon, I., and Sohraby, K., “Congestion Control for High Speed Packet Switched Networks”, INFOCOM ’90, pp. 520-526, 1990.
[14] Hashem, E., “Analysis of random drop for gateway congestion control”, Report LCS TR-465, Laboratory for Computer Science, MIT, Cambridge, MA, 1989, p.103.
[15] G. Di Fatta; F. Hoffmann; G. Lo Re; A. Urso, “A genetic algorithm for the design of a fuzzy controller for active queue management” , The IEEE Transaction on Volume 33, Issue 3, Aug. 2003
[16] A. Dhamdhere, H. Jiang, and C. Dovrolis, “Buffer Sizing for Congested Internet Links,” in Proceedings of IEEE INFOCOM, March 2005.
[17] D. Y. Eun and X. Wang, “Stationary Behavior of TCP/AQM with Many Flows under Aggressive Packet Marking,”in IEEE International Conference on Communication, 2005.
[18] P. Tinnakornsrisuphap and R. J. La,“Characterization of Queue Fluctuations in Probabilistic AQM Mechanisms,” in Proceedings of ACM SIGMETRICS, June 2004.
[19] D. Y. Eun and X. Wang, “Performance Modeling of TCP/AQM with Generalized AIMD under Intermediate Buffer Sizes,”tech. rep., North Carolina State University, Raleigh, NC, Oct. 2005.
[20] D. Y. Eun and N. B. Shroff, “A Measurement-Analytic Approach for QoS Estimation in a Network based on the Dominant Time Scale,” IEEE/ACM Transactions on Networking, vol. 11, pp. 222–235, April 2003.
[21] G. Raina and D. Wischik, “Buffer sizes for large multiplexers: TCP queueing theory and instability,” in EuroNGI, April 2005.
[22] S. H. Low, F. Paganini, J. Wang, and J. C. Doyle,“Linear stability of TCP/RED and a scalable control,” Computer Networks, vol. 43, pp. 633–647, Dec.2003.
[23] Paganini, F., Wang, Z., Doyle, J.C., and Low, S.H.: ‘Congestion control for high performance, stability and fairness in general networks’, IEEE/ACM Trans. Networking, 2005, 13, (1), pp. 43–56
[24] Kunniyur, S., and Srikant, R.: ‘An adaptive virtual queue (AVQ) algorithm for active queue management’, IEEE/ACM Trans. Networking, 2004, 12, (2), pp. 286–299
[25] Hollot, C.V., Misra, V., Towsley, D., and Gong, W.B.: ‘Analysis and design of controllers for AQM routers supporting TCP flows’, IEEE Trans. Autom. Control, 2002, 47, (6), pp. 945–959