TY - GEN
T1 - Exploiting AS hierarchy for scalable route selection in multi-homed stub networks
AU - Lee, Sanghwan
AU - Zhang, Zhi-Li
AU - Nelakuditi, Srihari
PY - 2004
Y1 - 2004
N2 - Multi-homing is a common practice among many (especially large) customer (or stub) networks. Although the purpose of multi-homing is primarily for enhanced reliability, it has also increasingly been used for load balancing and latency reduction. In this paper, we address the problem of how to perform scalable route selection in a multi-homed stub network to optimize network latency to various destinations as measured by round-trip-time (RTT). A straightforward method is to simply perform RTT measurements (e.g., using ping) to each destination via each provider and select the one with the minimum RTT as the "best" next-hop to the destination. Is there a more scalable alternative? To answer this question, we carry out a measurement-based study to analyze the differences of RTTs in using two different providers in a multi-homed stub network to reach a large number of randomly selected destinations. Our study reveals that because of the AS hierarchy, for a large fraction of the network prefixes, the two AS paths through two providers merge in the core of the Internet. Furthermore, the router at which the two router level paths merge is actually in the AS at which the AS level paths merge. This phenomenon causes the RTT difference between the two paths through the two providers to be determined by the non-shared portion of the paths. Our study reveals that most of the two router level paths through the two upstream providers merge at the AS at which the two AS level paths merge. Based on this finding, we devise a scalable route (next-hop provider) selection algorithm using BGP information in a multi-homed stub network. We also present a preliminary evaluation.
AB - Multi-homing is a common practice among many (especially large) customer (or stub) networks. Although the purpose of multi-homing is primarily for enhanced reliability, it has also increasingly been used for load balancing and latency reduction. In this paper, we address the problem of how to perform scalable route selection in a multi-homed stub network to optimize network latency to various destinations as measured by round-trip-time (RTT). A straightforward method is to simply perform RTT measurements (e.g., using ping) to each destination via each provider and select the one with the minimum RTT as the "best" next-hop to the destination. Is there a more scalable alternative? To answer this question, we carry out a measurement-based study to analyze the differences of RTTs in using two different providers in a multi-homed stub network to reach a large number of randomly selected destinations. Our study reveals that because of the AS hierarchy, for a large fraction of the network prefixes, the two AS paths through two providers merge in the core of the Internet. Furthermore, the router at which the two router level paths merge is actually in the AS at which the AS level paths merge. This phenomenon causes the RTT difference between the two paths through the two providers to be determined by the non-shared portion of the paths. Our study reveals that most of the two router level paths through the two upstream providers merge at the AS at which the two AS level paths merge. Based on this finding, we devise a scalable route (next-hop provider) selection algorithm using BGP information in a multi-homed stub network. We also present a preliminary evaluation.
KW - AS hierarchy
KW - Multi-homing
KW - Route selection
UR - http://www.scopus.com/inward/record.url?scp=14944366779&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=14944366779&partnerID=8YFLogxK
U2 - 10.1145/1028788.1028829
DO - 10.1145/1028788.1028829
M3 - Conference contribution
AN - SCOPUS:14944366779
SN - 1581138210
SN - 9781581138214
T3 - Proceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004
SP - 294
EP - 299
BT - Proceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004
PB - Association for Computing Machinery
T2 - Proceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004
Y2 - 25 October 2004 through 27 October 2004
ER -