論文目次 |
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. |