ROUTING IN HYPERCUBE NETWORKS WITH A CONSTANT FRACTION OF FAULTY NODES Academic Article uri icon

abstract

  • We consider routing in hypercube networks with a very large number (i.e., up to a constant fraction) of faulty nodes. Simple and natural conditions are identified under which hypercube networks with a very large number of faulty nodes still remain connected. The conditions can be detected and maintained in a distributed manner based on localized management. Efficient routing algorithms on hypercube networks satisfying these conditions are developed. For a hypercube network that satisfies the conditions and may contain up of 37.5% faulty nodes, our algorithms run in linear time and for any two given non-faulty nodes find a routing path of length bounded by four times the Hamming distance between the two nodes. Moreover, our algorithms are distributed and local-information-based in the sense that each node in the network knows only its neighbors' status and no global information of the network is required by the algorithms.

published proceedings

  • Journal of Interconnection Networks

author list (cited authors)

  • CHEN, J., WANG, G., & CHEN, S.

citation count

  • 6

complete list of authors

  • CHEN, JIANER||WANG, GUOJUN||CHEN, SONGQIAO

publication date

  • September 2001