Window flow control in FIFO networks with cross traffic.
We focus on window flow control as used in packet-switched  communication networks. The approach consists in studying the stability of a  system where each node on the path followed by the packets of the controlled  connection is modeled by a FIFO  queue of infinite capacity which receives in addition some cross traffic  represented by an exogenous flow. Under general stochastic assumptions, namely  for stationary and ergodic input processes, we show the existence of a maximum  throughput allowed by the flow control. Then we establish bounds on the value  of this maximum throughput. These bounds, which do not coincide in general, are  reached by time-space scalings of the exogenous flows. Therefore, the  performance of the window flow control depends not only on the traffic  intensity of the cross flows, but also on fine statistical characteristics such  as the burstiness of these flows. These results are illustrated by several  examples, including the case of a nonmonotone, nonconvex and fractal stability  region.
Introduction
Flow control mechanisms are used in packet-switched communication networks to prevent
routers from congestion, by regulating the input traffic generated by the users. The most
widely used mechanism is the window flow control, like that of TCP (Transmission Control
Protocol) over the Internet [7]. This mechanism consists in limiting the number of packets
in transit in the network to a given value called the window. The focus of this paper is
not on the window dynamics of TCP, which was studied in [10, 14, 15] in cases where
the connection consists of a single bottleneck link, but rather on the network dynamics. In
particular, we assume that the window either stabilizes as in TCP Vegas [6] or varies very
slowly compared to the time-scale of a packet, so that it can be considered as static, and
we evaluate in this case the effect of cross traffic on the performance of the flow control, in
terms of utilization of the network resources.
The main difficulty which arises in the analysis of current communication networks
is that the traffic may exhibit periodicity [8] and long-range dependence [16] which are
not captured by traditional Markovian models [11, 13]. In addition, it turns out that in
the particular case of window flow control, the throughput of the controlled connection
depends in a crucial way on fine statistical characteristics of the cross flows, and not only
on their traffic intensity. In [1], bounds on the performance of window flow control are
obtained in cases where the interaction with cross traffic may be modeled by so-called
service curves. Here we model the cross traffic at each node of the network by an exogenous
flow with general statistical assumptions, namely by a stationary and ergodic marked point
process. The reference model on which the analysis is based consists of a series of FIFO
queues in tandem. More general network topologies including multicast connections and/or
propagation delays are also considered along the same lines.
The paper is organized as follows. The model, its dynamics and its basic monotonicity
properties are described in Section 2. In Section 3, we present the stochastic framework of
the analysis and investigate the stability region of the model, that is the conditions under
which the system admits a finite stationary regime. In particular, we show that there exists
a maximum arrival rate of the packets below which the system is stable, and we refer to this
value as the maximum throughput of the connection. In Section 4, we establish bounds on
the maximum throughput, and show that these bounds which do not coincide in general, are
reached by time-space scalings of the exogenous flows. The results obtained are illustrated
by several examples in Section 5, including the case of a non-monotone, non-convex and
fractal stability region. Section 6 concludes the paper.
RR n 3434
4 F. Baccelli, T. Bonald
Model
2.1 Window flow control
The connection involves two users, referred to as the source and the destination. The source
sends data packets to the destination, which sends back an acknowledgment to the source
each time it receives a packet. The window flow control consists in limiting the number of
packets the source can consecutively send without waiting for any acknowledgment, to a
given value K called the window. Incoming packets that exceed the capacity of the window
are buffered at the source in the input queue until a new acknowledgment is received.
In the reference model, the path followed by the packets and the acknowledgments of
the controlled connection consists of N stations in tandem. The first stations represent the
forward path followed by the packets sent from the source to the destination, and the last
stations represent the reverse path followed by the acknowledgments sent back from the
destination to the source. No difference will be made between the forward and the reverse
path in the following, and we will simply refer to a packet of the controlled connection and
its acknowledgment as a controlled customer. Note that the number of controlled customers
in the network (excluding the input queue) is always limited by the window K . Each station
receives in addition a flow of cross customers which leave the network after the completion
of their service. At each station, all customers are served at unit rate by a single server under
the global FIFO discipline. All queues are of infinite capacity.
A
B1 B2 BN

Figure

1: Reference model
The reference model with a window of packets is shown in Figure 1 (in all
figures, controlled customers are in black and cross customers in white). More general
models including multicast connections and/or propagation delays are also considered along
the same lines (see Appendix B).
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 5
2.2 Dynamics
n be the arrival point process of the controlled customers, and B
the arrival point process of the cross customers at station i, with the usual conventions
1 .
We denote by ff i
n and U i
n the service time and the departure time of the n-th controlled
customer at (from) station i, and by fi i
n the service time and the departure time of
the n-th cross customer at (from) station i. Denoting by U 0
n the departure time of the n-th
controlled customer from the input queue (or equivalently its arrival time in the network), it
follows from the window flow control mechanism that
In addition, by the workload equation of a FIFO queue, we get for all
uU
and
where we use the convention that, when a cross customer and a controlled customer arrive
at a given station at the same time, the controlled customer is served first. We denote by
n the departure point processes of the controlled customers
from the input queue and from station i, respectively.
2.3 Monotonicity
For all k  l 2 Z, let A [k;l] be the [k; l]-restriction of A, that is the arrival point process
defined by T 0
We denote by D [k;l]
N the corresponding departure point processes. When k ! l,
we also define
The same notations are used for the corresponding departure point processes. The following
monotonicity property is crucial for the rest of the analysis.
RR n 3434
6 F. Baccelli, T. Bonald
A be any other arrival point process of controlled customers, and let ~
be the corresponding departure point processes. We have for all k  l 2 Z,
A [k;l] OE ~
A [k;l] =)
where we use the notation fT n g n OE f ~
to mean T n  ~
Proof. In view of (1), we have
so that
It follows then from (2) that
From (1), we get
and the proof follows by induction. 2
Remark 1 This monotonicity property does not hold with respect to the cross traffic flows.
Consider the case
2. Let
the cross customers leave the network at times f1; 5g,
and when the cross customers leave the network at times
In the rest of the paper, we denote by X 0 (t) and X i (t) the number of controlled customers
in the input queue and in station i at time t, respectively. We also denote by Y i (t) the
number of cross customers in station i at time t. By convention, these processes are taken
right-continuous with left-hand limits. Let Z i (t) be the cumulative number of controlled
customers in all stations up to i at time t, that is
At any time t, we have
and for all k  l 2 Z, denote by Z [k;l] (t) the value
of Z(t) when the arrival point process of the controlled customers is the restricted point
process A [k;l] . Lemma 1 admits the following key corollaries.
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 7
Corollary 1 For all k  l 2 Z, we have component-wise,
Proof. The proof follows from the fact that A [k;l] OE A [k\Gamma1;l] and from Lemma 1. 2
From Corollary 1, we can then define a function fZ(t)g by
For the following corollaries, we assume that there exists  ? 0 such that
lim
Corollary 2 Let ~
n be another arrival point process such that the associated
function f ~
Z(t)g is finite. Let
~
then the function fZ(t)g is also finite.
Proof. For any t 2 R, let m be the index of the last controlled customer arrived before time
t, namely
there exists l  m such that for all k  l,
A [k;l] OE ~
and it follows from Lemma 1 that
Hence,
so that the finiteness of f ~
Z(t)g implies that of fZ(t)g. 2
In the rest of the paper, we say that the system is saturated when the arrival point process
of the controlled customers is
RR n 3434
8 F. Baccelli, T. Bonald
Corollary 3 Denote by U n the departure time of the n-th controlled customer from the
input queue when the system is saturated. Let
lim
Proof. Denote by
DN the departure point processes associated with
A. It follows
from the definition of
A that for all k  l 2 Z,
A [k;l] OE A [k;l] ;
so that from Lemma 1,
In particular,
lim sup
denotes the sequence of points of D [1;+1)
lim
Z [1;+1)
and the result follows from (4) and Corollary 1. 2
The following lemmas show that the departure point processes D are also
monotone in the service times of the controlled customers and in the service times of the
cross customers, as well as in the window K . As immediate corollaries, the function fZ(t)g
is also monotone in the same quantities.
DN be the departure point processes associated with the system
where the service times of the controlled customers fff 1
are changed into
the sequences f~ff 1
We have for all k  l 2 Z,
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 9
Proof. In view of (1), we have
It follows then from (2) that
and from (1),
The result follows by induction. 2
DN be the departure point processes associated with the system
where the service times of the cross customers
are changed into the sequences
f ~
Z(t)g denote the corresponding queue size function.
We have, for all k  l 2 Z,
Similarly
Proof. The proof is exactly the same as that of Lemma 2. 2
Lemma 4 Let ~
DN be the departure point processes associated with the system
where the window is ~
K instead of K , and let f ~
Z(t)g be the associated queue size function.
We have, for all k  l 2 Z,
In addition
Proof. In view of (1), we have
~
It follows then from (2) that
and from (1),
~
The result follows by induction 2
RR n 3434
F. Baccelli, T. Bonald
3 Stability and maximum throughput
In this section, we first present the stochastic framework of the analysis. The reader is
referred to Appendix A for the main definitions and for the properties of stationary and
ergodic point processes to be used in the following. By means of a Loynes' scheme [12],
we then use the monotonicity property established in Section 2 to construct a stationary
regime for the queueing process
Finally, we prove the existence of a maximum throughput allowed by the flow control, that
is a maximum arrival rate of the controlled customers below which the system is stable.
3.1 Stochastic framework
The arrival times and the service times of the controlled customers are defined on a probabilit

equipped with an ergodic, measure-preserving flow f' A (t)g t2R .
We assume that the point process A is simple, ' A (t)-compatible, and admits fff n
as sequence of marks. We denote by  its finite and non-null intensity,
and by (A; ff) the corresponding stationary and ergodic marked point process. Let IP 0
A be
the Palm probability associated with A. We assume that the mean service time of the controlled
customers at station i, defined by ff
A (ff i
0 ), is finite and non-null. We denote
by
i the service rate of the controlled customers at station i.
The arrival times and the service times of the cross customers are defined on another
probability
equipped with an ergodic, measure-preserving flow
We assume that the point processes are simple, ' B (t)-compatible,
and admit respectively
as sequences of marks. Thus the corresponding
marked point processes are assumed to be jointly stationary and
ergodic. When the finite intensity  i of B i is non-null, we denote by IP 0
the associated
Palm probability and assume that the mean service time of the cross customers at station i,
defined by fi
0 ), is finite and non-null. The traffic intensity of the cross flow at
station i is then defined by ae We assume that
The controlled flow is assumed to be independent of the cross flows. In particular, the
probability space considered in the following is the product
defined by
\Omega =\Omega A
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 11
We define a flow f'(t)g t2R on this space by This flow is
measure-preserving but not necessarily ergodic. In the following, we say that a stochastic
process is stationary if it is compatible with the flow f'(t)g.
3.2 Construction of the minimum stationary regime
Let fZ(t)g be the stochastic process defined by (5). By construction, this process is compatible
with the flow f'(t)g.
Lemma 5 The process fZ(t)g is component-wise a.s. finite or a.s. infinite.
Proof. From (4), the '(t)-compatible process fZ(t)g is a.s. finite if and only if the random
variable a.s. finite. From the monotonicity property of Lemma 1, we have
is the number of points of A between 0 and t. Hence, defining for any fixed
2\Omega B the event
we get ' A (t)F A ae FA for all t  0. It follows then from the ergodicity of (IP A ; ' A (t)) that
IP A 1g. The mapping
defines a random variable
But by the same argument as above,
so that  It follows then from the ergodicity of (IP that
is IP B -a.s. constant, and
The result follows then from Fubini Theorem since
Z\Omega
A
Z\Omega
I fZ(!A ;! B )!1g IP A (d! A )IP B (d! B );
Z\Omega
Z\Omega
A
I fZ(!A ;! B )!1g IP A (d! A )
Z\Omega
12 F. Baccelli, T. Bonald
Corollary 4 Since the discrete flow f' n
A g n associated with the point process A is ergodic
on the Palm probability
A ) (see

Appendix

A), the result of Lemma 5 also
holds on the Palm probability
respect to A, given by
A
A \Theta FB ) and IP
Lemma 6 The process fZ(t)g is the minimum stationary regime of fZ(t)g.
Proof. Assume that there exists a finite stationary regime f ~
Z(t)g of fZ(t)g, and denote by
~
DN the corresponding departure point processes. For any k 2 Z, we get from (1),
so that from (2),
and by induction,
Therefore,
and the proof follows from the fact that this inequality holds for all k 2 Z. 2
Lemma 7 There exists a finite stationary regime for the queueing process fQ(t)g if and
only if the process fZ(t)g is a.s. finite.
Proof. If there exists a finite stationary regime for the queueing process fQ(t)g, there exists
also a finite stationary regime for fZ(t)g, and it follows from from Lemma 6 that fZ(t)g
is a.s. finite. Conversely, assume that the process fZ(t)g is a.s. finite. We can then define
a finite stationary queueing process fX (t)g for the controlled customers by X 0
and
DN be the associated '(t)-compatible departure point processes. In view of
(3), we can then construct the associated '(t)-compatible departure point processes of the
cross customers fV 1
n g, and define a finite stationary queueing process fY(t)g
by
I fT i
Window Flow Control in FIFO Networks with Cross Traffic 13
Remark 2 It follows from the '(t)-invariance of the probability measure IP that when the
process fZ(t)g is a.s. infinite, the number of customers in the input queue tends in probability
to infinity, that is component-wise,
Z [1;+1) (t) IP
3.3 Maximum throughput
In the following, we say that the system is stable if there exists a finite stationary regime for
the queueing process fQ(t)g. From Lemma 7, the finiteness of fZ(t)g provides a necessary
and sufficient condition for the stability of the system. Note that since the process fZ(t)g is
f'(t)g-compatible, its finiteness under the probability measures IP and IP 0 are equivalent.
In particular, the stability region of the system depends on the controlled flow only through
its distribution under IP 0 . Theorem 1 below which is the central result of the paper, shows
that the stability region is actually insensitive to the distribution of the interarrival times of
the controlled customers, and depends on the point process A only through its intensity .
Theorem 1 (Maximum throughput) There exists a constant
, which only depends on
the law of the cross flows under IP B and on the law of the service times of the controlled
customers under IP 0
A , and such that the system is stable whenever  !   and unstable
In this sense,   is the maximum throughput of the controlled flow.
Proof. The proof is given in the Palm setting, that is on the probability
defined Corollary 4. For any  ? 0, denote by fZ  (t)g the minimum stationary regime
obtained when the arrival point process of the controlled customers is the periodic point
process A We know from Corollary 4 that the process fZ  (t)g is either a.s.
finite or a.s. infinite. Define
and
set is empty. In view of Corollary 2, the process fZ  (t)g is a.s. finite for
all  ?   .
If  ! 1, then there exists  ?   such that  ! 1. From Corollary 2, the finiteness of
the process fZ  (t)g implies that of fZ(t)g. On the other hand, if  ? 1, then there exists
such that  ? 1. Assume that the process fZ(t)g is finite with strictly positive
probability. Then from Corollary 2, the process fZ  (t)g is also finite with strictly positive
probability, so that it is finite with probability 1, and
, a contradiction. 2
RR n 3434
14 F. Baccelli, T. Bonald
Remark 3 In view of the proof of Theorem 1, the result still holds if the controlled flow is
not independent of the cross flows under IP, provided that the service times of the controlled
customers are independent of the cross flows under IP 0 .
Remark 4 When the measure-preserving flow f' B (t)g is not ergodic with respect to IP B ,
Theorem 1 still applies, except that the maximum throughput
is no more a constant but
that is the system is stable on the
event
(!B )g and unstable on the event f ?
(!B )g. This case is illustrated by an
example in Section 5.
In the rest of the section, we assume that the service times of the controlled customers
are deterministic. We show that in this case, the maximum throughput of the controlled
flow is equal to the departure rate of the controlled customers from the input queue when
the system is saturated, i.e. when the arrival point process of the controlled customers is
given by
A. Thus the stability condition of the system is given by the so-called saturation
rule, although the system does not enter the monotone-separable framework of [5].
Theorem 2 (Saturation rule) Assume that the service times of the controlled customers
are deterministic and denote by U n the departure time of the n-th controlled customer from
the input queue when the system is saturated. We have
lim
a.s.
where   is the maximum throughput defined in Theorem 1.
Proof. Since the service times of the controlled customers are deterministic, fU n g n1 is
a functional of the cross traffic only, so that the reference probability space is actually
Denote by D(t) the number of points of fU n g n1 between 0 and t. Using
the fact that U it follows from the monotonicity property of
Lemma 2 that
From Kingman's subadditive ergodic theorem [9], there exists a constant  such that
lim
and we know from Corollary 3 that    .
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 15
Now using the same notations as in the proof of Theorem 1, let  be any fixed constant
such that  !
\Gamma1 . In view of the definition of
, the process fZ  (t)g associated with
A  is a.s. infinite. Define
I fX ((n+1))=0g ; 8t  0;
where [x] denotes the integer value of x and X  (t) is the number of controlled customers
in the input queue at time t when the arrival point process is fng n0 . In view of Remark
2, we have
\Gamma!
so that
lim
0:
Denote by A  (t) the number of points of A  between 0 and t and define another arrival
point process by
A
where ff 1 is the (non-null) service time of the controlled customers at station 1. By con-
struction, the input queue is then never empty at any time t  0, so that
A  (t)  D(t):
Therefore, using the fact that
lim
A  (t))
A  (t)
we get  \Gamma1  . Since this inequality holds for any  !   \Gamma1 , we obtain
. 2
Corollary 5 Assume that service times of the controlled customers are deterministic. If
there exists a stationary regime for the saturated system, that is a ' B (t)-compatible arrival
process of the controlled customers ~
defined on the probability space
such that the departure time of the n-th controlled customer is equal to
~
then the intensity of ~
A is equal to
.
RR n 3434
F. Baccelli, T. Bonald
Proof. Denote by ~  the intensity of ~
A. By the definition of
A, we have
A OE ~
A, so that by
Lemma 1, the corresponding departure point processes from the input queue satisfy
D.
But since the arrival time ~
T n of the n-th controlled customer corresponds to the departure
time of the (n \Gamma K)-th controlled customer, it follows from (1) that ~
A. Using Theorem
2, we obtain ~    .
Now define for all n 2 Z,
~
Y (\Gamma1;n]
Y (\Gamma1;n] (t)g is the queueing process of the cross customers obtained when the arrival
point process ~
A is restricted to (\Gamma1; n]. Since
there exists a.s. m  0 such that ~
n be the point process defined
by "
otherwise, and denote by "
U n g n the
corresponding departure point process from the input queue. By construction, we know
from Theorem 2 that
lim
From the monotonicity property of Lemma 1, we get ~
A and ~
D, so that ~
. 2
4 Bounds on the maximum throughput
In this section, we establish an upper bound and a lower bound on the maximum throughput
of the controlled flow, as defined in Section 3. Then we show that these bounds which
coincide only when there is a single bottleneck in the network, are tight in the sense that
both are reached by time-space scaling of the cross flows.
4.1 Upper bound
The upper bound is obtained by comparing the model with systems where the controlled
customers leave each station earlier. We first use the monotonicity of the departure times of
the controlled customers in the service times of the cross customers, then the monotonicity
of these departure times in the window K .
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 17
System without cross flows
The system without cross flows, obtained by reducing the service times of the cross customers
to zero, can be represented by a Petri network, as shown in Figure 2. This Petri
network is an event graph, the dynamics of which can be represented by linear equations
in the (max,+)-algebra (see [4]). Since this system depends on the marked point process
ff) only, which is compatible with the ergodic shift f' A (t)g on the probability space
necessary condition for the stability of this (max,+)-linear system is that
(K);
where (K) denotes the inverse of the associated Lyapunov exponent.

Figure

2: System without cross flows
Remark 5 By definition, (K) is given by the departure rate of the customers when the input
of the system is saturated [2]. In the case of deterministic service times of the controlled
customers, we get
From Lemma 3, a necessary condition for the stability of the original system is given by
System without flow control
The system without flow control, obtained by letting the window K tend to infinity, is shown
in

Figure

3. A necessary condition for the stability of this system is given by the usual traffic
conditions, namely
RR n 3434
F. Baccelli, T. Bonald
A

Figure

3: System without flow control
From Lemma 4, this provides a necessary condition for the stability of the original
system, so that
min
Remark 6 The value of this upper bound can be viewed as the so-called available band-width
of the controlled connection. It is then natural to define the utilization of the network
resources as the ratio
=, where
4.2 Lower bound
In the following, we denote by the stationary workload
process of the system in the absence of controlled customers, and define
Note that, since the input processes of the cross flows are not necessarily mutually indepen-
dent, we can have which corresponds to cases where the system is never empty.
The lower bound is obtained by comparing the system with that obtained when the
cross customers have a global preemptive priority (GPP) over controlled customers. That
is, whenever a cross customer arrives in any station of the network, the services of all
controlled customers present in the network are preempted, and can only restart when there
are no more cross customers in the network.
System under the GPP service discipline
It is easy to check that Lemma 1, Corollary 1 and Lemmas 5-6 hold under this service
discipline, so that we can define the corresponding minimum stationary regime f ~
Z(t)g .
Lemma 8 We have Z(t)  ~
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 19
Proof. Denote by ~
n g, the departure point processes of the
controlled customers under the GPP service discipline. As under this service discipline, a
controlled customer can be served at station i only if all cross customers and all controlled
customers arrived before itself in station i have been served, we get
U
m: u ~
U
U
U
Hence if for some p 2 Z, we have ~
U
n , for all n  p, we obtain
U
m: u ~
U
m: U
U
and it follows from (2) that ~
n , for all n  p.
Now let k  l 2 Z be fixed. From (1),
so that from the above property,
and by induction,
The result follows from the definition of the processes fZ(t)g and f ~
Z(t)g. 2
Lemma 9 Assume that fl ! 1. If  ! (K)(1 \Gamma fl), the system under the GPP service
discipline is stable, that is there exists a finite stationary regime for the associated queueing
process f ~
Q(t)g.
Proof. Since under the GPP service discipline, the cross customers have preemptive priority
over the controlled customers, there exists a unique '(t)-compatible process f ~
Y(t)g for the
number of cross customers in each station, and it is enough to show the finiteness of the
process f ~
Z(t)g.
RR n 3434
20 F. Baccelli, T. Bonald
Denote by fA(t)g the counting process associated with A such that
~
A be the point process associated with the counting process f ~
A(t)g, defined by
where
ae
Z uI fW(0)=0g ds
oe
Note that this point process is not necessarily simple. The stochastic process defined by
(5) for the system without cross flows, and with the arrival point process ~
A is given by
f ~
Z('(t))g. Applying the saturation rule of [5], a sufficient condition for this process to
be finite is that the intensity of ~
A is smaller than the departure rate of the customers in the
associated saturated system, namely (K). But since fl ! 1, we have
a:s:
\Gamma!
and noting that
Z '(t)I fW(0)=0g
if follows from the ergodicity of f' B (t)g that
a:s:
In particular,
~
a:s:
Thus if  ! (K)(1 \Gamma fl), the process f ~
Z(t)g is a.s. finite. 2
From Lemmas 8 and 9, a sufficient condition for the stability of the original system
(under the FIFO service discipline), is that  ! (K)(1 \Gamma fl). Therefore,
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 21
4.3 Tightness of the bounds
From (6)-(7) and (8), the constants
and
respectively provide an upper and a lower bound on the maximum throughput of the controlled
connection. It is not difficult to see that these bounds coincide if and only if ae i ? 0
for at most one i, say j, and In particular,  so that the
station j is the bottleneck of the connection, in the following strong sense:
. In the absence of cross customers, the maximum throughput of the connection is
given by the service rate  j at station j. In particular, increasing the window K has
no effect on this maximum throughput;
. No station except station j receives a cross flow.
In this case, the maximum throughput of the controlled connection is equal to the available
bandwidth as defined in Remark 6, that is
Remark 7 The single station case case where the bounds always co-
incide. This is not surprising since the model can then be seen as a single G/G/1 queue with
two types of customers, the controlled customers and the cross customers, and a conservative
service discipline which depends on the type of customers present in the queue. Such a
system is known to be stable when ae ! 1 and unstable when ae ? 1, where
is the total traffic intensity of both flows.
In the general case, the bounds do not coincide. In fact, we will show that in the case of
deterministic service times of the controlled customers, the upper bound on the maximum
throughput is reached when the cross flows are scaled in time and space by a factor which
tends to zero, so as to get fluid flows. Then we show that the lower bound is reached when
this scaling factor tends to infinity, so as to get bursty flows.
For any c ? 0, we denote by fW(c; t)g the stationary workload process of the system
without controlled customers, and where the cross flows are scaled by a factor c, namely
the arrivals on station i take place at times fcT i
and the corresponding service times
are fcfi i
. Note that the scaled cross flows are compatible with the measure-preserving,
ergodic flow f' B (c;
c
g, and that
c
RR n 3434
22 F. Baccelli, T. Bonald
System with asymptotically fluid cross flows
When the scaling factor c tends to zero, a direct application of the pointwise ergodic theorem
shows that the cross traffic workload arriving to station i in the interval (0; t], namely
I f0!cT i
c
I f0!T i
tends a.s. to tae i , so that the cross flows tend to be fluid. Theorem 3 below states that,
provided that the service times of the controlled customers are deterministic, the maximum
throughput of the controlled connection will then tend to the upper bound  max .
For sake of completeness, but also to facilitate the reading of the proof of Theorem 3,
we first study the limiting case where the cross flows are fluid. The dynamics of the system
is then given by (1) and
m: U
The monotonicity properties of 2.3 still hold. Using this, we show the existence of a
maximum throughput as in Theorem 1, and also that this maximum throughput is smaller
than  max , as in 4.1.
If the service times of the controlled customers are deterministic, the maximum
throughput of the controlled connection with fluid cross flows is equal to  max .
Proof. First note that in view of (9) and Remark 5,
and denote by ~
A the arrival point process with points fng n . In view of
Corollary 2, it is sufficient to show that the (deterministic) process f ~
Z(t)g associated with
~
A is finite to conclude the proof. We denote by ~
DN the departure point processes
associated with ~
A, and by oe i the cumulative service time of the controlled customers up to
station i, namely
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 23
In view of (2 0 ), using the fact that we have for any k 2 Z,
But since ~
it follows from (1) that
~
By induction, we get for all k  l 2 Z,
Thus using (4),
Z [k;l]
Z [k;l]
Z [k;l]
The result follows from the fact that these inequalities hold for all k  l 2 Z. 2
Remark 8 When the service times of the controlled customers are not deterministic, the
maximum throughput of the controlled connection in the presence of fluid cross flows is not
equal to  max in general.
Now we consider the original system with (discrete) cross flows scaled in time and space
by a factor c, and study the behavior of the corresponding maximum throughput  (c) when
c tends to zero.
Theorem 3 If the service times of the controlled customers are deterministic, the maximum
throughput of the controlled connection tends to its maximum value  max when the cross
flows are scaled in time and space by a factor which tends to zero, that is
lim
Proof. The proof is given on the probability
fixed
constants such that  max ? 1 and "oe N !  . For any c ? 0, define the event
f
Z oe
oe
I fW i (c;t)=0g dt  ff
RR n 3434
F. Baccelli, T. Bonald
are the cumulative service times of the controlled customers as defined
above. Let ~
A be the point process defined by the associated counting process
~
I F (c) ffi '(n):
We denote by f ~
Z(t)g the associated process defined by (5) and by ~
DN the corresponding
departure point processes. By the same inductive argument as that used in Lemma
10, we get for all k  l 2 Z,
By choosing " small enough, so that
the system without cross flows, with arrival point process ~
A and deterministic service times
"), is stable, and the corresponding departure point processes are
given by ~
"). The number of customers in this system
is bounded by K at any time t, so that
Z [k;l]
This inequality holds for all k  l 2 Z, which implies the finiteness of the process f ~
Z(t)g.
In addition, since the discrete flow f'(n)g n is measure-preserving, there exists an
random variable ~
(c) such that
~
a:s:
\Gamma! ~ (c) when t ! \Sigma1;
and the expectation of ~ (c) which is the same under IP and under IP 0 , is given by
From Corollary 2, we have ~ (c)
(c) a.s. and in particular,
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 25
But since
c
Z c( \Gamma"oe
by fixing " enough such that
it follows from the ergodicity of the flow f' B (t)g that
lim
Therefore,
lim inf
(c)
The result follows from the fact that these inequalities hold for all  such that  max ? 1. 2
System with asymptotically bursty cross flows
When the scaling factor c tends to infinity, the cross flows become more bursty, and we will
show that in this case, the maximum throughput of the controlled connection tends to the
lower bound  min .
We first consider the limiting system. On the event fW(0) 6= 0g, using the fact that a.s.
no cross customer arrives in the system at time 0, we have for some i,
c
so that the maximum throughput is equal to 0. On the complementary event
using the fact that a.s. no cross customer leaves the system at time 0, we have for all i
c
so that the maximum throughput is that of the (max,+)-linear system of 4.1, that is (K).
So the limiting system is intrinsically non-ergodic, with expected maximum throughput
To prove Theorem 4 below, we need the following technical result.
RR n 3434
26 F. Baccelli, T. Bonald
Lemma 11 For any b ? 0, let  b (K) be the inverse of the Lyapunov exponent associated
with the system without cross flows, where the service times of the controlled customers are
changed into the ' n
A -compatible sequences fff 1
I fff N n bg g n . We have
lim
Proof. By monotonicity, we have
Denote respectively by U n and U b
n the departure time of the n-th controlled customer from
the input queue, when the systems (without cross flows) with original service times and
with service times changed into fff 1
I fff N n bg g are saturated. Since
we have in view of Remark 5, b (K)
A (ff i
The result follows then from the fact that, by dominated convergence,
A (ff i
I fff i?bg 0:Theorem 4 The maximum throughput of the controlled connection tends to its minimum
value  min when the cross flows are scaled in time and space by a factor which tends to
infinity, that is
lim
Proof. Denote by S i
n respectively the beginning and the end of service of the n-th
cross customer at station i in the original system without controlled customers. When the
cross flows are scaled in time and space by the factor c, the beginning and the end of service
of the n-th cross customer at station i occur at times cS i
n and cV i
For a fixed b ? 0, consider the system where the input queue is saturated (i.e. the arrival
point process of the controlled customers is
A), the service times of the controlled customers
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 27
are given by fff 1
I fff N n bg g n , the arrival times of the cross customers are
given by fcT 1
service times are recursively defined by
ae
where ~
n denotes the beginning of service of the n-th cross customer at station i in this
system, namely if ~
g, denote the corresponding departure
point processes of the controlled customers,
~
m1: u ~
U
~
Denote by ~
n the departure time of the n-th cross customer from station i in this system.
For all n  0, we have ~
n , and for all n  1,
~
so that for all n 2 Z,
~
Therefore, ~
n for all n 2 Z, and from Corollary 3, using the monotonicity properties
of Lemmas 2 and 3, we get
(c)  ~
~
In addition, since the number of controlled customers in this system is always bounded
by K , we get for all
~
In particular, no controlled customer is served at station i in any interval (possibly empty)
of the form
RR n 3434
28 F. Baccelli, T. Bonald
Now consider the same system but without cross flows, and where the services of all controlled
customers are preempted at any time t such that
Denoting by ~
D the departure point process of the controlled customers from the input queue
in this system, we have ~
. The number of points of ~
between 0 and t is given by
where D(t) is the number of controlled customers which leave the input queue for the same
system but without preemption, and /(t) is the cumulative time during which the controlled
customers are not preempted between time 0 and t. Noting that the process fV(t)g defined
on the probability
I fcS i
is compatible with the flow f' B (t)g, we get
a:s:
Defining  b (K) as in Lemma 11, we obtain
~
a:s:
Therefore,
(c)  ~
(c)   b (K)
and since
I fS
we obtain by dominated convergence,
min  lim sup
(c)   b (K)
The result follows from Lemma 11 by letting b tend to infinity. 2
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 29
5 Examples
In all examples studied below, the number of stations is and the window is
The service times are deterministic, unless specified all equal to 1, i.e. ff 1
Z. The arrival process of the cross customers at station 1 is
periodic, with period   1. More precisely, we denote
space defined as
1 is the interval (0;  ], F 1 is the trace of the Borel oe-field on
\Omega 1 and IP 1 is the uniform measure
. The point process
defined by
Note that B 1 is ' 1 (t)-compatible, where f' 1 (t)g is the measure-preserving and ergodic
flow defined on this space by
In the following, we consider different point processes B 2 , and we use the saturation
rule of Theorem 2 to derive the maximum throughput
of the controlled flow. Note that
this maximum throughput does not depend on the arrival process of the controlled customers
(see Theorem 1). In particular, we do not specify the point process A, which can be any
stationary and ergodic point process in view of Remark 3.
5.1 Non-monotonic, non-convex and fractal stability region
In this example, B 2 is the null point process. We consider the saturated system, that is the
system where the arrival point process of the controlled customers is
A, and evaluate the
departure rate of the controlled customers, which coincide with the maximum throughput
. We distinguish between three cases, depending on the value of the integer value [ ] of  .
Case
We will show that station 1 is never empty in this case, so that the departure rate of the
controlled customers is simply given by
Assume that station 1 is empty at some time t ? 0. The controlled customer which is in
station 2, began its service at station 1 after time no later than time 1. Hence, the
cross customer arrived in station 1 between time t \Gamma  and time t, cannot have been served
before this controlled customer: This cross customer is in station 1 at time t, a contradiction.
RR n 3434
F. Baccelli, T. Bonald
Case [ even

Figure

4: Case [
As illustrated in Figure 4, the saturated system reaches a periodic steady state of period
. Since [ ]=2 controlled customers leave the system each period of time  , we get
Case [

Figure

5: Case [
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 31
Let p be the smallest integer q such that [q ] is even. We have
As illustrated in Figure 5, the saturated system reaches a periodic steady state of period p .
Since [p ]=2 controlled customers leave the system each period of time p , we get
Stability region
The stability region obtained, as well as the bounds on the maximum throughput, given in
view of (9) by
min =2
are shown in Figure 6. Note that the maximum throughput   is not monotone in the intensity
1 of the cross flow. In particular, an increase of the intensity  1 of the cross flow, may result
in an increase of the maximum throughput   of the controlled connection. Consider for
instance the case where the arrival point process of the controlled customers is of intensity
0:45. The system which is unstable when  stable when
This unexpected behavior is a consequence of the non-monotonicity of the system with
respect to the cross traffic (see Remark 1).
In addition, the maximum throughput   as a function of  1 is neither convex nor con-
tinuous. The upper bound is reached when2
whereas the lower bound is "almost" reached, when
Finally, the restriction of stability region to the region R such that which is
invariant by the similarity of center (0; 1=2) and ratio restricted to R, is fractal.
Remark 9 Due to the convention that when a controlled customer and a cross customer
arrive at a given station at the same time, the controlled customer is served first (see 2.2),
the maximum throughput
as a function of  1 is left-continuous with right-hand limits.
With the converse convention, this function would have been right-continuous with left-hand
limits.
RR n 3434

Figure

Stability region
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 33
In the two following examples, the service times of the cross customers are taken equal
to =2, i.e. fi 1
and  is supposed to be larger than 2.
5.2 Non-mutually independent cross flows
be the periodic point process defined by
The point processes B 1 and B 2 are ' 1 (t)-compatible on the probability
but not mutually independent.
Figure

7: Non-mutually independent cross flows
As illustrated in Figure 7, the saturated system reaches a periodic steady state, where
one controlled customer leaves the system each period of time  , so that
In particular, this maximum throughput tends to zero when  tends to infinity, although the
traffic intensities of the cross flows remain constant, equal to ae
This result is not surprising in view of Theorem 4, since in the absence of
controlled customers, the system is never empty, so that lower bound is equal to
RR n 3434
34 F. Baccelli, T. Bonald
5.3 Non-jointly ergodic cross flows
which a flow f' 2 (t)g similar to f' 1 (t)g
is defined. Let B 2 be the point process defined on the probability
in the
same way as B 1 is defined
Note that the point processes B 1 and B 2 are
mutually independent on the product
defined by
but not jointly ergodic on this space since the joint flow (t)g is not
ergodic. In this case, the maximum throughput is no more a constant but a random variable
(see Remark 4).

Figure

8: Cross flows "in phase"
We consider cases where
As illustrated by Figures 8 and 9 in the case the saturated system reaches a periodic
regime of period  . The number l of controlled customers which leave the system each
period of time  depends on the sample path
2\Omega , and can take any value in
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 35

Figure

9: Cross flows "out of phase"
the finite set Lg. More precisely, defining \Delta! as the unique element of the interval
we get
Therefore, there is a spectrum of L possible values for the maximum throughput of the controlled
flow, depending on the relative phases of the cross flows. Noting that the probability
of the event is zero, we have a.s.
and
2l
RR n 3434
36 F. Baccelli, T. Bonald
Remark 11 In this non-ergodic case,  min which is equal to
provides a lower bound on the expected maximum throughput. In particular, Theorem 4
takes here the form
lim
6 Conclusion
The performance of the window flow control in terms of maximum throughput of the controlled
connection depends in a crucial way on the characteristics of the cross flows. A first
surprising result is that this maximum throughput is neither monotone nor convex in the
traffic of the cross flows. In particular, the performance of the flow control can improve
when the intensity of the cross flows increases, or when these cross flows become more
ae

Figure

10: Effect of randomization
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 37
To illustrate this latter fact, consider the model of 5.1, where the periodic cross flow
is replaced by a renewal point process with interarrival times uniformly distributed on the
shows how the
maximum throughput as a function of the traffic intensity of the cross flow
"smoothed" when, starting from the periodic case the randomization factor e takes
the values 0:05, 0:1 and 1. These results were obtained by simulation of the associated
saturated system, by a QNAP program available in [17].0.250.750 0.25 0.5 0.75 1
Upper Bound
Lower Bound
ae

Figure

11: Impact of the burstiness of the cross flows
Another interesting result is that the maximum throughput of the controlled connection
is very sensitive to the burstiness of the cross flows. Consider for instance the case where
the cross flows are independent Poisson processes with deterministic service times equal to
ae. If the service times of the controlled
customers are deterministic and equal to 1, and the window is the upper bound and
the lower bound on the maximum throughput of the controlled flow are respectively given
by
RR n 3434
38 F. Baccelli, T. Bonald
We have shown (see Theorems 3 and 4) that   tends to these bounds when b tends to
zero and to infinity, respectively. This is illustrated by the simulation results of Figures 11
and 12, where the maximum throughput   and the utilization
are represented as
functions of the traffic intensity of the cross flows ae, for different values of b (see [17] for
the corresponding QNAP program). Thus when the cross flows consist of a fluid stream of
small packets (generated by Telnet connections for instance), the utilization of the network
resources by the controlled connection, given in view of Remark 6, by
is very close to its maximum value U when the cross flows consist of a
bursty stream of large packets (generated by batch arrivals of packets due to scene changes
in a video sequence for instance), the utilization of the network resources is close to its
minimum value
min
U min
ae
U

Figure

12: Utilization of the network resources
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 39
In particular, the effect of bursty cross flows on the performance of the controlled connection
grows with the number of nodes N on the round-trip path followed by the packets of the
controlled connection.
It is worth noting that these essential features of the window flow control are not captured
by models with a single bottleneck, for which the utilization of the network resources
is always equal to 1, and the maximum throughput of the controlled connection is simply
given by the available bandwidth on the (single) shared link.

Acknowledgements

. The authors would like to thank S. Foss for fruitful discussions on
the present paper, and in particular for having suggested Remark 4.


Appendix

A gives the main definitions on stationary and ergodic point processes used
in this paper. For a more complete presentation on the subject, we refer the reader to [3].


Appendix

extends the results obtained in this paper to more general models, including the
presence of propagation delays or the case of a multicast connection for instance.
A Stationary and ergodic point processes
IP) be a probability space, on which a flow f'(t)g t2R is defined:
(i) (t; !) ! '(t)! is measurable with respect to
B(R)\Omega F and F ,
(ii) '(t) is bijective for all t 2 R,
be a point process defined on the probability
the usual convention T 0  We assume that A
is simple, that is IP(T Z. For any sample path !
2\Omega , we
denote by A(!; C) the number of points of A belonging to the Borel set C . We say that A
is compatible with the flow f'(t)g, if
When the flow f'(t)g is measure-preserving, that is IP IP for all t 2 R, the point
process A is stationary. The intensity of A is then defined by
RR n 3434
If  is finite and non-null, we can define the Palm probability associated with A by
I F ffi '(t) A(dt)
Note that IP 0 (T
then a discrete measure-preserving flow f' n g n2Z on the
Palm probability
We say that a sequence of random variables fff n g n2Z on the probability
is a sequence of marks for A, if
Any sequence of marks of A (e.g. the interarrival times fT is stationary on the
Palm probability
since it is compatible with the discrete flow f' n g.
The flow f'(t)g is ergodic if for all F 2 F ,
In this case, we know from Birkhoff Ergodic Theorem that for any random variable X
defined on the probability
The ergodicity of f'(t)g with respect to IP implies the ergodicity of the discrete flow f' n g
with respect to IP 0 (the converse is also true), so thatN
Hence, for any f' t g-compatible process fX(t)g, that is
the expectation of X(0) under the Palm probability IP 0 is the empirical average of fX(t)g
at events, or event average, whereas the expectation of X(0) under IP is the usual time
average of this process.
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 41
B Extensions to more general models
Our structural results do not depend on the topology of the network provided that in the
absence of cross flows, the system is a single-input FIFO event graph [4]. In particular,
these results apply in the presence of deterministic propagation delays d
the stations, or in the case of a multicast connection where the data packets are duplicated
at some routers on the forward paths from the source to the destinations, and the acknowledgments
aggregated at some other routers on the reverse paths from the destinations to the
source. The corresponding models and the underlying event graphs are shown in Figures
13 and 14.
d2 d N
B1 B2 BN
A
d1 dN
d2

Figure

13: Model with propagation delays
RR n 3434
42 F. Baccelli, T. Bonald
BN
BN \Gamma2
A
BN

Figure

14: Multicast connection
INRIA
Window Flow Control in FIFO Networks with Cross Traffic 43



--R

Performance bounds for guaranteed and adaptive services
Ergodic theory of stochastic Petri networks
Elements of Queueing Theory
Synchronization and Lin- earity
On the saturation rule for the stability of queues
Vegas: End to end congestion avoidance on a global Internet
Internetworking with TCP-IP (Volume <Volume>I</Volume>) : principles
On traffic phase effects in packet-switched gateways
Subadditive ergodic theory
Performance analysis of window-based flow control using TCP/IP: The effect of high bandwidth-delay products and random loss
Optimal flow control of a class of queueing networks in equilibrium
The stability of queues with non independent inter-arrival and service times
Asymptotically optimal design of congestion control for high speed data networks
Window size behavior in TCP/IP with constant loss probability
Some observations on the dynamics of a congestion control algorithm

http://www.
--TR

--CTR
Franois Baccelli , Dohy Hong, TCP is max-plus linear and what it tells us on its throughput, ACM SIGCOMM Computer Communication Review, v.30 n.4, p.219-230, October 2000
Franois Baccelli , Dohy Hong, Interaction of TCP flows as billiards, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.841-853, August 2005
Vinod Sharma , Punyaslok Purkayastha, Stability and Analysis of TCP Connections with RED Control and Exogenous Traffic, Queueing Systems: Theory and Applications, v.48 n.3-4, p.193-235, November-December 2004
multiclass networks;stationary ergodic point processes;window flow control;+-linear system;stability;TCP