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.