以訊務相關性為基礎的整合性服務可調整QoS排程器之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：20

、訪客IP：3.144.212.145

姓名

胡世熙(Shih-Hsi Hu) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

以訊務相關性為基礎的整合性服務可調整QoS排程器之研究
(Study of the adjustable QoS scheduler for Integrated Services with traffic correlation)

相關論文

★ 應用MSPP至DWDM都會光纖網路的設計	★ 光網路與WiMAX整合架構研究及其簡化雛型實驗
★ 以Linux系統為基礎之NAT效能優化研究及其實作	★ 光波長劃分多工網路之路徑保護機制研究
★ 標籤交換網路下具有服務品質路由安排之研究	★ 以群體播送支援IPv6環境下移動式網路連結更新之研究
★ 無線區域網路資源動態分配之效能研究	★ 在微觀移動環境下有效資源保留之路徑管理研究
★ 無線網路交握程序之預先認證方法分析與比較	★ 無線區域網路虛擬允入控制之研究
★ IPv6環境下移動網路之連結更新程序及其效能之研究	★ 具有限數量波長轉換節點的分波多工網路之群播波長分配與容量計算研究
★ 階層化行動式IPv6移動錨點選擇機制研究	★ 具高能量移動節點之叢集式感測網路效能研究
★ 預先註冊之快速換手階層化行動式IPv6研究	★ 分波多工網際網路之跨層保護技術研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在這篇論文當中，藉由考慮到達網路節點之訊務量間的相關性質 (correlation property)，我們提出了一套在整合性服務架構 (Integrated Services) 中，提供服務品質 (QoS) 的排程機制設計方法。在所提出的方法中，我們採用了權重公平排隊機制 (Weighted Fair Queueing) 的基本概念。我們應用訊務流的相關性性質給我們帶來的啟發，設計動態地去調整每種服務型態的頻寬分享參數 (share weight factors)。在論文中，我們應用了自我迴歸整合移動平均 (Auto Regressive Integrated Moving Average) 模型來描述相關性性質，並且藉由模型中 AR 部分和 MA 部分的係數導出頻寬分享參數。我們做了一些實驗性質的模擬，來驗證說明所提出之機制的效能表現﹔此外，為了檢驗此機制所能提供給各種服務型態間的公平性指標，我們也定義了一個公平競爭參數 (Fair Play Parameter)。模擬結果顯示此機制可實現各服務類型之間的公平性，特別是在鏈結頻寬受限制的情況下。

摘要(英)

In this thesis, the design of a QoS scheduling scheme for the integrated services is proposed by considering the correlation property of the arriving traffic. The basic concept of the Weighted Fair Queueing (WFQ) is adopted in the proposed scheme. However, the correlation property of the traffic stream is applied as the heuristic to adjust the share weight factors of each traffic type dynamically. The Auto Regressive Integrated Moving Average (ARIMA) model is applied in this thesis to characterize the correlation property. And the share weight factors are derived from the parameters of the AR part and MA part. Experimental simulations are performed to illustrate the effectiveness of the proposed scheme. In addition to comparing the performance of each service types, we also define a fair play parameter (FPP) to examine the fairness index among various traffic streams of the proposed scheme. The experimental results indicate that the fairness among service classes can be achieved, especially when link capacity is limited.

關鍵字(中)

★ 服務品質保證
★ 時間數列分析與預測
★ 頻寬分配
★ 排程機制

關鍵字(英)

★ QoS
★ Time Series Analysis and Forecast
★ Bandwidth Allocation
★ Scheduling algorithm

論文目次

Table of Contents
中文摘要...……………………………………………………..I
Abstract.………………………………………………………II
Chapter 1………..………………………………………….. 1
Introduction…………………………………………..……. 1
1.1 Background and Motivation………………………….. 1
1.2 Literature Survey…………………………………….. 3
1.3 Organization of the Thesis……….…………………… 4
Chapter 2…………………………………………………… 6
Packet-Scheduling Algorithms Overview………………... 6
2.1 Introduction……………..………………….………... 6
2.2 Scheduling Algorithms Overview…………………..... 7
2.2.1 Strict Priority………………………………………….. 8
2.2.2 Weighted Fair Queueing (WFQ)………………………. 8
2.2.3 Differentiated Multi-layer Gated Frame Queueing……. 10
2.2.4 General Dynamic Guaranteed Rate Queueing………… 15
2.3 Summary of Surveyed Scheduling Algorithms………. 20
Chapter 3…………………………………………………… 22
Correlation Analysis By Using ARIMA………………….. 22
3.1 Introduction to Time Series………………………….. 22
3.1.1 Stationary and Nonstationary Time Series……………. 23
3.1.2 Seasonal Time Series………………………………….. 23
3.1.3 Basic Principles of Establishment Time Series Model… 25
3.2 ARIMA Models………………………………………. 26
3.2.1 Stationary Random Process and Its Characteristics……. 27
3.2.2 Stationary ARMA Models……………………………… 27
3.2.3 MA Models…………………………………………….. 28
3.2.4 AR Models…………………………………………….. 29
3.2.5 Mixed ARMA Models………………………………….. 31
3.3 Specification of ARIMA models……………………... 32
3.3.1 The Sample Autocorrelation Function…………………. 32
3.3.2 ACF for AR and MA models………………………….. 33
3.3.3 Partial Autocorrelation Function (PACF) for AR models 34
3.3.4 Random Walk and Extended ACF for ARIMA models.. 35
3.4 Estimation and Diagnostic Checking……………...…….. 40
3.4.1 Estimation……………………………………………… 40
3.4.2 Diagnostic Checking…………………………………… 42
Chapter 4…………………………………………………… 44
The Correlation Based Scheduling Scheme……………… 44
4.1 The Bandwidth Allocation Scheme………………….. 44
4.2 Simulation Architecture………………………….…… 49
4.3 Experimental Results…………………………………. 59
4.3.1 Simulation Results for Scheme I……………………….. 59
4.3.2 Simulation Results for Scheme II……………………… 67
4.3.3 Comparison between Scheme II and Non-change-factor Situation………………………………………………... 74
Chapter 5…………………………………………………… 76
Conclusions and Future Research Work………………… 76
References………………………………………………….. 77
List of Figures
Fig. 2-1 Output queue model…………………………………….. 8
Fig. 2-2 Weighted Fair Queueing……………………………….. 10
Fig. 2-3 Operation of the DMGFQ model……………………… 14
Fig. 2-4 Cell transmission table………………………………….. 18
Fig. 2-5 Swapping procedures in the priority portion……………. 20
Fig. 3-1 Stationary time series……………………………….…… 24
Fig. 3-2 Nonstationary time series…………………….…………. 24
Fig. 3-3 The first difference of the series in Figure 3-2…….……. 24
Fig. 3-4 Seasonal time series…………………………………….. 25
Fig. 3-5 Process of model establishment………………….……… 26
Fig. 3-6 A nonstationary series…………………………………… 36
Fig. 3-7 Memory function of a random walk…………………….. 37
Fig. 3-8 A series of Gaussian noise…………………………….… 38
Fig. 4-1 Scheduler logic operations………………………………. 50
Fig. 4-2 Logical architecture…………………………………….. 51
Fig. 4-3 Histogram of the Guaranteed service…………………… 52
Fig. 4-4 Histogram of the Controlled-load service………………. 52
Fig. 4-5 The processing time slot in case I……………………….. 55
Fig. 4-6 Histogram of the Guaranteed service…………………… 55
Fig. 4-7 Histogram of the Controlled-load-1 service…………….. 56
Fig. 4-8 Histogram of the Controlled-load-2 service…………….. 56
Fig. 4-9 The processing time slot in case II……………………… 59
Fig. 4-10 The ratio of traffic transmitted in real-time (For case I, Scheme I)………………………………………………... 61
Fig. 4-11 The ratio of traffic transmitted in backlog (For case I, Scheme I)……………………………………………….. 61
Fig. 4-12 The ratio of traffic transmitted in delay (For case I, Scheme I)……………………………………………….. 62
Fig. 4-13 Loss rate (For case I, Scheme I)………………………… 62
Fig. 4-14 Fair play parameter (For case I, Scheme I)……………… 63
Fig. 4-15 The ratio of traffic transmitted in real-time (For case I, Scheme I and II)…………………………………………. 64
Fig. 4-16 The ratio of traffic transmitted in backlog (For case I, Scheme I and II)…………………………………………. 64
Fig. 4-17 The ratio of traffic transmitted in delay (For case I, Scheme I and II)…………………………………………. 65
Fig. 4-18 Loss rate (For case I, Scheme I and II)………………….. 65
Fig. 4-19 Fair play parameter (For case I, Scheme I and II)………. 66
Fig. 4-20 The ratio of traffic transmitted in real-time (For case II, Scheme I)……………………………………………….. 68
Fig. 4-21 The ratio of traffic transmitted in backlog (For case II, Scheme I)……………………………………………….. 69
Fig. 4-22 The ratio of traffic transmitted in delay (For case II, Scheme I)……………………………………………….. 69
Fig. 4-23 Loss rate (For case II, Scheme I)……………………….. 70
Fig. 4-24 Fair play parameter (For case II, Scheme I)…………….. 70
Fig. 4-25 The ratio of traffic transmitted in real-time (For case II, Scheme I and II)…………………………………………. 72
Fig. 4-26 The ratio of traffic transmitted in backlog (For case II, Scheme I and II)…………………………………………. 72
Fig. 4-27 The ratio of traffic transmitted in delay (For case II, Scheme I and II)…………………………………………. 73
Fig. 4-28 Loss rate (For case II, Scheme I and II)…………………. 73
Fig. 4-29 Fair play parameter (For case II, Scheme I and II)……… 74
Fig. 4-30 Fair play parameter (For case I, Scheme II and Non-change-factor)…………………..………………….. 75
Fig. 4-31 Fair play parameter (For case II, Scheme II and Non-change-factor)…………..………………………….. 75
List of Tables
Table 3-1 The SEACF table……………………………………….. 39

參考文獻

[1] Shenker, S., Partridge, C. and R. Guerin, "Specification of Guaranteed Quality of Service," RFC 2212, September 1997.
[2] Wroclawski, J., "Specification of the Controlled Load Network Element Service," RFC 2211, September 1997.
[3] W. E. Leland et al., “On the Self-Similar Nature of Ethernet Traffic (Extended Version),” IEEE/ACM Transactions on Networking, Vol. 2, No. 1, Feb. 1994.
[4] L. Kleinrock, “Queuing Systems, Volume 2: Computer Applications,” Wiley, 1976.
[5] Andrew S. Tanenbaum. “Computer Networks 3rd edition,” pp. 380-381, Prentice-Hall, 1996.
[6] A. Demers, S. Keshav, and S. Shenker, “Analysis and Simulation of a Fair Queueing Algorithm,” Proceedings of ACM SIGCOMM’89, pp. 3-12.
[7] H. –B. Chiou, F. –M. Tsou, Z. Tsai, “DMGFQ : A Novel Traffic Scheduler with Differentiated QoS Guarantee for Internet Multimedia Services,” IEEE ICC ‘2001, June 11-15, 2001.
[8] A. Silberschartz, P. B. Galvin, “Operating System Concepts 5th edition,” Addison Wesley, 1997.
[9] J. Nagel, “On Packet Switches with infinite storage,” RFC 970, December 1985.
[10] Rich Seifert, “The Switch Book,” Wiley, 2000.
[11] K. Zhu, Y. Viniotis and Y. Zhuang, “Guaranteed Rate Scheduling with Adaptable Excess Bandwidth Distribution,” Communication Technology Proceedings, 2000. WCC - ICCT 2000. International Conference on Volume: 2 pp. 1457 –1464, 2000.
[12] Goncalo Quadros, Antonio Alves, Edmundo Monteiro and Fernando Boavida, “An Effective Scheduler for IP Routers,” Computers and Communications, 2000. Proceedings. ISCC 2000. Fifth IEEE Symposium on, 2000, pp. 764 –772.
[13] F. –M. Tsou, H. –B. Chiou and Z. Tsai, “A Novel ATM Traffic Scheduler for Real-Time Multimedia Data Transport with Improved Packet Level QoS,” IEEE ICME ‘2000, New York, USA, July 30-August 2, 2000.
[14] George C. Tiao, Chung Chen and Ruey S. Tsay, “Time series analysis and forecasting,” 2001年時間數列分析與預測講習會, June 26-30, 2001.
[15] G. E. P., Box, and D. A. Pierce, “Distribution of residual Autocorrelations in Autoregressive Integrated Moving Average Time Series models,” Journal of American Statistical Association, vol. 65, no. 332, 1970, pp. 1509-1526.
[16] A. Parekh, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks,” PhD dissertation, Massachusetts Institute of Technology, February 1992.
[17] Bennett, J.C.R. and H. Zhang, “WF2Q: worst-case fair weighted fair queueing,” INFOCOM ’’96. Fifteenth Annual Joint Conference of the IEEE Computer Societies, Networking the Next Generation., Proceedings IEEE, Vol. 1, pp. 120-128, 1996.
[18] N. Duffield, T. lakshman and D. Stiliadis, “On adaptive bandwidth sharing with rate guarantees,” Proc. IEEE INFOCOM ’98, pp. 1122-1130, 1998.
[19] P. Goyal, S. Lam and H. Vin, “Determining end-to-end delay bounds in heterogeneous networks,” Proc. of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV ’95), pp. 287-298, 1995.
[20] S. Shenker and J. Wroclawski, “Network Element Service Specification Template,” RFC 2216, September 1997.

指導教授

陳彥文(Yen-Wen Chen)

審核日期

2002-7-8

推文