Interval Routing & Layered Cross Product:
Compact Routing Schemes for Butterflies,
Mesh of Trees and Fat Trees
T.Calamoneri and M.Di Ianni
Abstract
Several networks admit $k$-Interval Routing Schemes only for rather large values of $k$. In particular, it has been proved that butterflies admit $k$-Interval Routing Schemes only for $k \in \Omega ( \sqrt{n/ \log n})$. In this paper we propose compact routing schemes having space and time complexities comparable to a 2-Interval Routing Scheme for the whole class of networks decomposable as Layered Cross Product (LCP) of trees. As a consequence, we are able to design a "quasi" 2-Interval Routing Scheme for butterflies, meshes of trees and fat trees. We also show that a compact routing scheme for networks which are LCP of cyclic graphs cannot be found by any method using only information about shortest paths on the factors.
PDF Files