Optimizing cost and performance for multihoming

ABSTRACT

Multihoming is often used by large enterprises and stub ISPs to connect to the Internet. In this paper, we design a series of novel smart routing algorithms to optimize cost and performance for multihomed users. We evaluate our algorithms through both analysis and extensive simulations based on realistic charging models, traffic demands, performance data, and network topologies. Our results suggest that these algorithms are very effective in minimizing cost and at the same time improving performance. We further examine the equilibrium performance of smart routing in a global setting and show that a smart routing user can improve its performance without adversely affecting other users.

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: Aditya Akella , Jeffrey Pang , Bruce Maggs , Srinivasan Seshan , Anees Shaikh, A comparison of overlay routing and multihoming route control, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 3: Amextel. http://www.amextel.com/dedicated.htm.
• 4: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: T. Bates and Y. Rekhter. Scalable Support for Multi-homed Multi-provider Connectivity, RFC 2260, Jan. 1998.
• 6: Z. Cao, Z. Wang, and E. Zegura. Performance of hashing-based schemes for Internet load balancing. In Proceedings of IEEE INFOCOM '01, Anchorage, AK, Apr. 2001.
• 7: Cisco Inc. Sample configurations for load sharing with BGP in single and multihomed environments. Available at http://www.cisco.com/warp/public/459/40.html.
• 8: R. Dai, D. O. Stahl, and A. B. Whinston. The economics of smart routing and QoS. In Proceedings of the Fifth International Workshop on Networked Group Communications (NGC'03), 2003.
• 9: F5 Networks, Inc. http://www.f5networks.com/.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: F. Guo, J. Chen, W. Li, and T. Chiueh. Experiences in building a multihoming load balancing system. In Proceedings of IEEE INFOCOM '04, Hong Kong, China, Apr. 2004.
• 12: Internap Networks, Inc. http://www.internap.com.
• 13: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, 1999.
• 14: lp_solve. ftp://ftp.ics.ele.tue.nl/pub/lp_solve/.
• 15: A. Mihailovic, G. Leijonhufvud, and T. Suihko. Providing multi-homing support in IP access networks. In PIMRC 2002, 2002.
• 16: NLANR. Round-trip time measurements. Available at http://watt.nlanr.net/Active/raw_data/cgi-bin/data_form.cgi.
• 17: Ariel Orda , Raphael Rom, Multihoming in computer networks: a topology-design approach, Computer Networks and ISDN Systems, v.18 n.2, p.133-141, February 1989/90 [doi>10.1016/0169-7552(90)90140-N]
• 18: Pacific Bell. https://ebiznet.sbc.com/calnetinfo/RiderC.
• 19: Proficient Networks, Inc. http://www.proficientnetworks.com.
• 20: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 21: Radware, Inc. http://www.radware.com/content/products/pd/default.asp.
• 22: Rocketfuel. PoP-level ISP maps. Data file policy-dist.tar.gz available from http://www.cs.washington.edu/research/networking/rocketfuel/, 2003.
• 23: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 24: RouteScience Technologies, Inc. http://www.routescience.com, June 2003.
• 25: RouteScience Technologies, Inc. Reengineering ISP connectivity to lower bandwidth costs. White Paper. Available at http://www.routescience.com, Apr. 2002.
• 26: RouteScience Technologies, Inc. Route optimization for ebusiness applications. White Paper. Available at http://www.routescience.com, 2003.
• 27: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 28: G. Schreck, C. Rustein, and M. Porth. The end of the private WAN. Forrester Brief, Mar. 2002.
• 29: P. Sevcik and J. Bartlett. Improving user experience with route control. Technical Report NetForecast Report 5062, NetForecast, Inc., 2002.
• 30: S. Sharma, J. Chen, W. Li, K. Gopalan, and T. Chiueh. Duplex: A reusable fault tolerance extension framework for network access devices. In Proceedings of 2003 International Conference on Dependable Systems and Networks (DSN 2003), June 2003.
• 31: P. Smith. BGP multihoming techniques. NANOG 23. http://www.nanog.org/mtg-0110/smith.html, Oct. 2001.
• 32: Neil Spring , Ratul Mahajan , Thomas Anderson, The causes of path inflation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863970]
• 33: H. Tangmunarunkit, R. Govindan, and S. Shenker. Internet path inflation due to policy routing. In Proceedings of SPIE ITCom, Denver, CO, Aug. 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Algorithms, Performance

Keywords:
algorithms, multihoming, optimization, smart routing