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

Journal Version

Conference Version