臺灣博碩士論文加值系統

近來網際網路快速的成長下，如何有效公平分配頻寬和避免網路崩潰的議題更顯重要。TCP乃是現今網路上最主要的壅塞控制的協定。TCP提供可靠性位元組流服務協定，也有壅塞控制的機制來防止過多的資料被傳送至網路，使得路由器或網路過載。然而TCP的表現會遭受和其他種傳輸協定競爭，和網路上不同RTT及動態改變可用頻寬等因素所影響。TCP允許不公平分配頻寬。擁有較大RTT的TCP資料流搶得較少的頻寬。因此，在未來的網際網路上，我們需要更快反應與更明確的流量控制機制。在此論文中我們針對此問題做研究。我們提出一新的架構，提供更快速、明確的方法來公平分配頻寬，並且可提供最小頻寬保證服務的機制。我們所提出端點對端點網路層的流量控制機制的基本概念乃是取至於非同步傳輸模式(ATM)網路所提供的可用速率(ABR)的服務類別。由於複雜度的問題，阻礙了ABR服務無法執行於網際網路上。我們所提出利用回授控制來明確指示速率的演算法適用於網際網路路由器上。路由器並不維持每個資料流狀態，他們只維持一個先進先出的佇列，同時利用一種簡單且快速的方法來估算資料流數目，及其他所需的資訊，用來算出最佳公平速率。在論文中我們經由詳細的模擬，證明利用明確指示速率來避免壅塞之機制可以達到相當好的公平性，並且適用於各種網路狀態。這個新的機制稱為利用明確指示速率來避免壅塞之機制。

Efficient fair bandwidth allocation and prevention of network collapse are significant in the high-speed networks. Transmission Control Protocol (TCP) is dominant in the current Internet for congestion control. However, TCP performance is affected by characteristics of competing flows and networks, such as, different round trip delays and dynamically changing available bandwidth. TCP allows unfair bandwidth allocation among flows.Furthermore, TCP flows with longer round trip delay get little bandwidth. Therefore, we need a faster response and more explicit flow control mechanism in the future Internet.In this thesis, we propose a novel explicit rate-based congestion avoidance scheme. The scheme is similar to ATM Available Bit Rate (ABR) services but its complexity is largely reduced to be able to implement in IP networks. In our proposed scheme, sources can adapt their sending rate according to network status. Adaptation of sending rates converges to max-min fairness with minimal rate guarantee. Furthermore, routers do not maintain per flow state; they use FIFO packet scheduling enhanced by an explicit rate feedback mechanism with estimations, including number of active flows, number of bounded flows and total bounded rate, based on a simple algorithm motivated from Bloom filter. We present and discuss simulations on the performance under various network conditions. The novel scheme is called Congestion Avoidance with Explicit Rate Indication (CAERI).

1. Introduction..................................1
1.1 Network Overview.............................1
1.2 Motivation for the Thesis....................3
1.3 Organization.................................4
2. Related Works and Summary of Result...........6
2.1 Credit-Based Approaches......................6
2.1.1 Discussion.................................8
2.2 ATM Rate-Based Approaches....................8
2.2.1 Binary Feedback Schemes....................9
2.2.1.1 Discussion...............................9
2.2.2 MIT Scheme................................10
2.2.2.1 Discussion..............................11
2.2.3 USCS Scheme...............................12
2.2.3.1 Discussion..............................14
2.2.4 CACP2 Scheme..............................15
2.2.4.1 Discussion..............................16
2.2.5 ERICA Scheme..............................16
2.2.5.1 Discussion..............................18
2.3 Recently Rate-Based Approaches..............19
2.3.1 CPG Scheme................................19
2.3.1.1 Discussion..............................21
2.3.2 Control-Theoretic Scheme..................22
2.3.2.1 Discussion..............................23
2.3.3 IPRC Scheme...............................24
2.3.3.1 Discussion..............................25
2.4 Summary and Discussion......................26
3. Optimality Criterion.........................28
3.1 Definition of the MAXMIN Optimum............29
3.2 Some of other Fairness Criteria.............30
4. Congestion Avoidance with Explicit Rate
Indication......................................33
4.1 Estimation of Number of Active Flows........34
4.2 ICMP Control Message........................36
4.3 Architecture of CAERI.......................38
4.3.1 Source Operation..........................39
4.3.2 Router Operation..........................39
4.3.3 Destination Operation.....................42
5. Convergence Properties.......................43
5.1 Convergence of the CAERI....................44
5.2 Convergence of Time.........................49
6. Simulation Results...........................51
6.1 Single Congestion Link......................52
6.2 Multiple Congestion Links...................55
6.3 Fairness among Flows with Different End-to-End Delay...........................................67
6.4 Summary of the Simulation Results...........69
7. Discussion...................................71
7.1 Discuss with the Minimal Rate Guarantee.....71
7.2 CAERI Operates in DiffServ Networks.........72
8. Summary and Future Work......................75
9. References...................................77

[1] ATM Forum, “ATM Forum Traffic Management
Specification Version 4.1,af-tm-0121.000,”March 1999.
[2] H. T. Kung, “Flow Control Virtual Connections Proposal for ATM Traffic Management,”ATM Forum 94-0632R2, September 1994.
[3] R. Jain, S. Kalyanaraman, and R. Viswanathan, “Simulation results: The EPRCA+ scheme,”ATM Forum, 94-0988, October 1994
[4] Anna Charny, David D. Clark, and Raj Jain,
“Congestion control with explicit rate indication,”In Proceedings of the IEEE International Communications Conference, June 1995.
[5] Lampros Kalampoulkas, Anujan Varma, and K.K.
Ramakrishan, “An efficient rate allocation algorithm for atm networks providing max-min fairness,” In 6th IEIP International Conference on High Performance Networking, September 1995.
[6] A. W. Barnhart, “Example Switch Algorithm for TM Spec,”ATM Forum 95-0195, February 1995.
[7] S. Kalyanaraman, and Raj Jain et. al., “The
ERICA Switch Algorithm for ABR Traffic Management in ATM Networks,”IEEE/ACM Transactions on Networking, February 2000.
[8] Jordi Ros, and Wei Kang Tsai, “A Theory of
Convergence order of max-min rate allocation and an optimal protocol,”INFOCOM, 2001
[9] Song Chong, Sangho Lee, and Sungho Kang,“A
simple, scalable, and stable explicit rate allocation algorithm for max-min flow control with minimum rate guarantee,” IEEE/ACM Transactions on Networking, June 2001
[10] L. Benmohamed, and S. M. Meerkov, “Feedback
Control of Congestion in Packet Switching Networks: The Case of Single Congested Node,” IEEE/ACM Transactions on Networking, December 1993.
[11] Mustafa A.A, Hassan M, and Jha S,“Design and Performance Evaluation of a Rate Feedback Control Architecture for TCP/IP Networks,”Computing, and Communications Conference, 2002. 21st IEEE International, 2002.
[12] J. Postel, “Internet Control Message Protocol,”IETF RFC 792, September 1981
[13] B. Bloom. Space/time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, July 1970.
[14] Cristian Estan, George Varghese, and Mike
Fisk,“Bitmap algorithms for counting active flows on high speed links,”UCSD technical report CS2003-0738, March 2003.
[15] http://www.isi.edu/nsnam/ns/
[16] Shakkottai S., Kumar A., Karnik A., and Anvekar A. “TCP performance over end-to-end rate control and stochastic available capacity,” IEEE/ACM Transactions on Networking, August 2001.