The case for separating routing from routers

ABSTRACT

Over the past decade, the complexity of the Internet's routing infrastructure has increased dramatically. This complexity and the problems it causes stem not just from various new demands made of the routing infrastructure, but also from fundamental limitations in the ability of today's distributed infrastructure to scalably cope with new requirements.The limitations in today's routing system arise in large part from the fully distributed path-selection computation that the IP routers in an autonomous system (AS) must perform. To overcome this weakness, interdomain routing should be separated from today's IP routers, which should simply forward packets (for the most part). Instead, a separate Routing Control Platform (RCP) should select routes on behalf of the IP routers in each AS and exchange reachability information with other domains.Our position is that an approach like RCP is a good way of coping with complexity while being responsive to new demands and can lead to a routing system that is substantially easier to manage than today. We present a design overview of RCP based on three architectural principles path computation based on a consistent view of network state, controlled interactions between routing protocol layers, and expressive specification of routing policies and discuss the architectural strengths and weaknesses of our proposal.

REFERENCES

• 1: A Border Gateway Protocol 4 (BGP-4). Internet Draft draft-ietf-idr-bgp4-24.txt, work in progress, November 2003.
• 2: AGARWAL, S., CHUAH, C.-N., AND KATZ, R. H. OPCA: Robust interdomain policy routing and traffic control. In Proc. IEEE OpenArch (April 2003).
• 3: William Aiello , John Ioannidis , Patrick McDaniel, Origin authentication in interdomain routing, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948133]
• 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: Anindya Basu , Chih-Hao Luke Ong , April Rasala , F. Bruce Shepherd , Gordon Wilfong, Route oscillations in I-BGP with route reflection, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: BATES,T.,CHANDRA, R., AND CHEN, E. BGP Route Reflection -An Alternative to Full Mesh IBGP. RFC 2796, April 2000.
• 7: David D. Clark , John Wroclawski , Karen R. Sollins , Robert Braden, Tussle in cyberspace: defining tomorrow's internet, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 8: DRAVES, R., KING, C., VENKATACHARY, S., AND ZILL, B. Constructing optimal IP routing tables. In Proc. IEEE INFOCOM (March 1999).
• 9: Rohit Dube, A comparison of scaling techniques for BGP, ACM SIGCOMM Computer Communication Review, v.29 n.3, July 1999 [doi>10.1145/505724.505729]
• 10: Nick Feamster , David G. Andersen , Hari Balakrishnan , M. Frans Kaashoek, Measuring the effects of internet path faults on reactive routing, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 11: Nick Feamster , Hari Balakrishnan, Towards a logic for wide-area Internet routing, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 25-27, 2003, Karlsruhe, Germany
• 12: FEAMSTER, N., AND BALAKRISHNAN, H. Verifying the correctness of wide-area Internet routing. Tech. Rep. MIT-LCS-TR-948, Massachusetts Institute of Technology, May 2004.
• 13: 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]
• 14: FEAMSTER, N., REXFORD, J., SHAIKH, A., AND VAN DER MERWE, J. Routing control platform: Architecture and practical concerns. http://www.research.att.com/~kobus/rcp-tr.pdf, June 2004.
• 15: Nick Feamster , Jared Winick , Jennifer Rexford, A model of BGP routing for network engineering, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 16: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 17: Forwarding and Control Element Separation (ForCES) Charter. http://www.ietf.org/html.charters/forces-charter.html.
• 18: GOODELL, G., AIELLO,W.,GRIFFIN,T.,IOANNIDIS, J., MCDANIEL,P.,AND RUBIN, A. Working around BGP: An incremental approach to improving security and accuracy of interdomain routing. In Proc. Network and Distributed Systems Security 2003, Internet Society (February 2003).
• 19: Ramesh Govindan , Cengiz Alaettinoğlu , Kannan Varadhan , Deborah Estrin, Route servers for inter-domain routing, Computer Networks and ISDN Systems, v.30 n.12, p.1157-1174, July 13, 1998 [doi>10.1016/S0169-7552(98)00008-7]
• 20: Timothy Griffin , Gordon T. Wilfong, Analysis of the MED Oscillation Problem in BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.90-99, November 12-15, 2002
• 21: Timothy G. Griffin , Gordon Wilfong, On the correctness of IBGP configuration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 22: HANDLEY, M., HUDSON, O., AND KOHLER, E. XORP: An open platform for network research. In Proc. SIGCOMM Workshop on Hot Topics in Networking (HotNets) (October 2002).
• 23: HASKIN, D. A BGP/IDRP Route Server alternative to a full mesh routing. RFC 1863, October 1995.
• 24: HORING, S., MENARD, J. Z., STAEHLER, R. E., AND YOKELSON, B. J. Stored program controlled network: Overview. Bell System Technical Journal 61, 7 (September 1982), 1579--1588.
• 25: John Jannotti , M. Frans Kaashoek, Network layer support for overlay networks, 2002
• 26: LAKSHMINARAYANAN, K., STOICA, I., AND SHENKER, S. Routing as a Service. Tech. Rep. UCB-CS-04-1327, UC Berkeley, 2004.
• 27: LAWSER, J. J., LECRONIER, R. E., AND SIMMS, R. L. Stored program controlled network: Generic network plan. Bell System Technical Journal 61, 7 (September 1982), 1589--1598.
• 28: MAHAJAN, R., WETHERALL, D., AND ANDERSON, T. Interdomain routing with negotiation. Tech. Rep. CSE-04-06-02, University of Washington, May 2004.
• 29: Zhuoqing Morley Mao , Ramesh Govindan , George Varghese , Randy H. Katz, Route flap damping exacerbates internet routing convergence, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 30: 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]
• 31: MCPHERSON, D., GILL,V.,WALTON, D., AND RETANA,A. Border gateway protocol (BGP) persistent route oscillation condition. RFC 3345, August 2002.
• 32: Akihiro Nakao , Larry Peterson , Andy Bavier, A routing underlay for overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863958]
• 33: 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]
• 34: RouteScience. Whitepaper available from http://www.routescience.com/technology/tec_whitepaper.html.
• 35: SHAIKH, A., AND GREENBERG, A. OSPF monitoring: Architecture, design, and deployment experience. In Proc. First Symposium on Networked Systems Design and Implementation (NSDI) (San Francisco, CA, March 2004).
• 36: Sockeye. http://www.sockeye.com/.
• 37: SUBRAMANIAN, L., ROTH,V.,STOICA, I., SHENKER, S., AND KATZ, R. Listen and whisper: Security mechanisms for BGP. In Proc. First Symposium on Networked Systems Design and Implementation (NSDI) (San Francisco, CA, March 2004).
• 38: Renata Teixeira , Jennifer Rexford, A measurement framework for pin-pointing routing changes, Proceedings of the ACM SIGCOMM workshop on Network troubleshooting: research, theory and operations practice meet malfunctioning reality, September 03-03, 2004, Portland, Oregon, USA [doi>10.1145/1016687.1016704]
• 39: Renata Teixeira , Aman Shaikh , Tim Griffin , Jennifer Rexford, Dynamics of hot-potato routing in IP networks, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 40: VILLAMIZAR, C., CHANDRA, R., AND GOVINDAN, R. BGP Route Flap Damping. RFC 2439, November 1998.
• 41: YANG, L., ET AL. Forwarding and Control Element Separation (ForCES) Framework. RFC 3746, April 2004.
• 42: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

General Terms:
Algorithms, Design, Management, Performance, Reliability

Keywords:
BGP, interdomain routing, routing architecture