This project focuses on developing multipath routing mechanisms to achieve enhanced robustness and performance in large-scale, heterogeneous internetworks. Specifically, our goal is to make use of the inherent redundancy exhibited by data networks, i.e., the availability of multiple routes between pairs of nodes. We name our approach "Stochastic Multipath Routing". By stochastic we mean that, given the set of available paths from source to destination, a packet takes one of these at random. Furthermore, the probability of choosing one path over another is determined according to suitable optimality criteria that, in our case, targets optimizing robustness, performance (throughput, delay, etc.), as well as load balancing. While several approaches to multipath routing have been proposed to-date, we claim that most of them do not activate multiple paths simultaneously. Instead, they keep information about multiple paths to be used if the current single path in use breaks. In this case, an alternate path is selected. Thus rather than multipath routing, most existing strategies use alternate path routing. This project will address the following fundamental issues:

Development of a theoretical foundation for multipath routing addressing multiple objectives including enhanced robustness, performance (e.g., throughput, delay) and load balancing.
Development of multipath routing algorithms for wired networks, MANETs, and hybrid networks.
Development of transport layer protocols that work well with multipath routing protocols in wireless (in particular MANETs) environments.

Although multi-path routing has lots of benefits compared to single-path routing, it is known that one of the biggest barriers to deploying multi-path routing schemes is TCP's low performance in the presence of persistent packet reorderings. While measuring security/delay/throughput under "Stochastic Multipath Routing", we were motivated to develop a new version of TCP that increases throughput under multi-path routing. The proposed TCP variant, or TCP-PR (TCP for Persistent Reordering), 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's performance. TCP-PR performs consistently better than existing mechanisms that try to make TCP more robust to packet reordering. In the case that packets are not reordered, TCP-PR maintains the same throughput as typical implementations of TCP (specifically, TCP-SACK) and shares network resources fairly. Furthermore, TCP-PR only requires changes to the TCP sender side making it easier to deploy.