支援即時應用之累積信用低延遲封包排程演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：24

、訪客IP：18.226.150.175

姓名

陳律翰(Lyu-han Chen) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

支援即時應用之累積信用低延遲封包排程演算法
(Credit-based Low Latency Packet Scheduling Algorithm for Real-time 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 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

諸如聲音、影像等的即時資料串流通常都不能忍受很高且不穩定的封包延遲。不幸的是，像WFQ (Weighted Fair Queueing)、SFQ (Start-time Fair Queueing)等為人所熟悉的演算法，在現實的網路環境當中都會遭遇由於封包到達時間不穩定所造成的封包延遲過大且不穩定的問題，最近幾年有些演算法試圖解決這個問題，例如LLQ (Low Latency Queueing)，但在LLQ演算法裡，只有高優先權的資料流有低延遲的保證，那些低優先權的資料流則有可能會有無法被服務的情形發生。LLEPS (Low Latency and Efficient Packet Scheduling)演算法也試圖解決這個問題，但是LLEPS需要很準確的時間間隔(time slot)支援，如果這個時間不準確，LLEPS仍會遭遇到不穩定的封包延遲問題，且如何正確地決定這個時間間隔在LLEPS這篇論文裡面並沒有提出，也仍是一個未解的問題，除此之外，即使LLEPS擁有準確的時間間隔，當封包以爆發(burst)形式出現時，LLEPS仍會遭遇封包延遲過大的問題。
因此在本篇論文中，我們利用累積信用的方式來保證即時資料串流有最低的延遲，並且透過模擬與之前所提出來的演算法做比較。

摘要(英)

Real-time traffic flows, such as streaming audio and video data, can not endure high or unsteady packet latencies. Unfortunately, some well-known scheduling algorithms such as Weighted Fair Queueing (WFQ), Start-Time Fair Queueing (SFQ)...etc. in real networks will be subjected to high and unsteady latencies due to the unsteady queueing delay problem, `the buffer underrun problem’’, that we will explain later in this paper. A few scheduling algorithms address this problem in recent years like Low Latency Queueing (LLQ) which may suffer from low priority traffic starvation problem. The QoS guarantee only satisfies the flow with highest priority. Another one that addresses this problem is Low Latency and Efficient Packet Scheduling algorithm (LLEPS) which requires additional parameter, time slot, support accurately. And how to determine the time slot value exactly to enable LLEPS to work efficaciously is another problem and is not mentioned in LLEPS. Even if we use accurate time slot value, the queueing delay of LLEPS is not stable enough when packets come in burst in the real networks.
Therefore, in this paper, we propose a packet scheduling algorithm, Credit-Based Low Latency Packet Scheduling (CBLLPS), using adaptive credit function to ensure low latency for streaming applications. Some simulation results are also presented.

關鍵字(中)

★ 排隊理論
★ 品質保證
★ 即時

關鍵字(英)

★ Queueing
★ QoS
★ Real-time

論文目次

1 Introduction (1)
2 Unsteady Queueing Delay Problem (6)
2.1 The Buffer Underrun Problem (6)
3. Related Scheduling Algorithms (9)
3.1 General Processor Sharing (GPS) (9)
3.2 Weighted Fair Queueing (WFQ) (10)
3.3 Worst-case Fair Weighted Fair Queueing (WF2Q) (12)
3.4 Self-Clocked Fair Queueing (SCFQ) / Start-Time Fair
Queueing (SFQ) (13)
3.5 Worst-case Fair Weighted Fair Queueing plus (WF2Q+) (15)
3.6 Low Latency Queueing (LLQ) (17)
3.7 Deficit Round Robin (DRR) /Nested Deficit Round
Robin (NDRR) (17)
3.8 Low Latency and Efficient Packet Scheduling (LLEPS) (19)
4 Credit-Based Low Latency Packet Scheduling
(CBLLPS) Algorithm (23)
4.1 Overview of CBLLPS algorithm (24)
4.2 Trade-off between credit and affected degree (25)
4.3 In an ideal case (26)
4.4 In a real case (27)
5 Simulations (31)
5.1 Queueing delay comparison of CBLLPS, LLEPS, SFQ,
WF2Q+, SCFQ, NDRR, LLQ (32)
5.1.1 Buffer underrun problem in ideal case (32)
5.1.2 Buffer underrun problem in real case (35)
5.2 Bandwidth reservation (39)
5.3 Bandwidth sharing (40)
6 Conclusion (42)
List of References 43

參考文獻

[1] A. Demers, S. Keshav and S. Shenker, "Analysis and simulation of a fair queueing algorithm", in Proceedings of ACM SIGCOMM'89, Vol. 19, Issue 4, Aug. 1989.
[2] A. Demers, S.Keshav and S.Shenker, "Design and Analysis of a fair queueing algorithm", Proceeding of ACM SIGCOMM, September 1989.
[3] L. Zhang, "VirtualClock: A new traffic control algorithm for packet switching networks", Proc. ACM SIGCOMM'90, Vol. 20, Issue 4, August 1990.
[4] A. Greenberg and N. Madras, "How fair is fair queueing", J. ACM, July 1992.
[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] S. J. Golestani, "A self-clocked fair queueing scheme for broadband applications", Proceedings of IEEE INFOCOM'94, Vol. 2, p636-646, June 1994.
[8] S. Floyd and V. Jacobson, "Link-Sharing and resource management models for packet networks", IEEE/ACM Transactions on Networking, August 1995.
[9] M. Shreedhar and George Varghese, "Efficient fair queueing Using deficit round-robin", IEEE Transactions on Networking, Jane 1996.
[10] D. Stilliadis and A. Varma, "Latency-Rate Server: A General Model for Analysis of Traffic Scheduling Algorithms", in Proceedings of IEEE INFOCOM'96, Vol. 1, p111-119, Mar. 1996.
[11] Jon C.R. Bennett and Hui Zhang, "WF2Q: Worst-case Fair Weighted Fair Queueing", in Proceedings of IEEE INFOCOM'96, Vol. 1, p120-128, Mar 1996
[12] 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.
[13] J. L. Rexford, A. G. Greenberg and F. G. Bonomi, "Hardware-efficient fair queueing architectures for high-speed networks", in Proceedings of IEEE INFOCOM'96, Vol. 2, p24-28, Mar. 1996.
[14] J. C. R. Bennett and H. Zhang, "Hierachical packet fair queueing algorithms", in Proceedings of ACM SIGCOMM'96, Vol. 26, Issue 4, August 1996.
[15] KJ. Loh, I. Gui and KC. Chua, "Performance of a Linux Implementation of Class Based Queueing", Computer Communications and Networks Proceeding, October 1998.
[16] D. Stilliadis and Anujan Varma, "Rate-Proportional Servers: A Design Methodology for Fair Queueing Algorithms", in Proceeding of IEEE/ACM Transactions on Networking, Vol. 6, Issue 2, Apr. 1998.
[17] D. Stilliadis and Anujan Varma, "Efficient Fair Queueing Algorithms for Packet-Switched Networks", in Proceeding of IEEE/ACM Transactions on Networking, Vol. 6, Issue 2, Apr. 1998.
[18] D. C. Stephens and H. Zhang, "Implementing distributed packet fair queueing in a scalable switch architecture", in Proceedings of IEEE INFOCOM'98, Vol. 1, p282-290, Mar. 1998.
[19] D. C. Stephens, J. C. R. Bennet and H. Zhang, "Implementing scheduling algorithms in high-speed networks", IEEE Journal on Selected Areas in Communications, Vol. 17, Issue 6, p1145-1158, June 1999.
[20] 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
[21] X. Fei and A. Marshall, "Delay Optimized Worst Case Fair WFQ (WF2Q) Packet Scheduling", ICC 2002, IEEE International Conference, 2002.
[22] A. Kortebi, L. Muscariello, S. Oueslati and J. Roberts, "Evaluating the number of active flows in a scheduler realizing fair statistical bandwidth sharing", in Proceedings of ACM SIGMETRICS'05, Vol. 33, Issue 1, June 2005.
[23] Hsiao-Kuang Wu, Ming-I Hsieh and Hsu-Te Lai, "Low latency and efficient packet scheduling for streaming applications", in Proceedings of Computer Communications, 2006.
[24] Q. Zhao and J. Xu, "On the Computational Complexity of Maintaining GPS Clock in Packet Scheduling", in Proceedings of IEEE INFOCOM'04, Vol. 4, p2383-2392, Mar. 2004.
[25] P. Valente, "Exact GPS Simulation with Logarithmic Complexity, and its Application to an Optimally Fair Scheduler", in Proceedings of ACM SIGCOMM'04, Vol. 34, Issue 4, Aug. 2004.
[26] H. Tayyar and H. Alnuweiri, "The Complexity of Computing Virtual-Time in Weighted Fair Queuing Schedulers", IEEE ICC 2004, p1996~2002, vol14, June 2004.
[27] K. Thompson, J. Miller, and R. Wilder, "Wide-Area Internet Traffic Patterns and Characteristics", IEEE Network, November/December 1997.
[28] J. Aracil, D. Morat, M. Izal, "Analysis of Internet Services in IP over ATM Networks", IEEE Communications Magazine, December 1999.
[29] Network Simulator: http://www.isi.edu/nsnam/ns/

指導教授

吳曉光(Hsiao-kuang Wu)

審核日期

2007-6-28

推文