MIRO: multi-path interdomain routing

ABSTRACT

The Internet consists of thousands of independent domains with different, and sometimes competing, business interests. However, the current interdomain routing protocol (BGP) limits each router to using a single route for each destination prefix, which may not satisfy the diverse requirements of end users. Recent proposals for source routing offer an alternative where end hosts or edge routers select the end-to-end paths. However, source routing leaves transit domains with very little control and introduces difficult scalability and security challenges. In this paper, we present a multi-path inter-domain routing protocol called MIRO that offers substantial flexiility, while giving transit domains control over the flow of traffic through their infrastructure and avoiding state explosion in disseminating reachability information. In MIRO, routers learn default routes through the existing BGP protocol, and arbitrary pairs of domains can negotiate the use of additional paths (bound to tunnels in the data plane) tailored to their special needs. MIRO retains the simplicity of BGP for most traffic, and remains backwards compatible with BGP to allow for incremental deployability. Experiments with Internet topology and routing data illustrate that MIRO offers tremendous flexibility for path selection with reasonable overhead.

REFERENCES

• 1: D. Zhu, M. Gritter, and D. Cheriton, "Feedback based routing," in Proc. SIGCOMM Workshop on Hot Topics in Networking, October 2002.
• 2: H. Tahilramani Kaur , S. Kalyanaraman , A. Weiss , S. Kanwar , A. Gandhi, BANANAS: an evolutionary framework for explicit and multipath routing in the internet, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 25-27, 2003, Karlsruhe, Germany
• 3: Barath Raghavan , Alex C. Snoeren, A system for authenticated policy-compliant routing, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 4: Katerina Argyraki , David R. Cheriton, Loose source routing as a mechanism for traffic policies, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016707.1016718]
• 5: Xiaowei Yang, NIRA: a new Internet routing architecture, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 25-27, 2003, Karlsruhe, Germany
• 6: 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
• 7: B. Quoitin, S. Uhlig, C. Pelsser, L. Swinnen, and O. Bonaventure, "Interdomain traffic engineering with BGP," IEEE Communication Magazine, 2003.
• 8: "University of Oregon Route Views Project." http://www.routeviews.org.
• 9: Y. Rekhter, T. Li, and S. Hares, "A Border Gateway Protocol 4 (BGP-4)." RFC 4271, January 2006.
• 10: G. Huston, "Interconnection, peering, and settlements," in Proc. INET, June 1999.
• 11: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 12: L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, June 2002.
• 13: 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]
• 14: Lakshminarayanan Subramanian , Matthew Caesar , Cheng Tien Ee , Mark Handley , Morley Mao , Scott Shenker , Ion Stoica, HLP: a next generation inter-domain routing protocol, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 15: M. Caesar and J. Rexford, "BGP policies in ISP networks," IEEE Network Magazine, October 2005.
• 16: Srikanth Kandula , Dina Katabi , Bruce Davie , Anna Charny, Walking the tightrope: responsive yet stable traffic engineering, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 17: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 18: M. Caesar, D. Caldwell, N. Feamster, J. Rexford, A. Shaikh, and J. van der Merwe," Design and implementation of a routing control platform, "in Proc. NSDI, May 2005.
• 19: Xiaowei Yang , David Wetherall , Thomas Anderson, A DoS-limiting network architecture, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 20: Lixin Gao , Jennifer Rexford, Stable internet routing without global coordination, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.681-692, December 2001 [doi>10.1109/90.974523]
• 21: Z. Morley Mao , Lili Qiu , Jia Wang , Yin Zhang, On AS-level path inference, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 22: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 23: I. Castineyra , N. Chiappa , M. Steenstrup, The Nimrod Routing Architecture, RFC Editor, 1996
• 24: R. Mahajan, D. Wetherall, and T. Anderson, "Negotiation-based routing between neighboring ISPs," in Proc. NSDI, 2005.
• 25: R. Johari and J. Tsitsiklis, "Routing and peering in a competitive Internet." LIDS Publication 2570, 2003.
• 26: Mike Afergan , John Wroclawski, On the benefits and feasibility of incentive based routing infrastructure, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016527.1016533]
• 27: J. Chen, P. Druschel, and D. Subramanian, "An efficient multipath forwarding method," in Proc. IEEE INFOCOM, pp. 1418--1425, March 1998.
• 28: Li Xiao , King-Shan Lui , Jun Wang , Klara Nahrsted, QoS Extension to BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.100-109, November 12-15, 2002
• 29: D. Walton, A. Retana, and E. Chen, "Advertisement of multiple paths in BGP." Internet Draft, draft-walton-bgp-add-paths-05. txt, Expires August 2006.
• 30: "Path computation element charter." http://www.ietf.org/html.charters/pce-charter.html.

INDEX TERMS

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

General Terms:
Design, Experimentation

Keywords:
BGP, flexibility, inter-domain routing, multipath routing, scalability