Name
Title | ||
|---|---|---|
Interval routing & layered cross product: compact routing schemes for butterflies, meshes of trees, fat trees and Beneš networks |
Abstract | ||
|---|---|---|
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 networks, although they cannot be decomposed as the LCP of trees. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0743-7315(03)00110-2 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
layered cross product,butterfly,general network,compact routing scheme,rooted tree,fat tree,shortest path,mesh of trees,compact routing schemes,benes network,networks decomposable,beneš,2-interval routing scheme,interval routing,cyclic graph,time complexity | Discrete mathematics,Topology,Link-state routing protocol,Equal-cost multi-path routing,Multipath routing,Dynamic Source Routing,Computer science,Static routing,Parallel computing,Destination-Sequenced Distance Vector routing,Routing table,Distance-vector routing protocol | Journal |
Volume | Issue | ISSN |
63 | 11 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
1 | 0.37 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tiziana Calamoneri | 1 | 511 | 46.80 |
| Miriam di Ianni | 2 | 144 | 17.27 |