TR#: | CS0690 |

Class: | CS |

Title: | OPTIMAL STRATEGIES FOR SOURCE
ROUTING IN A NETWORK WITH DEPENDENT PATHS |

Authors: | A. Itai and H. Shachnai |

PDF - Revised | CS0690.revised.pdf |

PDF - Revised again | CS0690.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). |

Copyright | The 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