The Internet has scaled massively over the past 15 years to extend to billions of users. These users increasingly require extensive applications and capabilities from the Internet, such as Quality of Service (QoS) optimized paths between end hosts. When default Internet paths may not meet their requirements adequately, there is a need to facilitate the discovery of such QoS optimized paths. Fortunately, even though the route offered by the Internet may not work (to the required level of performance), often there exist alternate routes that do work. When the direct Internet path between two Internet hosts for instance is sub-optimal (according to specific user defined criterion), there is a possibility that the direct paths of both to a third host may not be suffering from the same problem owing to path disjointness. Overlay Networks facilitate the discovery of such composite alternate paths through third party hosts. To discover such alternate paths, overlay hosts regularly monitor both Internet path quality and choose better alternate paths via other hosts. Such measurements are costly and pose scalability problems for large overlay networks. This thesis asserts and shows that these overheads could be lowered substantially if the network layer path information between overlay hosts could be obtained, which facilitates selection of disjoint paths. This thesis further demonstrates that obtaining such network layer path information is very challenging. As opposed to the path monitoring which only requires cooperation of overlay hosts, disjoint path selection depends on the accuracy of information about the underlay, which is out of the domain of control of the overlay and so may contain inaccuracies. This thesis investigates how such information could be gleaned at different granularities for optimal tradeoffs between spatial and/or temporal methods for selection of alternate paths. The main contributions of this thesis are: (i) investigation of scalable techniques to facilitate alternate path computation using network layer path information; (ii) a review of the realistic performance gains achievable using such alternate paths; and (iii) investigation of techniques for revealing the presence of incorrect network layer path information, proposal of new techniques for its removal.

The Internet has scaled massively over the past 15 years to extend to billions of users. These users increasingly require extensive applications and capabilities from the Internet, such as Quality of Service (QoS) optimized paths between end hosts. When default Internet paths may not meet their requirements adequately, there is a need to facilitate the discovery of such QoS optimized paths. Fortunately, even though the route offered by the Internet may not work (to the required level of performance), often there exist alternate routes that do work. When the direct Internet path between two Internet hosts for instance is sub-optimal (according to specific user defined criterion), there is a possibility that the direct paths of both to a third host may not be suffering from the same problem owing to path disjointness. Overlay Networks facilitate the discovery of such composite alternate paths through third party hosts. To discover such alternate paths, overlay hosts regularly monitor both Internet path quality and choose better alternate paths via other hosts. Such measurements are costly and pose scalability problems for large overlay networks. This thesis asserts and shows that these overheads could be lowered substantially if the network layer path information between overlay hosts could be obtained, which facilitates selection of disjoint paths. This thesis further demonstrates that obtaining such network layer path information is very challenging. As opposed to the path monitoring which only requires cooperation of overlay hosts, disjoint path selection depends on the accuracy of information about the underlay, which is out of the domain of control of the overlay and so may contain inaccuracies. This thesis investigates how such information could be gleaned at different granularities for optimal tradeoffs between spatial and/or temporal methods for selection of alternate paths. The main contributions of this thesis are: (i) investigation of scalable techniques to facilitate alternate path computation using network layer path information; (ii) a review of the realistic performance gains achievable using such alternate paths; and (iii) investigation of techniques for revealing the presence of incorrect network layer path information, proposal of new techniques for its removal.