Interval routing & layered cross product: compact routing schemes for butterflies, meshes of trees, fat trees and Beneš networks
✍ Scribed by Tiziana Calamoneri; Miriam Di Ianni
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 291 KB
- Volume
- 63
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we propose compact routing schemes having space and time complexities comparable to a 2-interval routing scheme for the class of networks decomposable as layered cross product (LCP) of rooted trees. As a consequence, we are able to design a ''quasi'' 2-interval routing scheme (i.e. a 2-interval routing scheme plus a fast and small local algorithm) for butterflies, meshes of trees and fat trees. Then we show that a compact routing scheme for general networks which are LCP of cyclic graphs cannot be found by any method using only information about shortest paths on the factors. Nevertheless, we extend our scheme to Benesň etworks, although they cannot be decomposed as the LCP of trees.