topology-based algorithms such as the Minimum
Hop (MH)
1
presently used in TCP/IP networks
[8,9]. For example in [1], the authors introduce the
bottleneck bandwidth as a metric and then define
the maximization of user throughput as optimi-
zation target. Similarly, in [2,3] the authors study
how to improve the throughput of high-bandwidth
traffic, such as large file transfers, in a network
where resources are fairly shared among connec-
tions. Their findings, obtained by simulation, show
that, at high loads, a MH routing algorithm
maximizes network and user performance; for
low-congested networks, instead, they propose an
algorithm, named Minimum Distance (MD)
routing, which offers better performance. However
they are unable to provide an algorithm that
merges the two behaviors. Researchers focused
their attention upon other aspects of QoS routing,
namely protocol overhead [5,7], implementation
issues [4,6], impact of update policies [5].
A major drawback, however, affects all QoS-
based routing algorithms. The cost function at the
core of the algorithms tries to find portions of the
network where resources are under-utilized and
exploits them to the benefit of connections that
would otherwise cross a congested portion of the
network. In doing so, as shown in [11] for the case
of simple alternate routing, the algorithm ends up
consuming more resources than MH routing does,
hence, in case of heavy congestion, QoS-based
routing wastes resources and performs poorly
compared with MH. A formal proof of this ob-
servation can be found in [10]. The extension of
this property to TCP/IP networks is not straight-
forward, since flows often exhibit a greedy, elastic
behavior, using up the available bandwidth. MH
routing has been already conjectured to be as-
ymptotically optimal as the load q offered to the
network tends to infinity, and many simulation
results confirm this intuition [2,3,13,16]. We stress
at this point that the poor performance of QoS-
based routing at high loads is not due to the sub-
optimality of the used algorithms, but is rooted in
the locality of the routing decision. Whenever a
call is routed, the given cost function is minimized/
maximized for the current state of the network,
necessarily disregarding the future network evo-
lution. Under heavy load, the overall network
benefit does not coincide with the cost function of
a single call, hence the minimization of the one
does not lead to the maximization of the other.
In the light of the above discussion, the draw-
back of QoS routing in the Internet is clear:
whatever is gained at low or medium network
loads, it is paid for at high network loads. What is
needed to solve this problem is a resilient algo-
rithm that allows the migration of a QoS-based
routing algorithm to MH routing as q grows large.
The problem is that q is typically not known to the
routing algorithm, not even in the case of cen-
tralized routing algorithms.
The contribution of this paper lies in the iden-
tification and definition of a class of routing algo-
rithms, named Network Graph Reduction (NGR),
whose performance encompasses that of QoS-
based routing algorithms at light and medium
loads, and the optimality of MH routing at high
loads. The goal is obtained by reducing the graph
that describes the network topology, and applying
a suitable metric to the reduced graph. Results are
reported showing both the elementary properties of
the algorithm, and its behavior in randomly gen-
erated topologies, both with uniform and non-
uniform, time-varying traffic.
The rest of the paper is organized as follows.
Section 2 provides a general description of the
NGR algorithm, along with implementation is-
sues. Section 3 presents the network and traffic
models used in the simulation presented in Section
4, in which the performance of the NGR algorithm
is compared to the one of classic QoS routing al-
gorithms, both in simple network scenarios, and in
more complex ones. Finally, conclusions and fu-
ture work are discussed in Section 5.
2. NGR routing algorithms
Routing can be formalized as the problem of
finding a suitable set of edges connecting two
nodes in a directed graph. QoS routing relies on
the definition of a suitable edge metric w, which
1
In this paper we refer to the MH algorithm as a special case
of the Shortest Path, in which all links have unitary costs.
476 C. Casetti et al. / Computer Networks 41 (2003) 475–487