Exploiting AS hierarchy for scalable route selection in multi-homed stub networks

Sanghwan Lee, Zhi-Li Zhang, Srihari Nelakuditi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004
Pages294-299
Number of pages6
StatePublished - Dec 1 2004
EventProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004 - Taormina, Italy
Duration: Oct 25 2004Oct 27 2004

Publication series

NameProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004

Other

OtherProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004
CountryItaly
CityTaormina
Period10/25/0410/27/04

Keywords

  • AS hierarchy
  • Multi-homing
  • Route selection

Fingerprint Dive into the research topics of 'Exploiting AS hierarchy for scalable route selection in multi-homed stub networks'. Together they form a unique fingerprint.

Cite this