AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing：对于多类排队的精确分析的一种有效算法.ppt

1、1,Giuliano Casale, Eddy Z. Zhang, Evgenia Smirni casale, eddy, Speaker: Giuliano Casale Numerical Methods for Structured Markov Chains, Dagstuhl Seminar November 11-14, 2007,College of William & Mary Department of Computer Science Williamsburg, 23187-8795, Virginia, US,Interarrival

2、Times Characterization and Fitting for Markovian Traffic Analysis,2,Outline,Motivations Review of MAP Fitting Algorithms from fitting counts to interarrival times (IAT) fitting observations on eigenvalue-based methods Jordan characterization of MAP moments and autocorrelations analysis of small MAPs

3、 Composition of large MAPs MAP fitting using higher-order correlations,3,Motivation,MAP/MMPP Model Parameterization Markovian models of network traffic MAP closed queueing networks (see slides E. Smirni) MAP fitting is not fully understood E.g., some questions: Fit the counting process or the intera

4、rrival process? How many moments? Which correlation coeffs? How fitting decisions affect queueing prediction? Is nonlinear optimization appropriate,4,MMPP Counting Process Fitting,Measuring counts in networks can be often easier than measuring interarrival times S. Li & C.L. Hwang, 1992, 1993: Circu

5、lant matrices to impose MMPP power spectrum A.T. Andersen & B.F. Nielsen, 1998: Superposition of MMPP(2)s (Kronecker sum) Matching of the Hurst parameter Degrees of freedom for optional least-square fitting of the interarrival time (IAT) autocorrelations (ACF) Good accuracy on the Bellcore Aug89/Oct

6、89 traces,5,MAP Counting Process Fitting,A. Horvth & M. Telek, 2002: Multifractal traffic model, e.g., Riedi et al., 1999 Traffic analysis based on Haar wavelet transform Each MAP(2) describes variability in the Haar wavelet coefficients at a specific time scale Almost optimal fitting of the BC-Aug8

7、9 trace Further improvements may not be easy: Higher-order moments of counts hard to manipulate,6,MAP Interarrival Process,Two-phase fitting fitting of PH-type distribution followed by fitting of IAT ACF Feasible manipulation of higher-order moments P. Buchholz et al., 2003, 2004: Expectation Maximi

8、zation (EM) algorithms Support for two-phase fitting Scalability of EM rapidly increasing (Panchenko & Thmmler, 2007,7,MAP Interarrival Process,Moment and ACF Analytical Fitting: Results only for MMPP(2), MAP(2), MAP(3) G. Horvth, M. Telek & P. Buchholz, 2005: Two-phase least-square fitting of PH di

9、strib. and ACF Optimization variables are the MAP transition rates, i.e., the O(n2) entries of the D0 and D1 matrices Simple to understand and implement Least-squares can be numerically difficult: small magnitude of transition rates compared to tolerance infeasibility due to inappropriate choice of

10、step size,8,Our observations,Observation 1: eigenvalues give direct control to the nonlinear solver on ACF decay and CDF tail Observation 2: lack of general Jordan analysis of IAT moments and autocorrelations Observation 3: eigenvalue-based least-squares tends to be numerically well-behaved Observat

11、ion 4: inverse eigenvalue problems often prohibitive, how do we determine D0 and D1? Superposition does not help for IAT process,9,Our contributions,A general Jordan analysis of MAP moments and autocorrelations Using this characterization we analyze the IAT process in small MAPs We find a compositio

12、nal approach to define the IAT process in large MAPs using small MAPs Main result: A least-squares that can fit IAT moments and correlations of any order,10,Why statistics of “any order”,Literature evaluates up to second-order properties Higher-order correlations are neglected, but,11,MAP Jordan Ana

13、lysis,Definition: MAP moments Definition: MAP autocorrelations Moments and correlations depend on matrix powers Eigenvalues explicited by the Cayley-Hamilton theorem,12,MAP Jordan Analysis Contd,13,MAP(3) Characterization Example,Define MAPs with given oscillatory ACF Generalization of Circulant MAP

14、s to IAT process,MAP Definition,Characterization,14,MAP(3) Characterization Example,SCV=4.87 p1=0 p2=0.0286,15,Composition of Large Processes,Idea: use Kronecker product to overcome inverse eigenvalue problem in eigenvalue-based fittings Kronecker product composition (KPC) One of the two D0 matrices

15、 must be diagonal No loss of generality Prevents negative (infeasible) off-diagonal entries inthe D0 matrix of the KPC,16,Jordan Analysis of KPC process,Eigenvalues and projectors Moments and autocorrelations,17,KPC Example,To the best of our knowledge, never shown in the literature a MAP with lag-1

16、 acf 0.5 Does it exist? MAP(2) must have lag-1 acf 0.5 Not found in 100.000 random MAP(3) and MAP(4) Answer: yes it exists, it can be defined by KPC A simple MAP(2,18,KPC Example Contd,What happens if we compose with KPC the MAP(2) with a PH renewal process? Composition with a hypoexponential proces

17、s,19,Jordan Analysis of KPC processIAT Joint Moments,Joint moments, e.g.,G. Horvth & M. Telek, 2007 Admits characterization similar to moments/acf Joint moments in KPC process Conclusion: KPC can fit moments of any order,20,Two-Phase Least Squares,We determine J small MAPs to be composed by KPC in o

18、rder to best fit a trace Lessons learned from Jordan analysis: first fit ACF and SCV, then moments,Phase 2: Fit moments,Phase 1: ACV+SCV,eigenvalue-based,mean and bispectrum,21,Results: BC-Aug89quality of fitting - MAP(16,22,Results: Seagate-Webquality of fitting - MAP(16,23,Results: BC-Aug89queueing prediction - MAP(16,24,Results: Seagate Webqueueing prediction - MAP(16,25,Conclusion,Jordan characterization allows: analysis of simple MAP processes least-square fitting that is numerically well-behaved Joint