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 finite. 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 finite 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 finite mean (and hence A(.) and D(.) are sta-
tionary increment processes). Let us assume that Q
t
is stationary and has a finite 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 definition 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.