Adaptive source routing in high-speed networks

The authors study algorithms for adaptive source routing in high speed networks, where some of the links are unreliable. Thus, the delivery of a single message towards its destination may require trying several paths. Assuming an a priori knowledge of the failure probabilities of links, the objective is to devise routing strategies which minimize the expected delivery cost of a single message. They describe optimal strategies for two cases: a tree-like network and a general serial/parallel graph. 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 serial/parallel graphs they show, that an optimal strategy can be easily derived from a fixed sequence of paths. They give an algorithm, polynomial in the number of links, for finding this sequence. For a general network they 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, they show, that for scenarios of adaptive source routing, the common greedy is not even a constant approximation to the optimal strategy