A tool for verified analysis of transient and steady states of queues

摘要

In the analysis of queueing systems, many approaches have been developed with different properties regarding the complexity and numerical stability of the computation. We have studied factorization methods, which proved to be efficient for traffic modelling in telecommunication systems as well as classical queueing systems.Since the traffic rate on each transmission link is limited by a constant forwarding capacity, discrete time models with distributions of finite support are then appropriate, including deterministic service as the simplest case. On the other hand, various autocorrelation structures of Internet traffic are taken into account using semi-Markovian modeling.We have developed the InterVerdiKom tool starting with steady state analysis of semi-Markov systems in discrete time based on Wiener-Hopf and polynomial factorization. The tool has been applied to evaluate the performance of switching systems with input from superposed on-off sources and for video traffic. Using approximations ofa Gaussian distribution function at stepwise refined discretization granularity, even servers with a first order autoregressive input have been analyzed at a controllable accuracy level.The tool makes use of interval arithmetic for verification of the accuracy of results of the steady state solution methods and has been extended recently to include transient system behavior.