Asymptotic Bounds for the Fluid Queue Fed by Subexponential on/off Sources

Vincent Dumas

INRIA-Rocquencourt

Algorithms Seminar

February 4, 1999

[summary by Jean-Marc Lasgouttes]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

This talk presents results from Dumas and Simonian [3] on the tail behaviour of the buffer content of a fluid queue processing the input of several exponential and subexponential sources. While the results in [3] are rather general, the presentation given here uses a simplified setting, for the sake of understandability.

1   Framework

Consider a fluid queue with infinite buffering capacity and outflow rate c. This queue is fed by N>1 independent stationary on/off sources, where source i, 1 i N is characterized by: The following notation will be useful later:
pi:=
E[Ain]
E[Ain+Sin]
,   ri := hi pi.
To characterize the stationary regime of source i, it is convenient to introduce the time elapsed in the current activity period Ai*, whose distribution is given by
Pr[Ai*=0] = 1-pi,
Pr[Ai*>x|Ai*>0]
=


x
Pr[Ain>y]
E[Ain]
dy.

In what follows, we restrict ourselves to the case where hi h, pi p and rir, for all 1 i N. If Vt is the volume of fluid in the buffer at time t (with V0=0), then the following result is well known:
Theorem 1   Let Wi[t] be the flow emitted by source i in stationary regime in the interval ]-t,0] and define W[t] := i=1NWi[t]. Then, assuming Nr<C,
 
lim
t
Vt
L
=
 
V :=
 
sup
t 0
(W[t]-ct).
It is important to have good estimates for Pr[V>x], since this can be used to determine loss rate in a finite buffer queue. A typical result in this respect is due to Anick, Mitra and Sondhi [1]: if there exist constants ai such that Pr[Ain>x] = O(e-ai x), 1 i N, then there exists a such that Pr[V>x]=O(e-a x).

However, recent studies have shown that some sources may have subexponential activity patterns, such as Pr[Ain>x] =O(x-si), si>1. The purpose of this work is therefore to find good estimates for the tail distribution of V when the sources are a mix of exponential and subexponential sources, extending the results of [2, 4, 5].

2   Lower and Upper Bounds

Let I be a subset of {1,...,N}, with cardinal |I|, and define
AI* :=
 
min
i I
Ai*,     W
 
_
I
 
[t]:=
 
iI
Wi[t],
n0 := inf{n0|nh+(N-n)r>c}.

Then the following bound holds as x:
Pr[V>x]
 
max
I
Pr [ (|I|h+(N-|I|)r-c)AI*>x ]
 
 
max
|I|=n0
 
i I
Pr [ (n0h+(N-n0)r-c)Ai*>x ] .

Similarly, defining Vi as
Vi:=
 
sup
t0
( Wi[t]-r(1+e)t ) ,
where e>0 is such that (n0-1)h+(N-n0+1)r(1+e)=c, one has
Pr [V> x]
 
|I|=n0
 
i I
Pr


Vi>
x
N-n0+1



.

3   Application to a Mix of Exponential and Subexponential Sources

Assume that the queues can be partitioned in two classes for some N0<N:
Pr[Ain>x] =O(x-s),     1 i N0,
Pr[Ain>x]
=O(e
-ai x
 
),    
N0< i N.
Then the main result of this study is as follows.
Theorem 2   The following approximations hold:

References

[1]
Anick (D.), Mitra (D.), and Sondhi (M. M.). -- Stochastic theory of a data-handling system with multiple sources. The Bell System Technical Journal, vol. 61, n°8, 1982, pp. 1871--1894.

[2]
Boxma (O. J.). -- Regular variation in multi-source fluid queue. In Ramaswami (V.) and Wirth (P. E.) (editors), Teletraffic Contributions for the Information Age. pp. 391--402. -- North-Holland, Washington DC, 1997. Proceedings ITC-15.

[3]
Dumas (V.) and Simonian (A.). -- Asymptotic bounds for the fluid queue fed by sub-exponential On/Off sources. -- Technical Report n°98028, MAB, Universit de Bordeaux 1, 1998.

[4]
Jelenovicz (P. R.) and Lazar (A. A.). -- Asymptotic results for multiplexing on/off sources subexponential on periods. Advances in Applied Probability, vol. 31, n°2, 1999.

[5]
Rolski (Tomasz), Schlegel (Sabine), and Schmidt (Volker). -- Asymptotics of Palm-stationary buffer content distributions in fluid flow queues. Adv. in Appl. Probab., vol. 31, n°1, 1999, pp. 235--253.

This document was translated from LATEX by HEVEA.