CryptoDB
Throughput-Optimal Routing in Unreliable Networks
Authors: | |
---|---|
Download: | |
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. |
BibTeX
@misc{eprint-2010-23132, title={Throughput-Optimal Routing in Unreliable Networks}, booktitle={IACR Eprint archive}, 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}, url={http://eprint.iacr.org/2010/231}, note={ paulbunn@math.ucla.edu 14723 received 24 Apr 2010}, author={Paul Bunn and Rafail Ostrovsky}, year=2010 }