Routing in Unreliable Networks.
Abstract
Consider strategies for selecting message routes in unreliable data communication networks. The following assumptions are made: the nodes of the network are perfectly reliable; the links are unreliable, and for each link l there is a probability P sub l, where 0 < P sub l <1 is a rational number, that the link is operative; links fail independently of each other. We focus on approaches that use two transmission paths simultaneously to transfer a message, maximizing the probability that at least one of the copies of the message arrives at the destination node. The intent is to trade increased use of network resources for a lowered transmission delay. Different versions of this problem; in one version one of the paths is fixed, and we are asked to find a second one that results in maximum message reception probability; in another version we look for two link disjoint path that maximize the same objective as before; in the third version we dispense with the disjointedness restriction of the previous problem. Complex ity results are given for these problems and solution techniques proposed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1986
- Accession Number
- ADA170736
Entities
People
- Isidro M. Figueredo
Organizations
- Massachusetts Institute of Technology