Introduction

The M/GI/1 queue is the most useful model for packet switching networks. It is often realistic to assume that packet arrival process is Poisson, but service time is not exponential at all. Services are independent when treatments depend upon the packet length, and when this length is constant, the adequate model is M/D/1. Otherwise M/GI/1 queues are used.

In this paper are considered known results [1] about M/GI/1 queue, but from a new point of view, allowed by an efficient use of formal computing. Efficient algorithms are designed in order to obtain bounds on performance criteria for such a queue. The tail of the response time distribution of such an M/GI/1 queue can be evaluated from Pollaczek-Khintchine formula, leading to deal with Laplace transforms.

But when dimensioning systems, Laplace transforms have to be inverted, and the usual numerical methods give approximations for which accurate error bounds are not available. This is rather not a new subject [2][3][4][5], but a new method to attack this old problem can be obtained as follows.

We have written, in Maple code, a package of procedures that computes the formal convolution of two piecewise polynomial functions (i.e. splines). This is especially usefull when dealing with inverse Laplace transform, since such a computation is strongly ill-conditioned. A method using exact computations during the first steps of iterative algorithms is therefore significantly more accurate than any other method. From these formal computations, two kinds of results concerning the sojourn-time pdf can be obtained: exact bounds for the first part of the curve and an accurate approximation of the second part of the curve. Moreover, unlike other algorithms, the proposed algorithm leads to an error term that is not an oscillating function, and requires no "calibrations".

The present paper is organized as follows: assumptions and notations are presented in section 1. The inversion of the Pollaczek-Khintchine formula is reminded in section 2. Two formal approaches are designed in sections 3 and 4. Numerical improvements are proposed in section 5. Conclusions are formulated in section 6, and the paper ends with some references.