Cryptology ePrint Archive: Report 2010/231

Throughput-Optimal Routing in Unreliable Networks

Paul Bunn and Rafail Ostrovsky

Abstract: 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.

Category / Keywords: cryptographic protocols / Network Routing; Fault Localization; Multi-Party Computation in Presence of Dishonest Majority; Communication Complexity; End-to-End Communication; Competitive Analysis; Asynchronous Protocols

Date: received 24 Apr 2010

Contact author: paulbunn at math ucla edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20100428:135410 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]