| Game-Theoretic Stochastic Routing (GTSR) is a multipath routing technique developed based on game theory. In this technique, the paths and the probability of taking a particular path are selected in such a way that maximizes security to link or node attacks and maximizes robustness to link or node failures. Despite the theoretical rigor, the application of GTSR in the real world requires some issues to be resolved. This thesis explores in particular three issues.; First, GTSR requires extensive computation. Furthermore, the next-hop probabilities depend on both the source and the destination, hence the stochastic routing table grows quadratically with the size of the network. In order to reduce the computational complexity, a hierarchical approach is developed. It is shown that in many of today's networks, this hierarchical approach provides nearly as much robustness as does the more computationally complex flat routing approach.; Second, TCP has been one of the significant deterrents to the deployment of multipath routing protocols including GTSR. Most standard implementations of TCP perform poorly when packets are reordered and packet reordering severely occurs in multipath routing. 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, tuners are maintained to keep track of how long ago a packet was transmitted. Through extensive simulations, we show that 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, we verify that TCP-PR competes with typical implementations of TCP fairly.; Lastly, through implementation on PlanetLab, we show that GTSR for overlay networks is efficient in overcoming path failures in the Internet in the sense that GTSR significantly reduces bursty packet losses. Furthermore, the evaluation based on distribution of failure duration verifies that a high degree of multipath is more helpful than a low degree of multipath in overcoming path failures. |
