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.