AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第1页
AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第2页
AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第3页
AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第4页
AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第5页
已阅读5页,还剩20页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论