Performance Analysis of Multiple Server Queues in Conjunction with MMPP Fitting for Self-Similar Traffic

近來的網路訊務研究顯示在乙太網路及廣域網路上的訊務，都呈現自我相似性或長距離關聯性的特性。與傳統的短距離關聯性訊務不同，自我相似性的訊務嚴重地降低網路的性能。然而，大多數具自我相似性的訊務模型本質上都有漸近性的特性，在緩衝器較短的排隊理論分析將顯得無效率。因此，一些研究提出以短距離關聯性訊務，在指定的時間範圍內，近似自我相似性訊務。藉現今排隊理論的技術，結合近似的短距離關聯性訊務模型，自我相似性輸入訊務的網路性能分析得以實現。 此外，矩陣解析法被廣泛地應用於分析類馬可夫(Markov-like)行為程序為輸入訊務之佇列系統，當緩衝器深度不大時，這種方法特別有用。我們利用矩陣解析法的技術，不僅能分析單一伺服器系統，且可分析具有限緩衝器的多重伺服器系統。一組多重伺服器系統，能讓多個輸入訊務進入設備，並同時處理固定數量之封包。這類的多重伺服器系統，被廣泛地應用在網路設備，如集線器，路由器和多埠多工器等，皆是應用多重伺服器當作其基礎模件。 綜合前兩項論述，考慮馬可夫模組化─卜瓦松程序模型(Markov modulated Poisson process, MMPP)為一短距離關聯性的訊務模型，且被證實它可近似自我相似訊務，在單一伺服器佇列系統的排隊行為，亦具有自我相似訊務之表現。結合多重伺服器系統及MMPP模組近似自我相似訊務之分析，將會提供網路硬體設計者正確的效能統計。我們期許這項研究，對欲從事網路更深入研究的研究員有助益。Seminal studies have shown that real Internet traffic is self-similar, that is, the traffic posseses long-range dependence property. This self-similar nature degrades the network performance. Most of the self-similar traffic models are asymptotic in nature thus they are less effective in view of queueing-based performance when buffer sizes are small. In view of this, some studies argued that short-range dependent models could fit into self-similar traffic to some extent. As queueing theory techniques are available for these models, thereby one can have network performance measures of the self-similar traffic. In addition, matrix-analytical methods (MAMs) have become very popular in the performance analysis of queueing system with Markovian input. The method is specifically useful when buffer sizes are not too large. We could make use of this technique in the analysis of multiple server systems with finite buffers. A multiple server system is a facility that let several branch traffics enter into system and copes with fixed number of packets at one processing time. Besides, multiple server systems are basic modules such as concentrators, routers, and multiplexers, which are extensively applied in networks. MMPP model is a short-range dependent model, has been proven that it can emulate the second-order self-similar traffic and gives fine queueing-estimation in single server queueing system. Analysis of multiple server systems with MMPP input traffic (pseudo self-similar traffic) provides hardware designer a right performance statistics. We hope that the analysis is helpful for the people in their further research.Chinese Abstract i English Abstract iii Chinese Acknowledgement v English Acknowledgement vii Contents ix List of Tables xi List of Figures xiii Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Structure of the Thesis 3 Chapter 2 Markov Mudulated Poisson Process (MMPP) and Self-Similar Traffic 5 2.1 Overview 5 2.2 Markov-Modulated Poisson Process 5 2.2.1 Overview of MMPP Model 6 2.2.2 Applications of the MMPP Model 8 2.3 The Self-Similar Process 10 2.3.1 Second-Order Self-Similar Process 10 2.3.2 Evidence of Self-Similarity in Network Traffic 12 2.3.3 Models of Self-Similar Traffic 13 2.3.4 Estimating and Testing for Self-Similarity 14 2.4 The Generalized Variance-Based Markovian Fitting 15 2.4.1 Fitting Model 16 2.4.2 Performance of Generalized Variance-based Fitting 18 Chapter 3 Finite Buffer Multiple Server System under MMPP Traffic Input 23 3.1 Overview 23 3.2 MMPP/D/1/K Queue 23 3.2.1 Formulation of MMPP/D/1/K Queue 25 3.2.2 Loss Probability for MMPP/D/1/K Queue 28 3.3 MMPP/D/c/K queue 29 3.3.1 Formulation of MMPP/D/c/K queue 31 3.3.2 Loss Probability for MMPP/D/c/K Queue 33 3.4 Comparison and Summary 34 Chapter 4 Performance Study of Multiple Server Queues in Conjunction with MMPP Fitting for Self-Similar Traffic 37 4.1 Overview 37 4.2 The Simulation Models 37 4.2.1 Simulation of Fractional Brownian Traffic 37 4.2.2 Simulation of the MMPP 41 4.3 Analytical Results and Simulation Results 42 4.3.1 Loss Probability of Finite Buffer Multiple Server Queue 43 4.3.2 Effect of Time-Scale Range on Loss Behavior 47 4.3.3 Effect of the Number of Superposed IPPs on Loss Behavior 52 4.4 Effect of the Number of Servers on Queueing-Based Prediction 55 4.4 Summary 63 Chapter 5 Advanced Applications –Terminal Multiplexers with Concentrator & FF Type WDM Optical Packet Switches 65 5.1 Overview 65 5.2 Application Ⅰ─ Terminal Multiplexers with Concentrators 66 5.2.1 Concentrator and MMPP/D/c/K Queue Modeling 67 5.2.2 Numerical Results 68 5.3 Application Ⅱ ─ FF type WDM Optical Packet Switch 75 5.3.1 Effect of Wavelength Conversions on WDM OPS 77 5.3.2 WDM Optical Packet Switch Modeling Using MMPP/D/c/K Queue 79 5.3.3 Numerical Results 80 5.4 Pitfalls of the Applications 89 5.5 Summary 91 Chapter 6 Conclusions 93 References 9