next up previous contents
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 $\pi(G)$ (respectively $\vec{\pi}(G)$), is the minimum, over all the routing functions R on G, of the edge-congestion (respectively arc-congestion) of R. Clearly, for every G, $\pi(G) \leqs 2
\vec{\pi}(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.


\begin{theorem}[\cite{CDSF98}]\mbox{}
\beginsmall{itemize}
\item For each fixed ...
... Note that
$\vec{\pi}(T_n) \approx 0.125n^3$.
\endsmall{itemize}
\end{theorem}

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


\begin{theorem}[\cite{RS97}]
\mbox{}
\beginsmall{itemize}
\item For every $n$-no...
...gestion is
$O(\pi(G))$\ and $k = O(\sqrt{n})$. \endsmall{itemize}
\end{theorem}




2000-03-21