This paper presents a new computational method for steady state analysis of finite quasi-birth-death (QBD) processes with level-dependent transitions. The QBD state space is defined in two-dimension with N phases and K levels. Instead of formulating solutions in matrix-geometric form, the Folding-algorithm provides a technique for direct computation of /spl pi/P=0, where P is the QBD generator which is an (NK)/spl times/(NK) matrix. Taking a finite sequence of fixed-cost binary reduction steps, the K-level matrix P is eventually reduced to a single-level matrix, from which a boundary vector is obtained. Each step halves the matrix size but keeps the QBD form. The solution /spl pi/ is expressed as a product of the boundary vector and a finite sequence of expansion factors. The time and space complexity for solving /spl pi/P=0 is therefore reduced from O(N/sup 3/K) and O(N/sup 2/K) to O(N/sup 3/ log/sub 2/ K) and O(N/sup 2/ log/sub 2/ K), respectively. The Folding-algorithm has a number of highly desirable advantages when it is applied to queueing analysis. First, the algorithm handles the multilevel control problem in finite buffer systems. Second, its total independence of the phase structure allows the algorithm to apply to more elaborate, multiple-state Markovian sources. Its computational efficiency, numerical stability and superior error performance are also distinctive advantages.>

For pt.I see ibid., p.1464 (1991). The authors apply their folding algorithm to study various queuing phenomena related to an asynchronous transfer mode (ATM) multiplexer. They examine how the different system parameters affect the packet loss and queuing delay, and show the performance improvements by overload controls. They also analyze the queuing performance under different dynamic resource allocation policies. These analyses provide important insights for ATM design. The wide applicability of the folding algorithm is emphasized by including many practical examples, whose complexities far exceed those found in the literature. A set of highly effective approximation techniques is also proposed to further extend the folding algorithm's application range.>

A general solution methodology is provided for analysis of multi-media traffic queues. An efficient algorithm for a class of quasi-birth-death (QBD) processes, which are very versatile in formulating multi-media traffic queues, is described. Based on the Markov chain reduction principle, the algorithm exploits structural property to overcome the difficulties caused by the extraordinarily large state space of the model. It is stable, accurate and efficient for handling very large-scale problems. Applications of the algorithm to analysis of multi-media traffic queues with finite buffer and multilevel overload controls are emphasized. Two continuous time QBD models are devised for the applications. Model 1 extends the finite M/M/1 queue with Markov-modulated Poisson arrivals. Model II is the Markovian version of the continuous fluid-flow model. Both queue distribution and packet loss rate are measured. The effectiveness of the algorithm is demonstrated through analysis of various design and control issues in multi-media traffic integrations.>