簡易檢索 / 詳目顯示

回結果列表
研究生： 張榮昇
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
相關次數： 點閱：311  下載：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.

    中文摘要 I ABSTRACT III ACKNOWLEDGEMENT V TABLE OF CONTENTS VI LIST OF FIGURES IX LIST OF TABLES XI Chapter 1 Introduction 1 1.1 Overview 1 1.2 Motivation and Objective 3 1.3 Organization of This Dissertation 7 Chapter 2 Research Background 9 2.1 Proportional Differentiation Model 9 2.2 Schedulers for PDD provisioning under Wired Environments 11 2.2.1 Waiting Time Priority (WTP) Scheduler 11 2.2.2 Proportional Average Delay (PAD) Scheduler 12 2.2.3 Hybrid Proportional Delay (HPD) Scheduler 13 2.2.4 Leung’s Algorithm 13 2.3 Problems of Scheduling in Wireless Environments 14 2.4 MAC Operations of IEEE 802.11 and 802.11e 16 2.5 Schedulers for PDD Provisioning under Wireless Environments 18 2.5.1 Wireless Waiting Time Priority (WWTP) Scheduler 18 2.5.2 Cross-layer Waiting Time Priority (CWTP) Scheduler 19 Chapter 3 A Look-Ahead Scheduler to Provide PDD in a Wireless Network with a Multi-state Link 21 3.1 Look-ahead Waiting Time Proirity (LWTP) Scheduler 21 3.2 Characteristics of LWTP 26 3.3 Simulation and Discussion 29 3.3.1 Simulation Model 29 3.3.2 Packet Arrival Rate 30 3.3.3 Channel Capacity 32 3.3.4 State Transition Rate 33 3.3.5 Number of Mobile Stations 35 3.3.6 Timescale 36 3.3.7 Variable Packet Size 37 3.3.8 Special Mobile Station Preference 38 3.3.9 Environment with Heterogeneous Channels 39 3.3.10 Comparison of LWTP to WWTP with Threshold 40 3.4 Summary 42 Chapter 4 A Cross-layer Scheduling Scheme to Provide PDD in a Wireless LAN 44 4.1 Architecture of CFS Scheme 44 4.2 Cross-layer Structure 45 4.2.1 Look-ahead Waiting Time Priority (LWTP) Module 47 4.2.2 Contention Window Adjustment (CWA) Module 48 4.2.3 Backoff Time Mapping (BTM) Module 49 4.3 Simulation and Discussion 51 4.3.1 Scenario 51 4.3.2 Dynamics of Packet Delay 53 4.3.3 Number of Mobile Stations 54 4.3.4 Packet Arrival Rate 56 4.3.5 Updating Period of Medium Utilization 57 4.4 Summary 58 Chapter 5 A Non-Work-Conserving Scheduler to Provide Proportional Delay Differentiated Services 60 5.1 Inner Reason of Unachievement 60 5.2 NWC Algorithm 63 5.3 Simulation and Discussion 65 5.3.1 Queueing Delay Ratios 66 5.3.2 Microscopic Views of Individual Packet Delay 67 5.3.3 Traffic with Inter-arrival of Pareto Distribution 72 5.3.4 Timescale 73 5.3.5 Summary 74 5.4 NWC with a Best-Effort Class 75 5.4.1 NWC-NWC and NWC-WC 76 5.4.2 Simulation Results 77 5.5 Summary 83 Chapter 6 Conclusions and Future Works 85 6.1 Conclusions 85 6.2 Future Works 86 References 88 Publication List 94 Curriculum Vitae 95

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

    QR CODE