Routing with packet duplication and elimination in computer networks

Packet duplication is discussed as a means of increasing network reliability in an environment where packet loss exists. Several methods of routing the duplicates are presented, one of which-the st-numbering-is shown to have the combined advantage of using disjoint paths and more even utilization of network resources. An additional mechanism, deliberate packet elimination, is introduced as a means of controlling congestion that may result, in part, from the duplication. A comprehensive model is defined encompassing the process of packet duplication together with both forms of packet elimination. Within this model, a cost function based on average packet delay is defined. A quasi-static distributed algorithm is developed that is optimal, deadlock free, and loop free. Extension of the model to include packet retransmission is considered