Technical Report CS0690

TR#:CS0690
Class:CS
Title: OPTIMAL STRATEGIES FOR SOURCE ROUTING IN A NETWORK WITH DEPENDENT PATHS
Authors: A. Itai and H. Shachnai
PDF - RevisedCS0690.revised.pdf
PDF - Revised againCS0690.revised2.pdf
Abstract: Algorithms for adaptive routing in a high speed network are examined. In such networks the intermediate nodes serve as switching elements with limited computational resources. The mode of operation is to specify an entire path from the source to the destination. If all the links of the path are nonfaulty then the message is transmitted; otherwise an indication is given to the first link that has failed. The source, upon learning of a failure, chooses another path and retransmits the message. The links of the network have independent a priori failure probabilities. The status of the links dose not change while attempting to transmit a message. First, the greedy algorithm (the algorithm which tries the paths in the order of increasing failure probability) is examined. It is shown to be optimal for a small class of networks, but not for all. The main result concerns series/parallel graphs, for which an optimal algorithm is presented. It is shown that an optimal algorithm can be easily derived from a fixed sequence of paths. Finally, an $O(|E|^{3})$ time algorithm to find this sequence is presented, $(|E|$ is the number of links in the network).
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0690), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion
admin