Reliable Single Message Transmission

Abstract

End-to-end communication considers the problem of sending messages from a sender S to a receiver R through an asynchronous, unreliable network, such as the Internet. We consider the specific problem of transmitting a single message from S to R through a network in which edges may fail, but cannot recover. We assume that there is at least one S,R-path without failing edges, but we do not know which path it is. Our aim is to design a protocol that ensures that a message sent by S will be received by R (no matter which edges fail) without generating an infinite number of messages in the process.

We characterize the family of networks in which this is possible in terms of forbidden rooted minors, and we give the protocol. We also show that there is a forbidden rooted minor characterization for the case when we can attach a header (containing routing information) of fixed length to the message and we discuss the algorithmic consequences of these characterizations.  Finally, we present recent work for the case that at most k edges can fail.

This is joint work with F. Fich, A. Kundgen, and R. Ramamurthi.