  We demonstrate the feasibility of end-to-end communication in highly
unreliable networks. 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.
  We present a robust routing protocol for end-to-end communication that is
simultaneously resilient to both forms of unreliability. In particular, we
prove rigorously that our protocol is SECURE against the actions of the corrupt
nodes, achieves correctness (Receiver gets ALL of the messages from Sender, in
order and without modification), and enjoys provably optimal throughput
performance, as measured using competitive analysis.
  Furthermore, our protocol does not incur any asymptotic memory overhead as
compared to other protocols that are unable to handle malicious interference of
corrupt nodes. In particular, our protocol requires O(n^2) memory per
processor, where n is the size of the network. This represents an O(n^2)
improvement over all existing protocols that have been designed for this
network model.

Networking and Internet Architecture