2.2. QUEUEING MODELS 39

at times {T

n

} that denote the arrival instants and decreases by 1 whenever packets depart from the

queue at instants that are denoted by {d

n

}.

2.2.1 QUEUES VIEWED FROM CONGESTION PROCESS VIEWPOIN T

Let A(s, t] denote the number of arrivals that occur and D(s, t] denote the number of departures in

the interval (s, t] . We assume throughout that the queue is work conserving in that the server does

not stop when there are packets in the queue. We also assume that the service discipline is FIFO.

Let Q

t

denote the number of packets in the queue at time t or the congestion process at time

t. Then:

Q

t

= Q

0

+ A(0,t]−D(0,t] t ≥ 0 (2.11)

Based on the evolution equation above, it is clear that Q

t

is a discrete valued process taking

values in ZZ

+

(the non-negative integers), and the sample paths are constant between jumps (of

value ±1) arrivals and departures. By construction, the process is right continuous. Let us make

some simple observation: if lim inf

t→∞

A(0,t]−D(0,t]

t

> 0 a.s., then Q

t

→∞a.s.. Such a situa-

tion implies that the queue is unstable. Our interest is when the queue is ﬁnite. This is related

to the notion of stability, and there are many different notions; for example, sup

t

Q

t

< ∞ a.s.,

lim sup

t→∞

1

t

t

0

Q

s

ds < ∞,etc. In these notes, our interest is to study conditions when stationary

arrival and departure processes result in Q

t

being a stationary process and conditions on the processes

such that the resulting buffer occupancy has a ﬁnite mean or higher moments and try to characterize

them explicitly. In the sequel, we will use A

t

and D

t

to denote A(0,t] and D(0,t], respectively.

However, before we state and prove the main stability result, let us see some implications

of stability in the sense that Q

t

is stationary with ﬁnite mean (and hence A(.) and D(.) are sta-

tionary increment processes). Let us assume that Q

t

is stationary and has a ﬁnite mean, taking

expectations in (2.11), E[Q

t

]=E[Q

0

], and hence E[A(0,t]] = E[D(0,t]] for all t implying that if

λ

A

= E[A(0, 1]] denotes the mean arrival rate, then: λ

A

= λ

D

d

= E[D(0, 1]], the mean departure

rate; in other words, the average input rate is equal to the average output rate.

Let us see another relation that follows from the queue evolution, the Lebesgue-Stieltjes

integration formula and the deﬁnition of palm probabilities. First, note that since Q

+

t

= 0 a.e. t.

(the trajectories are piecewise constant except at jumps), for any measurable, function f (.):

f(Q

t

) = f(Q

0

) +

t

0

[f(Q

s

) − f(Q

s−

)]dA

s

−

t

0

[f(Q

s

) − f(Q

s−

)]dD

s

(2.12)

Noting that at jumps T

n

of A

t

, we have f(Q

T

n

) = f(Q

T

n−

+ 1) and at jumps d

n

of D

t

, f(Q

d

n

) =

f(Q

d

n−

− 1)1I

[Q

d

n−

>0]

since departures can only take place when there are packets in the queue.

Now choose f(x) = 1I

[x=n]

and if {Q

t

} is stationary, substituting in (2.12), noting

E[1I

[Q

t

=n]

]=E[1I

[Q

0

=n]

] we obtain, for n ≥ 1:

E[

t

0

(1I

[Q

s−

+1=n]

− 1I

[Q

s−

=n]

)dA

s

]=E[

t

0

(1I

[Q

s−

−1=n]

− 1I

[Q

s−

=n]

)dD

s

]

Get *Performance Modeling, Loss Networks, and Statistical Multiplexing* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.