Routing in unreliable networks
Castiñeyra Figueredo, Isidro Sánchez Marcos · 1986
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.