Graph Minors and Reliable Single Message Transmission
by
Michael Pelsmajer
University of Illinois at Urbana-Champaign
Coauthors: Andre Kundgen (California State University at San Marcos), Faith E Fich (University of Toronto), Radhika Ramamurthi (University of Illinois at Urbana-Champaign)

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 SR-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 describe progress on characterizing 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. We also discuss the algorithmic consequences of these characterizations.

Date received: April 19, 2001