Paper 2010/231

Throughput-Optimal Routing in Unreliable Networks

Paul Bunn and Rafail Ostrovsky


We demonstrate the feasibility of throughput-efficient routing in a highly unreliable network. Modeling 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 specifications 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 throughput performance. Our proof proceeds in three steps: 1) We use competitive-analysis to find a lower-bound on the optimal throughput-rate of a routing protocol in networks susceptible to only edge-failures (i.e. networks with no malicious nodes); 2) We prove a matching upper bound by presenting a routing protocol that achieves this throughput rate (again in networks with no malicious nodes); and 3) We modify the protocol to provide additional protection against malicious nodes, and prove the modified protocol performs (asymptotically) as well as the original.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Network RoutingFault LocalizationCommunication ComplexityEnd-to-End CommunicationCompetitive AnalysisAsynchronous Protocols
Contact author(s)
paulbunn @ math ucla edu
2010-04-28: received
Short URL
Creative Commons Attribution


      author = {Paul Bunn and Rafail Ostrovsky},
      title = {Throughput-Optimal Routing in Unreliable Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2010/231},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.