In folded cube computer network, we developed a new algorithm for fault-tolerant routing which is based on detour and backtracking techniques. Its performance is analyzed in detail in the presence of an arbitrary number of components being damaged and derived some exact expressions for the probability of routing messages via optimal paths from the source to obstructed node. The probability of routing messages via an optimal path between any two nodes is a special case of our results, and can be obtained by replacing the obstructed node with the destination node. It is also showed that in the presence of component failures this algorithm can route messages via an optimal path to its des tination with a very high probability.
展开▼