AN EFFICIENT ADAPTIVE ROUTING ALGORITHM FOR THE FAULTY STAR GRAPH

This paper introduces an adaptive distributed routing algorithm for th e faulty star graph. The algorithm is based on that the n-star graph h as uniform node degree n - 1 and is n- 1-connected. By giving two rout ing rules based on the properties of nodes, an optimal routing functio n for the fault-free star graph is presented. Far a given destination in the n-star graph, n-1 node-disjoint and edge-disjoint subgraphs, wh ich are derived from n - 1 adjacent edges of the destination, can be c onstructed by this routing function and the concept of Breadth First S earch. When faults are encountered, according to that there are n - 1 node-disjoint paths between two arbitrary nodes, the algorithm can rou te messages to the destination by finding a fault-free subgraphs based on the local failure information (the status of all its incident edge s). 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 a daptively find a path of length at most d + 4f to route messages succe ssfully from a source to a destination, where d is the distance betwee n source and destination.