Many recent studies have shown that end-to-end path selection can increase availability using mechanisms based on overlay networks or end-host and edge multi-homing. In this paper, we address several unanswered questions about the path diversity that these machanisms take advantage of: regardless of the path selection techniques used, where in the network is it necessary to provide path choice in order to achieve the best gains in availability, and why is this the case?

We present results of measurement simulations of inferred autonomous system (AS) topologies to discover the AS-level path disjointness properties of three multipath construction mechanisms. We find that a mechanism that selects both the egress edge leaving a source and the ingress edge entering the destination can often obtain as many disjoint paths as an optimal source routing mechanism. In contrast, choosing just the egress edge tends to favor paths that enter the same ingress edge at the destination, resulting diminished failure resilience. These results are consistent across several different inferred AS topologies, and agree with the results observed using traceroute data between a subset of the Internet ASes.

18 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]