### 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Network RoutingFault LocalizationCommunication ComplexityEnd-to-End CommunicationCompetitive AnalysisAsynchronous Protocols
Contact author(s)
paulbunn @ math ucla edu
History
Short URL
https://ia.cr/2010/231

CC BY

BibTeX

@misc{cryptoeprint:2010/231,
author = {Paul Bunn and Rafail Ostrovsky},
title = {Throughput-Optimal Routing in Unreliable Networks},
howpublished = {Cryptology ePrint Archive, Paper 2010/231},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/231}},
url = {https://eprint.iacr.org/2010/231}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.