International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Throughput-Optimal Routing in Unreliable Networks

Authors:
Paul Bunn
Rafail Ostrovsky
Download:
URL: http://eprint.iacr.org/2010/231
Search ePrint
Search Google
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
}