Interdomain routing performs the critical function of gluing together individual pieces of the Internet topology to create a connected data delivery infrastructure. Today this critical function is performed by the Border Gateway Protocol (BGP) [rfc1771] which establishes reachability information among Autonomous Systems (ASes). However despite its importance, current measurements and analysis have not led to a basic understanding of BGP's dynamics, performance under stress, fundamental weaknesses, and potential breaking points (if any). Although a few data collection points have been set up in the last few years [ripe,routeviews], the routing data collected by these measurement points are mixed with measurement artifacts [ftntalk], thus the data do not necessarily reflect the protocol's behavior in actual operation. In order for the Internet to continue its unprecedented growth, the interdomain routing protocol must continue to evolve to meet ever increasing and sometimes contradictory requirements. There is a general belief that the current BGP routing protocol may be unable to meet its new requirements (for instance, accomodating the sharp increase in use of site multi-homing, which keeps routing tables from optimally small sizes[huston:scale:2001]). BGP is generally thought to be reaching the end of its useful lifetime, although this has not been validated by analysis or measurements [nimrod,irtfrr,huitema:ipng,huston:scale:2001]. Due to the lack of a shared understanding of the problem and lack of sufficient data and analysis, there is no consensus on where/when BGP collapses and what (if anything) should be done.

The BBGP team has identified the following fundamental technical requirements that the global routing must meet: it must scale in order to handle the growth (both in the number of users and in the richness of connectivity); security and resilience are critical issues, so it must continue to function in face of ever increasing faults and attacks; it must be able to fully utilize the rich Internet connectivity; and it must both allow network operators to apply various policy constraints and implementors to easily extend the protocol's functionality when needed. Based on the above criteria the project team proposes to tackle the challenge with the following 3 steps:

1. Develop measurement methodologies and collect data necessary to understand the current BGP operation, its overhead, dynamics under stress, potential vulnerabilities, inadequacies in functionality. The research will base this measurement effort on precise requirements that isidentiied as lacking in existing data, such as for the data not to be collected over vulnerable multihop links [ftntalk].
2. Guided by our measurement and analysis, evaluate several proposed design approaches, including meeting the requirements by tinkering with BGP, by a NIMROD-like [nimrod] maps-approach, by two different approaches to handling multihoming scalability, and by a Clean Slate approach of a complete BGP replacement. Each of these approaches emphasizes different aspects of the interdomain routing problem. The project team believes there are fundamental trade-offs between many of the desired technical requirements and that these trade-offs are currently not well understood. The combination of measurement and rigorous analysis with a team including operations expertise will bring these trade-offs into clear view.
3. Based on the data analysis and design evaluations the project team will produce a final approach as the recommendation for moving forward. Through iterations of the above steps, the proposed research undertaking is expected to produce new understanding of current interdomain routing operations, their dynamics and resilience (or lack of it), and vulnerabilities; a new analysis will also be produced that draws on direct and intensive measurement and operations knowledge to capture the fundamental trade-offs among interdomain routing requirements; and a conclusion will be reached on how to meet the future Internet's interdomain routing needs.

BBGP is collaboration between UCLA, USC/ISI, U Oregon.

BBGP is funded by NSF under Dr. Mari Maeda's Special Projects program.