電信級網路優先佇列之效能模式及分析

PERFORMANCE MODELING AND ANALYSIS OF PRIORITY QUEUEING IN CARRIER-GRADE NETWORKS

陳雲龍(Yun-lung Chen)

指導教授 ： 陳建華

大同大學/電機資訊學院/通訊工程研究所/博士(2009年)

摘要

隨著現代人對電信網路提供的服務品質要求越來越高，電信級的網路交換技術因而扮演著關鍵的角色。當大量的突暴訊務隨機進入交換網路時，必定有一些訊務會無法立即被處理，以致因網路壅塞造成訊務延遲，封包可能被丟棄或重送，這將影響整個網路的效能。優先佇列的設計可改善進入交換網路節點或節點間的封包訊務流之處理。MB/G/1模型若使用嵌入式Markov鏈方法(embedded Markov chain)或增添變數技巧 (supplementary variable technique)，可用來分析交換網路節點優先佇列的效能。然而具有兩級優先佇列的MB/G/1 所推導出的平均佇列長度表示式使用到的參數稍多，一旦佇列超過兩級，表示式就開始變得非常複雜。因此一般分析MB/G/1使用的佇列級數最多只到兩級為止，這對多媒體寬頻網路應用的效能分析非常不利。本論文主要目標即在於提出簡單可靠的平均佇列長度表示式。使得佇列一旦超過兩級以上時，電信級網路之效能分析依然可容易實現。
為避免MB/G/1佇列超過兩個等級以上時所遭遇的問題，我們採用GE/G/1優先佇列模型。當進入GE/G/1佇列的訊務流呈現著整批形式並具突暴特性時，可經數學推導證實它與MB/G/1優先佇列模型非常類似。當分析兩個等級以上的優先佇列，所得出的平均佇列長度表示式，所需參數不但簡單，經與模擬結果比較，也證實非常精確。為方便說明網路效能分析，我們以兩種電信級的應用驗證我們所分析的模型。應用一討論電信級VoIP網路內的SIP-T訊令系統，以兩級GE/G/1優先佇列分析討論，我們可推導出簡單與非常接近精準的平均佇列長度表示式。並與兩級MB/G/1優先佇列的平均佇列長度表示式做比較。應用二討論ATM為基礎的MPLS (Multiprotocol Label Switching)電信級網路內的LER (Label Edge Router)系統。我們以具有四種類型服務等級的GE/G/1優先佇列做效能分析。此外，封包抵達速率的平均值與變異數所定義的變異係數的平方 (Squared Coefficient of Variation)對整個分析是否會開始退化也是重要的指標參數，本文所得到的數值結果將可提供未來電信級網路效能評估與部署時的考量。

關鍵字

突暴訊務 ； 平均佇列長度 ； 最大熵 ； GE分佈模型 ； 相繼到達時間間隔分佈 ； 增添變數技巧

並列摘要

Real data traffic exhibits burstiness which is beyond what Poisson model can characterize. The non-preemptive MB/G/1 priority queue with bulk arrivals is not a viable method to deal with the bursty traffic, because it is difficult to analyze when the number of priorities is more than two. Since the closed-form expression of the mean queue length (MQL) is usually complicated, studies were therefore restricted to two-class MB/G/1. We apply the principle of maximum entropy (ME) to provide an analytical framework for the approximate analysis of a stable multiple-class G/G/1 queue. The generalised exponential (GE) model is used to approximate general distributions with known first two moments. The close-form expression of the MQL requires only a few parameters for calculation, such as means and variation. The credibility of the ME solutions may gradually begin to deteriorate due to the increasing values of the squared coefficient of variations (SQVs) of interarrival times and service times.
To apply the priority queue analysis in studying the network performance, we discuss two cases in carrier-grade networks. The first application establishes a GE/G/1 priority queue for an SIP-T signaling system in carrier-grade VoIP network with two priority classes. We obtain simple and closed-form expressions of the MQL. The numerical results and computer simulations further confirm the accuracy and robustness of a GE/G/1 priority queue. In the second application we use the four-class GE/G/1 priority queue to model the multimedia services of the label edge router (LER) in ATM-based MPLS networks. The increased number of priority classes is critical for multimedia service. We obtain the boundary conditions of MQL and mean queueing delay (MQD) for each priority class. These metrics are crucial for improving QoS and system performance in a carrier-grade network. More sophisticated derivation and simulation results are presented. The comparison between analytical and simulation results shows a close approximation in MQL and MQD for multiclass non-preemptive priority queues.

並列關鍵字

Guaranteed SIP-T Message (GM) ； Squared Coefficient of Variation (SQV) ； Tolerance of Error (Tol-Err) ； Generalised Exponential (GE) ； Maximum Entropy Method (MEM)

參考文獻

[2] N. K. Jaiswal, Priority Queues, Academic Press, NY, USA. 1968.

[3] L. Kleinrock, Queueing Systems, Vol. I, Wiley, NY, USA, 1975.

[4] H. Takagi and Y. Takahashi, “Priority queues with batch Poisson arrivals,” Operations Research, Letters 10, pp. 225-232, 1991.

[5] D. D. Kouvatsos, “Entropy maximization and queueing network models,” Annals of Operation Research, vol. 48, no. 1, pp. 63-126, 1994.

[6] D. D. Kouvatsos, “Maximum entropy analysis of queueing network models,” Performance Evaluation of Computer and Communication Systems, vol. 729, pp. 245-290, 1993.