針對串流應用程式所設計的低延遲及高效率的封包排程

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：16

、訪客IP：52.14.150.55

姓名

賴旭德(Hsu-Te Lai) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

針對串流應用程式所設計的低延遲及高效率的封包排程
(Low Latency and Efficient Packet Scheduling for Streaming Applications)

相關論文

★ 具多重樹狀結構之可靠性群播傳輸	★ 在嵌入式行動裝置上設計與開發跨平台Widget
★ 在 ARM 架構之嵌入式系統上實作輕量化的手持多媒體播放裝置圖形使用者介面函式庫	★ 基於網路行動裝置所設計可擴展的服務品質感知GStreamer模組
★ 針對行動網路裝置開發可擴展且跨平台之GSM/HSDPA引擎	★ 於單晶片多媒體裝置進行有效率之多格式解碼管理
★ IMS客戶端設計與即時通訊模組研發：個人資訊交換模組與即時訊息模組實作	★ 在可攜式多媒體裝置上實作人性化的嵌入式小螢幕網頁瀏覽器
★ 以IMS為基礎之及時語音影像通話引擎的實作:使用開放原始碼程式庫	★ 電子書嵌入式開發: 客制化下載服務實作, 資料儲存管理設計
★ 於數位機上盒實現有效率訊框參照處理與多媒體詮釋資料感知的播放器設計	★ 具數位安全性的電子書開發：有效率的更新模組與資料庫實作
★ 適用於異質無線寬頻系統的新世代IMS客戶端軟體研發	★ 在可攜式數位機上盒上設計並實作重配置的圖形使用者介面
★ Friendly GUI design and possibility support for E-book Reader based Android client	★ Effective GUI Design and Memory Usage Management for Android-based Services

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

即時性的應用程式(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.

關鍵字(中)

★ 即時應用程式
★ 封包排程

關鍵字(英)

★ packet scheduling
★ real-time application
★ streaming
★ queuing

論文目次

Chapter 1 INTRODUCTION 1
Chapter 2 RELATED WORK 6
2.1 Class Based Queue 6
2.2 Weighted Fair Queue 6
2.3 Worst-case Fair Weighted Fair Queuing (WF2Q) 9
2.4 Delay Optimized Worst Case Fair WFQ (WF2Q) Packet Scheduling 11
2.5 Deficit Round Robin 13
2.6 Nested Deficit Round Robin 14
2.7 A Dynamic Regulation and Scheduling Scheme for Real-Time Traffic Management (RCSP) 15
2.8 Motivation of LLEPS 16
Chapter 3 OVERVIEW OF LLEPS 20
Chapter 4 DETAILED ALGORITHM 23
4.1 Components of LLEPS 23
1) Queues: 24
2) Min Heap: 24
3) System Timer: 25
4) Scheduler: 25
4.2 Function Descriptions 26
Chapter 5 SIMULATION Experiments 35
5.1 Simulation Environment 35
5.2 Bandwidth Sharing 35
5.3 Bandwidth Reservation 38
5.4 Buffer Under Run Problem 39
5.5 Delay Comparison of LLEPS, WFQ and NDRR 43
5.6 Two Problems of LLEPS 45
Chapter 6 IMPROVED ALGORITHM 48
Chapter 7 CONCLUSION AND FUTURE WORK 50
REFERENCES 52

參考文獻

[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.

指導教授

吳曉光(Hsiao-Kuang Wu)

審核日期

2003-7-5

推文