Rafail Ostrovsky - Publications

Asynchronous Throughput-Optimal Routing in Unreliable Networks.

Paul Bunn, Rafail Ostrovsky


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

[Abstract] [pdf]

Fetch PDF file of the paper

Back to Publications List