An Efficient Adaptive Routing Algorithm for the Faulty Star Graph

Leqiang BAI  Hiroyuki EBARA  Hideo NAKANO  Hajime MAEDA  

IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.8   pp.783-792
Publication Date: 1998/08/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
star graph,  node-disjoint subgraph,  node-disjoint path,  fault-tolerance,  adaptive routing,  

Full Text: PDF(875KB)>>
Buy this Article

This paper introduces an adaptive distributed routing algorithm for the faulty star graph. The algorithm is based on that the n-star graph has uniform node degree n-1 and is n-1-connected. By giving two routing rules based on the properties of nodes, an optimal routing function for the fault-free star graph is presented. For a given destination in the n-star graph, n-1 node-disjoint and edge-disjoint subgraphs, which are derived from n-1 adjacent edges of the destination, can be constructed by this routing function and the concept of Breadth First Search. When faults are encountered, according to that there are n-1 node-disjoint paths between two arbitrary nodes, the algorithm can route messages to the destination by finding a fault-free subgraphs based on the local failure information (the status of all its incident edges). As long as the number f of faults (node faults and/or edge faults) is less than the degree n-1 of the n-star graph, the algorithm can adaptively find a path of length at most d+4f to route messages successfully from a source to a destination, where d is the distance between source and destination.