OPTIMAL TWO-COPY ROUTING SCHEME IN A COMMUNICATION WORK.

Abstract

The authors consider a static routing problem in a network with failure-prone links. Two copies of each externally generated message are sent from the source to the destination along two disjoint paths with the objective of reducing the delay resulting from retransmissions of unsuccessful packets. They formulate an optimal-routing problem using a suitable delay function. This results in a nonlinear programming problem of minimizing the delay over routing assignment under certain constraints. Specifically, they impose a disjoint-path constraint on the route assignment. This nonlinear program is solved by an iteration method incorporating a combinatorial algorithm. The solution converges to the global minimum for a convex objective function over a convex feasible region.