跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳育葵
研究生(外文):WU YU-KUEY
論文名稱:提供比例式延遲差異性服務相關排程演算法之研究
論文名稱(外文):The Scheduling Algorithms for Proportional Delay Differentiated Services
指導教授:張仲儒
指導教授(外文):Chung-Ju Chang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電信工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:57
中文關鍵詞:排程理論比例式延遲差異性服務
外文關鍵詞:scheduling algorithmproportional delayDifferentiated Services
相關次數:
  • 被引用被引用:0
  • 點閱點閱:161
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在現今網際網路上,即時性的應用日漸增多,為了保證此類應用在網路上傳送封包的品質,亟需一套機制來確保其服務品質(QoS),其中IETF在RFC2475所提出的差異性服務(Differentiated Services)可在網際網路上實現不同類輸入間性能表現(如平均封包延遲、平均封包遺失率)達到相對差異的服務品質保證。在本篇論文中,我們設計一套排程理論以達成不同類別間倍比式延遲的差異性服務。在此模型中,性能表現必須具備兩個特性。第一為可預測性,指即使在短期時間內高優先權類別仍然可得到比低優先權類別更好的服務;第二為可控制性,指不同類別間性能表現的預設差異不會因網路情況的變化而有所改變。
故我們先針對Kleinrock所提出的WTP (waiting-time priority)封包排程理論作分析,並就其在可控制性表現方面的不足作改進。我們提出的D-WTP (dynamic waiting-time priority)是依據排隊理論所得結果,並預測下一個調整視窗的系統負載,動態的設定一個決定優先權的控制參數,如此可使在此調整視窗內離開的不同類別封包其平均延遲達到一個預設的比例,因而達到可控制性的要求。然而,當這個方法運用到多個輸入類別及更真實的網路訊務時,其表現則不如預期。故我們進一步提出了ADP (average-delay priority)封包排程理論來解決這些問題,ADP在決定優先權時是根據不同類別的平均延遲,其定義是將已離開封包之平均延遲和仍在佇列封包之平均等待時間做一個權重式的加總,如此可在長期時間延遲比例及短期時間延遲變異上取得均衡,由模擬結果可知ADP改善D-WTP性能表現上的障礙,並達成了無論在長期或短期時間上可預測性及可控制性的要求。

Recently, the Differentiated Services (DiffServ) model has been proposed to provide different degrees of QoS guarantee. In this thesis, we aim to design scheduling mechanisms that provide proportional delay differentiation among different classes. These scheduling algorithms have two important goals need to be achieved. First one is predictability, which means the higher classes will always get better services than the lower classes (or at least no worse) even under short timescales. The second critical factor is controllability. That is, we claim that a scheduling algorithm should also provide consistent quality differentiation regardless of any system load, class load distribution, or stochastic arrival process.
First, we investigate the behavior of waiting-time priority (WTP) scheduler, which was regarded as the most effective method in achieving proportional delay differentiation. By referencing the result from its theoretical queueing analysis, we propose an algorithm, which called dynamic waiting-time priority (D-WTP). It indeed improves the system performance under both long-term and short-term situations, especially in moderate load condition.
However, D-WTP still has some drawbacks. It is only valid when two classes exist and the performance downgrades with non-Poisson traffic arrivals. So we innovate another method, which called average-delay priority (ADP) algorithm, to solve these problems. ADP differs from D-WTP in the fact that it does not use the theoretical results and avoids the error caused by prediction. The simulation results show that ADP can have a very good short-term performance as well as the precise long-term achieved ratios among classes independent of any traffic intensity or class load distribution. It is also robust for bursty traffic pattern and suitable for multiple classes.

Contents
Chinese Abstract i
English Abstract ii
Acknowledgement iii
Contents iv
List of Figures vi
List of Tables vii
1 Introduction 1
2 A Dynamic Waiting-Time Priority Scheduling Algorithm 5
2.1 Introduction 5
2.2 Related Work 7
2.3 Theoretical Analysis of WTP Algorithm 9
2.4 Dynamic Waiting-Time Priority Scheduler 18
2.5 Simulation Results 23
2.5.1 Behavior of Long-term Achieved Ratio 23
2.5.2 Behavior of Short-term Achieved Ratio 27
2.6 Concluding Remarks 32
3 An Average-Delay Priority Scheduling Algorithm 33
3.1 Introduction 33
3.2 Average-Delay Priority (ADP) Scheduler 34
3.2.1 Forwarding Mechanism 35
3.2.2 Time Window Consideration 39
3.3 Simulation Results 42
3.3.1 Behavior of Long-term Achieved Ratio 42
3.3.2 Behavior of Short-term Achieved Ratio 47
3.4 Concluding Remarks 53
4 Conclusion 54

Bibliography
[1] A. Mankin, F. Baker, B. Braden, S. Bradner, M. O’Dell, A. Romanow, A. Weinrib, and L. Zhang, “RSVP Version 1: Applicability Statement, Some Guidelines on Deployment,” IETF RFC 2208, September 1997.
[2] S. Blake, et al., “An Architecture for Differentiated Services,” IETF RFC 2475, December 1998.
[3] J. Heinanen, F. Baker, W. Weiss, J. Wrockawski, “Assured Forwarding PHB Group,” IETF RFC 2597, June 1999.
[4] K. Poduri, K. Nichols, V. Jacobson, “An Expedited Forwarding PHB,” IETF RFC 2598, June 1999.
[5] C. Dovrolis and P. Ramanathan, “A case for relative differentiated services and the proportional differentiation model,” IEEE Network, pp. 26—34, Sept.-Oct. 1999.
[6] C. Dovrolis, D. Stiliadis and P. Ramanathan, “Proportional differentiated services: delay differentiation and packet scheduling,” ACM SIGCOMM’99, pp. 109-120.
[7] J. Bennett and H. Zhang, “Hierarchical Packet Fair Queueing Algorithms,” IEEE/ACM Trans. Networking, vol. 5, pp. 675-689, 1997.
[8] K. Zhu, Y. Zhuang and Y. Viniotis, “Achieving End-to-end Delay Bounds by EDF Scheduling without Traffic Shaping,” Proc. IEEE INFOCOM 2001, pp. 1493-1501.
[9] C.C. Li, S.L. Tsao, M.C. Chen, Y. Sun, Y.M. Huang, “Proportional delay differentiation service based on weighted fair queueing,” Computer Communications and Networks, 2000.
[10] L. Kleinrock, Queueing Systems, Volume Ⅱ. John Wiley and Sons, 1976.
[11] T. Nandagopal, N. Venkitaraman, R. Sivakumar, and V. Barghavan, “Delay Differentiation and Adaptation in Core Stateless Networks,” Proc. IEEE INFOCOM 2000, pp. 421-430.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top