![AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第1页](http://file1.renrendoc.com/fileroot2/2019-3/4/126aad07-7f76-4c06-86b6-ad8d0455dd11/126aad07-7f76-4c06-86b6-ad8d0455dd111.gif)
![AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第2页](http://file1.renrendoc.com/fileroot2/2019-3/4/126aad07-7f76-4c06-86b6-ad8d0455dd11/126aad07-7f76-4c06-86b6-ad8d0455dd112.gif)
![AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第3页](http://file1.renrendoc.com/fileroot2/2019-3/4/126aad07-7f76-4c06-86b6-ad8d0455dd11/126aad07-7f76-4c06-86b6-ad8d0455dd113.gif)
![AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第4页](http://file1.renrendoc.com/fileroot2/2019-3/4/126aad07-7f76-4c06-86b6-ad8d0455dd11/126aad07-7f76-4c06-86b6-ad8d0455dd114.gif)
![AnEfficientAlgorithmfortheExactAnalysisofMulticlassQueueing:对于多类排队的精确分析的一种有效算法.ppt_第5页](http://file1.renrendoc.com/fileroot2/2019-3/4/126aad07-7f76-4c06-86b6-ad8d0455dd11/126aad07-7f76-4c06-86b6-ad8d0455dd115.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 知识产权交易中的评估方法及法律问题探讨
- 社交平台在商业推广中的实战经验
- 商业银行考试题与参考答案
- 社区健康教育中的数字化技术应用探讨
- 知识产全管理在企业发展中的作用与影响
- 电子竞技行业的人才培养机制优化研究
- 电子商务在环保领域的应用探索
- 班主任安全工作计划范文
- 社交电商平台的客户关系管理策略
- 各学校招生计划
- 110KV送出线路工程施工组织设计方案和对策
- 二零二五年度大型自动化设备买卖合同模板2篇
- 城市交通系统中的空间正义问题-深度研究
- 2024版金矿居间合同协议书
- 2024年03月江苏2024年中国工商银行苏州分行社会招考笔试历年参考题库附带答案详解
- 2025年北师大新版高二物理上册阶段测试试卷
- 2024年青岛职业技术学院高职单招语文历年参考题库含答案解析
- GA/T 2145-2024法庭科学涉火案件物证检验实验室建设技术规范
- 2025内蒙古汇能煤化工限公司招聘300人高频重点提升(共500题)附带答案详解
- 《餐饮服务礼貌用语》课件
- 2025年中国融通资产管理集团限公司春季招聘(511人)高频重点提升(共500题)附带答案详解
评论
0/150
提交评论