臺灣博碩士論文加值系統

即時性的應用程式(Real-Time Applications)需要有足夠的頻寬預留才可運作順暢。Class Based Queue (CBQ), Nested Deficit Round Robin(NDRR)之類的封包排程方式主要就是針對頻寬保留所設計的。然而這些方式會造成網路封包的延遲時間的不穩定，而使得應用程式需要使用更大的封衝區來播放媒體串流(media stream)。即時性應用程式大體來說希望有較小的封包延遲。然而長及不穩定的封包延遲時間會危及到服務品質(Quality of Service)。目前有些封包排程方式可以使封包的延遲時間相當穩定，但是它們需要知道每個串流(flow)的細節。GPS (General Processor Sharing)-like的封包排程方式並沒有考量到串流資料實際的運作情形。一條經過許多路由器所遞送的串流不會是非常平順的。而GPS-like的封包排程方式還到這些不平順的串流時會產生額外的封包延遲時間。在這篇論文中，我們提出了一個可以針對串流應用程式(streaming applications)提供低延遲及有效率的封包排程方式名為LLEPS，以保證串流應用程式可以運作順暢。

Adequate bandwidth allocations and strict delay requirements are critical for real time applications. Packet scheduling algorithms like Class Based Queue (CBQ), Nested Deficit Round Robin (Nested-DRR) are designed to ensure the bandwidth reservation function. However, they might cause unsteady packet latencies and introduce extra application handling overhead, such as allocating a large buffer for playing the media stream. High and unstable latency of packets might jeopardize the corresponding Quality of Service since real-time applications prefer low playback latency. Existing scheduling algorithms which keep latency of packets stable require knowing the details of individual flows. GPS (General Processor Sharing)-like algorithms does not consider the real behavior of a stream. A real stream is not perfectly smooth after forwarded by routers. GPS-like algorithms will introduce extra delay on the stream which is not perfectly smooth. This thesis presents an algorithm which provides low latency and efficient packet scheduling service for streaming applications called LLEPS.

Chapter 1 INTRODUCTION1
Chapter 2 RELATED WORK6
2.1 Class Based Queue6
2.2 Weighted Fair Queue6
2.3 Worst-case Fair Weighted Fair Queuing (WF2Q)9
2.4 Delay Optimized Worst Case Fair WFQ (WF2Q) Packet Scheduling11
2.5 Deficit Round Robin13
2.6 Nested Deficit Round Robin14
2.7 A Dynamic Regulation and Scheduling Scheme for Real-Time Traffic Management (RCSP)15
2.8 Motivation of LLEPS16
Chapter 3 OVERVIEW OF LLEPS20
Chapter 4 DETAILED ALGORITHM23
4.1 Components of LLEPS23
1)Queues:24
2)Min Heap:24
3)System Timer:25
4)Scheduler:25
4.2 Function Descriptions26
Chapter 5 SIMULATION Experiments35
5.1 Simulation Environment35
5.2 Bandwidth Sharing35
5.3 Bandwidth Reservation38
5.4 Buffer Under Run Problem39
5.5 Delay Comparison of LLEPS, WFQ and NDRR43
5.6 Two Problems of LLEPS45
Chapter 6 IMPROVED ALGORITHM48
Chapter 7 CONCLUSION AND FUTURE WORK50
REFERENCES52

[1]S. Blake, D. Black, M.Carlson, E. Davies, Z. Wang and W. Weiss, “An architecture for differentiated services”, RFC 2475, December 1998.
[2]K. Nichols, V. Jacobson and L. Zhang, “Two-bit differentiated services architecture for the Internet”, IETF RFC 2638, July 1999.
[3]R. Braden and D. Clark, “Integrated Services in the Internet Architecture: An Overview”, RFC 1633, July 1994.
[4]R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin, ”Resource ReSerVation protocol (RSVP) — Version 1 Functional Specification”, RFC 2205, September 1997.
[5]A. K. Parekh, “A generalized processor sharing approach to flow control in integrated services networks”, Ph.D. thesis, Dept. Elec. Eng. Comput. Sci., MIT, 1992.
[6]A. K. Parekh and R. G. Gallagher, “A generalized processor sharing approach to flow control in integrated services networks: the single-node case”, IEEE/ACM Transactions on Networking, June 1993.
[7]L. Zhang, “VirtualClock: A new traffic control algorithm for packet switching networks”, Proc. ACM SIGCOMM’90, August 1990.
[8]G. Xie and S. Lam, “Delay guarantee of virtual clock server”, IEEE/ACM Transactions on Networking, December 1995.
[9]S. Floyd and V. Jacobson, “Link-Sharing and resource management models for packet networks”, IEEE/ACM Transactions on Networking, August 1995.
[10]KJ. Loh, I. Gui and KC. Chua, “Performance of a Linux Implementation of Class Based Queueing”, Computer Communications and Networks Proceeding, October 1998.
[11]K. Cho. “A Framework for Alternate Queueing: Towards Traffic Management by PC-UNIX Based Routers”, Annual Technical Conference, USENIX, 1998.
[12]The Linux Project. http://www.linux.org/
[13]The FreeBSD Project. http://www.freebsd.org/
[14]A. Demers, S.Keshav and S.Shenker, “Design and Analysis of a fair queueing algorithm”, Proceeding of ACM SIGCOMM, September 1989.
[15]J. C. R. Bennett and H. Zhang, “Hierachical packet fair queueing algorithms”, Proc. SIGCOMM’96, August 1996.
[16]S. J. Golestani, “A self-clocked fair queueing scheme for broadband applications”, Proceedings of IEEE INFOCOM, June 1994.
[17]P. Goyal, H. M. Vin, and H. Cheng, “Start-time fair queueing: A scheduling algorithm for integrated services packet switching networks”, TR-96-02, Dept. Comput. Sci., Univ. Texas at Austin, Jan 1996.
[18]Jon C.R. Bennett and Hui Zhang, ”WF2Q: Worst-case Fair Weighted Fair Queueing”, INFOCOM ’96, Proceedings IEEE, Mar 1996
[19]X. Fei and A. Marshall, “Delay Optimized Worst Case Fair WFQ (WF2Q) Packet Scheduling”, ICC 2002, IEEE International Conference, 2002.
[20]N. Figucra and J. Pasquale, “Leave-in-time: A new service discipline for real-time communication in a packet-switching data network”, Proc. SIGCOMM’95, September 1995.
[21]A. Greenberg and N. Madras, “How fair is fair queueing”, J. ACM, July 1992.
[22]S. Keshav, “On the efficient implementation of fair queueing”, Internetworking: Research and Experience, September 1991.
[23]M. Shreedhar and George Varghese, “Efficient fair queueing Using deficit round-robin”, IEEE Transactions on Networking, Jane 1996.
[24]Salil S. Kanhere and Harish Sethu, “Fair, Efficient and Low-Latency Packet Scheduling using Nested Deficit Round Robin”, Proceedings of the IEEE Workshop on High-Performance Switching and Routing (HSPR), May 2001
[25]H. Zhang and D. Ferrari. “Rate-Controlled service disciplines”, Journal of High Speed Networks, 1994.
[26]H. Zhang and D. Ferrari, “Rate-Controlled static-priority queueing”, Proc. IEEE INFOCOM ’93, September 1993
[27]S. Iatrou and I. Starvrakakis, “A Dynamic Regulation and Scheduling Scheme for Real-Time Traffic management”, IEEE/ACM Transactions on Networking, February 2000.
[28]H. Schulzrinne, S. Casner, R. Frederick and V. Jacobson. “RTP: A Transport Protocol for Real-Time Application”, RFC1889, 1996.
[29]http://www.isi.edu/nsnam/ns/
[30]V. Jacobson, “Congestion Avoidance and Control”, Proceeding of ACM SIGCOMM, August 1988.
[31]S. Floyd and V. Jacobson, “Random early detection for congestion avoidance”, IEEE/ACM Transactions on Networking, July 1993.
[32]D. Lin and R. Morris, “Dynamic of Random Early Detection”, Proceeding of ACM SIGCOMM, September 1997.
[33]W. Feng, D. Kandlur, D. Saha, and K. Shin., “A Self-Configuring RED Gateway”, Proc. IEEE INFOCOM, March 1999.
[34]K. Ramakrishnan and S. Floyd, “A Proposal to Add Explicit Congestions Notification (ECN) to IP”, RFC 2481, January 1999.
[35]Wu-Chang Feng, Kandlur, D.D., Saha D. and Shin K.G., ”Stochastic fair blue: a queue management algorithm for enforcing fairness”, Proceeding of IEEE, INFOCOM 2001, April 2001.
[36]Wu-Chang Feng, Shin K.G., Kandlur D. D. and Saha D., ”The BLUE active queue management algorithms”, IEEE/ACM Transaction on Networking, August 2002.
[37]W. Richard Steven, “TCP/IP Illustrated Volume 1: The Protocols”, Addison-Wesley.
[38]Gary R. Wright and W. Richard Steven, “TCP/IP Illustrated Volume 2: The Implementation”, Addison-Wesley.
[39]M. Mathis et al., “TCP Selective Acknowledgement Options”, RFC 2018, April 1996.
[40]S. Floyd, “A Report on Recent Developments in TCP Congestion Control”, IEEE Communications Magazine, April 2001.