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

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:

silence periods, where it generates no traffic, of length S_in, n� 1, i.i.d. and exponentially distributed;
activity periods, where it generates traffic at peak rate h_i, of length A_in, n� 1; these variables are i.i.d., but no assumption is made on their distribution for now.

The following notation will be useful later:

p_i:=

E[A_in]

E[A_in+S_in]

, r_i := h_i p_i.

To characterize the stationary regime of source i, it is convenient to introduce the time elapsed in the current activity period A_i^*, whose distribution is given by

Pr[A_i^*=0]

= 1-p_i,

Pr[A_i^*>x|A_i^*>0]

�
�

�

Pr[A_in>y]

E[A_in]

dy.

In what follows, we restrict ourselves to the case where h_i� h, p_i� p and r_i�r, for all 1� i� N. If V_t is the volume of fluid in the buffer at time t (with V₀=0), then the following result is well known:

Theorem 1 Let W_i[t] be the flow emitted by source i in stationary regime in the interval ]-t,0] and define W[t] := �_i=1^NW_i[t]. Then, assuming Nr<C,

lim

t��

V_t

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 a_i such that Pr[A_in>x] = O(e^-a_ⁱ^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[A_in>x] =O(x^-s_ⁱ), s_i>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

A_I^* :=

min

i� I

A_i^*, W

[t]:=

�

i�I

W_i[t],

n₀ := inf{n�0|nh+(N-n)r>c}.

Then the following bound holds as x��:

Pr[V>x]

�

max

[

(|I|h+(N-|I|)r-c)A_I^*>x

]

�

max

|I|=n₀

�

i� I

[

(n₀h+(N-n₀)r-c)A_i^*>x

]

Similarly, defining V_i as

V_i:=

sup

t�0

(

W_i[t]-r(1+e)t

)

where e>0 is such that (n₀-1)h+(N-n₀+1)r(1+e)=c, one has

[V> x] �

�

|I|=n₀

�

i� I

�
�
�
�

V_i>

N-n₀+1

�
�
�
�

3 Application to a Mix of Exponential and Subexponential Sources

Assume that the queues can be partitioned in two classes for some N₀<N:

Pr[A_in>x]

=O(x^-s),

1� i� N₀,

Pr[A_in>x]

=O(e

-a_i x

N₀< i� N.

Then the main result of this study is as follows.

Theorem 2 The following approximations hold:

if N₀<n₀, then Pr[V>x]=O(e^{-a x});
if N₀� n₀, then Pr[V>x]=O(x^-n_⁰^(s-1)).

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 L^AT_EX by H^EV^EA.