** Next:** Interval Routing for Distributed
** Up:** Variations on the Interval
** Previous:** Deadlock-Free Interval Routing Schemes
** Contents**

##

Congestion of Interval Routing

The *edge-congestion* of a routing function *R* is the maximum,
taken over all edges, of the number of routing paths using the same
edge. Similarly, the *arc-congestion* of *R* is the maximum
number of routing paths using the same arc. The *edge-forwarding
index* (respectively *arc-forwarding index*) of *G*, denoted
by
(respectively ), is the minimum, over all
the routing functions *R* on *G*, of the edge-congestion (respectively
arc-congestion) of *R*. Clearly, for every *G*,
.
See [HMS89] for an introduction. The
edge/arc-congestion of an IRS is the edge/arc-congestion of its
induced routing function. The first study of congestion of Interval
Routing appears in [CDSF98] where they show several results for
specific topologies like trees, *d*-dimensional grids, and chordal
rings.

Congestion of Interval Routing is treated also in [RS97] for
arbitrary graphs.

*2000-03-21*