The Multi-Branched Method of Moments for Queueing Networks
File(s)0902.3065v1.pdf (249.53 KB)
Submitted version
Author(s)
Casale, Giuliano
Type
Conference Paper
Abstract
We propose a new exact solution algorithm for closed multiclass product-form queueing networks that is several orders of magnitude faster and less memory consuming than established methods for multiclass models, such as the Mean Value Analysis (MVA) algorithm. The technique generalizes the recently proposed Method of Moments (MoM) which, differently from MVA, recursively computes {higher-order} moments of queue lengths instead of mean values. The main contribution of this paper is to show that the information used in the MoM recursion can be increased by considering multiple recursive branches that evaluate models with fewer queues. This reformulation allows to define a simpler matrix difference equation for computing normalizing constants which leads to large computational savings with respect to the MoM recursion. Computational analysis shows many cases where the proposed algorithm is between 1,000 and 10,000 times faster and less memory consuming than MoM, thus extending the range of multiclass models where exact solutions are feasible.
Date Issued
2009-10-23
Date Acceptance
2009-09-13
Citation
SIXTH INTERNATIONAL CONFERENCE ON THE QUANTITATIVE EVALUATION OF SYSTEMS, PROCEEDINGS, 2009, pp.227-236
ISBN
978-0-7695-3808-2
Publisher
IEEE
Start Page
227
End Page
236
Journal / Book Title
SIXTH INTERNATIONAL CONFERENCE ON THE QUANTITATIVE EVALUATION OF SYSTEMS, PROCEEDINGS
Copyright Statement
© 2009 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000275039200026&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Source
6th International Conference on the Quantitative Evaluation of Systems
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Theory & Methods
Mathematics, Applied
Computer Science
Mathematics
COMPUTATIONAL ALGORITHMS
NORMALIZATION CONSTANTS
GENERATING-FUNCTIONS
EXPONENTIAL SERVERS
BEHAVIOR
SYSTEMS
Publication Status
Published
Start Date
2009-09-13
Finish Date
2009-09-16
Coverage Spatial
Budapest, HUNGARY