ADAPTIVE SOURCE ROUTING IN HIGH-SPEED NETWORKS

We study algorithms for adaptive source routing in high-speed networks , where some of the links are unreliable. Thus, the delivery of a sing le message to its destination may require trying several paths. Assumi ng a priori knowledge of the failure probabilities of links, our objec tive is to devise routing strategies which minimize the expected deliv ery cost of a single message. We describe optimal strategies for two c ases: a tree-like network and a general serial/parallel topology. Wher eas in the first case the greedy algorithm is shown to be optimal (i.e ., it is best to try the paths by decreasing order of their success pr obabilities), there is no simple decision rule for the second case. Ho wever, using some properties of serial/parallel graphs, we show that a n optimal strategy can be easily derived from a fixed sequence of path s. We give an algorithm, polynomial in the number of links, for findin g this sequence. For a general network, we show that the problem of de vising an optimal strategy can be solved in polynomial space and is #P -Hard, and that the minimal expected delivery cost in a given network is also hard to approximate. Finally, we show that for scenarios of ad aptive source routing, the common greedy strategy is not even a consta nt approximation to the optimal strategy. (C) 1996 Academic Press, Inc .