Basic Search / Detailed Display

Author: 絲玉琴
Yu-Chin Szu
Thesis Title: 提供比例式漏失率差別服務之丟棄機制
Dropping Mechanisms for Providing Proportional Loss Rate Differentiated Services
Advisor: 賴源正
Yuan-Cheng Lai
Committee: 周立德
Li-Der Chou
Chiung-San Lee
Yue-Li Wang
Gwo-Guang Lee
Degree: 博士
Department: 管理學院 - 資訊管理系
Department of Information Management
Thesis Publication Year: 2009
Graduation Academic Year: 97
Language: 英文
Pages: 68
Keywords (in Chinese): 服務品質比例式漏失率差別比例式延遲差別無線網路多重狀態鏈路模糊理論
Keywords (in other languages): Quality of Service (QoS), proportional delay differentiation, proportional loss rate differentiation, wireless network, multi-state link, fuzzy theory
Reference times: Clicks: 508Downloads: 2
School Collection Retrieve National Library Collection Retrieve Error Report

網路應用需多樣化服務品質的要求,比例式差別服務可提供網路管理者藉由操控品質差別參數來調整不同類別所接受到服務品質之差距,並確保在不同時段內此差距比例都是維持一致的。換言之,比例式差別服務具可控制(controllable)及可預期(predicable)兩項特性,故成為差別式服務研究之主流。而所使用的評量依據主要包括產能(throughput)、封包佇列延遲(queueing delay)、封包漏失率(loss rate)及封包延遲變異(jitter)。
本論文首先提出兩個在具有多重鏈路狀態之無線網路環境下提供比例式漏失率差別服務之演算法,NDR(No-Debt Reference)及RP(Random Probability)。此兩種演算法主要考量無線鏈路頻寛及累積積欠次數,其會丟棄鏈路頻寛較差的佇列的封包以改善網路效能。可積欠次數造成短期目標漏失比率的偏離可藉由補償機制於恢復期望的長期比例。模擬結果可以觀察此兩種演算法相較於其他方法,在無線網路上,確實可以達到較接近期望之漏失比率,較小的排隊延遲及漏失率,以及較佳的產能。
在某些情況下,會希望兩個效能參數皆具比例式差別。因此我們提出一個稱為DPDL(Debt-aware Proportional Delay and Loss differentiation)的演算法,其能在多重鏈路狀態之無線網路環境下提供比例式延遲差別服務及比例式漏失率差別服務。DPDL包含借用觀念的排程及借用觀念丟棄器兩個部分,目的是維持比例式延遲及比例式漏失率,同時亦減少排隊延遲、漏失率及增進產能。
本論文最後利用模糊理論的觀念提出一個Fuzzy Proportional Loss Rate Dropper(FPLR),透過鏈路頻寛較差的小封包較易丟棄的概念,達成漏失率比例。與其他方法用於無線網路上比較,模擬結果顯示FPLR可以達到較接近期望之漏失率比率,較小的排隊延遲及漏失率,以及較佳的產能。

Various network applications require different guarantee of the quality of services (QoS). The proportional differentiation model offers the network manager a means of varying quality space between service classes according to the given quality differentiation parameters (QDP), and ensures that the differentiation between classes is consistent in any measured timescale. That is, the mode can perform the controllable and predictable QoS, and thus it has gained the most attention as being a main solution to provide relative service differentiation. Also the proportional services can be differentiated according to different performance metrics, such as throughput, delay, loss rate, or jitter.
Most of the related work focused on providing the proportional delay differentiation (PDD) and proportional loss differentiation (PLD) model in a wired network. However, because of the some specific link characteristics of wireless network, some methods can not operate directly under wireless networks. Although some algorithms may operate normally, their performances are poor. Therefore, it is necessary to redesign suitable algorithms based on the characteristics of wireless networks.
This dissertation first proposed two channel-aware and debt-aware droppers, named No-Debt Reference (NDR) and Random Probability (RP), to provide PLD in a wireless network with a multi-state link. The two proposed droppers prefer dropping the packet destined to a poor channel to improve the performance, causing some loss debt, which will be compensated later to keep PLD. From simulation results, NDR and RP actually achieve similar accurate loss rate proportion, lower queueing delay and loss rate, and higher throughput, compared with other methods in the wireless environment.
Nevertheless, in certain cases, it is desirable to achieve proportional differentiation on both performance parameters. Then we address how to provide PDD and PLD in a wireless network and propose an algorithm called Debt-aware Proportional Delay and Loss differentiation (DPDL), which includes a debt-aware scheduler and a debt-aware dropper. DPDL maintains PDD and PLD in a wireless network with a multi-state link, meanwhile, it achieves lower queuing delay, lower loss rate, and higher throughput.
Finally, this dissertation using fuzzy theories proposes a dropper, Fuzzy Proportional Loss Rate Dropper (FPLR), to prefer dropping the small packets destined to a poor channel to improve the performance. FPLR actually achieves similar accurate loss rate proportion, lower queueing delay and loss rate, and higher throughput, compared with other methods in the wireless environment.

中文摘要 I ABSTRACT III 誌謝V TABLE OF CONTENTS VI LIST OF FIGURES IX LIST OF TABLES X Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Organization 3 Chapter 2 Research Background 4 2.1 Proportional Differentiation Model 4 2.2 Schedulers for PDD under Wired Networks 5 2.2.1 Waiting Time Priority (WTP) Scheduler 5 2.2.2 Proportional Average Delay (PAD) Scheduler 6 2.2.3 Hybrid Proportional Delay (HPD) Scheduler 6 2.3 Droppers for PLD under Wired Networks 7 2.3.1 Proportional Loss Rate (PLR) 7 2.3.2 Average Drop Distance (ADD) 8 2.3.3 Debt-aware Dropper 8 2.3.4 Others 9 2.4 The Problem of Achieving PLD in a Wireless Network 10 2.5 The Fuzzy Controller 11 Chapter 3 Achieving Proportional Loss Rate Differentiation in a Wireless Network with a Multi-state Link 12 3.1 Two Proposed Droppers 12 3.1.1 No-Debt Reference (NDR) Dropper 12 3.1.2 Random Probability (RP) Dropper 16 3.2 Characteristics of two droppers 18 3.3 Simulation and Discussion 18 3.3.1 Simulation Model 19 3.3.2 Packet Arrival Rate 20 3.3.3 Timescale 22 3.3.4 Number of Mobile Hosts 23 3.3.5 State Transition Rate 25 3.3.6 debt_TH and maxdeb 26 3.4 Summary 27 Chapter 4 Using Debt Mechanism to Achieve Proportional Delay and Loss Differentiation in a Wireless Network with a Multi-state Channel 28 4.1 Algorithm 28 4.1.1 Proportional Differentiation Dropper 28 4.1.2 Proportional Differentiation Scheduler 30 4.2 Simulation and Discussion 34 4.2.1 Packet Arrival Rate 35 4.2.2 Timescale 37 4.3 Summary 39 Chapter 5 A Fuzzy Dropper to Provide Proportional Loss Rate Differentiation in a Wireless Network with a Multi-state Channel 40 5.1 Fuzzy Proportional Loss Rate Dropper (FPLR) 40 5.1.1 Fuzzification 41 5.1.2 Rule Establishment 42 5.1.3 Defuzzification 43 5.1.4 Debt Decision 44 5.1.5 Algorithm 44 5.2 Simulation and Discussion 47 5.2.1 Simulation Models 48 5.2.2 Packet Arrival Rate 49 5.2.3 Timescale 51 5.2.4 Number of Mobile Hosts 52 5.2.5 State Transition Rate 54 5.2.6 Distribution of Packet Sizes 55 5.2.7 Threshold 56 5.3 Summary 57 Chapter 6 Conclusions and Future Works 58 6.1 Conclusions 58 6.2 Future Works 60 Terms 61 References 63 Publication List 66 Curriculum Vita 68

[1]R. Braden, D. Clark, and S. Shenker, “Integrated Services in the Internet Architecture: an Overview,” IETF RFC 1633, June 1994.
[2] S. Blake, D. Black, M. Carlson, Z. Wang, and W. Weiss, “An Architecture for Differentiated Services,” IETF RFC 2475, December 1998.
[3]K. Nichols, V. Jacobson, and K. Poduri, “Expedited Forwarding PHB Group,” IETF RFC 2598, June 1999.
[4]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, Auguest 1998.
[5]C. Dovrolis, D. Stiliadis, P. Ramanathan, “Proportional Differentiated Services: Delay Differentiation and Packet Scheduling,” ACM SIGCOMM Computer Communication Review, vol. 29, issue 4, pp. 109-120, October 1999
[6]C. Dovrolis, D. Stiliadis, and P. Ramanathan, “Proportional Differentiated Services: Delay Differentiation and Packet Scheduling,” IEEE/ACM Transactions on Networking, vol. 10, no.1, pp. 12-26, February 2002.
[7]Y. C. Lai and W. H. Li, “A Novel Scheduler for the Proportional Differentiation Model by Considering Packet Transmission Time,” IEEE Communications Letters, vol. 7, no.4, pp. 189-191, April 2003.
[8]C. Dovrolis and P. Ramanathan, “Proportional Differentiated Services, Part II: Loss Rate Differentiation and Packet Dropping,” IEEE/IFIP Int. Workshop Quality of Service (IWQoS), pp. 52-61, June 2000.
[9]U. Bobin, A. Jonsson, and O. Schelen, “On Creating Proportional Loss-Rate Differentiation: Predictability and Performance,” Lecture Notes in Computer Science, vol. 2092, pp. 372-379, June 2001.
[10]J. Zeng and N. Ansari, “An Enhanced Dropping Scheme for Proportional Differentiated Services,” ICC’03, vol. 3, pp. 11-15 2003.
[11]J. Aweya, M. Ouellette, and D. Y. Montuno, “Weighted Proportional Loss Rate Differentiation of TCP Traffic,” International Journal of Network Management, vol. 14. pp. 257-271, June 2004.
[12]M. Zhang, J. Wu, C. Lin, and K. Xu, “WSAP: Provide Loss Rate Differentiation with Active Queue Management,” ICCT’2003, pp. 385-391, July 2003.
[13]X. Zhou, D. Ippoliti, and T. Boult, “HPPD: A Hop-count Probabilistic Packet Dropper,” ICC’2006, pp. 116-120, June 2006.
[14]Y. Cao and V. O. K. Li, “Scheduling Algorithm in Broad-Band Wireless Networks”, Proceedings of the IEEE. vol. 89, no. 1, pp. 76-87, January 2001.
[15]L. Kleinrock, Queueing Systems, Vol. 2, Computer Applications, Wiley-Interscience, 1976.
[16]Y. Huang, and R. Gu, “A Simple FIFO-Based Scheme for Differentiated Loss Guarantees,” Twelfth IEEE International Workshop on Quality of Service (IWQOS 2004), pp.96-105, June 2004.
[17]O. Pang, V. C. Leung, and S. C. Liew, “An Enhanced Autorate Algorithm for Wireless Local Area Networks Employing Loss Differentiation,” IEEE Transactions on Vehicular Technology, vol. 57, no. 1, pp. 521-531, January 2008.
[18]C. H. Lim and J. W. Jang, “Robust End-to-End Loss Differentiation Scheme for Transport Control Protocol over Wired/Wireless Networks,” IET Communications, vol. 2, issue 2, pp. 284-291, February 2008.
[19]E. H. Mamdani, “Application of fuzzy algorithms for simple dynamic plant,” Proc. Inst. Elect. Eng., vol. 121, pp. 1585-1588, 1974.
[20]E, H. Mamdani and S. Assilian, “An Experiment in Liquistic Synthesis with a Fuzzy Logic Controller,” Int. J. Man Mach. Stud., vol. 7, pp. 1-13, 1975.
[21]D. Y. Yang, T. J. Lee, K. Jang, J. B. Chang, and S. Choi, “Performance Enhancement of Multi-Rate IEEE 802.11WLANs with Geographically-Scattered Stations,” IEEE Trans. Mobile Computing, vol. 5, no. 7, pp. 906-919, July 2006.
[22]S. T. Sheu, J. C. Chen, H. W. Tseng, and H. T. Chiang, “A Safe Multiple Access-rates Transmission (SMART) Scheme for IEEE 802.11 Wireless Networks,” AINA 2003, pp.172-175, March 2003.
[23]L. Zadeh, “Soft Computing and Fuzzy Logic,” IEEE Softw., vol. 11, no. 6, pp. 48-56, 1994.
[24]A. Kumar, J.Kaur, and H. M. Vin, “End-to-End Proportional Loss Differentiation,” Tech. rep. TR-01-33, September 2001.