摘要: We survey in this paper the classical results, and also most recent field of Interval Routing, a well-known strategy to code compact way distributed routing algorithms. These results are classified several themes: characterization, compactness shortest path, dilation stretch factor, specific class graphs (interconnection networks, bounded degree, planar, chordal rings, random graphs, etc.), other extensions proposed literature: dead-lock free, congestion, non-deterministic, problems related Routing. For each these themes we review state art propose open problems.
elsevier.com
sci-hub.se 参考文章(68)
Peter Thompson, David May, Transputers and routers: components for concurrent machines OUG-13 Proceedings of the 13th Occam user group technical meeting on Real-time systems with transputers. pp. 215- 231 ,(1990)
H. Hofestädt, A. Klein, E. Reyzl, Performance benefits from locally adaptive interval routing in dynamically switched interconnection networks EDMCC2 Proceedings of the 2nd Euronean Conference on Distributed Memory Computing. pp. 193- 202 ,(1991) , 10.1007/BFB0032936
Marshall Hall, Combinatorial Theory, 2nd Edition ,(1967)
Enrico Nardelli, Michele Flammini, On the path length in interval routing schemes ,(1997)
Ton Kloks, Treewidth: Computations and Approximations ,(1994)
Johan Vounckx, J. A. Peperstraete, Geert Deconinck, Rudy Lauwereins, Fault-Tolerant Compact Routing Based on Reduced Structural Information in Wormhole-Switching Based Networks. Proceedings 1ste Colloqium on structural information and communication complexity. pp. 125- 148 ,(1994)
Lata Narayanan, Naomi Nishimura, Interval Routing on k -trees. SIROCCO. pp. 104- 118 ,(1996)
Rastislav KráĽovič, Branislav Rovan, Peter RuŽička, Daniel štefankovič, Efficient Deadlock-Free Multi-dimensional Interval Routing in Interconnection Networks international symposium on distributed computing. pp. 273- 287 ,(1998) , 10.1007/BFB0056489
J. van Leeuwen, R.B. Tan, Routing with compact routing tables Unknown Publisher. ,(1983)
T. Eilam, S. Moran, S. Zaks, A Simple DFS-Based Algorithm for Linear Interval Routing international workshop on distributed algorithms. pp. 37- 51 ,(1997) , 10.1007/BFB0030674