A NEW COMPUTATIONAL APPROACH FOR STOCHASTIC FLUID MODELS OF MULTIPLEXERS WITH HETEROGENEOUS SOURCES

In this paper we derive an efficient computational procedure for the s ystem in which fluid is produced by N-1 on-off sources of type 1, N-2 on-off sources of type 2 and transferred to a buffer which is serviced by a channel of constant capacity. This is a canonical model for mult iservice ATM multiplexing, which is hard to analyze and also of wide i nterest. This paper's approach to the computation of the buffer overfl ow probability, G(x) = Pr(buffer content > x), departs from all prior approaches in that it transforms the computation of G(x) for a particu lar x into a recursive construction of an interpolating polynomial. Fo r the particular case of two source types the interpolating polynomial is in two variables. Our main result is the derivation of recursive a lgorithms for computing the overflow probability G(x) and various othe r performance measures using their respective relations to two-dimensi onal interpolating polynomials. To make the computational procedure ef ficient we first derive a new system of equations for the coefficients in the spectral expansion formula for G(x) and then use specific prop erties of the new system for efficient recursive construction of the p olynomials. We also develop an approximate method with low complexity and analyze its accuracy by numerical studies. We compute G(x) for dif ferent values of x, the mean buffer content and the coefficient of the dominant exponential term in the spectral expansion of G(x). The accu racy of the approximations is reasonable when the buffer utilization c haracterized by G(O) is more than 10(-2).