An Exact Solution to An Approximated Model of RED
Claus Bauer

Homayoun Youseﬁ’zadeh

Dolby Laboratories
San Francisco, CA, 94103, USA
Email: cb@dolby.com

Hamid Jafarkhani

Department of EECSUniversity of California, Irvine, USA
Email: {hyouseﬁ,hamidj}@uci.edu

Abstract— In this paper, we propose an analytical model tocapture the dynamics of the RED algorithm. We ﬁrst develop asystem of recursive equations that describes the packet dropping
behavior of the RED algorithm. Using a notion from the theoryof random walks, we then derive an exact-closed form expressionthat characterizes the loss characteristics of a RED queue. We
validate the derived formula by a numerical comparison with therecursive equations.

I. I NTRODUCTION
The traditional Internet architecture relies on a best-effort
architecture for all kinds of data trafﬁc. The feedback-based
TCP protocol has initially been used to provide reliable dataservices. However, the emergence of real-time applications
puts strict latency demands on the network infrastructurethat cannot be guaranteed by the TCP protocol. The IETF
has introduced the integrated and the differentiated service
technologies to provide stronger quality of service guarantees.
The quality of service performance of a network also depends on the packet drop mechanisms of routers. The simplest
dropping schemes drop all packets arriving at a full queue.
Active Queue Management (AQM) has been proposed as amean to alleviate some congestion problems. Variations of
AQM include Early Packet Discard [7], and Random Early
Drop [11]. A widely studied AQM scheme is Random Early
Detection (RED) [4], [5]. Newer AQM schemes such as
Adaptive Virtual Queue Algorithm [8], Random Exponential
Marking [1] have been shown to address several shortcomingsof RED. However, the RED algorithm continues to be used inpractice and any new insights in its performance are of beneﬁt
to network operators.
From a practical stand point, the deployment of the RED
algorithm is difﬁcult because it must conﬁgured by choosing
the values of several parameters. The optimal conﬁguration ofthese parameters is not well understood.
Using simpliﬁed assumptions, guidelines for setting the
RED parameters have been proposed in [5]. Most of thesestudies [3] are based on heuristics or simulations, but not
on a strict mathematical analysis. In [2], the RED algorithm
is modelled stochastically, whereas in [10] a Markov based
approach is used to study the optimal tuning of the RED
algorithm.
Most of the aforementioned research has focused on tuning
the RED parameters, namely, the maximum and minimum
thresholds. The average loss rate of a RED queue has notbeen studied in detail. A model of the loss behavior of the
RED algorithm was ﬁrst introduced in [13]. The authors model

the RED queue as a 3 state Markov model. An approximatedclosed-form solution of the Markov model is derived. While
the solution provides satisfactory approximated results, it still
different from the precise values.
In this paper, we improve on the work of [13] by deriving
an exact closed-form solution for a 4-state Markov model of a
RED queue. The Markov model is derived by approximating
an exact queueing model of a RED queue. Introducing a
notion from the theory of random walks, we then derive anexact solution of the Markovian RED model. In particular,
our model allows us to derive the expected loss probabilities
over arbitrary long periods of time. We calculate the average
probability of dropping k out of n packets which allows thedesign of optimal Reed-Solomon codes.
In Section II, we ﬁrst deﬁne an exact queueing model of a
RED queue which we then approximate by a Markov modelof the RED queue. We present a closed form solution of
the Markov model in Section III. We evaluate our results
numerically in Section IV and conclude in Section V.
II. M ODEL AND TERMINOLOGY
We ﬁrst deﬁne an exact queueing system of the RED
algorithm. For the subsequent analysis of the RED algorithm,
we then convert the queueing system into an 4-state Markov
model which approximately describes the dynamics of RED
and which we solve exactly in the following section. Finally,
we present a recursive formula that describes the loss behaviorof the RED algorithm.
A. RED algorithm
The RED algorithm is typically applied to a queue at theoutput of a switch. A packet arriving at the queue is dropped
with probability p calculated based on the average queue
size qt . The average queue size qt is calculated using an
exponential weighted moving average as
qt = (1 − wq )qt−1 + wq q̃t .
Here, qt is the current average queue size, qt−1 is the averagequeue size at the last time instant, wq is the weighting function
deﬁning the exact low-pass ﬁlter, and q̃t is the current instantaneous queue size. qt is then compared to two thresholds,
a minimum threshold qmin and a maximum threshold qmax .
Each arriving packet is dropped with probability p given by
qt < qmin 0,
qt −qmin
p
,
q
≤
q
≤
q
,
(1)
p =
max
min
t
max

 qmax −qmin1,
qmax < qt ,1930-529X/07/$25.00 © 2007 IEEE
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE GLOBECOM 2007 proceedings.

Fig. 1. M/D/1/K approximation of the steady-state behavior of RED under quasi-stationary assumptions. For clarity, only the full set of transitions associatedwith k = qmax are shown.

where pmax ≤ 1.

with π0∞ = 1 − ρ and π1∞ = (1 − ρ)(eρ − 1).

B. Exact queueing model of RED queue

In this paper, we assume the average load ρ to be constant.
In practice, data trafﬁc is often sent using the TCP protocol
which adjusts its sending rate in reaction to the dropping
behavior of the RED queue. We are currently investigating
how our approach could be extended to this scenario.

We consider a queuing system with the capacity of K ﬁxed
size packets operating under the RED queuing discipline. A
ﬁxed packet size can represent an atomic unit of operation
when receiving variable length packets and thus does not
represent a loss of generality. We deﬁne the steady states of thequeue occupancy model as U0 , .., UK . We denote the transition
probabilities as uij , 0 ≤ i, j ≤ K, where some uij = 0.
The RED queuing system is described by its trafﬁc pattern
and is assumed to be operating in its steady-state regime. In[10], the authors develop a model for analyzing both transientand steady-state behavior of RED queues accommodating alarge population of random trafﬁc sources the trafﬁc generation
pattern of which is described by a Poisson arrival processwith a time varying rate. As the result of enforcing RED
packet discarding mechanism with a small averaging factor
of wq in the order of 10−3 and for a slowly varying Poissonparameter, the RED queue is considered to be operating ina quasi-stationary state. As such, the behavior of the queue
can be approximated with M/G/1/K queuing discipline. For
the purpose of our study, we select the M/D/1/K queuing
discipline, as shown in Fig. 1, not only as a special case of
M/G/1/K but as the best practical alternative. For an M/D/1/K
queue with a load factor ρ, we normalize the service time toindicate the time unit such that the arrival intensity is equal toρ. Then, the steady-state probabilities πk of being in state k fork ∈ {1, · · · , K} form a discrete Probability Density Function
the terms of which are calculated as∞πk
if k ∈ {0, · · · , K − 1}
π0∞ +ρG(K) ,
(2)
πk =
G(K)
1 − π∞ +ρG(K) , if k = K0

K−1

where G(K) = k=0 πk∞ . Further, the steady-state probability πk∞ of state k for an inﬁnite capacity M/D/1 queuingsystem with load ρ is identiﬁed in Page 44 of [6] ask−ikπk∞ = (1 − ρ) [ i=1 eρi (−1)k−i (iρ)(k−i)!
(3)
k−i−1
k−1
+ i=1 eρi (−1)k−i (iρ)
k≥2(k−i−1)! ] ,C. 4-state Markov approximation model
We now use the exact queueing model from the previous
section to derive an Markov approximation model for the RED
algorithm. We use the model to derive a closed form solution
for the average probability of dropping k out of n packets.
According to the way p is deﬁned in eqn. (1), we candeﬁne three aggregate states that characterize the behaviorof the RED algorithm. We deﬁne the bad aggregate stateb, the intermediate aggregate state I, and the good aggregate state g, where packets are dropped with probability
qt −qminp = 1, p = qmax
−qmin pmax , and p = 0, respectively.
We divide the integers in the interval [0, K] into three subsets Sg := {1, .., qmin }, SI := {qmin+1 , .., qmax }, Sb =Ui ,{qmax+1 , .., qK }. From Fig. 1, we see that b =
I=

i∈Sb

Ui , g =
i∈SI

Ui .
i∈Sg

We further divide the aggregate state I in two sub-aggregate
states I b and I g where I b denotes the sub-aggregate state of
I where a packet is dropped. Similarly, I g denotes the subaggregate state of I where a packet is not dropped. For further
usage, we set SIb = SIg = SI . For p deﬁned as in eqn. (1)and assuming the RED queue is in aggregate state I, I b occurs
with conditional probability p and I g occurs with conditional
probability 1 − p. We note that whereas for the aggregate state
I the loss probability p of an arriving packet is a randomvariable, for each of the sub-aggregate states I b and I g the loss
behavior is deterministic, i.e., p = 0 and p = 1, respectively.
We now derive the transition probabilities pij , i, j ∈{b, I b , I g , g}, where pij denotes the probability that the RED
queue changes from aggregate state i to aggregate state j upon
the arrival of a packet, from the queueing model given in
Fig. 1. The transition probability pij is the probability that the

1930-529X/07/$25.00 © 2007 IEEE
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE GLOBECOM 2007 proceedings.

system changes from any state Uk in the set Si to any state
Ul in the set in the change Sj . By the deﬁnition of the states
Ib (and Ig ), we see that the probability that state Ui , i ∈ SI ,belongs to Ib is PLOSS (i). For Ig , it is 1 − PLOSS (i). Settingi ∈ {Sb , Sg }, 
 πi ,i ∈ SIb ,πi PLOSS (i),
πi∗ =
(4)


πi (1 − PLOSS (i)), i ∈ SIg ,j ∈ {Sb , Sg },  uij ,
j ∈ SIb ,uij PLOSS (j),(5)
u∗ij =
uij (1 − PLOSS (j)), j ∈ SIg ,we derive
pij =

 
k∈Si l∈Sjk∈Si

P (v + z, v, c) =

,

g

(6)

We see from (4) and (6) that the transition probabilities pij
are a function of the loss probabilities PLOSS (i).
In the sequel of this paper, we will only refer to the four
aggregate states b, I b , I g , g and refer to them simply as states.
We ﬁrst calculate the quantities P (v + z, v, j), j ∈{b, I b , I g , g} which are deﬁned as the probabilities of droppingz out of (v + z) arrived packets and being in state j after the(v + z)-th packet is buffered/dropped by the RED algorithm.
Summing over the loss probabilities of the 4 different states of
the RED queue, we obtain the overall probability P (v + z, v)
to lose z out of (v + z) packets as
P (v + z, v, j).

(7)j∈{b,I b ,I g ,g}We now calculate the loss probabilities P (v + z, v, j) as
functions of the transition probabilities pij and the steadystate probabilities jss , j ∈ {b, I b , I g , g}, where jss is theprobability that the RED queue is in state j.
We describe the dynamics of a RED queue via the following
P Ig Ig

PgI g
Ig

Pgg
g

P Ig Ib

P (v + z − 1, v, d)pdc .

(9)For c ∈ {b, Ib },P (v + z, v, c) =d∈{b,I b ,I g ,g}The loss probabilities for a single packet can be calculated
from the transition and steady state probabilities as follows:
P (1, 0, j)

P (1, 1, j)
P (1, 1, j)=

0, j ∈ {g, I g }

(10)
g
b
+ pbj bss + pI b j Iss(11)= pgj gss + pI g j Iss

P bg

(12)
= 0, j ∈ {b, I b }gbg= pgj gss + pI j Iss + pbj bss + pI b j Iss (13)j ∈ {g, I g }.

Similar to eqn. (8) - (9), one can formulate a system of
equations to calculate the initial steady state probabilities: Forc ∈ {b, I b , I g , g},

D. Recursive deﬁnition of loss probabilities

P (v + z, v) =(8)j ∈ {b, I b },i, j ∈ {b, I , I , g}.
b

P (v − 1 + z, v − 1, d)pdc .
d∈{b,I b ,I g ,g}

P (1, 0, j)

πk∗ u∗kl

πk∗recursive relations. For c ∈ {g, Ig },css=

dss pdc .

(14)d∈{b,I b ,I g ,g}The system of equations (14) can be solved by noting that
only three of the four equations are linearly independent andthat the sum of the four steady state probabilities equals one.
We introduce some further terminology. In order to express
the quantities P (v + z, v, j) as a function of the steady state
probabilities jss , we have to consider all possible scenarios
which lead to z drops out of (v + z) arrived packets and leave
the RED queue in to state j after the (v + z)-th packet has
been buffered/dropped by the RED algorithm. In other words,
we have to look at all random walks of length (v + z + 1)
that start in an initial steady state jss with j ∈ {b, I b , I g , g},that after the buffering/dropping of the t = v + z-th packet
ﬁnishes in state j, and that after the buffering/dropping after
any of the intermediate packets t = 1, .., v + z − 1 are in oneof the four states j ∈ {b, I b , I g , g}. For the calculation of thepacket loss probabilities, we assume that no packet is either
received or gets lost in the initial state jss . The transition
probabilities between the different states at consecutive steps
are the transition probabilities pij , 1 ≤ i, j ≤ 4 deﬁned above.
We further deﬁne a 4 × 4 integer matrix a =(aij )i,j∈{b,I b ,I g ,g} . We deﬁne the functions f i,j (n+1, a) as thenumber of possibilities to construct a random walk of lengthn + 1 that starts in state i, ﬁnishes in state j, and that for eachi, j ∈ {b, I b , I g , g} contains 0 ≤ ai,j ≤ n transitions from4
ai,j = n.
state i to j. We require of course thati,j∈{b,I b ,I g ,g}I

P Ib Ib
Fig. 2.

b

b
PIb b

Pbb

We note that the function f i,j (n + 1, a) can be equal to zero.
For example, if n = 2, i = j = I g , ag,g = 2, and all otherg gai,j = 0, then f I ,I (a) = 0 as it is not possible to constructa random walk of length n that starts and ends at I g , when
only aij = 0 with (i, j) = (g, g).

Four state Markov model of RED algorithm

1930-529X/07/$25.00 © 2007 IEEE
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE GLOBECOM 2007 proceedings.

III. S OLUTION OF THE RED M ARKOV MODELIn eqn. (8) - (9) we have deﬁned a set of recursive equations
that allow us to calculate the quantities P (v + z, v, j). In thissection, we derive closed-form solutions for the P (v +z, v, j).
In particular, we show the following theorem:
Theorem 1: For v + z ≥ 1, c ∈ {b, I b , I g , g}
P (v + z, v, c)=

Dv,z,d,c dss .

(15)

d∈{b,I b ,I g ,g}where for i, j ∈ {b, I b , I g , g} :Dv,z,i,j
v,z,∗

(16)

v,z,∗

v,z,∗

v,z,∗

=

v,z,∗

v,z,∗

....
agg ≥0 agI g ≥0 agb ≥0 agI b ≥0

aI b b ≥0 aI b I b ≥0

a b
a
a
a g a
f i,j (v + z + 1, a)pagggg pgIgIg pgbgb pgIgIb ..pI bIbb b pI bIIb Ibb .

The notationv,z,∗
aij ≥0denotes only summing over such aij thatsatisfy the following conditions:ajb +j∈{b,I b ,I g ,g}

ajI b

= z

(17)

ajI g

= v,

(18)

j∈{b,I b ,I g ,g}ajg +j∈{b,I b ,I g ,g}j∈{b,I b ,I g ,g}where the 4 × 4 matrix a = (aij )i,j∈{b,I b ,I g ,g} is determinedby the values aij over which the terms Dv,z,i,j are summed.
Remark: Closed-form expressions for the functions f i,j (n, a)
are not known. However, the actual values of f i,j (n, a) do notdepend on the transition and steady state probabilities. Thus,
they can be calculated off-line by an exhaustive search.
A. Proof of Theorem 1
In the deﬁnitions of the terms P (v + z, v, j), the quantity
k := v + z expresses the number of packets that have been
received at a RED queue during the observation period. We
prove Theorem 1 by induction over k. This means that for
the inductive step, we assume that the eqn. (15) have beenshown for all pairs v and z that satisfy k = v + z, and under
this assumption show that they also hold for all pairs v and z
satisfying k + 1 = v + z.
Inductive base case k=1: We start with the case v = 0, z = 1.
We ﬁrst consider the term P (1, 0, g). We have to show thatfor j = g eqn. (10) follows from eqn. (15) with c = g. We
see from eqn. (15) with c = g that it is sufﬁcient to showthat D0,1,j,g = 0 for j ∈ {b, I b , I g , g}. Eqn. (18) with v = 0
implies that ajg = 0 for j ∈ {b, I b , I g , g}. However, ajg =0, j ∈ {b, I b , I g , g} implies that f j,g (2, a) = 0 as there is no
possibility to construct a random walk of length 2 that ends at
g if there are no transitions from any state j ∈ {b, I b , I g , g}
to state g. Thus, D0,1,j,g = 0. The same argument shows that
P (1, 0, I g ) is deﬁned correctly by eqn. (15) with c = Ig .
We now consider the term P (1, 0, b). We show that eqn.
(11) follows from eqn. (15) for c = b. We see from (18) withv = 0 that for each D0,1,j,b there is ajg = ajI g = 0 forj ∈ {b, I b , I g , g}. Thus, we are only left with terms ajI b andajb . We note that for a random walk of length 2, for each j
exactly one of the entries ajb or ajI b is not equal to zero. If thisentry is of the type ajI b , then f j,b (2, a) = 0 because a random
walk of length 2 cannot terminate at b if only transitions oftype akI b happen. If the only non-zero entry of matrix a isof type ajb , there is exactly one possibility of constructing arandom walk of length 2 that begins at j and ends at b, i.e.,
f j,b (2, a) = 1. Summarizing the ﬁndings of this paragraph, we
see that eqn. (11) follows from eqn. (15) with c = b. We canshow in the same way that the quantity P (1, 0, I b ) is deﬁned
correctly by eqn. (15) with c = Ib .
Second, we consider the case v = 1 and z = 0. We showthat for j = b (and j = I b ) eqn. (12) follows from eqn. (15)with c = b (c = Ib ). We argue similarly as above to showbthat f j,b (2, a) and f j,I (2, a) are equal to zero. In particular,
we show that eqn. (17) with z = 0 implies f j,b (2, a) = 0b(and f j,I (2, a) = 0). Next, we consider the term P (1, 1, g).
We have to show that eqn. (13) follows from eqn. (15) withc = g.. We see from eqn. (17) for z = 0 that all ajb =ajI b = 0. Arguing as above, we see that for each j exactly
one of the two entries ajg or ajI g is not equal to zero. We
further follow the argument above to show that in the ﬁrst
case f j,g (2, a) = 1 and in the second case f j,g (2, a) = 0,.
The expression P (1, 1, I g ) is treated in the same way.
Inductive step from k to k+1: We now show that if the eqns.
(15) are true for all pairs v and z satisfying k = v + z, thenthey are also true for all pairs v and z satisfying k +1 = v +z.
We ﬁrst consider the quantity P (v + z, v, g). By the inductive
assumption, we see that on the right hand side of eqn. (8)with c = g, we have k = v − 1 + z. Thus, we can apply the
inductive assumption to the right hand side of eqn. (8) withc = g. We insert the eqn. (15) in both sides of eqn. (8) withc = g. We have to show that for c ∈ {b, I b , I g , g}, there is
Dv,z,c,g=

Dv−1,z,c,d pdg .

(19)d∈{b,I b ,I g ,g}In order to show eqn. (19) with c = g, we proceed in 2 steps:
1) Dv,z,i,j is deﬁned in eqn. (16) via a multiple summation
over the terms aij . Each of the speciﬁc sixteen tuples
ai,j , i, j ∈ {b, I b , I g , g} occurring in the multiple summation deﬁnes a matrix a. We show that a matrix aappears on the left hand side of eqn. (19) with c = g,i.e., in the summation deﬁning Dv,z,g,g , if and only if
it also appears on the right hand side of eqn. (19) withc = g, i.e., for at least one of the terms Dv−1,z,g,g pgg ,gb
Dv−1,z,g,I pI g g , Dv−1,z,g,b pbg , or Dv−1,z,g,I pI b g it ispart of the summation deﬁning the term.
2) For a ﬁxed matrix a appearing on both sides of eqn. (19)with c = g, we show that the sum of the terms f i,j (·, ·)which are counted when a appears in the summationdef. a term D or Dp is equal on both sides of the eqn.
The relation (19) with c = g then follows from both claims.
In order to show the ﬁrst claim, we distinguish two cases.
In the ﬁrst case Dv,z,g,g = 0. The deﬁnition (16) of Dv,z,g,g

1930-529X/07/$25.00 © 2007 IEEE
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE GLOBECOM 2007 proceedings.

f i,j (k + 1, a)=f i,l (k, a − Jl,j ).
l∈{b,I b ,I g ,g}, al,j >0

For c = g, the eqn. (19) is shown in the same way as forc = g. The inductive steps for eqn. (15) with c = g are shownin the same way as for c = g. 
IV. N UMERICAL RESULTS
In this section, we numerically evaluate the performanceof the RED algorithm using Theorem 1. As an input fora numerical evaluation, we require values for the transition
probabilities pij as deﬁned in sec. II. In [13], a methodology toderive these values from actual simulations has been described.
We have used the methodology proposed in [13] and havederived the transition probabilities given in Table I. Using
these values, we calculate the values of P (v + z, v) as deﬁned
in eqn. (7). The results are shown in Fig.3.
We have calculated the values P (v + z, v) using eqn. (7).
The values P (v + z, v, j) can be obtained using either therecursive eqn. (8) - (9) or via the closed-form expressions ofTheorem 1. As Theorem 1 provides an exact solution for thequantities P (v +z, v, j), we expect that both ways to calculate
P (v+z, v, j) give identical results. Our numerical experiments
conﬁrm this expectation. This improves over the previous
work in [13] where one could observe numerical differences
between the recursive and the closed-form solutions.

TABLE IT RANSITION PROBABILITIES
b
Ib
g
Ig
0.16

b
0.6
0.3
0
0.1

Ib
0.3
0.4
0.1
0.2

8

10

g
0.0
0.1
0.36
0.2

Ig
0.1
0.2
0.54
0.5

0.14

0.12

v=2

0.1
P(v+z,v)

implies that f g,g (·, ·) = 0 for all terms f g,g (·, ·) appearing
in the deﬁnition of Dv,z,g,g . In other words, there exists no
possible random walk of length (v + z + 1) starting andterminating in state g. This implies that there exists no random
walk of length (v + z) starting in state g and terminating inany state j. Otherwise, one could construct a random walk oflength (v + z + 1) starting and terminating in g by taking arandom walk of length (v + z) that starts in g and terminatesin j and adding an additional transition from j to g. Thus, theterms f ·,· (·, ·) appearing in the deﬁnitions of the terms D on
the right hand side are all equal to zero. This proves eqn. (19)with c = g when Dv,z,g,g = 0.
In the second case, in the deﬁnition of Dv,z,g,g we sum over at
least one matrix a such that f g,g (v + z + 1, a) = 0. For such amatrix a, the deﬁnition of f g,g (v + z + 1, a) implies that there
are u, 1 ≤ u ≤ 4 states ji , with 1 ≤ i ≤ u, ji ∈ {b, I b , I g , g}such that aji g = 0.
We now deﬁne a 4×4 matrix Jij as the matrix with the (i, j)
entry equal to 1 and all other entries equal to 0. We deﬁnea − Jij as the matrix obtained by the per-entry subtraction of
the matrix entries. For any matrix a with f g,g (v+z +1, a) = 0
and ji such that aji g = 0, one can easily verify that the matrix
a − Jji g appears in the summation (16) deﬁning Dv−1,z,g,ji .
Multiplying Dv−1,z,g,ji by pji g on the right hand side ofeqn. (19) with c = g changes the matrix a − Jji g to a. In
consequence, each matrix a appearing on the left-hand side ofeqn. (19) with c = g also appears on the right-hand side forthe terms Dv−1,z,g,ji when aji g = 0. The inverse statement
follows in the same way. Thus, the second claim follows from
Lemma 1 the proof of which we omit for space reasons:Lemma 1: For k ≥ 1,

0.08

0.06

0.04

v=20

0.02

0

2

4

6

Fig. 3.

12

14

16

18

20

z

P (v + z, v) for v ∈ [2, 20]

V. C ONCLUSIONSIn this paper, we develop an exact queueing model of the
RED algorithm which we convert into a four state Markov
model. We use the Markov model to describe the loss characteristics of a RED queue. We derive an exact closed-form
solution of the Markov model. We show via simulations thatthe closed-form solution matches exactly with a recursive
description of the loss process.
R EFERENCES[1] S. Athuraliya, V. H. Li, S.H. Low, Qinghe Yin, “ REM: Active Queue
Management,” IEEE Network, May 2001.
[2] H.M. Alazemi, A. Mokhtar, M. Azizoglu, “Stochastic Approach forModeling Random Early Detection Gateways in TCP/IP Networks,” In
Peoc. IEEE ICC, 2001.
[3] T. Bonald, M. May, J. Bolot, “Analytic Evaluation of RED Performance,”
In Proc. IEEE INFOCOM, 2000.
[4] R. Braden et al., “Recommendations on Queue Management and Congestion Avoidance in the Internet,” IETF RFC 2309.
[5] S. Floyd, V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance,” IEEE/ACM Trans. Networking, August 1993.
[6] E. Gelenbe, G. Pujolle, “Introduction to Queueing Networks,” John
Wiley & Sons, Inc., ISBN 0-471-96294-5, 1998.
[7] V. Jacobson, “Presentations to the IETF Performance and Congestion
Control Working Group,” August 1989.
[8] S. Kunniyur and R. Srikant, “Analysis and Design of An Adaptive
Virtual Queue (AVQ) Algorithm for Active Queue Management, In Proc.
ACM SIGCOMM, 2001.
[9] P. Lassila, J. Virtamo, “Modeling the Dynamics of the RED Algorithm,”
In Proc. ACM Quality of Future Internet Services (QofIS), 2000.
[10] P. Kuusela, P. Lassila, J. Virtamo, P. Key, “Modeling RED with Idealized
TCP Sources,” In Proc. IFIP Performance Modeling and Evaluation of
ATM & IP Networks, 2001.
[11] A. Romanov, S. Floyd, “Dynamics of TCP Trafﬁc over ATM networks,”
In Proc. ACM SIGGCOMM, 1994.
[12] H. Sanneck, G. Carli, R. Koodli, “A Framework Model for Packet
Loss Metrics Based on Loss Runlengths,” In Proc. SPIE/ACM SIGMM
Mulitmedia Computing and Networking, 2000.
[13] M.B. Singh, H. Youseﬁ’zadeh, H. Jafarkhani, “A Finite State Markov
Chain Model for Statistical Loss across A RED Queue,” In Proc.
IEEE/IARIA ICHSN, 2005.

1930-529X/07/$25.00 © 2007 IEEE
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE GLOBECOM 2007 proceedings.