Asynchronous Throughput-Optimal Routing in Unreliable Networks.
Paul Bunn, Rafail Ostrovsky
Abstract:
We demonstrate the feasibility of throughput-efficient routing in a highly unreliable network. Modelling a network as a graph with vertices representing nodes and edges representing the links between them,we consider two forms of unreliability: unpredictable edge-failures, and deliberate deviation from protocol specification by corrupt nodes. The first form of unpredictability represents networks with dynamic topology, whose links may be constantly going up and down; while the second form represents malicious insiders attempting to disrupt communication by deliberately disobeying routing rules, by e.g.introducing junk messages or deleting or altering messages.We present a robust routing protocol for end-to end communication that is Simultaneously resilient to both forms of unreliability,achieving provably optimal throughout performance.
comment: ICALP 2010: 236-248
Fetch PDF file of the
Back to Publications
List