研究生: |
張榮昇 Arthur - Chang |
---|---|
論文名稱: |
提供比例式延遲差別服務之新排程機制 Novel Scheduling Mechanisms for Providing Proportional Delay Differentiated Services |
指導教授: |
賴源正
Yuan-Cheng Lai |
口試委員: |
陳金蓮
Jean-Lien Chen 張瑞雄 Ruay-Shiung Chang 王有禮 Yue-Li Wang 林盈達 Ying-Dar Lin 陳俊良 Jiann-Liang Chen 周立德 Li-Der Chou |
學位類別: |
博士 Doctor |
系所名稱: |
管理學院 - 資訊管理系 Department of Information Management |
論文出版年: | 2007 |
畢業學年度: | 95 |
語文別: | 英文 |
論文頁數: | 109 |
中文關鍵詞: | 服務品質 、比例式延遲差別 、等待時間優先等級 、多重狀態鏈路 、跨階層排程 |
外文關鍵詞: | QoS, proportional delay differentiation, waiting time priority, multi-state link, cross-layer scheduling, non-work-conserving scheduler |
相關次數: | 點閱:315 下載:3 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
由於網路應用程式的蓬勃發展,要求網路提供服務品質(QoS)保證的需求與日遽增。在眾多被提出的QoS模式中,比例式延遲差別(PDD)模式因具有可控制及可預測的特性,而受到許多研究者的青睞,許多針對提供PDD模式而設計的排程演算法紛紛被提出來。然而,這些研究主要面臨兩個問題:首先,大部份相關的研究都是把焦點放在如何於有線的網路環境中提供PDD,但由於無線網路的日益普及,許多的應用程式也轉移到無線環境上使用,對於PDD模式的需求因此應運而生;其次,目前的排程法在短時間量程(short timescale)或較低量之負載情況下,無法達到期望之延遲比例,以致於無法提供PDD模式。
有鑑於此,本論文首先提出一個在具有多重鏈路狀態之無線網路環境下提供比例式延遲差別服務之演算法。本演算法稱為預視等待時間優先權排程法(look-ahead waiting time priority, LWTP),乃預先評估選取之封包若經傳送對其他封包等待時間造成的影響,嘗試傳送封包至具有高通道容量的移動主機,同時維持比例式延遲差別。LWTP藉由排程時動態考量因地因時變動的無線鏈路頻寬,以避免隊頭阻塞,並達到比例式延遲差別及降低排隊延遲。透過模擬結果可以觀察出LWTP相較於別的排程法,確實可達到較接近期望之延遲比例,同時亦得到較小的排隊延遲。
LWTP主要是以集中式排程在網路層運作,本論文進一步將研究範圍延伸並考慮媒體存取層(MAC)的運作及分散式排程的特性,以提供更切合實際無線網路之PDD模式。因此提出一個作用於無線區域網路之跨層微調排程方法(cross-layer fine-tuning scheduling, CFS),目的是維持無線工作站間的比例式延遲差別,同時增進整體無線區域網路的效能。CFS整合LWTP以考量因地因時變動的鏈路頻寬,並微調MAC層之競爭視窗且適當的選取退後時間。CFS在無線工作站內協調網路層、媒體存取層及實體層跨階層合作,同時以分散式的方式作用在各無線工作站間。模擬結果顯示CFS相較於現行的IEEE 802.11e,可提供更佳的比例式延遲差別及更好之效能。
最後,本論文探討PDD模式為何在短時間量程(short timescale)或較低量之負載情況下,無法達到期望之延遲比例的原因,同時提出一個非工作守恒(non-work-conserving)的排程法(稱之NWC),透過替空佇列維持一個虛擬等待時間,使得所有類別之佇列都可以互相比較封包之優先等級。當一個空佇列擁有最高優先等級時,NWC會暫停傳送封包,導致伺服器閒置,因此進一步提出兩種方法,在原本伺服器應閒置的時間內,改傳送盡力服務(best-effort)類別之封包。與其他工作守恒的排程法比較此兩種方法可提供較可預測且較可控制的延遲比例,伴隨著良好的產出和平均排隊延遲。
The issue of guaranteeing Quality of Services (QoS) in a network has emerged in recent years. The proportional delay differentiation (PDD) is one of the most well-known QoS models and has drawn much attention because of its “controllable” and “predictable” characteristics. However, current researches encounter with two major difficulties: first, most of the related works focused on providing the PDD model in a wired network. Since there has been an emerging interest aspiring to exploit wireless networks nowadays, the demand for PDD over there also rises more urgently. Second, current schedulers cannot achieve the desired delay proportion if in short timescale or under light/moderate load, thus leading to the failure of consistently achieving the PDD model.
Thus, firstly, this dissertation proposes a novel scheduler to provide the proportional delay differentiation in a wireless environment, in which a multi-state link exists. This scheduler, look-ahead waiting time priority (LWTP), previews the influence of a packet selected for transmission on the waiting times of other packets, tries to transmit packets to a mobile station which has a high-capacity channel, and maintains proportional delay differentiation simultaneously. LWTP can achieve proportional delay differentiation and low queueing delay, by adapting with the location-dependent and time-varying capacity of the wireless link and conquering the head-of-line blocking problem. The simulation results demonstrate that the LWTP scheduler actually achieves much closer to the desired delay proportion between classes and induces smaller queueing delays, compared with the past schedulers.
LWTP only aims to function at the network layer in a centralized manner. Therefore, this dissertation further extends the research scope to consider a wireless environment where the characteristics of the MAC layer also matter. We address how to provide PDD in a wireless LAN (WLAN) and propose a cross-layer fine-tuning scheduling (CFS) scheme with the goal to maintain PDD among all wireless stations while improving performance in a WLAN. CFS additionally considers the location-dependent and time-varying channel capacity to schedule packets, finely tunes the contention window, and properly arbitrates the backoff time. Also, CFS operates in a fully distributed manner among all stations and in a cross-layer approach in each station. The simulation results demonstrate that the CFS scheme can provide more satisfactory PDD and higher performance in a WLAN, compared with IEEE 802.11e.
Finally, this dissertation explores the reason why the present schedulers performing the PDD model cannot achieve desired delay proportion observed in short timescales under light/moderate load. Then, this dissertation proposes a non-work-conserving (NWC) scheduler, which utilizes the pseudo-waiting time for an empty queue and forces each class to compare its priority with those of all other classes. NWC will suspend the server from transmitting packets immediately if an empty class has the maximum priority, resulting in an idle server. Therefore, this dissertation further proposes two approaches, which will serve a best-effort class during the idle time. Compared with other work-conserving schedulers, the proposed approaches can provide more predictable and controllable delay proportion, accompanied with satisfactory throughput and average queuing delay.
[1] N. Christin and J. Liebeherr, “A QoS architecture for quantitative service differentiation,” IEEE Communications Magazine, vol. 41, no. 6, pp. 38-45, June 2003.
[2] R. Braden, D. Clark, and S. Shenker, Integrated Services in the Internet Architecture: an Overview. IETF RFC 1633, 1994.
[3] Z. Wang, Integrated Services, in: Internet QoS: Architectures and Mechanisms for Quality of Service. Morgan Kaufmann Publishers, pp. 15-78, 2001.
[4] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, An Architecture for Differentiated Services, IETF RFC 2475, Dec. 1998.
[5] K. Nichols, V. Jacobson, and K. Poduri, Expedited Forwarding PHB Group, IETF RFC 2598, June 1999.
[6] D. Clark and W. Fang, Explicit Allocation of Best Effort Packet Delivery Service, IEEE/ACM Transactions on Networking, vol. 6, no. 4, pp. 362-373, Aug. 1998.
[7] C. Dovrolis and P. Ramanathan, A Case for Relative Differentiated Services and the Proportional Differentiation Model, IEEE Network, vol. 13, issue 5, pp. 26-34, 1999.
[8] L. Kleinrock, Queueing Systems, Volume 2: Computer Applications, Wiley-Interscience, 1976.
[9] J. Liebeherr and N. Christin, Rate Allocation and Buffer Management for Differentiated Services. Computer Networks, vol. 40, no. 1, pp. 89-110, Sept. 2002.
[10] C. Dovrolis, D. Stiliadis, and P. Ramanathan, Proportional Differentiated Services: Delay Differentiation and Packet Scheduling, IEEE/ACM Transactions on Networking, vol. 10, issue 1, pp. 12-26, Feb. 2002.
[11] H. Saito, C. Lukovszki, and I. Moldovan, Local Optimal Proportional Differentiation Scheduler for Relative Differentiated Services, Proc. IEEE ICCCN, Las Vegas, Nevada USA, Oct. 2000.
[12] M. K. H. Leung, J. C. S. Lui, and D. K. Y. Yau, Adaptive Proportional Delay Differentiated Services: Characterization and Performance Evaluation, IEEE/ACM Transactions on Networking, vol. 9, issue 6, pp. 801-817, Dec. 2001.
[13] H. Ngin and C. Tham, Achieving Proportional Delay Differentiation Efficiently, Proc. IEEE International Conference on Networks, pp. 27-30, Singapore, Aug. 2002.
[14] S. C. M. Lee, J. C. S. Lui , and D. K. Y. Yau, Admission Control and Dynamic Adaptation for A Proportional-Delay Diffserv-Enabled Web Server, Proc. the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, California USA, pp. 172-182, June 2002 .
[15] S. Vuong and X. Shi, A Proportional Differentiation Service Model for the Future Internet Differentiated Services, Proc. ICCT2000, Beijing, China, Aug. 2000.
[16] S. Bodamer, A New Scheduling Mechanism to Provide Relative Differentiation for Real-Time IP Traffic, Proc. IEEE GLOBECOM 2000, San Francisco USA, pp. 646-650, Nov. 2000.
[17] S. Sankaran and A. E. Kamal, A Combined Delay and Throughput Proportional Scheduling Scheme for Differentiated Services, Proc. IEEE GLOBECOM 2002, Taiwan, Nov. 2002.
[18] J. Wei, Q. Li, and C.-Z. Xu, VirtualLength, A New Packet Scheduling Algorithm for Proportional Delay Differentiation, Proc. of ICCCN, Dallas, TX, pp. 3311-336, Oct. 2003.
[19] A. Striegel and G. Manimaran, Packet Scheduling with Delay and Loss Differentiation, Computer Communications, vol. 25, no. 1, pp. 21-31, Jan. 2002.
[20] C. Dovrolis and P. Ramanathan, Proportional Differentiated Services, Part II: Loss Rate Differentiation and Packet Dropping, Proc. IWQoS2000, Pittsburgh, PA, pp. 52-61, June 2000.
[21] U. Bodin, A. Jonsson, and O. Schelen, On Creating Proportional Loss-Rate Differentiation: Predictability and Performance, Proc. IWQoS2001, Karlsruhe, Germany, vol. 2092, pp. 372-388, June 2001.
[22] Y.-C. Lai and W.-H. Li, A High-Performance Scheduler to Achieve Proportional Delay Differentiation, IEE Proceedings of Communications, vol. 150, no. 3, pp. 153-158, June 2003.
[23] IDC: ‘U.S. WLAN Equipment 2005-2009 Forecast by Vertical Market’, Market Report, IDC, Aug. 2005.
[24] IEEE 802.11 WG, Reference number ISO/IEC 8802-11:1999(E) IEEE Std 802.11, 1999 edition. International Standard for Information Technology - Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 1999.
[25] IEEE 802.11 WG, Draft Supplement to Standard for Telecommunications and Information Exchange Between Systems-LAN/MAN Specific Requirements - Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Medium Access Control (MAC) Enhancements for Quality of Service (QoS), IEEE 802.11e-2005, Sept. 2005.
[26] M. R. Jeong, K. Kakami, H. Morikawa, and T. Aoyama, Wireless Scheduler Providing Relative Delay Differentiation, Proc. The Third International Symposium on Wireless Personal Multimedia Communications, Bangkok, Thailand, pp. 1067-1072, Nov. 2000.
[27] Y. Xue, K. Chen, and K. Nahrstedt, “Achieving proportional delay differentiation in wireless LAN via cross-layer scheduling,” Wireless Communications and Mobile Computing, vol. 4, no. 8, pp. 849-866, 2004.
[28] Y. Cao and V. O. K. Li, Scheduling Algorithms in Broad-Band Wireless Networks, IEEE Proceedings of the IEEE, vol. 89, no. 1, pp. 76-87, January 2001.
[29] N. Ramos, D. Panigrahi, and S. Dey, “Quality of Service Provisioning in 802.11e Networks: Challenges, Approaches, and Future Directions,” IEEE Network, pp. 14-20, July/Aug. 2005.
[30] W. Pattara-Atikom, P. Krishnamurthy, and S. Banerjee, “Distributed Mechanisms for Quality of Service in Wireless LANs,” IEEE Wireless Communication, vol. 10, pp. 26–34, June 2003.
[31] Y. Ge and J. Hou, “An Analytical Model for Service Differentiation in IEEE 802.11,” IEEE ICC ’03, vol. 2, pp. 1157–62, May 2003.
[32] K. Liu, T. Wong, J. Li, L. Bu, and J. Han, “A Reservation-based Multiple Access Protocol with Collision Avoidance for Wireless Multihop Ad Hoc Networks,” IEEE ICC ’03, vol. 2, pp. 1119–23, May 2003.
[33] J. D. P Pavon and S. Choi, “Link Adaptation Strategy for IEEE 802.11 WLAN via Received Signal Strength Measurement,” IEEE ICC ’03, vol. 2, pp. 1108–13, May 2003.
[34] S. Park, K. Kim, D. C. Kim, S. Choi, and S. Hong, “Collaborative QoS Architecture between DiffServ and 802.11e Wireless LAN,” Proc. IEEE VTC ’03-Spring, Jeju, Korea, Apr. 2003.
[35] I. Chlamtac, M. Conti, and J. Liu, “Mobile Ad Hoc Networking: Imperatives and Challenges,” Ad Hoc Networks J., vol. 1, no. 1, 2003.
[36] M. Jaseemuddin, “An Architecture for Integrating UMTS and 802.11 WLAN Networks,” IEEE ISCC ’03, pp. 716–23, June 2003.
[37] H. Zhu and I. Chlamtac, “An Analytical Model for IEEE 802.11e EDCF Differential Services,” Proc. 12th Intl. Conf. Comp. Commun. And Networks, Dallas, TX, Oct. 2003.
[38] N. Ramos, D. Panigrahi, and S. Dey, “ChaPLeT: Channel-dependent Packet Level Tuning for Service Differentiation in IEEE 802.11e,” Proc. Int’l. Symp. Wireless Pers. Multimedia Commun., Yokoshuka, Japan, 2003.
[39] M. Malli, Q. Ni, T. Turletti, and C. Barakat, “Adaptive Fair Channel Allocation for QoS Enhancement in IEEE 802.11 Wireless LANs,” Proc. IEEE ICC, Paris, France, 2004.
[40] P. Ansel, Q. Ni, and T. Turletti, “An Efficient Scheduling Scheme for IEEE 802.11e,” Proc. Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2004.
[41] N. Ramos, D. Panigrahi, and S. Dey, “Dynamic Adaptation Policies to Improve Quality of Service of Multimedia Applications in WLAN Networks,” Proc. Int’l. Wksp. Broadband Wireless Multimedia, San Jose, CA, 2004.
[42] A. Grilo, M. Macedo, and M. Nunes, “A Scheduling Algorithm for QoS Support in IEEE 802.11E Networks,” IEEE Wireless Commun., pp. 36–43, June 2003.
[43] Y. Xiao and H. Li, “Evaluation of Distributed Admission Control for the IEEE 802.11e EDCA,” IEEE Radio Commun. Supp., IEEE Commun. Mag., pp. S20–S24, Sept. 2004.
[44] D. Pong and T. Moors, “Call Admission Control for IEEE 802.11 Contention Access Mechanism,” Proc. IEEE GLOBECOM, 2003.
[45] T. S. Rappaport, Modern Wireless Communication Systems, Wireless Communications Principles and Practice, 2nd Ed., Prentice Hall PTR, pp. 25-56, 2002.
[46] V. V. Veeravalli and A. Sendonaris, The Coverage-Capacity Tradeoff in Cellular CDMA Systems, IEEE Transactions on Vehicular Technology, vol.48, no.5, pp. 1443-1450, Sept. 1999.
[47] D. Gross and C. M. Harris, Fundamentals of Queueing Theory, 3rd Ed., Wiley-Interscience, 1998.
[48] H. Zhu, M. Li, I. Chlamtac, and B. Prabhakaran, “A survey of Quality of Service in IEEE 802.11 Networks,” IEEE Wireless Communications, vol. 11, no. 4, pp. 6–14, Aug. 2004.
[49] Q. Ni, L. Romdhani, and T. Turletti, “A survey of QoS enhancements for IEEE 802.11 wireless LAN,” Journal of Wireless and Mobile Computing, John Wiley, vol. 4, no. 5, pp. 547-566, 2004.
[50] L. Romdhani, Q. Ni, and T. Turletti, “Adaptive EDCF: Enhanced Service Differentiation for IEEE 802.11 Wireless Ad Hoc Networks,” IEEE Wireless Communications and Networking Conference, New Orleans, Louisiana, Mar. 2003.
[51] L. Bajaj, M. Takai, R. Ahuja, K. Tang, R. Bagrodia, and M. Gerla, “GloMoSim: A Scalable Network Simulation Environment,” Technical Report 990027, UCLA Computer Science Department, May 1999.
[52] M. Jain and C. Dovrolis, End-to-End Available Bandwidth: Measurement Methodology, Dynamics, and Relation with TCP Throughput, IEEE/ACM Transactions on Networking, vol. 11, issue 4, pp. 537-549, Aug. 2003.
[53] S. McCreary and K. Claffy, Trends in Wide Area IP Traffic Patterns, Technical Report, CAIDA, Feb. 2000.
[54] C. Demichelis and P. Chimento, IP Packet Delay Variation Metric for IP Performance Metrics, IETF RFC 3393, 2002.