跳到主要內容

臺灣博碩士論文加值系統

(3.81.172.77) 您好!臺灣時間:2022/01/21 19:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:李維席
研究生(外文):Wei-Hsi Li
論文名稱:多個達成比例式延遲差異模型之新排程演算法
論文名稱(外文):Several Novel Schedulers to Achieve Proportional Delay Differentiation
指導教授:賴源正賴源正引用關係
指導教授(外文):Yuan-Cheng Lai
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:68
中文關鍵詞:相對式服務差異比例式延遲差異模型等待時間優先權封包排程演算法服務品質
外文關鍵詞:Relative Service DifferentiationWaiting Time Priority SchedulerQuality of ServicesProportional Delay Differentiation Model
相關次數:
  • 被引用被引用:0
  • 點閱點閱:452
  • 評分評分:
  • 下載下載:82
  • 收藏至我的研究室書目清單書目收藏:1
在網際網路的各種資料傳輸中,比例式延遲差異模型為各個服務類別之間提供了相當固定的封包延遲差異。而等待時間優先權封包排程演算法(WTP),是目前大家公認可以用來達成比例式延遲差異模型的最佳演算法;在這個演算法中,封包的傳送優先權會隨著它在佇列中的等待時間增加而呈現比例式的增加。本論文針對比例式延遲差異模型提出進階型等待時間優先權封包排程演算法Advanced-WTP (AWTP);AWTP 修改自WTP,它的演算法中除了考慮封包的等待時間外,還考慮了各種大小不同封包的傳輸時間。實驗結果顯示,網路使用量為中等時(60%~90%),即使在短的監控時間間隔下,AWTP不但可以比WTP達成更精準的延遲比例,更可以大大地降低整體的封包延遲時間。本論文中的其他實驗項目還包括了頻寬分配比例,封包大小的平均值及封包間的變異係數…等等;AWTP亦在多重服務類別環境下來測試它的強健度。結果顯示,在這些實驗中,AWTP的各項功能總是優於WTP。然而在不同頻寬分配比例下,AWTP無法維持穩定的封包延遲比例,所以本論文提供三個改良過的演算法Minus-WTP (MWTP), Existed-WTP (EWTP) 與 Counted-WTP (CWTP)來解決AWTP因為不同頻寬分配比例所產生的問題。除AWTP外,本論文亦為比例式延遲差異模型提供另外兩個排程演算法Variance-WTP (VWTP)與Threshold-WTP (TWTP);VWTP修改自AWTP,而TWTP則修改自WTP。網路使用量為中等時(60%~90%),實驗結果顯示VWTP與TWTP皆可降低整體的封包延遲時間;VWTP可以比WTP達成更精準的延遲比例,而TWTP與WTP所達成的封包延遲比例則較為相近。最後,有鑒於WTP無法在輕等與中等網路流量時達到要求的封包延遲比例,本論文提出non work-conserving (NWC)排程演算法,NWC為比例式延遲差異模型提出一個新穎的定義用來計算平均封包延遲,在NWC演算法中,所有的封包必須要同時地比較它們的等待時間優先權,即使有些佇列還是空的,它們也必須運用虛假的等待時間優先權來替代以利進行比較。實驗結果顯示,在輕等及中等的網路流量下,NWC可比WTP達到更精確的封包延遲比例,而且能逼近所要求的封包延遲比例;封包延遲的行為在微觀下,NWC較Leung演算法更能使封包延遲成比例。NWC的確為比例式延遲差異模型提出了一個適合且合理的定義。
The proportional delay differentiation model provides a consistent packet delay differentiation between various classes of service. The waiting time priority (WTP) scheduler is a priority scheduler in which the priority of a packet increases in proportion to its waiting time, and it is known as the best scheduler to achieve the proportional delay differentiation model. This paper proposes an Advanced-WTP (AWTP) scheduler, modified from WTP, that accounts for the packet transmission time. Simulation results reveal that when the link utilization is moderate (60%~90%), this scheduler not only obtains more accurate delay proportion than the WTP scheduler, no matter in short or long timescales, but also reduces the average queuing delay (waiting time). The effects of traffic load distribution, mean packet size and its coefficient of variation, on both schedulers' performance are also examined. Also, AWTP is evaluated in a multi-class environment to verify its robustness. AWTP always outperforms WTP in these cases. However, AWTP may not maintain stable delay ratios under various traffic load distributions. Three modifications named Minus-WTP (MWTP), Existed-WTP (EWTP), and Counted-WTP (CWTP), are proposed to remedy this problem of AWTP algorithm. Besides, we propose another two packet schedulers, named Variance-WTP (VWTP) and Threshold-WTP (TWTP), for achieving proportional delay differentiation model. The former is directly modified from AWTP and the latter is modified from WTP. In moderate load conditions (60%~90%), TWTP achieves delay ratios similar to WTP, and VWTP can achieve more accurate delay ratios than WTP. Both of them can greatly reduce overall packet delay, especially TWTP. Finally, a non work-conserving (NWC) scheduler, which is modified from the concept of WTP, is provided for proportional delay differentiation model. The novel and original definition of NWC is that it forces all packets to have to compare waiting time priorities with all HOL packets, even when some service queues are empty, their classes must employ pseudo waiting time priorities for comparison. Simulation results show the performance of WTP, Leung algorithm, and NWC. In moderate and light load conditions, NWC can obtain more accurate delay proportion than WTP, even in short-term timescale. Under microscopic views, NWC makes packet delays to be more proportional than Leung algorithm. NWC just provides appropriate and feasible definition to achieve proportional delay differentiation model.
Contents

Abstract in Chinese…………………………………………………iv
Abstract in English……………………………………………vi
Acknowledgement…………………………………………………viii
Contents………………………………………………………………ix
List of Tables……………………………………………xiii
List of Figures…………………………………………………xiv
Chapter 1 Introduction 1
Chapter 2 Background 4
2.1 Proportional differentiation model4
2.2 WTP scheduler…………………………5
2.3 Leung’s algorithm……………………6

Chapter 3 A High-Performance Scheduler 7
3.1 AWTP algorithm………………………7
3.2 An example……………………………8
3.3 Characteristics of AWTP……………9
3.4 Simulation Results and Their Implications10
3.4.1 Case1:………………………………11
3.4.1.1 Queueing delay ratio…………11
3.4.1.2 Delay improvement………………12
3.4.1.3 Queueing delay distribution…13
3.4.1.4 Timescale…………………………14
3.4.2 Case2: Traffic load distribution15
3.4.3 Case3:………………………………15
3.4.3.1 Average packet size……………16
3.4.3.2 Variance of packet size………17
3.4.4 Case4: Robustness…………………18
3.5 Computation complexity………………19
3.6 Summary……………………………………19

Chapter 4 Three Remedied Algorithms for Advanced Waiting Time Scheduler 21
4.1 Instability…………………………………21
4.2 Reason…………………………………………22
4.3 Three remedied algorithms…………………23
4.3.1 MWTP algorithm………………………………24
4.3.2 EWTP algorithm………………………………24
4.3.3 CWTP algorithm………………………………25
4.4 Simulation results and their implications26
4.4.1 Case1: Queueing delay ratio and delay improvement27
4.4.1.1 Queueing delay ratio……………27
4.4.1.2 Delay improvement…………………29
4.4.2 Case2: Traffic load distribution30
4.4.3 Case3: Timescale………………………32
4.5 Summary………………………………………33

Chapter 5 Two High-Performance Schedulers 35
5.1 VWTP algorithm………………………………35
5.2 TWTP algorithm………………………………36
5.3 Characteristic of AWTP, VWTP, and TWTP38
5.4 Simulation results and their implications40
5.4.1 Case1: Queueing delay ratio and delay improvement41
5.4.1.1 Queueing delay ratio…………………41
5.4.1.2 Delay improvement………………………42
5.4.1.3 Timescale…………………………………43
5.4.2 Case2: Traffic load distribution………44
5.4.3 Case3:…………………………………………45
5.4.3.1 Average packet size………………………45
5.4.3.2 Variance of packet size…………………46
5.4.4 Case4: VT Influence on TWTP………………47
5.5 Summary……………………………………………49

Chapter 6 A Non-Work-Conserving scheduler 50
6.1 Motivations………………………………………50
6.2 NWC algorithm……………………………………52
6.3 Simulation results and their implications53
6.3.1 Queueing delay ratio…………………………53
6.3.2 Delay aggravation……………………………55
6.3.3 Microscopic views of queueing delay variations57
6.3.4 Pareto process…………………………………59
6.3.5 Timescale…………………………………………60
6.4 Summary………………………………………………62
Chapter 7 Conclusions 63
Bibliography 65
Biography 68
[1] I. Stoika, S. Shenker, and H. Zhang: Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks, in Proceedings ACM SIGCOMM, Sept. (1998)
[2] I. Stoika, and H. Zhang: Providing Guaranteed Services Without Per Flow Management, in Proceedings ACM SIGCOMM, Sept. (1999)
[3] A. Charny: Delay Bounds in a Network with Aggregate Scheduling, Tech. Rep. Draft version 3, Cisco Systems, Feb. (2000)
[4] D. D. Clark and W. fang: Explicit Allocation of Best Effort Packet Delivery Service, IEEE/ACM Transactions on Networking, vol. 6, pp. 362-373, Aug. (1998)
[5] J. L. Boudec, M. Hamdi, L. Blaxevic, and P. Thiran: Asymmetric Best Effort Service for Packet Networks, in Proceedings Global Internet Symposium, Dec. (1999)
[6] R. Braden, D. Clark, S. Shenker: Integrated Services in the Internet Architecture: an Overview. RFC 1633 (1994)
[7] J. Wroclawski: the Use of RSVP with IETF integrated Services, RFC 2210, Sept. (1997)
[8] Abhay K. Parekh, Robert G. Gallager: A Generalized processor Sharing Approach to Flow Control in Intergated Services networks: The Single_Node Case, IEEE/ACM Transactions on Networking, vol. 1, No.3, June (1993)
[9] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss: An Architecture for Differentiated Services. RFC 2475 (1998)
[10] M. May, J. C. Bolot, C. Diot, and A. Jean-Marie: Simple Performance Models of Differentiated Services Schemes for the Internet, in Proceedings IEEE INFOCOM, Mar. (1999)
[11] J. S. Sahu, D. Towsley: A Quantitative Study of Differentiated Services for the Internet, in Proceedings Global Internet symposium, Dec. (1999)
[12] W. Feng, D. D. Kandlur, D. Saha, and K. G. Shin: Adaptive Packet Marking for Maintaining End-to-End Throughput in a Differentiated-Services Internet, IEEE/ACM Transactions on Networking, vol. 7, pp. 685-597, Oct. (1999)
[13] I. Stoika, and H. Zhang: LIRA: An Approach for Service Differentiated Services Network, Tech. Rep., Texas A&M University, Feb. 2000
[14] K. Nichols, S. Blake, F. Baker, and D. L. Black: Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers. IETF RFC 2474 (1998)
[15] K. Nichols, V. Jacobson, and L. Zhang: A Two-bit Differentiated Services Architecture for the Internet, July 1999. IETF RFC 2628
[16] C. Dovrolis, D. Stiliadis, and P. Ramanathan: Proportional Differentiated Services: Delay Differentiation and Packet Scheduling. ACM SIGCOMM (1999)
[17] C. Dovrolis, and P. Ramanathan: A Case for Relative Differentiated Services and the Proportional Differentiation Model. IEEE network (1999)
[18] H. Saito, C. Lukovszki, I. Moldovan: Local Optimal Proportional Differentiation Scheduler for Relative Differentiated Services. Computer Communications and Networks (2000)
[19] L. Kleinrock: Queueing Systems, Volume 2: Computer Applications. Wiley-Interscience (1976)
[20] Y. Matsumoto, Y. Takahashi, and T. Hasegawa: The effects on Packet Size Distributions on Output and Delay Processes of CSMA/CD. IEEE Transactions on Communications, Vol. 38, NO. 2 (1990)
[21] K. H. Leung, John C. S. Lui, and David K. Y. Yau: Characterization and Performance Evaluation for Proportional Delay Differentiated Service. Network Protocols (2000)
[22] Y. C. Lai, W. H. Li, and A. Chang: A Novel Scheduler for the Proportional Delay Differentiation Model by Considering Packet Transmission Time. ICOIN16, Cheju Island, Korea (2002)
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top