Premium
Routing in quasi torus networks
Author(s) -
Chen YaoMin,
Sasaki Galen H.
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199612)28:4<195::aid-net4>3.0.co;2-g
Subject(s) - network topology , torus , topology (electrical circuits) , computer science , routing (electronic design automation) , node (physics) , network packet , path (computing) , mathematics , computer network , combinatorics , engineering , geometry , structural engineering
A routing scheme is presented for a class of mesh topologies, which include tori and variations of tori. The variations model torus networks that have undergone topological perturbations. Such perturbations are due to addition and deletion of nodes, which may occur because of network failure and incremental network growth. Since the routing scheme is operable over a class of topologies, where addition or deletion of a node keeps a topology within the class, it is robust to incremental changes in network topology. In addition, it requires only minimal space and processing at the network nodes, which makes it suitable for high‐speed implementation. Its efficiency, in terms of path length taken by packets, is demonstrated through both computer simulation and mathematical analysis. The analysis uses a random topology model to show that for “typical” topologies the scheme routes packets along near‐optimum paths. © 1996 John Wiley & Sons, Inc.