We introduce the game-theoretic stochastic routing (GTSR) framework, a proactive alternative to today's reactive approaches to route repair. GTSR minimizes the impact of link and router failure by 1) computing multiple paths between source and destination and 2) selecting among these paths randomly to forward packets. Besides improving fault tolerance, the fact that GTSR makes packets take random paths from source to destination also improves security. In particular, it makes connection eavesdropping attacks maximally difficult as the attacker would have to listen on all possible routes. The approaches developed are suitable for network layer routing, as well as for application layer overlay routing and multipath transport protocols such as the stream control transmission protocol (SCTP). Through simulations, we validate our theoretical results and show how the resulting routing algorithms perform in terms of the security/fault-tolerant/delay/throughput trade-off. We also show that a beneficial side effect of these algorithms is an increase in throughput, as they make use of multiple paths.

This paper describes a technique to reduce the computational complexity of max-flow routing, based on a hierarchical decomposition of the network. The computational complexity of this hierarchical max-flow routing is comparable to that of Dijkstra's and Bellman-Ford's algorithms. It is shown that in many of today's networks, this hierarchical approach provides nearly the same performance as flat (i.e., non-hierarchical) routing, with significantly less computation.

Most standard implementations of TCP perform poorly when packets are reordered. In this paper, we propose a new version of TCP that maintains high throughput when reordering occurs and yet, when packet reordering does not occur is friendly to other versions of TCP. The proposed TCP variant, or TCP-PR, does not rely on duplicate acknowledgments to detect a packet loss. Instead, timers are maintained to keep track of how long ago a packet was transmitted. In case the corresponding acknowledgment has not yet arrived and the elapsed time since the packet was sent is larger than a given threshold, the packet is assumed lost. Because TCP-PR does not rely on duplicate acknowledgments, packet reordering (including out-of-order acknowledgments) has no effect on TCP-PR performance. Through extensive simulations, we show that TCP-PR performs consistently better than existing mechanisms that try to make TCP more robust to packet reordering. When the case that packets are not reordered, we verify that TCP-PR maintains the same throughput as typical implementations of TCP (specifically, TCP-SACK) and shares network resources fairly.

Shortest path routing leaves connections at risk of interception and eavesdropping since the path over which data packets travel is fairly predictable and easy to determine. To improve routing security, we propose a proactive mechanism, which we call secure stochastic routing, that explores the existence of multiple routes and forces packets to take alternative paths probabilistically. We investigate game theoretic techniques to develop routing policies which make interception and eavesdropping maximally difficult. Through simulations, we validate our theoretical results and show how the resulting routing algorithms perform in terms of the security/delay/throughput trade-off. We observe that a beneficial side-effect of these algorithms is an increase in throughput, as they make use of multiple paths. The Internet was designed to use redundancy to enhance reliability. We suggest that, through stochastic methods, redundancy be used to increase security.