Modeling random early detection in a differentiated services network.
An analytical framework for modeling a network of random early detection (RED) queues with mixed traffic types (e.g. TCP and UDP) is developed. Expressions for the steady-state goodput for each flow and the average queuing delay at each queue are derived. The framework is extended to include a class of RED queues that provides differentiated services for flows with multiple classes. Finally, the analysis is validated against ns simulations for a variety of RED network configurations where it is shown that the analytical results match with those of the simulations within a mean error of 5%. Several new analytical results are obtained; TCP throughput formula for a RED queue; TCP timeout formula for a RED queue and the fairness index for RED and tail drop.
INTRODUCTION
The diverse and changing nature of service requirements among Internet applications mandates
a network architecture that is both flexible and capable of differentiating between the
needs of different applications. The traditional Internet architecture, however, offers best-effort
service to all traffic. In an attempt to enrich this service model, the Internet Engineering Task
Force (IETF) is considering a number of architectural extensions that permit service discrimi-
nation. While the resource reservation setup protocol (RSVP) [1], [2] and its associated service
classes [3], [4] may provide a solid foundation for providing different service guarantees, previous
efforts in this direction [5] show that it requires complex changes in the Internet architecture.
That has led the IETF to consider simpler alternatives to service differentiation. A promising
approach, known as Differentiated Services (DiffServ) [6], [7], [8] allows the packets to be classified
(marked) by an appropriate class or type of service (ToS) [9] at the edges of the network,
while the queues at the core simply support priority handling of packets based on their ToS.
Another Internet-related quality of service (QoS) issue is the queue's packet drop mechanism.
Active queue management (AQM) has been recently proposed as a means to alleviate some
congestion control problems as well as provide a notion of quality of service. A promising
class is based on randomized packet drop or marking. In view of the IETF informational RFC
Random Early Detection (RED) [11] is expected to be widely deployed in the Internet.
Two variants of RED, RIO [12] and WRED [13] have been proposed as a means to combine the
congestion control features of RED with the notion of DiffServ.
This work aims to make a contribution towards analytical modeling of the interaction between
multiple TCP flows (with different round-trip times), non-responsive flows (e.g. UDP)
and active queue management (AQM) approaches (e.g. RED) in the context of a differentiated
services architecture. A new framework for modeling AQM queues is introduced and applied
to a network of RED queues with DiffServ capabilities termed DiffRED which is similar to the
RIO and WRED algorithms. Our work complements previous research efforts in the area of
Manuscript first submitted December 7, 2000.
A. A. Abouzeid is with the Department of Electrical, Computer and Systems Engineering, Rensselaer Polytechnic Institute,
8th St., Troy NY 12180, USA (e-mail: abouzeid@ecse.rpi.edu).
S. Roy is with the Department of Electrical Engineering, University of Washington, Box 352500, Seattle WA 98195-2500,
USA (e-mail:roy@ee.washington.edu).
Part of the material in this paper (Section III.A,B) was presented at IEEE Global Communications Conference, San Francisco,
November 2000, and is included in a revised form in this paper.
TCP modeling under AQM regimes. Specifically, this work has the following unique contributions

C1. TCP timeout in AQM Networks: We derive an expression for the probability of a timeout
that reduces the inaccuracy by as much as an order of magnitude vis-a-vis previous state-of-art
[14], [15]
C2. Poisson Process Splitting (PPS) Based Analysis for TCP flows: We show by analysis
and simulations that the PPS approximation holds for a population of heterogeneous (in terms
of delay) TCP flows sharing a bottleneck RED queue.
C3. Fairness Results: We derive expressions for the fairness index of a population of heterogeneous
TCP flows for the case of RED and compare it to Tail Drop.
C4. Network of AQM (RED) Routers: We extend the result to a network of AQM queues
with TCP (and UDP) flows.
C5. Network of DiffRED Routers: Finally, the results are extended to a network of RED and
DiffRED queues.
While the details of the above contributions are presented in the following sections, we first
comment on the relation between the above contributions and previous/concurrent related work.
Literature Review
The steady-state throughput of a single TCP-Reno (or NewReno) flow with Tail Drop (TD)
queueing policy where packet drops can be modelled as an i.i.d loss with probability p has
been shown to have the well-known inverse- # p dependance. This result was derived by several
authors [16], [17], [18] using different analytic approaches; for example, [16] used a non-homogeneous
Poisson process approximation of the TCP flow while [17], [18] use a fixed point
approximation method, both yielding the same dependance to within a multiplicative constant.
This result which we call throughput formula1, does not incorporate the effect of TCP timeout
mechanism.
In [14], the above was extended to include timeouts for a Tail-Drop queue for scenarios where
it is reasonable to assume that conditioned on a packet loss, all remaining packets in the same
window of data are also lost (i.e. burst loss within the same window round). Based on this
assumption, the authors derive a more accurate formula which we term throughput formula2,
for the steady-state TCP throughput. Specifically, this derivation includes (as an intermediate
step) an expression for the probability, given a packet loss, that this loss will be detected by a
timeout - we term this the the timeout formula. An alternative timeout probability was derived
in [15] with independent packet losses (i.e. without the assumption of burst loss within a loss
window). However, the result is not available in closed form and requires the knowledge of the
window size probability distribution function.
Building on the above two formulae for the throughput of an individual TCP flow, Bu et al.
[19] extend the analysis to a network of RED queues by solving numerically coupled equations
representing the throughput for each individual flow. A similar approach is adopted in [20],
[21].
Our contribution C4 listed above is similar to [19], [20], [21] insofar that we also seek to
model a network of AQM queues with TCP flows. However, unlike [19], [20], [21], we do
not use any of the formulae derived earlier. Specifically, we show that the timeout formula
derived in [14] largely over-estimates the probability of a timeout detection for an AQM queue
due to the assumption of burst loss within a loss window, via analysis that is supported by ns2
simulation. Thus in C1, we derive a new formula for the timeout probability and compare the
accuracy of the new formula with those derived earlier.
In [11], the authors predict that the well known bias of TCP against connections with larger
delay sharing a bottleneck Tail Drop queue will only be slightly affected by the introduction
of RED without any definitive analytical support. Our results in C2, C3 precisely quantify the
amount of unfairness experienced by TCP flows over a bottleneck RED vis-a-vis a Tail Drop
Packet Drop ProbabilityAverage Queue (packets)
minth maxth
Fig. 1. RED packet drop probability as a function of
the average queue size
(1)
(2)Average Queue Size
(1)
(2)
Drop Probability
minth maxth
Fig. 2. Schematic of the DiffRED packet drop probability
for two classes of service.
queue by using a PPS approximation (that is shown to hold within an acceptable error margin)
and hence deriving a fairness index for a population of heterogeneous TCP flows for the two
cases of RED and Tail Drop.
Paper outline
The paper is organized as follows. In Section II, we present the network model considered
in this paper, describe the RED and DiffRED algorithms and outline our modeling approach.
Section III considers a single congested RED queue, the PPS property is shown to hold for a
population of heterogeneous flows, the analytical results for a single RED queue are validated
against ns simulations and the fairness results of RED versus Tail-Drop are presented. Section
IV presents a derivation of our timeout formula and a comparison between our results and
previous results from [14] and [15] against ns simulations. Section V presents the analysis of
a network of DiffRED 1 queues with TCP and UDP flows. The network model validation is
presented in Section VI. Section VII concludes the paper outlining future extensions.
II. MODELING AND NOTATION
A. The RED Algorithm
We briefly review the original RED algorithm (see [11] for further details). A RED router
calculates a time-averaged average queue size using a low-pass filter (exponentially weighted
moving average) or smoother over the sample queue lengths. The average queue size is compared
to two thresholds: a minimum threshold (minth) and a maximum threshold (maxth).
When the average queue size is less than minth no packets are dropped; when the average
queue size exceeds maxth, every arriving packet is dropped. Packets are dropped probabilistically
when the time-averaged queue size exceeds minth with a probability p that increases
linearly until it reaches maxp at average queue size maxth as shown in Fig. 1. RED also has
an option for marking packets instead of dropping them.
B. The DiffRED algorithm
We propose to investigate a DiffRED algorithm that is identical to the original RED algorithm
except for the following important change - DiffRED differentiates between different packets
by appropriately labelling each with the class it belongs to. If a packet is not labelled, it will
be assigned the default (lowest) class. The RED queue associates a priority coefficient, denoted
by # (c) , for each class 1 # c # C where C is the total number of classes. The lowest priority
class corresponds to # and the c-th (higher) priority class packets have coefficient # (c) ,
It will be shown in Section II that RED is a special case of a DiffRED queue with no service differentiation.
Packet Drop Probability(packets)
minth
Average Queue
Fig. 3. Packet drop probability for the "Gentle" variant
of RED.
Packet Drop Probability(packets)
minth
Average Queue
(2)
(1)
Fig. 4. Packet drop probability for the "Gentle" variant
of DiffRED.
# (2)
# (c)
# (C) . When a DiffRED queue receives a packet, it
updates the average queue size and drops the packet with probability equal to p # (c) for a class
c packet. Thus, for the same congestion level (i.e. average queue size), higher priority packets
are dropped with a lower probability. A schematic diagram of the DiffRED dropping algorithm
for the case of depicted in Figure 2. The plot shows that the packet drop probability
function (as a function of the average queue size) has a lower slope for the higher priority class
(for while the drop function for the lower priority class has a higher
slope.
C. The Gentle Variant of RED
In the recently recommended "gentle" 2 variant of RED [22], the packet-dropping probability
varies from maxp to 1 as the average queue size varies from maxth to 2maxth . Figures 3-4
depict the packet drop probability for RED and DiffRED with this option enabled. Our model
applies equally well to both cases, but the model with the "gentle" option requires less restrictive
assumptions and hence is applicable to a wider range of parameters as will be discussed in
Section II-E.
D. Network Model and Notations
Assume a network of V queues that support M TCP flows and N UDP flows. Each TCP
connection is a one way data flow between a source S j and destination D j , with reverse traffic
consisting only of packet acknowledgments (ACKs) for each successfully received packet at the
destination (i.e. no delayed-ACKs). Throughout the paper, we will assume that the TCP flows
are indexed by 1 while UDP flows are indexed by M <
shows a network with denote the total round-trip
propagation and transmission delays for the j th , flow (not including queuing
delay) and let - v denote the v th queue link capacity (packets/sec.
Denote a zero-one (M +N)-V dimensional order matrix O with elements
that specifies the order in which the j th flow traverses the v th queue. A 0
entry indicates that the corresponding flow does not pass through that queue. Since each flow
passes through at least one queue, each row in O must have at least one entry equal to 1.
In this work, we consider TCP-NewReno and assume the reader is familiar with the key
aspects of the window adaptation mechanism [23], [24] - i.e., the two modes of window increase
(slow start and congestion avoidance) and the two modes of packet loss detection (reception of
multiple ACKs with the same next expected packet number or timer expiry). Our analysis
This option makes RED much more robust to the setting of the parameters maxth and maxp.
S5
Fig. 5. Experimental network topology with two RED queues.
applies best to TCP-NewReno since we assume that multiple packets within the same loss
window will trigger at most one duplicate ACK event (rather than one for
Modeling Approach
The primary challenge facing any analytical approach is to capture the complex interplay of
TCP congestion control algorithm and active queue management policies as RED. We adopt
a mean value analysis (using fixed point approximation) to estimate (long-term) averages of
various parameters as done in [17], [18], [19], [25], [26], while recognizing that such analysis
does not allow for accurate prediction of higher order statistical information (e.g. variances).
We next state and discuss the following modeling assumptions:
A1: A congested queue is fully utilized (except possibly at some isolated instants).
A2: Each TCP flow passes through at least one congested queue.
A3: The probability of a forced packet loss is negligible. 3
A1 is a well known result that has been observed in the literature through Internet measurements
as well as simulations and was also confirmed in all the simulations we performed. A2
is reasonable if the TCP flows window size are not limited by the receiver's advertised window
sizes. A3 implies that we model only 'unforced' (or probabilistic) RED packet losses and ignore
forced losses which should be avoided when configuring RED queue parameters 4 . Note that it
is much easier to configure a RED (or DiffRED) queue to avoid forced packet drops when the
"gentle" option is used, as noted in [22] due to its avoidance of the abrupt increase in the drop
probability from maxp to 1. Nevertheless, our analysis results hold even if the "gentle" option
is not used, as long as A3 holds.
III. SINGLE QUEUE
The aim of this section is two-fold: (i) we outline an analysis using the PPS approximation 5
and (ii) derive a result for the probability that a loss is detected by a timeout (TO) and not
Duplicate Acknowledgment (DA). Both of these results will be used in the following section in
a network (rather than a single queue) set-up.
A. PPS Based Analysis for TCP flows
Consider M Poisson processes, each with an arrival rate # j at a single queue that randomly
drops packets with a probability p. Let P i,j denote the probability that the i th packet loss event
belongs to the j th flow. From the PPS (Poisson Process Splitting) property,
(1)
independent of i.
3 Forced packet losses are those due to either buffer overflow or due to packet drop with probability one.
4 This assumption has been adopted in many previous AQM-related research efforts (e.g. [27]).
5 Part of this Section was presented in a preliminary form in [28].
Consider now M TCP flows - let X i denote the i-th inter-loss duration at the queue as shown
in Fig. 6 and Q i,j the queue size for session j packets at the end of epoch i. Then the net
round-trip propagation and queuing delay for connection j at the end of the i th epoch is #
flows share the same buffer, Q the
steady-state average queue size.
Let W i,j denote the window size of the j th flow just before the end of the i th epoch and W av j
denote flow j time-averaged window size (as opposed to E[W i,j that represents the mean
window size just prior to the end of the epoch).
We postulate that, for M TCP flows sharing a queue,
(2)
Equation 2 is a postulate that the PPS approximation (1) holds for a population of TCP flows
sharing a random drop queue. To justify the above we first consider the case of TCP flows that
are perpetually in the congestion avoidance phase (additive increase - multiplicative decrease
(AIMD) mode of window size) and use an analytical description of AIMD to derive expressions
for the steady state average window and throughput. These expressions are then validated
against ns simulations in support of (2). A modified PPS approximation for the case of timeouts
is postponed to Sec. V.
The window evolution of the TCP-Reno sessions is governed by the following system of
equations (refer to Figure 6),
w.p. P i,j
Taking the expectation of both sides of (3)
where we used the independence approximation E[W i,j P fixed point approximation
Similarly, denoting #
, then, by fixed point approximation to (2),
. (5)
Substituting by (5) in (4),
Equation (6) is a system of M quadratic equations in the M unknowns W j (or #
it can be readily verified by direct substitution that
time
Window
4,1
4,2
Fig. 6. A schematic showing the congestion window size for two (i.e. sessions with different
round-trip delays sharing a bottleneck link with RED queue. Packet loss events are indicated by an X.
is an explicit solution for (6) and hence,
Remarkably, the above result implies that the average steady-state window size is the same for
all flows; also, W j implicitly depends on Q and X that need to be determined.
To relate the above result for W j to W av j
, let W # i,j denote flow j window size just after the
start of epoch i. It is straightforward to verify that
and from (3)
hence
where
Finally, let r j denote flow j steady-state throughput (in packets/sec). Then,
In case of full bottleneck link utilization,
which, by substituting from (14) and
Finally, let p denote the average packet drop probability of the RED queue. Then,
(RED or TD)G Sink
Bottleneck Linkt
l
nt
Fig. 7. Schematic of multiple TCP connections sharing a bottleneck link.


I
th max th 1/max p Q (an.) Q
Since the RED average packet drop probability also satisfies
Q- min th
th - min th
a relationship between Q and X follows by equating (17) and (18).
B. Single Queue Validation
The analytic expressions for various parameters of interest for RED queues derived in the
preceding section will be compared against results from ns simulations.

Figure

7 depicts the ns simulation model used for validating the above results. M TCP flows
share a common bottleneck link with capacity - packets/sec and (one-way) propagation delay
# . Forward TCP traffic is a one way flow between a source S j and the sink, with reverse traffic
consisting only of packet acknowledgments (ACKs) for each successfully received packet at the
sink. We consider the long run (steady-state) behavior and assume that the sources always have
packets to transmit (e.g. FTP of large files). The j-th flow encounters a one-way propagation
delay # j , and is connected via a link with capacity # j packets/sec. to the bottleneck queue. The
total round-trip time for propagation and transmission (but excluding queuing) for the j-th flow
is thus

Table

I lists the parameters used for two sets of simulation experiments with RED policy using
the ns simulator [29] (more validation experiments are available in [30]); the link capacities
- and # j (packets/second), propagation delays # and # j (seconds) for the topology in Fig. 7 as
well as the number of competing flows used for each simulation. In each simulation, a value
for the link delay # 1 of the first flow and a factor d > 1 is chosen such that the remaining # j
are specified according to # i.e. the access link (from source to queue) propagation
delay profile increases exponentially. The values of # 1 and d for each simulation are listed in

Table

I. For each simulation we compare the analysis results to the simulations measurements
of Q in

Table

I. All simulations use equal packet size of 1 KBytes. Figures 8-9 show the
measured and the computed r j for each competing flow, where the x-axis indicates the computed
We choose to show the un-normalized r j (packets/second) rather than the normalized
Average round-trip time E[g (seconds)
Average
transmission
rate
(packets/second)
Analysis
Simulation
Fig. 8. Results for Exp.1.
Average
transmission
rate
(packets/second)
Analysis
Simulation
Fig. 9. Results for Exp.2.
throughput since the difference between the simulations measurement and the analysis results
are indistinguishable if shown normalized to the link capacity.
C. Fairness Properties of RED versus Tail-Drop
TCP's inherent bias towards flows with shorter round-trip time as a result of its congestion
window control mechanism is well-known - in [31], it has been shown that when multiple TCP
flows with different round-trip times share a Tail Drop queue, the steady-state throughput of a
flow is inversely proportional to the square of the average round-trip delay (see Appendix A for
a simple derivation of this result). Our analysis/simulations results (specifically, (9) and (14))
of a single RED queue with multiple TCP flows and without timeouts (see comment at the end
of this section) reveal a dependence of the throughput that differs from that of Tail Drop.
Consider parameter K j defined by (13). For a population of heterogeneous flows, P j is
directly proportional to the TCP flow throughput and hence inversely proportional to the round-trip
delay - K j increases with round-trip delay. Since
mild variation. Hence, for a large number of flows, the dependence of flow throughput on K j
can be neglected 6 . Thus, the conclusions in the remainder of this section will be a lower bound
to the improvement in fairness compared to Tail Drop.
With the above assumptions (i.e. neglecting the effect of K j ), the results of (9) and (14)
show that the average transmission rates of competing connections at a congested RED queue
is inversely proportional to the average round-trip times and not to the square of the average
round-trip times as in Tail Drop. A fairness coefficient # may be defined as the ratio of the lowest
to the highest average throughput among the competing flows sharing a queue (i.e. ideally,
denote the fairness coefficients of the equivalent 7 Tail
Drop and RED queues. Then,
implying that the RED queue achieves a higher fairness coefficient.
The previous definition of fairness only considers the flows with the maximum and minimum
transmission rates; in the pioneering work of [32], the following index #(r) was introduced to
quantify fairness based on the rates of all flows:
ideally fair allocation (r results in #(.) = 1; and a worst
case allocation ( r
, which approaches zero for large n.
6 In the limit as the number of flows tends to infinity, K flows. Note that if the impact of K j were to be
included, it would help decrease TCP bias against larger propagation delay since it increases with the round-trip time.
7 An equivalent queue is one that has identical TCP flows and the same average queue size ([11])
With this definition, the fairness index for a queue with n TCP flows yields
As an illustrative example, consider TCP flows with an exponentially decaying (or increasing)
delay profile with factor d. Then, assuming large n (and hence neglecting the effect of K j for
the case of RED), it follows after some simple algebraic manipulations that
#RED (d) =n
and
i.e. # TD
An intuitive explanation for this decrease in bias (i.e. fairness coefficient closer to one) for
RED is in order. TCP increases its window size by one every round-trip time - thus, lower delay
links see a faster increase in their window size. In case of synchronized packet loss (Tail Drop
queues), all windows are (typically) reduced at the same time, and hence the average window
size is inversely proportional to the average round-trip time. But since the throughput of a flow
is proportional to the window size divided by the round-trip time, the average rate of each TCP
session is inversely proportional to the square of the average round-trip time. In case of RED,
when a packet is dropped, the chances that the packet will belong to a certain connection is (on
the average) proportional to that connection transmission rate- thus TCP sessions with lower
delays are more likely to have their windows reduced. The analytical results show that this
causes the average window size to be equal for all connections (6) and thus the throughput of
a connection is only inversely proportional to the round-trip-delay. Thus while the basic RED
algorithm does not achieve throughput fairness among the competing flows, it substantially
reduces the bias as compared to Tail Drop.
Finally, the above fairness results do not take into account the effect of TCP timeouts. For
reasons previously shown via simulations in the literature, the occurrence of timeouts will, in
general, increase the unfairness in TCP against longer delay links.
IV. TIMEOUT FORMULA FOR A TCP FLOW WITH RANDOM PACKET LOSS
In this section, we first derive an expression for the probability that a packet loss event will be
detected by a timeout (TO) (i.e. not a duplicate ACK detection (DA) event). Next, we compare
our result and those in the literature against ns simulations.
A. Analysis
Consider an instant during a TCP-Reno session at which the window size is in the congestion
avoidance phase. Let w denote the current congestion window size, in packets, during which at
least one packet loss takes place; each packet is assumed lost independently with probability p.
Let the current round be labelled as round i for reference (see Figure 10). Let P (w,
the probability, conditioned on at least one packet loss during the current window round, that
packet k will be the first packet lost during the round. Then,
The k-1 packets transmitted before the first loss in the current round will cause the reception
of k - 1 ACKs in the next round (i hence the release of an equal number of packets.
Packet sequence number
w-k
round i round i+1 round i+2
new packets
Time
Fig. 10. Analysis of the probability of a TO vs. TD. Successful packets (i.e. not dropped), dropped packets, and
ACK packets for packet k are represented by white-filled, completely shaded and partly shaded rectangles
respectively. In this example,
denote the number of duplicate ACKs received in round due to the
successful transmission of N 2 out of the k-1 packets in round i+1. Similarly, consider the w-k
packets transmitted after the first loss during round i (the current round), and let N
denote the number of packets successfully transmitted out of the w - k packets. Notice that,
unlike the N 2 packets, the N 1 packets are transmitted after the first loss packet in the current
round. Hence, N 1 duplicate ACKs will be generated immediately in round i + 1.
Let D(w, denote the probability that a DA detection takes place in round 2.
Then,
Notice that the above expression is independent of k. This is expected, and can be stated simply
as the probability of at least 3 out of
Let Q(w) denote the probability of a TO detection in rounds 2. Then
For retaining only the most significant terms yields
(w - 1)(w - 2)p (w-3) (27)
Following a DA detection, the window is halved and TCP attempts to return to its normal
window increase mode in congestion avoidance. However, one or more losses may take place
in the immediate following round (i.e. before the window is increased). In this paper, consecutive
congestion window rounds in which packet loss is detected by DA without any separating
additive window increase will be treated as one loss window, that ultimately terminates via either
a DA or a TO. Let Z(w) denote the probability that a TO will take place (either immediately
or following a sequence of consecutive DA's). Then,
log w
where the logarithm is base 2.
Finally, recalling that W i denotes the window size at the end of the i th epoch, applying a fixed
point approximation to (28) yields
where Z(W ) is given by (28).
validation and comparison with previous results
In this section, previous results for Z(w) are listed and compared with the results of a representative
simulation using ns consisting of multiple TCP flows sharing a bottleneck RED queue.
In [14], the following expression for Z(W ) was derived
assuming that, once a packet is lost, all remaining packets in the same congestion window are
also lost (which is probably reasonable for a Tail Drop queue). In [19], the authors argue that
this is still a good result when applied to an AQM like RED which drops packets independently.
We show here that this is not true.
In [15], the following expression for Z(w) was derived
which is the same as our expression for Q(w) in the previous section (26). However, the authors
do not analyze the case where multiple consecutive DA's ultimately cause a TO. Also, the
expression for E[Z(w)] was not derived in [15], since the analysis relies on the knowledge
of the congestion window probability distribution function. Nevertheless, we show here that
applying a fixed point approximation to (31), yielding
would result in an under-estimation of the timeout probability.
In order to compare between the accuracy of our result (29) and the previous results (30)
and (32) when applied to a RED queue, we construct the following simulation using ns. A
single congested RED queue is considered with a number of identical TCP flows ranging from
5 to 40. The RED parameters are set as follows:
and ECN disabled. The link capacity is 1 Mbps and two-way propagation delay (no including
queuing) is 20 ms. The packet size is 1 KB. The buffer size is selected large enough to avoid
buffer overflow. The trace functionality within ns was enhanced so as to record, for one of the
flows, the time instant, congestion window size and the reason (TO or DA) for each window
decrease. Post-processing scripts were used to compute the average window size just before a
packet loss detection (i.e. W ), the average packet drop through the queue (p), the total number
of packet loss detection events that are detected by TO and those detected by DA, and hence the
0.40.81.2
Number of TCP flows
Measured E[W]/10
Measured E[p]
Measured TO prob. E[Z(W)]
Z(E[W]) from our analysis
Z(E[W]) from Padhye et al.
Fig. 11. Comparison between different timeout formulae against ns simulations for TCP-NewReno.
measured E[Z(W )]. Finally, the measured p and W from the simulations were substituted in
(29), (30) and (32) to compute Z(W ). The results are shown in Figure 11.

Figure

11 does not show the results from (32) since the values produced are practically 0,i.e.,
excessively under-estimates the probability of a timeout. Figure 11 shows that our result is
much more accurate than that of [14] (as expected). The improvement accuracy is up to an order
of magnitude for small number of competing flows (and hence small p). The reason is that, for
small p, the assumption of conditional burst loss used in [14] becomes very unrealistic. As p
increases, the RED queue operation approaches that of Tail Drop, since p approaches maxp
(and hence all arriving packets are dropped with higher probability, resulting in synchronous
operation of the flows and thus burst losses). However, even for high p, our formula is more
accurate than that of [14].
V. NETWORK ANALYSIS
Since a RED queue is a special case of a DiffRED queue with # we present an
analysis for the case of DiffRED queues. In the first subsection, we consider a network of TCP
and UDP flows and we model the additive increase/multiplicative decrease dynamics of TCP
only. Next, we extend the model results to capture the TCP timeout behavior.
A. Modeling without timeouts
Let minth v , maxth v and maxp v
(c) denote the DiffRED parameters of the v th queue. Let
(c) denote the priority coefficient of class c, where # v
denote the average
(steady state) packet drop probability in the v th queue. Let p v
(c) denote the average packet drop
probability for class c at the v th queue. Then for the case of the "gentle" variant,
qv -minthv
th
th
(c)
while for the case without the "gentle" variant,
qv -minthv
According to the description of the DiffRED dropping algorithm (Figure 2)
where (35) assumes that all the DiffRED queues in a network use the same value of the class
priority coefficients (i.e. # (c) is independent of v) 8 .
Let #(j) and p v (j) denote the priority coefficient and average drop probability at the v th
queue for the class that flow j belongs to. For the case of the "gentle" variant, it follows
from (33) and (35) that
-maxp (1)
while for the case without the "gentle" variant
Let r j denote the steady state packet transmission rate of flow j. Let the generator matrix
G denote the fraction of the j th flow transmission rate at the input of the v th queue. Then the
elements of G are
h(o(j, v), o(j, k)) (38)
where
h(o(j, v), o(j,
denote the steady state probability that the dropped packet belongs to the v th queue.
Applying A4,
Let P j|v denote the probability that, conditioned on a packet loss from the v th queue, that
packet loss belongs to the j th flow, then, using A4,
Let P j denote the probability that a packet loss belongs to the j th flow. Then,
which by substituting from (40) and (41) yields,
8 It is possible to extend the analysis by assuming that each queue has a different set of priority coefficients by defining #v (c)
for each queue. This may be specifically valuable when modeling the interaction between DiffServ enabled and non-DiffServ
queues. However, for initial model simplicity, we postpone this to future extensions.
where the above is simply the ratio of the sum of the packet drop rates of flow j at all the queues
to the sum of the packet drop rates of all flows in the network.
Now, we can consider one of the TCP flows in the network and consider its window evolution.
Let Y i denote the time at which the i th random packet loss (caused by any of the V queues and
causing a packet loss from one of the M event takes place, and X
the i-th inter-loss duration (epoch).
Let the j th TCP session window size (in packets) at the beginning and end of the i th epoch
be denoted by W i,j and W i+1,j respectively. Let q i,v denote the queue size of queue v at the end
of epoch i; then the net round-trip propagation and queuing delay for connection j at the end of
the i th epoch is #
Following the same steps as before, the window evolution of the TCP sessions is governed
by the system of equations (4), where E[#
This system
of equations captures only the TCP additive increase/multiplicative decrease dynamics but not
the impact of timeout - this is done in the next section.
From Sec. III-A,
and
where K j is given by (12).
Substituting by X from (44), P j from (43) and r j from (45) in (4),
Finally, for congested links (A1),
M+N
while for uncongested (underutilized) links,
M+N
The set of M equations (46)-(48) in the M
are then solved numerically as explained in Section IV.
B. Modeling TCP timeout mechanism
In this section, we show how the model can be extended to incorporate the effect of timeouts.
Since it is well known that the slow start behavior has a negligible effect on the TCP steady-state
throughput, we neglect slow start and assume that the window size after a timeout is
set to 1 and that TCP continues in the congestion avoidance phase after some idle duration
(discussed below). For simplicity, only single timeouts are considered since the difference in
performance between a single timeout and multiple timeouts is insignificant (both result in very
time
window
Fig. 12. Approximate timeout behavior. After timeout, slow-start is neglected, and TCP is assumed to resume in
congestion avoidance mode with an initial window size value of one packet.
low throughput). Thus, our objective is to model the approximate timeout behavior depicted in
Fig.12 , where a single timeout causes the window size to be reduced to one, and TCP refrains
from transmission (i.e. is idle) for a period of one round-trip time (# i,j ).
Let Z(W i,j ) denote the probability that, given a packet loss belonging to flow j, that loss will
result in a timeout. Then, following the same steps as before (for
w.p.
w.p.
where
Taking the expectations of both sides and simplifying,
denote the steady-state proportion of time that TCP flow j is busy (b
the non-responsive flows). Following the same derivation steps as before,
and
An expression for derived (and validated) in Sec. IV (equation 29). An expression
for b j is derived as follows.
Let X i,j denote the inter-loss times between packet losses of TCP flow j (as opposed to X i
which denotes the inter-loss times in the network) and consider the window size evolution of
flow j in between two consecutive Duplicate ACK (DA) events (see Fig. 12) Then,
and hence
Let NDA (W j ) denote the average (from a fixed point approximation argument) expected
number of consecutive DA's. Then NDA distribution with parameter
and finally,
Thus, a set of M equations in the M+V unknowns is obtained by substituting by b j from (57)
and P j from (52) in (51). The remaining V equations correspond to (47)-(48) with modification
to include the timeout behavior yielding,
M+N
for fully utilized links and
M+N
for underutilized links.
A solution for the M +V unknowns is obtained by solving the M +V equations numerically
as explained in the following section.
VI. NETWORK MODEL RESULTS
In order to validate the analysis presented in the previous sections, we present a representative
number of comparisons between the numerical results obtained from the solution of the M +V
non-linear equations and the simulation results from the ns-2 simulations.
The simulations reported here use the "gentle " option of RED in the ns-2 simulator set to
"true" (i.e. it uses the gentle variant) and the "setbit " option set to false (i.e. packet drops
instead of marking). Other experiments without the "gentle" option provide results with similar
accuracy (not reported here due to space constraints).
We first describe the technique used for solving the non-linear equations. We then summarize
the modifications to the RED algorithm in ns-2 to simulate the DiffRED behavior. And finally,
we present the validation experiments.
A. The network solver
In the analysis section, the V +M unknowns (W j ,
are related by a set of non-linear equations. In general, a set of non-linear equations
can be solved using a suitable numerical technique. Two main problems encountered in solving
non-linear equations are; (i) the uniqueness of the solution and (ii) the choice of an appropriate
initial condition that guarantees the convergence towards a true solution. In this section, we
describe the algorithm used to achieve both objectives.
Our algorithm is based on the observation that there exists a unique solution for (46)-(48)
that satisfies 0 # q v # maxth v and W j > 0. Thus, the network solver is composed of the
following two steps (or modules):
Step I
The set of equations (46)-(48) is solved using any iterative numerical technique. We used a
modified globally convergent Newton-Raphson technique [33] that operates as follows: (1) It
chooses initial conditions randomly within the solution space; (2) Performs Newton-Raphson
technique while checking for convergence; (3) If the algorithm converges to a valid solution,
the program terminates; else, the program repeats from step (1) again.
Note that the resulting solution does not take into account timeouts or non-responsive flows -
hence, step II.
Step II
This step of our algorithm uses the solution provided in step I as initial conditions - it also uses
a globally convergent Newton-Raphson technique applied this time to the extended modeling
equations describing the timeout behavior in (51)-(52), (58)-(59) (and, if applicable, the UDP
behavior).
Thus, the network solver is composed of two modules, each of which uses an iterative numerical
method; the first module solves the simplified model and thus provides an approximate
solution for the network which is then fed into the next module that refines the network solution
providing a more accurate one. This technique has proved to converge to the correct solution in
all experiments we tried, a representative of which (a total of 160 experiments) are reported in
the following sections.
B. Modifying ns-2 to model DiffRED
The following modifications to ns-2 were incorporated. In the packet common header, we
added a priority field that contains an integer specifying the priority class of the packet. Sim-
ilarly, an additional parameter for the TCP object specifying its class of service was added;
when a TCP session is established, this parameter is set to the selected class of service for that
session. The TCP mechanism is also modified to label each packet by the TCP session priority
(by copying the TCP session class of service to the packet header of the packet being transmit-
ted). Finally, the RED algorithm is modified so as to first check for the packet class (from the
packet header) and compute the packet drop probability according to the mechanism outlined
in Sections II.B (for the case without the "gentle" option) or II.C (for the "gentle" variant).
C. Experimental Topology
We use the topology of Figure 5. It consists of two RED/DiffRED queues Q 1 and Q 2 . There
are a total of five sets of flows going through the queues and each flow set is composed of four
identical flows. In the figure, S denotes the source (origin) while D denotes the destination
for those flows. Three sets of flows (S1, S2 and S3) arrive at Q 1 , out of which only one
traverses through Q 2 . Two other sets of flows arrive at Q 2 . The only two bottleneck links
in the topology are those of Q 1 and Q 2 , where the link speeds are - 1 and - 2 (packets/sec) and
In the experiments, we vary the priority class of S2, allowing it to have a higher priority in
some of the experiments to compensate it for the higher loss rate it suffers since it has to traverse
both queues.
Each experiment is composed of five simulation runs, at the end of each we compute the
parameters of interest; average queue size for each queue, average window size for each TCP
flow and the average goodput (number of packets received at the destination per second). The
duration of each run is long enough to guarantee the operation of the network in the steady
state for a long duration. We then compute the average, among the simulation runs, of each
of these parameters and compare with the network solver results. In the figures, we plot one
point (x, y) for each experiment, where x represents the simulation result and y represents the
corresponding result obtained from applying our analytical network solver. Hence, ideally, all
points should lie on a line with a slope of 45 degrees.

II
PARAMETERS SETTINGS FOR THE EXPERIMENTAL NETWORK TOPOLOGY OF FIG.5 AND FIG.16. LINK
size obtained from simulations (packets)
Average
queue
size
obtained
from
analysis
(packets)
Fig. 13. Average queue size obtained from simulations and analysis for the experiments with TCP traffic only.
D. Experiments with TCP only
A total of eighty experiments have been performed with various parameters. The parameters
of five of these experiments are shown in Table I. Three additional similar sets are performed
but by reducing the bottleneck link speeds by half for each set (i.e. the first experiment in the
last set would configure the bottleneck links at 4Mbps) thus forming twenty experiments. These
twenty experiments are repeated four times, with the priority coefficient of the higher priority
flow S2 varying from 0.1 to 1.0 (in steps of 0.3). The results are shown in Figures 13-15.
Note that this also validates the analysis for the RED case, since setting the priority coefficient
to 1.0 corresponds to RED operation.
In

Figure

13, each experiment results in two points, one for each queue. Hence, the figure
contains a total of 160 simulation/analysis comparison points. On the other hand, in Figure 14
and

Figure

15, each experiment results in three comparison points. The reason is that TCP flows
and S3 (on one hand) and S4 and S5 have identical goodput and congestion window size
values. Thus, each experiment renders three window sizes (and three goodput values), one for
and S3, one for S2 and a third for S4 and S5 for a total of 240 comparison points for each
of these figures.
E. Experiments with TCP and UDP
To validate the model results for mixed TCP and UDP traffic, we modify the topology of

Figure

5 to Figure 16 by adding two sets of UDP (constant bit rate) flows, one that originates at
Average window size for TCP flows obtained from simulations (packets)
Average
window
size
for
flows
obtained
from
analysis
(packets)
Fig. 14. average congestion window size from simulations and analysis for the experiments with TCP traffic only.
Average goodput obtained from simulations (kbps)
Average
goodput
obtained
from
analysis
Fig. 15. The average goodput obtained from simulations and analysis for the experiments with TCP traffic only.
S6 and passes through both queues before exiting the network while the other originates at S7
and passes only through Q2. The transmission rates of the UDP flows are set such that the total
transmission rates of S1 and S2 equals 10% of the link capacities - 1 and - 2 . The results are
shown in Figures 17-19.
Just like Figures 13-14, Figures 17-18 contains a total of 160 and 240 simulation/analysis
comparison points (respectively). However, unlike Figure 15 which contains 240 comparison
points Figure 19 contains an additional 160 comparison points accounting for the 2 UDP flows
in each of the 80 experiments.
Finally, in Figure 20, we show the results of varying the priority coefficient for one of the
experiments (the first experiment in Table I) separately. The figure shows how the priority
coefficient is effective in boosting S2 goodput from its low value when to a much
higher value (almost equal to the other TCP flows rate) when
S5
Fig. 16. Experimental network topology with two RED queues.
size obtained from simulations (packets)
Average
queue
size
obtained
from
analysis
(packets)
Fig. 17. Average queue size obtained from simulations and analysis for mixed TCP and UDP traffic.
3051525Average window size for TCP flows obtained from simulations (packets)
Average
window
size
for
flows
obtained
from
analysis
(packets)
Fig. 18. Average congestion window size obtained from simulations and analysis for mixed TCP and UDP traffic.
Average goodput obtained from simulations (kbps)
Average
goodput
obtained
from
analysis
Fig. 19. Average goodput obtained from simulations and analysis for mixed TCP and UDP traffic.
Coefficient for the higher priority flows (Set 2)
Goodput
flows S1 and S3
flows S4 and S5
UDP flows S6
UDP flows S7
Fig. 20. Effect of varying the priority coefficient of S2 on its goodput. The experiment parameters are shown in
the first entry of Table I.
VII. CONCLUSION
In this paper, an analytical model for a network of RED/DiffRED queues with multiple competing
TCP and UDP flows was presented. Unlike previous work, our analysis is specifically
targeted towards AQM schemes which are characterized by random packet drop (unlike Tail
Drop queues which drop packets in bursts). Our main contributions are (i) An accurate timeout
formula that is orders of magnitude more accurate than the best-known analytical formula, (ii)
Closed form expressions for the relative fairness of RED and Tail-Drop towards heterogeneous
flows (iii) Analysis of RED queues in a traditional as well as differentiated services net-
work. Our analysis has relied on a set of approximations to the timeout dynamics as well as to
the loss rate process of each flow in the network. The analytical results were validated against
ns simulations. These show that the results are accurate within a mean margin of error of 2%
for the average TCP throughput, 5% for the average queue size and 4% for the average window
size attributable to the approximations introduced in Section II. The model proposed should
be applicable to a variety of AQM schemes that rely on randomized (instead of deterministic)
packet drops.
A number of avenues for future research remain. First, the model can be extended to the
analysis of short-lived flows and the effects of limiting advertised congestion window. Also
model extensions to other versions of TCP (e.g. Tahoe, SACK,.etc.) and to the case of ECN
[34] may be considered. Finally, as noted in (8), especially with the expected coexistence
of DiffServ networks with best effort networks, an extension of this model that captures the
interaction between traditional RED queues and DiffRED would be valuable.




In Sec. III-C, we have stated that the average window size of a TCP flow passing through a
Tail Drop queue is inversely proportional to its round-trip delay.
Proof: We show below that, for a Tail-Drop queue, the steady state window size for any flow
is inverse proportional to the round-trip time.
In Tail Drop queues, buffer overflow causes (typically) at least one packet loss from each
flow passing through the queue ([35], [36]). Using the same notations as Sections II and III,
Taking expectation of both sides of (60), and denoting
proving the claim.



--R

Resource ReSerVation Protocol (RSVP)-Version 1 functional specification
RSVP: A new resource ReSerVation protocol.
Specification of controlled-load network element service
Specification of guaranteed quality of service.
The Use of RSVP with IETF Integrated Services.
An architecture for differentiated services.
An approach to service allocation in the Internet.

Definition of the differentiated services field (DS filed) in the IPv4 and IPv6 headers.
Recommendations on queue management and congestion avoidance in the Internet.
Random early detection gateways for congestion avoidance.
Explicit allocation of best-effort packet delivery service
Technical Specification from Cisco.
Modeling TCP Reno performance: A simple model and its empirical validation.
Comparative performance analysis of versions of TCP in a local network with a lossy link.
The stationary behavior of ideal TCP congestion avoidance.
The macroscopic behavior of the TCP congestion avoidance algorithm.
Promoting the use of end-to-end congestion control in the internet
Fixed point approximations for TCP behavior in an AQM network.

A framework for practical performance evaluation and traffic engineering in ip networks.
Recommendation on using the gentle variant of RED.
TCP/IP Illustrated
The NewReno Modification to TCP's Fast Recovery Algorithm.
Blocking probabilities in large circuit-switched networks
The performance of TCP/IP for networks with high bandwidth-delay products and random loss

Analytic understanding of RED gateways with multiple competing TCP flows.

Stochastic Models of Congestion Control in Heterogeneous Next Generation Packet Networks.
Flow Control in High-Speed Networks
Analysis of the increase and decrease algorithms for congestion avoidance in computer networks.
Numerical Recipes in C: The Art of Scientific Computing.
A proposal to add explicit congestion notification (ECN) to IP.
Oscillating behavior of network traffic: a case study simulation.
Congestion avoidance and control.
--TR
Congestion avoidance and control
Analysis of the increase and decrease algorithms for congestion avoidance in computer networks
Numerical recipes in C (2nd ed.)
TCP/IP illustrated (vol. 1)
Random early detection gateways for congestion avoidance
The performance of TCP/IP for networks with high bandwidth-delay products and random loss
The macroscopic behavior of the TCP congestion avoidance algorithm
Explicit allocation of best-effort packet delivery service
Comparative performance analysis of versions of TCP in a local network with a lossy link
Promoting the use of end-to-end congestion control in the Internet
Modeling TCP Reno performance
Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED
Stochastic models of congestion control in heterogeneous next generation packet networks
differentiated services;performance analysis;network modeling;random early detection;UDP;TCP