State-dependent M/G/1 type queueing analysis for congestion control in data networks.
We study a linear-increase multiplicative-decrease flow control mechanism. We consider congestion signals that arrive in batches according to a Poisson process. We focus on the case when the transmission rate cannot exceed a certain maximum value. The distribution of the transmission rate in steady state as well as its moments are determined. Our model is particularly useful to study the behavior of TCP (Transmission Control Protocol) the congestion control mechanism in the Internet. Burstiness of packet losses is captured by allowing congestion signals to arrive in batches. By a simple transformation, the problem can be reformulated in terms of an equivalent M/G/1 queue, where the transmission rate in the original model corresponds to the workload in the 'dual' queue. The service times in the queueing model are not i.i.d., and they depend on the workload in the system.
INTRODUCTION
I
N today's high speed telecommunication networks, a large
part of the traffic is able to adapt its rate to the congestion
conditions of the network. Congestion control is typically designed
so as to allow the transmission rate to increase linearly
in time in the absence of congestion signals, whereas when congestion
is detected, the rate decreases by a multiplicative factor.
This is both the case of the Available Bit Rate (ABR) service
category in ATM [1] (see definition and use of RDF and RIF)
as well as the Transmission Control Protocol (TCP) in the Internet
environment [10], [22]. Congestion is detected by the
source through signals. In case of ABR, the congestion signals
are RM (Resource Management) cells that have been marked
due to congestion information in some switch along the path of
the connection. In case of the Internet, the congestion signals
are packet losses that are detected by the source either through
the expiration of a retransmission timer, or through some negative
acknowledgement mechanism (three duplicate ACKs [22]).
There is also a proposal to add some explicit congestion signaling
to the Internet (the ECN proposal [7]).
The performance evaluation of congestion control mechanisms
is an important issue for network and protocol design.
This evaluation requires a description of times between the arrivals
of consecutive congestion signals. Experimentations over
the Internet [4], [15] have shown that on long distance connec-
tions, the Poisson assumption about the times between congestion
signals is quite reasonable. This happens when the through-put
of the studied connection is small compared to the exogenous
traffic, and when the number of hops on the path is large
so that the superposition of the packet drops in routers leads to
exponential times between congestion signals. For local area
networks, we noticed that the congestion signals may arrive in
Altman, K. Avrachenkov, and C. Barakat are with INRIA, Sophia-
Antopolis, France. Email: {altman,kavratch,cbarakat}@sophia.inria.fr.
R. N-ez-Queija is with CWI, Amsterdam, The Netherlands. Email:
sindo@cwi.nl.
y Corresponding author.
bursts [4]. However, the times between bursts correspond well
to the Poisson assumption. For this reason, we consider the case
when congestion signals arrive in batches according to a Poisson
process. Batches contain a random number of congestion
signals and each such signal causes the division of the transmission
rate by some constant fl. In the sequel, we also refer to a
batch of congestion signals as a loss event.
We focus on the case when a certain limitation on the transmission
rate exists. We determine the exact expression of the
throughput under such a limitation. In the literature, only simplistic
approximations have been proposed [3], [19] so far. We
study two possible scenarios that lead to such a limitation:
(i) Peak Rate limitation: the limitation is not due to congestion
in the network but rather to some external agreement. In that
case, when the transmission rate reaches a certain level M , it
remains constant until a loss event appears. For example in case
of TCP, the window cannot exceed the buffer space available at
the receiver [22]. This is known as the end-to-end flow control
of TCP. In the ABR service of ATM, the transmission rate cannot
exceed the Peak Cell Rate imposed by the contract between
the user and the network.
(ii) Congestion limitation: the limitation on the transmission
rate is due to congestion in the network that occurs whenever
the input rate reaches a level M . In that case we shall have
an extra batch of congestion signals when the level M is attained
which also causes a reduction of the transmission rate by
a random factor. A typical example of such limitation is the
available capacity in the network. There is a maximum limit
on the number of packets a source can keep in the network and
once this limits is exceeded packets are dropped. Another example
is the reserved bandwidth in a Differentiated Services
network [9] in cases when packets exceeding the reserved band-width
are dropped rather than injected into the network as low
priority packets [21].
In the particular case in which the batches contain a single
congestion signal, the peak rate limitation model reduces to the
one studied in [15], who already attempted at computing the
first two moments of the transmission rate. A remarkable observation
is done in that reference showing that the flow control
can be reformulated in terms of an equivalent M/G/1 queue,
where the transmission rate is translated into the workload of the
queue. The congestion signals correspond to customers arriving
at the queue according to a Poisson process. The service times in
the 'dual' queueing model are not i.i.d., and they depend on the
workload in the system. This transformation is also valid in our
more general setting except that in our model with congestion
limitation, there is an additional arrival in the equivalent queueing
model (in addition to the Poisson arrival stream) that occurs
whenever the queue empties. Another difference is that in our
case congestion signals arrive in batches. Without loss of gen-
erality, we consider that the occurrence of a batch of congestion
signals corresponds to the arrival of a client into the dual queueing
model. Hence, the service time of a client is also a function
of the number of congestion signals in the corresponding batch.
We solve in this paper the Kolmogorov equations and obtain
the exact probability distribution as well as the moments of the
transmission rate (of the window in case of TCP) for both prob-
lems. In doing so, we correct an error 1 in [15].
We briefly mention some related results. Queueing analysis
with service times that depend on the workload or on the queue
length have been also considered in [2], [12], [17], [20]. Our
model is a special case of the one studied in [20], where an implicit
characterization of the steady state distribution is obtained
(closed-form expressions were obtained for special cases that
do not cover our model). In [12] an asymptotic approximation
is used for solving state-dependent GI/G/1 queues in which both
inter-arrival times, service requirements and the service rate may
depend on the workload. The peak rate limitation model is a
special case of the model with a general stationary and ergodic
arrival process studied in [4]. For that model only bounds on the
throughput were obtained. Exact expressions for the throughput
were obtained there for the case in which no limitation on the
transmission rate exists (see also [3], [14], [16], [19]).
The structure of the paper is as follows. In Section II we describe
a general model of flow control with limitation on the
transmission rate and we provide a preliminary analysis. The
two cases of peak rate limitation and congestion limitation are
described separately in Sections II-A and II-B. It is shown that
a special case of the model with congestion limitation reduces
to that of the model with peak rate limitation. Hence, it suffices
to analyze the latter case. We then derive the moments and the
distribution of the transmission rate in Sections III and IV in
terms of one unknown constant: the probability of attaining the
maximum rate. This constant is computed in Section V. In Section
VI we specify our model to an important particular case,
that of one congestion signal per batch and a reduction factor
equal to one half. Based on this particular case, we present in
Section VII some numerical and experimental results to validate
the model. We conclude the paper with a section on future re-search

II. FLOW CONTROL WITH RATE LIMITATION: MODELS AND
PRELIMINARY ANALYSIS
We present in this section our model for the rate evolution of
the flow control mechanism. In the sequel we adopt the usual
terminology for TCP, the well known window-based congestion
control protocol of the Internet: we shall work with the window
size rather than the transmission rate. The transmission rate of a
window-based flow control mechanism is at any moment equal
to the window size divided by the round-trip time (RTT) of the
connection.
Let M denote the maximum window size. The limitation on
the window size is either due to a peak rate limitation or to a congestion
limitation. In the following we explain the similarities
and the differences between the models in the two cases. While
1 In a private communication, the authors of [15] announced to replace the
draft with a new one.
no congestion signal is received and the window is smaller than
M , the window of the protocol increases linearly at rate ff ? 0.
In case of TCP, is the number of
data packets covered by an ACK (usually 2, see e.g.[19], [22])
and where RTT is the average round-trip time of the connection
assumed to be independent of the window size [4], [19].
We assume that batches containing a random number of
congestion signals arrive according to an independent Poisson
process. We denote the sizes (i.e., the numbers of congestion
signals) of consecutive batches by and we assume
that these constitute an i.i.d. sequence. The size of an
arbitrary batch is generically denoted by N d
. The Poisson
process and the sequence N k , are independent of
each other and independent of the past evolution of the window.
For each congestion signal received, the window is divided by a
which is a fixed parameter. That is, if an arriving
batch contains signals, the window is multiplicatively
decreased by a factor fl \Gamman . Immediately after the
multiplicative decrease, the window restarts its linear increase.
In case of peak rate limitation, the window stays constant at M
when this maximum level is reached until the next congestion
signal is received. In case of congestion limitation, immediately
upon reaching M , a congestion signal is received and the
window is decreased. We present the two cases separately in
Sections II-A and II-B.
Before doing so, we introduce some further common nota-
tion. We denote the p.g.f. (probability generating function) of
the distribution of N by
\Theta z N
z
Note that the peak rate limitation model with
reduces to the model studied in [15], where congestion signals
appear according to a Poisson process and where the window
is divided by two upon every congestion signal occurrence. By
considering a general model, we aim to account for a wide range
of flow control mechanisms other than TCP and for future enhancements
to TCP congestion control.
Let us denote the window size at time t - 0 by W (t) 2
(0; M ]. We have the following stability result which follows
from Theorem 1 in [4]:
Theorem II.1: There exists a stationary process W   (t) such
that W (t) converges to W   (t) in distribution for any initial state.
Moreover, we have P-a.s.
lim
sup
0: (2)
Note that (2) implies that the stationary distribution of W (t) is
unique. For x 2 (0; M ], denote the (time-average) distribution
function by
It follows from Theorem II.1 that this limit is independent of
W (0) and coincides with the stationary distribution of W (t).
We first assume that F (x) is continuous in x 2 (0; M) (in the
case of peak rate limitation it is clear from physical considerations
that F (x) has an atom at assumption
we find a function F (x) which is an equilibrium distribution for
the window size and, hence, from its uniqueness it follows that it
is the desired distribution. Instead of F (x) it will be convenient
to work with the complementary distribution function
To differentiate between the cases of peak rate limitation and
congestion limitation, in the latter case we attach a superscript cl
to the symbols introduced above, e.g., the distribution function
is denoted by F cl (x). Next we treat the two cases separately.
In particular we show how the analysis of the model with congestion
limitation reduces to that of the model with peak rate
limitation. Therefore, we concentrate on the peak rate limitation
model in the subsequent sections.
A. Flow control with peak rate limitation
With peak rate limitation, when the window reaches the maximum
level M , it stays there until the next congestion signal is
received. In Section II-C below we show that the window size
process W (t) can be related to the workload of an M/G/1 queue
(see also [15]). The workload of this state-dependent M/G/1
queue can be seen to be a Markov process (e.g. see [11]), and
hence the window size evolution W (t) is a Markov process as
well. With this in mind, we derive a steady-state Kolmogorov
equation for F which will be the basis to our
analysis. We use the following up and down crossing argument:
Assume that the process is in equilibrium and consider a level
M). Whenever the window size increases from less than
or equal to x to more than x we say that an up crossing of the
level x has occurred. Similarly, if the window size decreases
from more than x to less than or equal to x we say that a down
crossing of the level x has occurred. Let [t; t + \Delta] be a small
time interval, where t is a deterministic time moment. When the
process is in equilibrium, the probability of up-crossing
is equal to the probability of down-crossing
After equating these, we pass \Delta # 0. Since we assumed that
is continuous for x ! M (see Remark
1 for a justification of this assumption), we conclude that the
derivative of F (x) exists and is continuous for all x except at
\Gamman , when q n ? 0. For x 2 (0; M)nfM fl \Gamman gn=1;2;:::
we obtain the following steady-state Kolmogorov equation
ff d
dx
or, equivalently,
\Gammaff d
dx
From this differential equation we shall determine F (x), x 2
(0; M), in terms of the probability
In Section III we first use (4) to determine the moments of the
window size distribution in terms of PM . Then we find the distribution
function itself in Section IV. The unknown PM is then
determined using the fact that F (x) is a complementary probability
distribution function 1). However, the expression
obtained for PM in this way, does not lend itself for computational
purposes. Therefore we show an elegant alternative to
determine PM in Section V, which leads to an efficient and numerically
stable algorithm for computations.
B. Flow control with congestion limitation
When the maximum window size M is due to congestion lim-
itation, immediately upon reaching the level M a batch of congestion
signals is generated. Here we study the case when the
size of such a batch has the same distribution as the random variable
N . In [5] we treat a more general case when the number of
congestion signals that result from reaching M has a different
distribution than N . Similarly as in Section II-A, we can derive
the following differential equation for F cl
\Gammaff d
dx
F cl
F cl
cl
ae
oe
with,
d
dy
F cl
The additional term, compared to (4), comes from the fact that a
down crossing of the level x may be due to the fact that the level
M is reached and that the rate is decreased by a factor fl \Gamman with
\Gamman M - x. Note that if F (x) is the unique complementary
distribution function satisfying (4) then
F cl
is the unique complementary distribution function satisfying (5).
This follows immediately by substituting (6) into (5). This relation
has a simple geometric interpretation. Using the fact that
the Poisson process is memoryless, if we consider the model
with peak rate limitation only at moments when the window is
less than M (i.e., we cut out all periods where the window equals
what we get is identical to the model with congestion lim-
itation. Thus, we can concentrate on finding the distribution
function F (x) for the peak rate limitation model and then use
(6) or the equivalent:
F cl
In particular, the moments of the window size in the two models
are related by:
cl
In Section III below we derive a recursive relation for E
\theta

Combined with (7), this gives a recursion on E
cl
which
we report at this point for completeness:
cl
kffE
cl
Remark 1: We emphasize that in the congestion limitation
model, the quantity PM has no clear interpretation. In Section
V we use the interpretation of this quantity in the peak rate limitation
model to compute it. If we were to analyze the congestion
limitation model without using (6), then from (5) we could express
F cl
using the same techniques as in Section IV -
in terms of g instead of PM . Note that these two constants are
related:
The constant g can be determined using that F cl
(x) is a complementary
probability distribution, see (24) below. Since from the
analysis of Section V we obtain a more tractable expression for
PM (see Remark 2 for a related discussion), we will not further
dwell on this approach.
C. The dual M/G/1 queueing model
Before proceeding with determining the moments and the distribution
of the window size, we briefly show how the flow control
problem can be related to an M/G/1 queueing problem with
service depending on the system workload, see also [15]. First
we concentrate on peak rate limitation, then we comment on
congestion limitation. Define
ff
Namely, U(t) is obtained by 'flipping' W (t) around a horizontal
line. In particular, the area between W (t) and the maximum
window size M (Figure 1) corresponds to the area below U(t).
Note that U(t) resembles the evolution in time of the workload
(or the virtual waiting time) in a queueing system. A window
equal to M corresponds to an empty queueing system. The linear
increase in workload between arrivals of congestion signals
corresponds to the decrease in workload due to service in the
M/G/1 model. The arrival of a batch of congestion signals in
our model corresponds to an arrival in the M/G/1 model. The
reduction of the window upon a loss event corresponds to the increase
in workload upon arrival in the equivalent M/G/1 model.
Given that the amount by which the window is reduced depends
on the current value of the window (and of course on the number
of congestion signals in the batch), the service time in the dual
queueing model is dependent on the current workload there. We
conclude that the dual model behaves indeed as an M/G/1 queue
(infinite buffer capacity, one server and Poisson arrivals with intensity
-) with state-dependent service requirements. If Un is
the workload seen by arrival n in the M/G/1 queue, then its service
time xn is equal to
where Nn is the number of congestion signals in the nth batch
of congestion signals in the original model. Instead of working
with the window as we are doing in this paper, one could
solve the queueing problem and switch back to the flow control
problem by using Equation (10). In particular, E

\theta

and PM is equal to the fraction of time the server in the
dual queueing model is idle.
In the case of congestion limitation, the only difference in the
dual queueing model is that we have an additional arrival once
the system becomes empty. This makes of the arrival process
the sum of a Poisson process of intensity - and another process
that depends on the workload of the system. The definition of
the service time and the transformation back to the flow control
problem remain the same.
III. MOMENTS OF THE WINDOW SIZE DISTRIBUTION
We further focus on the model with peak rate limitation. In
this section we study the moments of the window size. The
k-th moment of the transmission rate can be simply obtained
by dividing the k-th moment of the window size by (RTT ) k .
Of particular interest is the expectation of the transmission rate
which coincides with the throughput of the transfer or the time
average of the transmission rate. Let X denote the throughput.
We have
RTT
The second moment is also important since it tells us how much
the transmission rate varies. Some applications (e.g., real time
multimedia flows) are sensitive to variations in transmission
rate. One could envisage to tune the flow control so that to reduce
these variations.
Define for Re(!) - 0 the LST (Laplace-Stieltjes Transform)
of the window size distribution by
Z M+
e \Gamma!x dF (x):
Taking LTs (Laplace Transforms) in (4) leads to:
ff
\Gamma-
Xn=1
\Gamman q n
\Gamman !)
Note that (12) holds in particular for limitation
on the window size, in which case
\theta

\theta

\Gamman !)
(\Gammafl \Gamman !) k
Substituting this in (12), using the absolute convergence of the
doubly-infinite series to interchange the order of summation and
Fig. 1. Area associated with a single loss
equating the coefficients of equal powers of ! we get, for
\theta

kff
\theta

from which the moments of the window size distribution can be
obtained recursively. In particular we find for 2:

\theta
These first two moments can be also obtained using direct argu-
ments, see Remarks 1 and 2 below. Such arguments were also
used by Misra et al. [15] for the case
ever, in their analysis an error appears which results in an additional
equation besides (14) and (15) from which they determine
an erroneous expression for the probability PM (see Remark 2).
Remark 1: The mean window size can be obtained by considering
the mean drift. The upward drift of the window
size is given by ffP fW ! Mg and the downward drift equals
\theta
. Equating these gives (14).
We can further derive E
applying an argument similar
to Little's law as was done by Misra et al. [15] for the case
1. For details we refer to [5]. The main idea
is sketched in the following. For the dual queueing model described
in Section II-C, we can equate the mean workload
with - times the mean area below U(t) 'induced by a single ar-
rival' (use that Poisson Arrivals See Time Averages). Back in
the original model, the 'mean surface' of the area above W (t)
in

Figure

The expected surface of the area 'induced' by a single loss
event (the surface of the larger triangle minus that of the smaller
one) is equal
\theta

Multiplying this by -, equating the result with
using indeed gives (15).
Remark 2: For a special case of our model, yet another way is
pursuit in [15] to derive (14) and (15). However, there, the final
result is incorrect due to a small error in an intermediate step.
\theta

d
dt
d
\theta

\theta

In steady state we have E [W
\theta W (t) 2
\theta

and PM (t) j PM . Substitution into the above gives
together with
\theta

Together with (14) this leads to (15). For the case
and N j 1, the formula given in [15] for E
\theta

(below
Formula (4) in that reference) differs from (16) by a factor
This resulted in a third (incorrect) equation
which is linearly independent of (14) and (15) from which
PM was determined simultaneously with
.
In Section V we show how PM can be determined correctly and
computed efficiently.
IV. WINDOW SIZE DISTRIBUTION FUNCTION
We find in this section the explicit expression of the cumulative
distribution of the window size. The distribution of the
transmission rate can be simply obtained by rescaling the window
axis by 1/RTT. We start first by the case of finite M .
We provide the expression of the distribution in every interval
for the case
we give an expression of the distribution for any x ? 0
as an infinite sum of exponentials.
A. Window distribution for finite M
For Equation (4) reduces to:
\Gammaff d
dx
hence,
To find the entire distribution we introduce, for
Equation (4) can now be written as:
d
dx
ff
Since F (x) is continuous for
F k is recursively given by
ff
u=x
ff u
We conclude from the above recursion that a solution to (19) and
(20) has the following form
To determine the coefficients c (k)
i , we substitute (21) into (19).
Then, equating terms with the same exponents, we get the following
recursive formula
Once the coefficients c (k)
are computed, the coefficient
1 can be determined from (20):
ff
c (k\Gamma1)
ff
ff
Note that to compute the coefficients c (k)
, we do not need PM .
Hence, using that F (x) is a complementary distribution func-
tion, PM is then determined by:
ff M=fl k\Gammai
However, this relation is not suitable to compute PM , see Re-mark
Remark 1: With (18) and (21) we have found an equilibrium
distribution function F (x) satisfying (4). By Theorem II.1 it
is the unique solution and, hence, the assumption that F (x) is
continuous for x ! M is justified.
Remark 2: Recursion (22) is suitable to determine the distribution
function on an interval M=fl k - x - M when k is not too
large. For large k the recursion may become instable, since it involves
subtraction of numbers of the same order. Therefore (24)
is not suitable to compute PM . In Section V below we derive
an alternative expression for PM , which leads to a numerically
stable and efficient algorithm to compute PM .
B. Window distribution for infinite M
In this case, the results derived in the previous subsection cannot
be applied immediately by letting M go to infinity. How-
ever, we can derive the LST of the window size distribution by
similar arguments. When
ff
\Gamman !)
or, equivalently,
ff
\Gamman !): (25)
Substituting the above equation repeatedly into itself l times,
applying partial fraction expansion at each step, and then taking
l !1, we conclude that -
f(!) can be expressed as follows:
for certain coefficients c i (this is formally justified later). To
determine the constants c we substitute (26) into
(25) and equate coefficients multiplying the terms 1=(!
This leads to the recursive formula
c i\Gammak
which determines the ratios c i =c 0 (it is for this reason that both
sides contain a factor 1=c 0 ). The coefficient c 0 follows from
It can be shown that the infinite series in the expression of c 0
converges and hence all the coefficients c i exist. The proof of
convergence is given in Appendix A. The inversion of (26) back
into the time domain gives:
with Given that the coefficients c i
exist, the above series is absolutely convergent for any value of
1). Thus, it is the unique solution to
For the case of no window size limitation and N j
F (x) was already obtained in [18].
V. THE PROBABILITY OF MAXIMUM WINDOW SIZE
In Sections III and IV we determined the window size distribution
and its moments in terms of PM . In this section we
derive an expression for PM from which it can be computed ef-
ficiently. For this we introduce the random variable T (x) which
is the time until the window size returns to the value x, starting
just after a loss event occurs with the window size being equal
to x 2 (0; M ]. We denote its expectation by E(x) := E [T (x)],
Then, from elementary renewal theory,
1=-
1=- +E(M)
We now proceed to find the function E(x). A typical evolution
of the window size is depicted in Figure 2. For simplicity in the
figure only loss events having are depicted. The times to
recover from losses are partly cut out of the picture (denoted by
the shaded areas).
Suppose for the moment that the initial loss (at the level x)
was such that (in the figure be the
time to get back at level x conditional on and we further
E(x) =X
x
Fig. 2. TCP window
If no losses occur during the time
\Gamman )x=ff, i.e., the window size x is reached in a straight line
from the starting point at fl \Gamman x (in the figure fl \Gamma1 x). Each time
a loss occurs at a level y 2 (fl \Gamman x; x) it takes T (y) time units
to get back at the level y. Because of the memoryless property
of the Poisson process, if we take out the shaded areas in Figure
2 and concatenate the non-shaded areas then the cut points
(where the shaded areas used to be) form a Poisson process on
the straight line from fl \Gamman x to x. Thus if the cut points are given
by (in the figure
\Gamman )x
Since the loss process is a Poisson process, the mean number
of cut points is \Gamman )x=ff and the position of each of the
points y j is uniformly distributed over the interval (fl \Gamman x; x),
see for instance [23, Thm. 1.2.5]. Hence,
\Gamman )x
ff
\Gamman x
E(y)
\Gamman )x
dy
\Gamman )x
ff
\Gamman x
E(y)dy: (32)
Using (1) and (31) we now arrive at
\Gamman x
E(y)dy: (33)
Although in the finite-window case (M ! 1) the above integral
equation has only meaning for it is well defined
for all x ? 0, and the solution to (33) is unique, see [5]. Define
the LT of E(x):
e \Gamma!x E(x)dx:
In [5] it is shown that - using
that the q n and E(x) are non-negative we may interchange the
order of integration and summation (twice), finally arriving at:
Repeated substitution of this equation into itself and applying
partial fraction expansion leads us to the following candidate
solution:
where the e i are constants to be determined. This representation
will be justified by showing that it leads us to the unique solutions
to (34) and (33). Substituting (35) into (34) and equating
the coefficients multiplying the terms 1=(fl
\Gamman q n
e i\Gamman
\Gamman q nX
We note that the ratios e i =e 0 are non negative and can be computed
recursively from (36). Then the normalizing constant
can be computed from (37).
From (36) it can be shown (by induction on i) that
that is, the e i decay exponentially fast in i as i !1. Therefore
the right hand side of (35) certainly converges for ! ? -=ff and,
from its construction, (35) is the solution to (34). By partial
fraction (35) can be rewritten as:
ff
Inverting this LT gives:
e
Using this in (30) we have
e
Note that because of (38) and
e
PM can be computed efficiently from (41).
VI. SPECIAL CASE: ONLY ONE CONGESTION SIGNAL PER
LOSS EVENT AND A
In this section we specify our results for the important particular
case of TCP flow control with only one division of the
window by a factor 2 at loss events. Namely, we take
and in the model
with peak rate limitation, see [15] for a similar model. In Section
VII-B we compare the results from this particular case of
our model to measurements from the Internet. We worked with
long distance connections where congestion signals rarely appear
in batches and where the process of loss events is close to
Poisson [4]. From (14) and (15) we obtain the expressions for
the first two moments of the window size distribution.
The throughput of TCP can be obtained from Equation (11).
The distribution function itself or the complementary distribution
function F (x) is computed successively on the intervals
using (21) with 2. Recursion
(22) reduces to
c (k\Gamma1)
and c (k)
1 is given by (23). When 1, the distribution function
is given by (29) with
and c 0 is given by (28).
Finally,
where the coefficients e i are given by
e
VII. MODEL VALIDATION
In this section we compare measurements from long distance
and long life TCP connections with the results of Section VI
limitation). Comparison of real measurements
with the model with clustered (batch) arrivals of congestion
signals is a topic of current research, see also Section
VIII.
Due to the large number of hops and the multiplexing of exogenous
traffic in network routers, the Poisson loss process assumption
is expected to hold on long distance connections [15].
Our TCP receivers implement the delay ACK mechanism [22]
and our TCP senders increase their windows in the congestion
avoidance mode by approximately one packet every window's
worth of ACKs. Thus, we take ff equal to 1=(2RTT ) [19]. First,
we show theoretically how the window size is distributed in the
stationary regime. Second, we compare our results to measurements
from the Internet.
A. Numerical results
Consider the case of a long TCP connection with packets of
size 1460 bytes and a constant RTT of one second. Using the
results of Section VI, we computed the cumulative distribution
function F (x) of the window size and its probability density
Probability Density Function
Window size (kbytes)515253545Average inter-loss time (s)0.050.150.250.350.45Fig. 3. Limited receiver window:
Probability Density Function
Window size (kbytes)
Fig. 4. Unlimited receiver window:
function f(x) for increasing values of the intensity of losses.
We consider the both cases
limited receiver window). In Figures 3 and 4 we plot our results
for the density function f(x). For the case Kbytes, we
computed the distribution function successively for the intervals
so on. In the case of an unlimited
receiver window, we used the expression of the density function
as an infinite sum of exponentials (Equation (29)). Note that
when solving numerically the model for the distribution, several
infinite series, e.g. (29) and (42), need to be computed. As
we discussed in previous sections, these infinite series converge
quite fast; so one needs to use only a small number of terms.
When Kbytes, the discontinuity of f(x) at
is clearly seen in Figure 3 (especially for large inter-loss times).
The pulse PM at is depicted by an area equal to PM .
When 1, the density function exhibits neither pulses nor
discontinuities (Figure 4).
B. Experimental results
Our experimental testbed consists of a long life and long
distance TCP connection between INRIA Sophia Antipolis
and Michigan State University (US). The TCP connection
is fed at INRIA by an infinite amount of data. The New
Reno version of TCP [8] is used for data transfer. We changed
the socket buffer at the receiver in order to account for different
values of M . We considered three values of M : 32, 48 and
Kbytes. For every value of M , we ran the TCP connection
window (bytes)
Cumulative Distribution Function
Model Measurements
Fig. 5. Receiver window
window (bytes)
Cumulative Distribution Function
Model
Measurements
Fig. 6. Receiver window
for approximately one hour and we registered the trace of the
connection using the tcpdump tool developed at LBNL [13].
We also developed a tool that analyzes the trace of the connection
and that detects the times at which the window is reduced.
Moreover, our tool gives the average RTT of the connection and
the statistics of the window per RTT. We compared for the three
values of M , the distribution of the window size from measurements
to that given by our model. The results are plotted in

Figures

5, 6 and 7.
When M is small, we observe a good match between the measured
distribution and the one resulting from our model. How-
ever, for larger values of M , the difference between the two in-
creases. In particular, as M increases, the measured probability
density concentrates around the average window size. This deviation
can be explained from the measured distribution of times
between loss events. First, we plot in Figure 8 the distribution
of inter-loss times for Kbytes. This distribution is in
agreement with an exponential law, resulting in a good match
between the model and the measurements. Figures 9 and 10
show the measured distributions for the other two values of M .
We observe that the loss process is no longer Poisson, but closer
to a deterministic process. Small inter-loss times are less frequent
as M increases, and the medium inter-loss times domi-
nate. This results in a degradation of the correspondence between
our model and the measurements.
One explanation of the deviation of the loss process from a
Poisson process for larger values of M is the following. A true
Poisson loss process implies that the time until the next loss
event is independent of the past. This is the case when the congestion
of the network is dominated by the exogenous traffic and0.20.610 10000 20000 30000 40000 50000 60000 70000
window (bytes)
Cumulative Distribution Function
Model
Measurements
Fig. 7. Receiver window
Probability
density
function
Exponential distribution
Measurements
Fig. 8. Case of
not dependent on the measured connection. Namely, when the
measured connection's share of the available bandwidth on the
path is small compared to that of the exogenous traffic. A small
M limits the bandwidth share of our connection and limits its
impact on the network, resulting in a loss process close to Pois-
son. However for large M , the measured connection realizes a
larger share of the bandwidth and thus contributes more to the
congestion of network routers. When it reduces its window, the
state of the network changes and becomes under-loaded. Some
time is needed for the network to be loaded again. This is the
reason for which small inter-loss times start to get small proba-
bilities. In such a case when the loss process is close to a deterministic
process, a simple fixed-point method as that proposed
in [3], [19] can be used to approximate the achieved throughput.
VIII. CONCLUSIONS AND FUTURE RESEARCH
We studied additive-increase multiplicative-decrease flow
control mechanisms under the assumption that congestion signals
arrive in batches according to a Poisson process. As high-lighted
in [15], the model can be reformulated as an M/G/1
queuing problem with service time dependent on system work-
load. We tried to keep the model as general as possible in order
to account for a wide range of congestion control strategies. We
calculated explicit expressions for the moments as well as the
distribution of the transmission rate (of the window size in case
of TCP). For the case of single congestion signals, we compared
our results to measurements from TCP connections over the In-
ternet. From our experiments, we concluded that our model
leads to accurate results when the times between losses are close
to being exponentially distributed.
Probability
density
function
Exponential distribution
Measurements
Fig. 9. Case of
Probability
density
function
Exponential distribution
Measurements
Fig. 10. Case of
Currently, we are working on the validation of our model
with clustered congestion signals. Our measurements over the
Internet have shown that on some paths especially short distance
ones, the loss process presents a high degree of burstiness.
We are currently also studying the extension of the analysis to
more general inter-loss time processes, in particular to MMPPs
(Markov Modulated Poisson Processes).

ACKNOWLEDGEMENT

We would like to thank V. M. Abramov for comments that
improved the presentation of the paper. Also, we thank the department
of Mathematics of Michigan State University and in
particular L.B. Freidovich for providing us with a computer account
for our Internet experiments.
A.



We shall prove here that the infinite series in Equation (28)
converges. Denote a i := c i =c 0 . Using (27), a i satisfies the
folowing recurrent relation
a
To prove that series
a i is absolutely convergent, it is enough
to prove that the majorant series
defined below, is
convergent.
Consider b i+1
Thus, b i+1 therefore, the series
(and hence
absolutely convergent for fl ? 1.



--R

The ATM Forum Technical Committee
"Investigation of a queueing system with service depending on queue length"
"TCP in presence of bursty losses"
"A stochastic model of TCP/IP with stationary random losses"
"State- dependent M/G/1 type queueing analysis for congestion control"
"A queueing system with queue length dependent service times, with applications to cell discarding in ATM networks"
"TCP and Explicit Congestion Notification"
"The NewReno Modification to TCP's Fast Recovery Algorithm"
"Assured Forwarding PHB Group"
"Congestion avoidance and control"
"Asymptotic Analysis of a state-dependent M/G/1 queueing system"
"A state-dependent GI/G/1 queue"

"The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm"
" Stochastic differential equation modeling and analysis of TCP-windowsize behavior"
"The Window Distribution of Multiple TCPs with Random Queues"
"On queues with dependent interarrival and service times"
"The stationary behavior of ideal TCP congestion avoidance"
"Modeling TCP Through- put: a Simple Model and its Empirical Validation"
" Single-server queues with service time dependent on waiting time"
"A Quantitative Study of Differentiated Services for the Internet"
Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms"
" Stochastic Models - An Algorithmic Approach"
--TR
Asymptotic analysis of a state-dependent <italic>M</>/<italic>G</>/1 queueing system
Congestion avoidance and control
TCP and explicit congestion notification
The macroscopic behavior of the TCP congestion avoidance algorithm
Modeling TCP throughput
TCP in presence of bursty losses

--CTR
Brbara Gonzlez-Arvalo, Performance of a Leaky Bucket System with Long-Range Dependent Input Traffic, Queueing Systems: Theory and Applications, v.46 n.3-4, p.439-459, March-April 2004
Carsten Burmeister , Ulrich Killat , Jens Bachmann, TCP over Rate-Adaptive WLAN - An Analytical Model and its Simulative Verification, Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks, p.339-348, June 26-29, 2006
Deb , R. Srikant, Rate-based versus queue-based models of congestion control, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
Gang Wu , Edwin K. P. Chong , Robert Givan, Predictive buffer control in delivering remotely stored video using proxy servers, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.18, p.3721-3742, 21 December 2006
state-dependent queue;control protocol;linear increase and multiplicative decrease;congestion control in data networks;transmission