臺灣博碩士論文加值系統

CSFQ可以利用低設計複雜度達到網路頻寬公平共享。基於此架構，每個核心路由器只在本身區域決定公平性，而往往忽略可能在下游端發生的壅塞。CSFQ不能避免封包因於中途被丟棄而發生的網路崩潰。
在本篇論文中，我們利用回饋控制加強CSFQ。我們最主要的想法是在出口路由器監測每筆網路串流的標籤，入口路由器則定期地送控制封包至出口路由器。當出口路由器收到入口路由器送來的控制封包，它會將先前監測到的流量平均速率送回去。而入口路由器再根據回傳的控制封包來決定對該筆網路串流應調整的速度。
這篇論文最主要的貢獻在於使得CSFQ避免造成網路的崩潰，並達到全域最大-最小公平性。由模擬數據顯示我們的方法是一個達到此目的之簡單方法。

The Core-Stateless Fair Queueing (CSFQ) is designed to achieve fair bandwidth sharing with low implementation complexity. It makes the decisions locally at each router and ignores congestion that may occur downstream. CSFQ can not prevent congestion collapse from undelivered packets.
In this thesis, we enhance CSFQ with the feedback control. The key idea is to monitor each flow’s label in the egress router. The ingress router periodically sends control packet to the egress router. When the forward control packet arrives at the egress router, the egress router takes the result of average fair share rate into the feedback control packet and turns it around. The ingress router uses the information carried in the backward control packet to regulate the rate of the flow.
Our key contribution is to enhance CSFQ such that it prevents congestion collapse from undelivered packets and achieves global max-min fairness. Through the simulation, we show that our enhancement is a feasible way that allows CSFQ to achieve the global max-min fairness.

CHAPTER 1 INTRODUCTION 1
CHAPTER 2 BACKGROUND AND RELATED WORKS 3
2.1 QUALITY OF SERVICE IN IP NETWORKS 3
2.1.1 Integrated Services 3
2.1.2 Differentiated Services 5
2.2 CONTROL BEST-EFFORT TRAFFIC 7
2.3 THE DEFINITION OF FAIRNESS 9
2.4 CSFQ MECHANISM 10
2.4.1 Architecture 10
2.4.2 Edge Router 12
2.4.3 Core router 13
2.5 PROBLEM DESCRIPTION 15
2.5.1 Congestion Collapse 15
2.6 DESIGN GOAL 17
2.6.1 Global Max-min Fairness 17
2.6.2 Approximate the Fairness of TCP Competing with UDP Flows 18
CHAPTER 3 PROPOSED METHOD 19
3.1 THE IMPACT OF FAIR SHARE RATE 19
3.2 BEHAVIOR OF AN EDGE ROUTER 21
3.3 CONGESTION DETECTION 23
3.3.1 Estimate The Round Trip Time 23
3.3.2 Treat the Network as a “BIG FIFO” 24
3.4 THE RATE CONTROL ALGORITHM 27
CHAPTER 4 SIMULATION RESULTS 30
4.1 THE IMPACT OF CONGESTION COLLAPSE 31
4.2 MULTIPLE CONGESTED LINKS 35
4.3 APPROXIMATE THE FAIR SHARE WHEN TCP FLOW IS COMPETING WITH UNRESPONSIVE FLOWS 36
CHAPTER 5 CONCLUSION 39
REFERENCE 40

[1] Sally Floyd and Kevin Fall, “Promoting the use of end-to-end congestion control in the internet,” IEEE/ACM Transactions on Networking, Auguest 1999.
[2] Dimitri Bertsekas and Robert Gallager, Data Networks, chapter 6, pp.524-529, Prentice-Hall,1987.
[3] I. Stoica, S. Shenker, and H. Zhang, “Core-stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks,” ACM SIGCOMM 98, Auguest 1998, Canada.
[4] Ucb/lbnl/vint network simulator —ns (version 2)
[5] Celio Albuquerque, Brett J. Vickers and Tatsuya Suda, “Network Border Patrol” IEEE Infocomm 2000.
[6] K.K Ramakrishnan and R. Jain, “A Binary FeedBack Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Laywer,” ACM Transactions on Computing Systems, 1990
[7] George Varghese, “Efficient fair queuing using deficit round robin,” in Proceedings of ACM SIGCOMM 96, October 1996
[8] I. Stoica “simulation code for CSFQ,” http://www.cs.berkeley.edu/~istoica/csfq/,1998
[9] R. Braden, D. Clark, and S. Shenker,” Integrated Services in the Internet Architecture: an Overview,” RFC 1633, June 1994
[10] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An Architecture for Differentiated Services,” RFC 2475, December 1998
[11] J. Wroclawski, “Specification of Controlled-Load Network Element Service,” RFC 2211, September 1997
[12] S. Shenker, C. Partridge, and R. Guerin “Specification of Guaranteed Quality of Service,” RFC 2212, September 1997
[13] J. Wroclawski,”The Use of RSVP with IETF Integrated Services,” RFC2210, September 1997
[14] V. Jacobson, K. Nichols, K. Poduri “An Expedited Forwarding PHB” RFC 2598,June 1999
[15] J. Heinanen, F. Baker, W. Weiss, J. Wroclawski, “Assured Forwarding PHB Group”, RFC 2597,June 1999
[16] Lawrence S.Brakmo, Sean W.O’Malley, Larry L.Peterson “TCP Vegas: New Techniques for Congestion Detection and Avoidance” SIGCOMM,1994