ized. This paper studies how rapidly
routing can respond, without compromising stability.
We present a sucient condition for the local stability of
end-to-end algorithms for joint routing and rate control.
The network model considered allows an arbitrary intercon-
nection of sources and resources, and heterogeneous propa-
gation delays. The sucient condition we present is decen-
tralized: the responsiveness of each route is restricted by the
round-trip time of that route alone, and not by the round-
trip times of other routes. Our results suggest that stable,
scalable load-sharing across paths, based on end-to-end mea-
surements, can be achieved on the same rapid time-scale as
rate control, namely the time-scale of round-trip times.
Categories and Subject Descriptors
C.2.2 [Computer-Communication Networks]: Network
Protocolscongestion control, routing protocols
General Terms
Algorithms, Theory
Keywords
Internet, dynamic routing, scalable TCP
1.
INTRODUCTION
Historically, the primary purpose of IP routing has been to
maintain connectivity in the presence of topology changes
and network failures. IP routing typically chooses the short-
est path to the destination, based on simple metrics like hop
count or distance. While the simplicity of this approach has
made IP routing highly scalable, there has long been a desire
to improve the reliability and performance of the Internet
through the use of routing metrics that are more sensitive to
congestion [28]. More recently there has also been increas-
ing interest in multi-path routing, motivated by applications
to ad-hoc networks [4, 11] and overlay TCP [7], and by per-
ceived problems with current routing protocols [21, 29]. But
despite the potential advantages of dynamic routing, it has
in the past been dicult to deploy in packet-based networks
like the Internet because of potential instability, manifested
as routing oscillations [26].
In recent years theoreticians have developed a framework
that allows a congestion control algorithm such as Jacob-
sons TCP [9] to be interpreted as a distributed mechanism
solving a global optimization problem: for reviews see [12,
19, 20, 22]. The framework is based on uid-ow models,
and the form of the optimization problem makes explicit
the equilibrium resource allocation policy of the algorithm,
which can often be restated in terms of a fairness criterion.
And the dynamics of the uid-ow models allow the ma-
chinery of control theory to be used to study stability, and
to develop rate control algorithms that scale to arbitrary
capacities [14, 19, 22].
Han et al. [7] have used the framework to study multi-
path routing in the Internet. They have presented an al-
gorithm that can be implemented at sources to optimally
split the ow between each source-destination pair, and they
develop a sucient condition for the local stability of the al-
gorithm. The condition is decentralized in the sense that the
gain parameters for the routes serving a particular source-
destination pair are restricted by the round-trip times of
those routes, and not by round-trip times elsewhere in the
network.
In this paper we improve on this result, and present an al-
gorithm with a sucient condition for local stability that is
decentralized in the stronger sense that the gain parameter
for each route is restricted by the round-trip time of that
route, but not by the round-trip times of other routes, even
those other routes serving the same source-destination pair.
The novel feature of our scheme is that the control exerted
by a source over its available route ow rates is treated sim-
ilarly to link congestion feedback. This allows us to apply
established single-path techniques to our multi-path model.
The condition we derive is conceptually simpler than that of [7], and is less demanding in the case where the round-trip
times associated with a source-destination pair are highly
heterogeneous. The sucient condition is a generalization
of Vinnicombes [23] original condition for the single path
case, and depends explicitly on the fairness criterion imple-
mented by the algorithm. The sucient condition constrains
the speed of routing adaptation to essentially the same time-
scale as is allowed for rate control.
In this paper we are modelling networks with path diversity,
i.e. systems where at least some source-destination pairs
have access to two or more dierent routes. At the min-
imum, we assume that, for these source-destination pairs,
the source can send dierent ows addressed to the same
destination over dierent routes, for example, through dif-
ferent Internet service providers, or dierent initial wireless
links. We note that explicit support for edge routing is not
currently available in the Internet, but it is enough for our
purpose that by some means or other it is possible to create
some path diversity.
A helpful distinction, developed by Zhu et al. [29], is to
view routing information as separated into its structural and
dynamic components, the former being concerned with the
existence of links, and the latter with the quality of paths
across the network. We suppose that the routes available,
however discovered, are xed on the time-scale we are con-
sidering. Our focus in this paper is the stability or otherwise
of the systems response to dynamic information.
More formally, we suppose the network comprises an inter-
connection of a set of sources, S, with a set of resources,
J. Each source s
S identies a unique source-destination
pair. Associated with each source is a collection of routes,
each route being a set of resources. If a source s transmits
along a route r, then we write r
s. Likewise, if a route r
uses a resource j we write j
r. For a route r we let s(r)
be the (unique) source such that r
s(r). We let R denote
the set of all routes.
We make no assumptions about whether the routes r
s
are disjoint. Clearly the ability to generate resource disjoint
routes will assist in the construction of highly robust end-to-
end communication for the source-destination pair labelled
by s, but our model also covers the case where some or all
of the routes r
s share some path segments.
In our model a route r has associated with it a ow rate
x
r
(t)
0, which represents a dynamic uid approximation
to the rate at which the source s(r) is sending packets along
route r at time t.
For each route r and resource j
r, let T
rj
denote the
propagation delay from s(r) to j, i.e. the length of time it
takes for a packet to travel from source s(r) to resource j
along route r. Let T
jr
denote the propagation delay from
j to s(r), i.e. the length of time it takes for congestion
control feedback to reach s(r) from resource j along route
r. In the protocols we shall be considering, a packet must
reach its destination before an acknowledgement containing
congestion feedback is returned to its source. Further, we
assume queueing delays are negligible. Thus for all j
r,
T
rj
+ T
jr
= T
r
, the round trip time for route r.
Use the notation a = (b)
+
c
to mean a = b if c > 0 and
a = max(0, b) if c = 0.
We are now ready to introduce our uid-ow model of joint
routing and rate control:
d
dt x
r
(t) =
r
x
r
(t) 1
r
(t)
U
s
(r)
(y
s
(r)
(t))
+
x
r
(t)
(1)
where r
(t) =
jr
µ
j
(t
T
jr
),
(2)
µ
j
(t) = p
j
(z
j
(t)),
z
j
(t) =
r
:jr
x
r
(t
T
rj
)
(3)
and
y
s
(t) =
rs
x
r
(t
T
r
).
(4)
Here and throughout we assume that, unless otherwise spec-
ied, j ranges over the set J, r ranges over the set R, and s
ranges over the set S.
We motivate (1-4) as follows. The ow through resource j
at time t, z
j
(t), comes from routes r that pass through re-
source j; and the ow that resource j sees at time t on route
r left its source a time T
rj
earlier. If we suppose that re-
source j adds a price p
j
(z
j
) onto packets when the total ow
through resource j is z
j
, then we obtain (3). The total price
accumulated by a single packet on route r, and returned
to the source s(r) via an acknowledgement received at time
t, is given by (2). Finally (1) corresponds to a rate control
algorithm for the ow on route r that comprises two compo-
nents: a steady increase at rate proportional to
r
x
r
(t); and
a steady decrease at a rate depending upon both the price
signals arriving back from route r, and the total rate of ac-
knowledgements y
s
(r)
(t) over all routes serving the source
for route r. We shall see that the functions U
s
, s
S, ap-
pearing in (1) determine how resources are shared. And
later, in Section 3, we shall reinterpret p
j
as the drop or
mark probability at resource j rather than a price.
Although y
s
(t) can be interpreted as the rate of acknowl-
edgements received by source s, an alternative, and possibly
more practical, implementation of (4) would be that each
packet sent along a route r
s is marked with the ow rate
or window size for r at time of sending. The source then
computes y
s
(t), according to (4), from the values recorded
in returning acknowledgements. Later we shall consider an
alternative scheme, where each packet sent by s is marked
with the total ow rate over all r
s, and where, when an
acknowledgement packet is returned, x
r
is updated accord-
ing to
d
dt x
r
(t) =
r
x
r
(t)

1 r
(t)
U
s
(r)
as
(r)
x
a
(t
T
r
) +
x
r
(t)
;
(5)
here the sum
as
(r)
x
a
(t
T
r
) is just the total ow rate
recorded in a returning acknowledgement. We shall see that
this alternative scheme has similar stability properties as
those we prove for (1-4). Under mild assumptions we shall establish that the sys-
tem (1-4) is locally stable about an equilibriu