Throughput-Optimal Routing in Unreliable Networks

We demonstrate the feasibility of throughput-ecient routing in a highly unreliable net-work. 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 specications by corrupt nodes. The rst form of unpre-dictability represents networks with dynamic topology, whose links may be constantly going up and down; while the second form represents malicious insiders attempting to disrupt communi-cation 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 nd 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 ma-licious nodes); and 3) We modify the protocol to provide additional protection against malicious nodes, and prove the modied protocol performs (asymptotically) as well as the original