We study algorithms for adaptive source routing in high-speed networks, where some of the links are unreliable. Thus, the delivery of a single message to its destination may require trying several paths. Assuming a priori knowledge of the failure probabilities of links, our objective is to devise routing strategies which minimize the expected delivery cost of a single message. We describe optimal strategies for two cases: a tree-like network and a general serialrparallel topology.
Ε½ Whereas 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 probabilities , there is no simple decision rule for the second case. However, using some properties of serialrparallel graphs, we show that an optimal strategy can be easily derived from a fixed sequence of paths. We give an algorithm, polynomial in the number of links, for finding this sequence. For a general network, we show that the problem of devising 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 adaptive source routing, the common greedy strategy is not even a constant approximation to the optimal strategy.