This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2008 proceedings.

Optimal Statistical Tuning of the RED Parameters
Homayoun Youseﬁ’zadeh
Amir Habibi
Hamid Jafarkhani
Department of EECSUniversity of California, Irvine[hyousefi,ahabibi1,hamidj]@uci.edu

Abstract— Achieving minimal loss while satisfying an acceptable delay proﬁle remains to be an open problem under the RED
queuing discipline. In this paper, we present a framework targeted
at optimal ﬁne tuning of the RED parameters in order to address
such problem. For a given trafﬁc pattern and utilizing a statistical analysis of ﬁnite-state Markov chains, we formulate an optimization problem aimed at addressing the loss and delay tradeoffof the RED queuing discipline. Our two-step iterative solution to
the problem identiﬁes the optimal settings of the RED parameters.
We prove the convergence of our solution and investigate its low
complexity characteristics. We apply our framework to a number of generic queuing and TCP scenarios in order to capture loss
and delay performance of our algorithms versus buffer capacity
and service rate. Based on our results, we argue that our modelis capable of optimally addressing the loss-delay tradeoff of RED
queues accommodating time-varying trafﬁc proﬁles.
Index Terms— RED, Markov Chain, Optimal Parameter Fine
Tuning, Packet Loss, Queuing Delay.

Claus Bauer
Dolby Laboratories
San Francisco, CA
cb@dolby.com

This paper is structured as follows. In Section II, we discuss RED preliminaries. In Section III, we formulate and solve
our optimization problem. We consider two cases associatedwith instantaneous and average queue sizes observed in a RED
queue. Section IV provides our simulation results applied toboth generic queuing and TCP scenarios. Finally, Section V
concludes this paper.
II. RED P RELIMINARIESIn this section, we describe the RED algorithm and its associated queuing models in conjunction with the arriving trafﬁc
proﬁle of the queue. Our objective is to identify the steady-state
distribution probability of the occupancy of a given buffer the
behavior of which is governed by RED.
A. The RED Algorithm

I. I NTRODUCTION
In the past years, Active Queue Management (AQM)
schemes [5] have been proposed as key schemes to prevent
excessive loss of Internet trafﬁc. Random Early Drop (RED)[11] and Random Early Marking (REM) [15] are arguably themost widely studied AQM schemes. While both schemes follow the same concept of operation pertaining to early detectionof a congestion phenomenon, RED relies on intermediate nodes
to react to a congestion phenomenon rather than the end nodes
utilized by REM.
Although random early detection schemes can potentiallyoutperform traditional drop-tail schemes, it is often difﬁcult
to parameterize random early detection queues under different
congestion scenarios. In addition, there is a need for constantﬁne tuning of parameters to adapt to current network conditions. To that end and based on simpliﬁed models, guidelines
have been proposed in [7], [6], [21] for setting RED parameters. However, most studies on RED are based on heuristics or
simulations rather than a systematic approach. Of the literaturearticles, the authors of [2] and [9] have modeled RED stochastically, while those of [14], [20], and [19] have used a Markovian
model to study RED.
In this paper, we perform a systematic study on the optimal
ﬁne tuning of RED parameters. The parameters of interest include the two thresholds, the probability of drop in the intermediate regime, and the instantaneous queue weighting function.
Given the statistical properties of the arrival pattern of a RED
queue, our objective is to minimize its loss characteristic whilesatisfying an acceptable delay proﬁle. The formulation of ourproblem appears in the form of a constraint optimization problem that can be efﬁciently solved in two iterative steps.

The average queue size of a RED queue is calculated using a
low-pass ﬁlter with an exponential weighted moving average as
qt = (1 − wq ) qt−1 + wq q̃t(1)

where qt is the current average queue size, qt−1 is the averagequeue size at the last time instant, wq is the weighting function, and q˜t is the current instantaneous queue size. qt is thencompared to two thresholds, a minimum threshold qmin anda maximum threshold qmax . Each arriving packet is dropped
with probability p given byif
qt < qmin
 0,q−qmin

=
p
,
if
q
p=
i
min ≤ qt < qmax
qmax −qmin max
1,if
qt ≥ qmax(2)
While in our study p is varied linearly from 0 to pmax in the region between qmin and qmax , there are many other possibilities
of choosing this drop probability. Examples include choosing
p as a nonlinear convex, or nonlinear concave function of thequeue size.
B. Trafﬁc Proﬁling
We consider a queuing system with the capacity of K ﬁxed
size packets operating under the RED queuing discipline. We
note that 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. The RED queuing system is
described by its trafﬁc pattern and is assumed to be operating in
its steady-state regime. In [12] and [13], the authors develop amodel for analyzing both transient and steady-state behavior of978-1-4244-2075-9/08/$25.00 ©2008 IEEE

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2008 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.

RED queues accommodating a large population of random trafﬁc sources the trafﬁc generation pattern of which is describedby a Poisson arrival process with a time varying rate. As theresult of enforcing RED packet discarding mechanism with asmall averaging factor of wq in the order of 10−3 and for a
slowly varying Poisson parameter, the RED queue is considered
to be operating in a 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 not only as a special case of M/G/1/K but
as the best practical alternative considering the fact that today’s
Internet network buffers provide a ﬁxed deterministic service
rate. Fig. 1 shows such queuing system.
For an M/D/1/K queue with a load factor ρ, we normalize
the service time to indicate the time unit such that the arrival
intensity is equal to ρ. Then, the steady-state probabilities πk ofbeing in state k for k ∈ {1, · · · , K} form a discrete Probability
Density Function (PDF) the terms of which are calculated as∞πk
if k ∈ {0, · · · , K − 1}
π0∞ +ρG(K) ,
(3)
π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 queuing systemwith load ρ is identiﬁed in Page 44 of [8] as
πk∞

k−i
k
= (1 − ρ) [ i=1 eρi (−1)k−i (iρ)(k−i)!
k−i−1
k−1+ i=1 eρi (−1)k−i (iρ)
k≥2(k−i−1)! ] ,(4)

with π0∞ = 1 − ρ and π1∞ = (1 − ρ)(eρ − 1). We note that
depending on the choice of ρ, the numerical evaluation of theexpression of (4) faces stability issues for the values of k larger
than 12. In such cases, the asymptotic approximation of Equation (15.1.4) of [17] can be used to identify the steady-state
probabilities as(5)πk∞ ≈ C0 er0 (k−1) − er0 k
where r0 is the unique negative zero of the equation r = ρ(1 −1−ρ.
e−r ) and C0 = ρe−r
0 −1
We note that a similar approach can be applied to the case ofan M/G/1/K, or G/G/1/K queue.

III. O PTIMAL F INE T UNING OF THE RED PARAMETERS
For the discussion of this section, we focus on ﬁne tuningof the RED parameters namely qmin , qmax , pmax , and wq for
a given trafﬁc pattern. We work with ﬁxed size packets andassume a deterministic service time of one packet per unit time.
A. The Case of Instantaneous Queue Size
In this section, we establish a foundation for our optimization problem by focusing on the case of instantaneous queuesize, i.e., wq = 1. From the discussion of the previous section
and given ρ, one can determine the steady-state probabilities πkof being in state k where k ∈ {1, · · · , K}. Given such probabilities, the probability of loss for an arriving packet at a RED
queue is expressed as
PLOSS =

q
max

πk

k=qmin +1

k − qminpmax +
qmax − qminKπk (6)

k=qmax +1

Note that Equation (6) represents a statistical average in which
the probability of loss in each state is calculated based on thequeue occupancy in comparison with the RED thresholds. In
the presence of a FIFO service discipline utilized by M/D/1/K
queuing discipline, the statistical queuing delay of a packet arriving at a RED queue is calculated asqmin
πk (k + 1)
PDELAY =k=0
qmax
k−qmin+k=qmin +1 πk (k + 1)(1 − qmax −qmin pmax )(7)
Once more, we note that Equation (7) represents a statistical
average in which the delay in each state is calculated based on
the queue occupancy and the probability of drop in comparison
with the RED thresholds. Utilizing Equation (6) and (7), we can
now formulate a primal constrained optimization problem that
attempts at minimizing the probability of packet loss subject
to an upper bound Dmax on its statistical queuing delay. As adual problem, we can also attempt at minimizing the statisticalqueuing delay of a packet subject to an upper bound on its loss
probability.
In what follows we focus on the primal problem. The primal
optimization problem is formulated asminqmin ,qmax ,pmax

PLOSS

(8)

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2008 proceedings.

PDELAY ≤ Dmax
0 ≤ qmin < qmax ≤ K
0 ≤ pmax ≤ 1

Subject To:

(9)
(10)
(11)

Since qmin , qmax , and pmax appear as decision variables of the
optimization problem, solving the problem yields their optimalvalues.
Generally speaking, the problem above is categorized under NonLinear Integer Programming (NLIP) problems. Since
the decision variables appear in the boundary of summations
as well as within the expressions, solving the problem is notstraightforward. In speciﬁc, applying standard numerical optimization approaches such as Sequential Quadratic Programming (SQP) method in conjunction with line search algorithms
introduce both convergence and complexity issues. In addition,utilizing Dynamic Programming (DP) to jointly solve for thethree decision variables yields high space- and time-complexity
results. In order to efﬁciently solve the problem, we describe a
two-step iterative solution to the problem formulated above andprove that our solution is guaranteed to converge to a local minimum.
In the ﬁrst step, we analytically solve for the optimal valuep∗max assuming qmin and qmax are ﬁxed and given.
Step 1: In the ﬁrst step, we work with ﬁxed thresholds qmin andqmax . Thus, the only decision variable in solving the optimization problem is pmax . While the cost function is minimized forthe smallest value of pmax , the constraint function (9) enforces
a lower bound on the value of pmax . The optimal value of pmax
is then calculated at the boundary point of the constraint function (9) asqmin
πk (k + 1)
Dmax =
k=0
qmax
k−qmin∗+k=qmin +1 πk (k + 1)(1 − qmax −qmin pmax )(12)
The solution to the equation above appears asqmax
πk (k+1)−Dmax
k=0(qmax − qmin )p∗max = qmax
π (k+1)(k−q)
k=qmin +1

k

min

(13)
Note that the operation associated with deriving the value ofp∗max from Equation (13) has a time complexity in the orderof O(K). Further, the value of p∗max satisﬁes the constraintfunction (11).
In the second step, we provide a reduced order search strat∗∗
and qmax
based on aegy in order to identify the values of qmin
ﬁxed value of pmax given in the ﬁrst step.
Step 2: In the second step, we work with a ﬁxed value pmax
obtained by the solution of step 1. Thus, the decision variables
in solving the optimization problem are qmin and qmax . Considering the fact that qmin and qmax are integer values whenworking with the instantaneous queue size and paying attention
to the constraint function (10), we propose performing an intelligent search algorithm in the 2D space of (qmin , qmax ). Fig.
points in the
2 sketches the feasible region containing K(K+1)
2
2D space of (qmin , qmax ). Hence, the search algorithm has toevaluate the values of the cost function (8) and the constraint
points to identify thefunction (9) with a ﬁxed pmax at K(K+1)
2∗∗, qmax). Therefore, the time complexity
optimal values (qminof the search algorithm is in the order of O(K 3 ).

Fig. 2. The feasible region of (qmin , qmax ) in their 2D space.

Considering the staging approach of our solution, one canreach the optimal solution by iteratively applying the resultof the second step to the ﬁrst step and vice versa. Thus, we
propose the following algorithm to solve the constraint NLIP
problem identiﬁed by the cost function (8) and constraintfunctions (9), (10), and (11).
Iterative Optimization Algorithm• Step 1: Start from an initial assignment of thresholds(qmin , qmax ) by uniformly splitting the buffer space between them, i.e., qmin = K/3 and qmax = 2K/3. In
addition, set the initial iteration number it = 0, the maximum number of iterations itmax = 106 , and stoppage
criterion variables L1 = 0, L2 = 1, δ = 10−6 .
• Step 2: Calculate the optimal value of pmax from Equation
(13).
∗
∗
• Step 3: Identify the optimal values of qmin and qmax asfollows:
Reset the intermediate variable L3 to the value 1.
f or (qmax = 1 to K) {f or (qmin = 0 to qmax − 1) {– If the constraint function (9) is satisﬁed, calculate thevalue of the cost function (8) and store it in the intermediate variable L4 .
∗∗← qmin , qmax
← qmax , and– If L3 > L4 , then qmin
L3 ← L4 .
} /* f or (qmin = 0 to qmax − 1) */} /* f or (qmax = 1 to K) */|L1 −L2 |• Step 4: Set L1 ← L2 and L2 ← L3 . If
< δ orL1
it > itmax STOP.
• Step 5: Go back to Step 2.
We note that the time complexity of implementing the above
algorithm is O(IK 3 ) where I indicates the number of iterations.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2008 proceedings.

Theorem 1: The two-step iterative optimization algorithm
given in this section with decision variables pmax , qmin , qmax
converges to a local minimum.
The theorem is a special case of Theorem 2.
B. The Case of Average Queue Size
In this subsection, we generalize the formulation of the previous section to the case of average queue size.
We open our discussion by indicating that our objective is
to ﬁrst express the current average queue size qt in terms ofthe current instantaneous queue size q̃t . The latter is equivalent
to providing the solution to the ﬁrst-order difference equation
expressed by (1) with input q̃t and output qt . Relying on themethod of successive calculations and starting from the initialcondition q0 , the following pattern is observed.
t

qt = (1 − wq )t q0 +wq (1 − wq )t−k q̃k

(14)

k=1

Since the equation has a unique solution, it is sufﬁcient to verify
that Equation (14) satisﬁes the original equation. Relying on
induction, we start from Equation (1) to note thatqt==

(1 − wq )qt−1 + wq q˜t(1 − wq )((1 − wq )t−1 q0
+

t−1


t−k−1

wq (1 − wq )

(15)

=
=

(1 − wq )t q0 +(1 − wq )t q0 +

k=1
t


q̃k ) + wq q˜twq (1 − wq )t−k q̃k + wq q˜twq (1 − wq )t−k q̃kk=1

arriving at the right hand side of Equation (14).
Analyzing the solution (14), we notice that it consists of atransient and a steady-state term. Considering the fact that 0 ≤1 − wq ≤ 1, the transient term (1 − wq )t q0 goes to zero insteady-state. The steady-state solution is thus expressed as
qt =

t


Note that the impact of working with the average queue size on
the optimization problem is that the steady-state probabilities
appearing in the cost and constraint functions are now depending on the RED parameter wq representing a new decision variable of the optimization problem. While one can still utilize thetwo-step recursive optimization approach to solve the resulting
problem, the closed-form expression identiﬁed for p∗max in theﬁrst step does not hold any longer. Rather, a numerical optimization approach such as Sequential Quadratic Programming(SQP) [3] should be used in conjunction with a line search algorithm such as the one proposed by [18] to calculate the valuesp∗max and wq∗ in the ﬁrst step.
SQP relies on the Lagrangian theory to convert an optimization problem in its standard form to one without constraints.
We deﬁne the Lagrangian function of the original problem of
the ﬁrst step as
L

k=1
t−1


of qt only depends on a small number of random variables qt ,qt−1 , qt−2 , and so on considering the fact that scaling factor
1 − wq is smaller than one.
Once the PDF of qt is calculated, we can revert back to theconstrained optimization problem with the cost function (8) andconstraint set (9), (10), and (11). In the latter case, a new constraint related to the variable wq is added to the constraint set
as(17)
0 ≤ wq ≤ 1

wq (1 − wq )t−k q̃k

(16)

k=1

Our numerical evaluations have supported the observation thatthe set of discrete random variables {q̃k }tk=1 are Independently
and Identically Distributed (IID) in the steady-state1 . Recall
that the distribution of discrete random variables {q̃k }tk=1 canbe determined from the trafﬁc and queuing proﬁle. Relying on
the IID assumption, the steady-state PDF of the random variable qt appearing in the form of a weighted sum of t randomvariables {q̃k }ti=k can be numerically calculated as a scaled discrete convolution of a number of PDFs, [16]. Further, the PDF
1 Note that the IID assumption does not lead to the loss of generality as we
utilize it to reduce the complexity of numerically calculating the resulting PDF
of qt . The PDF of qt can be numerically calculated even in the absence of the
IID property albeit with a higher complexity.

=

PLOSS + λ1 (PDELAY − Dmax )+ λ2 (pmax − 1) + λ3 (wq − 1)(18)

where the parameters λ1 , λ2 , and λ3 are the Lagrange multipliers. Having deﬁned the Lagrangian function of the ﬁrst step,
the necessary conditions for optimality are represented by the
Karush-Kuhn-Tucker (KKT) conditions described below.
∇L(p∗max , wq∗ ) = 0∗
λ∗1 ((PDELAY− Dmax )) = 0∗ ∗λ2 (pmax − 1) = 0
λ∗3 (wq∗ − 1) = 0

(19)

∂L ∂L
where ∇L = [ ∂p∂L
, ∂L , ∂λ,] and the coefﬁcients λ1 ∗ ,max ∂wq
1 ∂λ2
λ2 ∗ , λ3 ∗ are Lagrange multipliers at the local optimum. Positive multipliers indicate active constraints. We now generalize
Theorem 1 to express:

Theorem 2:
The two-step iterative optimization algorithm given in this section with decision variables
pmax , wq , qmin , qmax converges to a local minimum.
The proof of the theorem is similar to that of Theorem
3.1 of [22]. It is skipped here due to shortage of space.
Next, we investigate potential implications of utilizing average queue lengths rather than instantaneous queue lengths on
the second step of our proposed algorithm. In the latter scenario, we note that the search of the second step has to be∗
performed over a continuous K × K space to identify qmin∗
and qmax . In order to perform the search over the feasible
region of the K × K space, a quantized grid covering thetriangle with edges at coordinates (0, 0), (K, 0), and (K, K)

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2008 proceedings.

IV. S IMULATION R ESULTS
In this section, we validate the performance of our optimal RED algorithm via NS2 [1] simulations. The topology of
our experiments includes a single server queue the behavior ofwhich is governed by RED. We experiment with ﬁxed length
data packets of size 1024 bytes and in the case of utilizing TCP
ﬂows ACKnowledgment (ACK) packets of size 40 bytes. In our
experiments, all of the values of qmin , qmax , and K are normalized and expressed as multiples of a size of a data packet. The
RED queue is fed with UDP Poisson arrival patterns, FTP arrival patterns utilizing TCP Reno, and HTTP arrival patterns
utilizing TCP Reno. The queue is assumed to offer a normalized service rate of one packet per second. The latter allows us
to examine the performance of our optimal algorithm under the
M/D/1/K queuing model as well as TCP trafﬁc patterns mapped
to G/G/1/K queuing models.
Viewing the queue capacity K and the maximum delay
threshold Dmax as our design parameters, our experiments spanover two sets. In the ﬁrst set of experiments, we investigate theloss performance of our proposed solution for a ﬁxed Dmax andvarying queue sizes. In the second set of experiments, we investigate the loss performance of our proposed solution for a ﬁxed
K and varying delay thresholds. We compare the performanceof our solution with that of standard RED. We note that the parameters of standard RED are selected from the default settingsof NS2 representing the best heuristic and numerical ﬁndingsin the literature. Thus, the parameters of standard RED are set
at qmin = 5, qmax = 15, and pmax = 0.1. For the case of
average queue size, standard RED uses wq = 0.002.
In the discussion and ﬁgures below, our optimal RED andstandard RED algorithm are referred to as ORED and SRED,
respectively. Fig. 3 illustrates the comparison results of ORED
with those of SRED for the case of instantaneous queue size
utilizing three different choices of load factor ρ associated witha Poisson arrival pattern. As observed from the ﬁgure, the loss
performance of ORED is by far better than that of SRED for all
three choices of ρ.

9

ORED 84%8

Loss (%)

is formed. Therefore, the complexity of the search is muchhigher depending on the granularity of the quantization grid.
The time complexity of implementing the above algorithm is2
I max(O(K K
G  , N log N ) where I, G, and N indicate thenumber of iterations, the grid size, and the degree of quadratic
estimation identiﬁed by SQP method, respectively.
With a large grid size and when wq is ﬁxed, e.g., wq = 0.002,
the complexity of the problem is reduced to that instantaneousqueue size.
At the end of this section, the following remarks are in order. First, the dual problem of our optimization problem forboth cases of instantaneous and average queue size is obtainedby swapping the cost function (8) with the constraint function(9). The dual problem can then be solved relying on a similar
two-step iterative approach described in this section. Second,
it is important to emphasize on the fact the derivation of our
optimization results is independent of the trafﬁc proﬁle model
as discussed in the Section II-B. In fact, optimization results
are valid for as long as the steady-state probabilities of being ineach state can be identiﬁed either analytically or numerically.

SRED 84%

7

ORED 92%

6

SRED 92%

5

ORED 99%
SRED 99%

4
3
2
1
0
20

100

200
300
Queue Size (K)

400

500

Fig. 3. A performance comparison of ORED and SRED for a ﬁxed normalized
service rate of one packet per second, Dmax = 100msec, and a Poisson arrival
pattern with load factors ρ ∈ {88%, 96%, 99%}. The case of instantaneousqueue size with wq = 1 is considered.

Next, we investigate the performance of our scheme in conjunction with TCP trafﬁc where the sources adjust their transmission rate according to the received ACK packets. We notethat in the experiments with TCP trafﬁc sources, we numerically generate the PDF of qt as opposed to utilizing the discussion of Section II-B. Starting with pre-determined values of
SRED parameters and adjusting RED parameters as an experiment progresses, our approach works by counting the frequencyof queue occupancy as a million packet moving average. Fig. 4
illustrates the results of feeding the queue with FTP and HTTP
trafﬁc patterns for the case of average queue size. The three
curves in each ﬁgure are associated with an aggregate trafﬁcpattern generated by 1, 10, and 100 sources. As observed fromthe ﬁgures, ORED is still by far outperforming SRED.
In the second set of experiments, the queue size is ﬁxed. Fig.
5 illustrates the loss performance of ORED as a function of delay threshold for four different values of K. The trafﬁc patterngenerated by 10 FTP sources. The curves show that increasing
the value of Dmax will result in reducing the loss by servicing
more packets staying in the queue for a longer period of time.
The results of SRED are not shown for clarity but exhibit
similar patterns. We have observed that each curve of SRED
is always above the curve of ORED for the same choice of K.
While not shown here due to space shortage, our experiments inthe case of average queue size and in a broad range of parameterselections have led to observing results consistent with thosereported here.
Considering the relatively low complexity of our algorithms
associated with an average value of I = 10 for Poisson experiments and I = 25 for TCP experiments2 , we argue that
applying our technique to identify optimal settings of RED parameters is highly desired.
V. C ONCLUSIONSIn this paper, we presented optimal algorithms for the ﬁnetuning of the parameters of the RED queuing discipline. Our
2 We note that the increased number of iterations in the case of utilizing TCP
sources is related to applying the moving averaging technique for identifying
the PDF of qt .

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC 2008 proceedings.

8

SRED 100

7

SRED 10

6

SRED 1
ORED 100

Loss (%)

5

ORED 10
4

ORED 1

3
2
1
0
20

100

200
300
Queue Size (K)

400

500

approach spanned over two scenarios working with instantaneous and average queue sizes. For a given trafﬁc pattern andutilizing a statistical analysis approach based on a ﬁnite-state
Markov chain, we formulated and efﬁciently solved an optimization problem aimed at addressing the loss and delay tradeoff of a RED queue. Relying on an iterative two-step approach,
our solution to the problem identiﬁed the optimal settings of
the RED parameters. We proved the convergence of our algorithms and investigated their low complexity characteristics.
We applied our algorithms to a variety of scenarios, including
generic queuing and TCP scenarios, in order to capture theirloss and delay performance versus buffer capacity and service
rate. Based on our results, we argued that our model is capableof optimally addressing the loss-delay tradeoff of RED queues
accommodating time-varying trafﬁc proﬁles.

(a)

6

SRED 100
SRED 10

5

SRED 1
ORED 100

Loss (%)

4

ORED 10
3

ORED 1

2
1
0
20

100

200
300
Queue Size (K)

400

500

(b)
Fig. 4. A performance comparison of ORED and SRED for aggregate trafﬁc patterns generated by (a) {1, 10, 100} FTP, and (b) {1, 10, 100} HTTP
sources. A ﬁxed normalized service rate of one packet per second, Dmax =100msec, and the case of average queue size is considered.

2.5
ORED 50
2

ORED 100
ORED 200

Loss %

1.5

ORED 500

1

0.5
0
0.01

0.02

0.03

0.04

0.05

0.06

0.07

0.08

0.09

0.1

Dmax

Fig. 5. A performance comparison of ORED as a function of Dmax for four
different choices of queue size K ∈ {50, 100, 200, 500} with an aggregate
trafﬁc pattern of 10 FTP sources. The case of instantaneous queue size with
wq = 1 is considered.

R EFERENCES[1] -,“The
Network
Simulator
NS2,”
Availableat
http://www.isi.edu/nsnam/ns/.
[2] H.M. Alazemi, A. Mokhtar, M. Azizoglu, “Stochastic Approach for Modeling Random Early Detection Gateways in TCP/IP Networks,” In Proc.
IEEE ICC, 2001.
[3] D.P. Bertsekas, “Nonlinear Programming, 2nd Edition,” Athena Scientiﬁc
Publishing, 1999.
[4] T. Bonald, M. May, J. Bolot, “Analytic Evaluation of RED Performance,”
In Proc. IEEE INFOCOM, 2000.
[5] R. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S.
Floyd, V. Jacobson, G. Minshall, C. Petridge, L. Peterson, K. Ramakrishnan, S. Shankar, J. Wroclawski, L. Zhang, “Recommendations on Queue
Management and Congestion Avoidance in the Internet,” Internet Draft,
March 1997.
[6] V. Firoiu, M. Borden, “A Study of Active Queue Management for Congestion Control,” In Proc. IEEE INFOCOM, 2000.
[7] S. Floyd, V. Jacobson, “Random Early Detection Gateways for Congestion
Avoidance,” IEEE/ACM Trans. Networking, August 1993.
[8] E. Gelenbe, G. Pujolle, “Introduction to Queueing Networks,” John Wiley& Sons, Inc., ISBN 0-471-96294-5, 1998.
[9] L. Guan, I.U. Awan, M. E. Woodward, “Stochastic Modeling of Random
Early Detection Based Congestion Control Mechanism for Bursty and Correlated Trafﬁc,” In Proc. IEE Software 151, October 2004.
[10] C.V. Hollot, V. Misra, D. Towsley, W. Gong, “Analysis and Design ofControllers for AQM Routers Supporting TCP Flows,” IEEE Trans. Automatic Control, June 2002.
[11] V. Jacobson, “Presentations to the IETF Performance and Congestion
Control Working Group,” August 1989.
[12] P. Lassila, J. Virtamo, “Modeling the Dynamics of the RED Algorithm,”
In Proc. ACM Quality of Future Internet Services (QoFIS), 2000.
[13] P. Kuusela, P. Lassila, J. Virtamo, P. Key, “Modeling RED with Idealized TCP Sources,” In Proc. IFIP Performance Modeling and Evaluationof ATM & IP Networks, 2001.
[14] R. Laalaoua, T. Czachorski, “Markovian Model of RED Mechanism,” In
Proc. CCGRID, 2001.
[15] S.H. Low , D.E. Lapsley, “Optimization Flow Control I: Basic Algorithm
and Convergence,” IEEE/ACM Trans. Networking, December 1999.
[16] A. Papoulis, S.U. Pillai, “Probability, Random Variables, and Stochastic
Processes,” Fourth Edition,. McGraw-Hill, 2002.
[17] J. Roberto, U. Mocci, J. Virtamo, “Broadband Network Trafﬁc,” Final
Report of Action COST 242, Springer Verlag, ISBN 3-540-61815-5, 1996.
[18] D.F. Shanno, “Conditioning of Quasi-Newton Methods for Function Minimization,” Mathematics of Computing, Vol. 24, pp 647-656, 1970.
[19] S. Suthaharan, “Markov Model Based Congestion Control for TCP,” Annual Simulation Symposium, 2004.
[20] Y.C. Wang, J.A. Jiang, R.G. Chu, “Drop Behaviour of Random Early
Detection with Discrete-Time Batch Markovian Arrival Process,” In Proc.
IEE Software 151, August 2004.
[21] T. Ye, S. Kalyanraman, “Adaptive Tuning of RED Using On-line Simulation,” In Proc. IEEE GLOBECOM 2002.
[22] H. Youseﬁ’zadeh, H. Jafarkhani, A. Habibi, “Layered Media Multicast
Control (LMMC): Rate Allocation and Partitioning,” IEEE Trans. Multimedia, June 2005.