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

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 <i>scalable</i> route selection in a multi-homed <i>stub</i> network to optimize network latency to various destinations as measured by round-trip-time (RTT). A straight forward 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.

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 <i>non shared</i> 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.

REFERENCES

• 1: Aditya Akella , Bruce Maggs , Srinivasan Seshan , Anees Shaikh , Ramesh Sitaraman, A measurement-based analysis of multihoming, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863995]
• 2: Bassam Halabi, Internet Routing Architectures, Cisco Press, 1997
• 3: Lakshminarayanan Subramanian, Sharad Agarwal, Jennifer Rexford, and Randy H. Katz. Characterizing the internet hierarchy from multiple vantage points. In Proc. IEEE INFOCOM, New York, NY, June 2002.
• 4: University of oregon route views project. http://www.routeviews.org.
• 5: Route science company. http://www.routescience.org.
• 6: Proficient networks. http://www.proficient.net.
• 7: Geoff Huston. Interconnection, peering and settlements--part i. In Internet Protocol Journal, Jun 1999.
• 8: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 9: Sanghwan Lee, Zhi-Li Zhang, and Srihari Nelakuditi. Impact of as hierarchy on multihoming performance: A stub network perspective. Technical report, Computer Science Department, Univ. of Minnesota, February 2004.
• 10: Nick Feamster , Jay Borkenhagen , Jennifer Rexford, Guidelines for interdomain traffic engineering, ACM SIGCOMM Computer Communication Review, v.33 n.5, October 2003 [doi>10.1145/963985.963988]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Measurement, Performance

Keywords:
AS hierarchy, multi-homing, route selection