The Need for Routing in Complex Networking Systems or Why a Border Gateway Protocol?
By Jessica Yu and Hans-Werner Braun
Merit/NSFNET
September 1989
The infrastructure of the Internet is becoming more complex with time, as the number of connected networks increases as well as the number of users on individual component networks. Today the Internet is approaching 1000 networks and the number is still rapidly increasing. An order of magnitude increase in the number of networks over the next few years is not out of the question. Given the dramatic increase in the use of Internet protocols abroad, the order of magnitude may be exceeded. Even today the Internet connects to many foreign countries.
The ARPANET Core
A few years ago it was sufficient to deal with fairly simple routing protocols on campuses and at research centers which were connected to "the Core," a national networking infrastructure commonly known as the ARPANET. The ARPANET Core exchanged network reachability information via the Exterior Gateway Protocol (EGP) between the "Core gateways" and the routers which connected the ARPANET nodes with the external networks.
The ARPANET Core gateways used an interior gateway protocol to exchange routing information among themselves. At that time the Internet was implemented in a tree-like structure with the exterior networks forming the branches. A reachability protocol (EGP), rather than a full fledged routing protocol was sufficient for connectivity between the Core and the exterior networks. Typically no backup links were used, as these would have required more extensive flow control of routing information. The Core was the entity which had ubiquitous routing information and which was allowed to pass on third party information via Exterior Gateway Protocol.
With the advent of the NSFNET, the core model had to be abandoned as the Internet changed into a mesh of networks, rather than a simple tree. The result was that more than one entity passes on third party exterior information and has ubiquitous routing information.
In such an environment, the Exterior Gateway Protocol (EGP) could only be applied by carefully controlling the flow of routing information by means of a policy routing database. This database helped to engineer the network by allowing the dynamic nature of routing advertisements to be predictable and controllable; the NSFNET has operated in this environment since July 1988.
The NSFNET Routing Design
The NSFNET routing design allows for clustering multiple network numbers into Routing Domains (RD), which roughly translate to mid-level networks. With the use of EGP, the NSFNET is using the EGP Autonomous System numbers to identify specific Routing Domains. One may thenn view the larger Internet as a collection of Routing Domains upon which the NSFNET bases its routing, using EGP and the policy routing database to distribute routing between RDs.
Exterior Gateway Protocol
While the use of EGP sufficed for the deployment of the current phase of the NSFNET, we are increasingly faced with the shortcomings of the protocol. Some of the constraints include:
Border Gateway Protocol
Early this year, personnel from IBM and Cisco Systems collaborated to design a new routing protocol, Border Gateway Protocol (BGP), which will allow the exchange of routing information between RDs. Subsequently, BGP emerged to become an agenda topic of the IETF Interconnectivity Working Group and is described in RFC 1105.
BGP is a protocol which exchanges routing information between the border gateways of adjacent Routing Domains, thus making it an Inter-Domain routing protocol. Further, within a Routing Domain, all the internal border gateways have virtual connections to all the other border gateways in a fully connected mesh. BGP relies on underlying transport protocols to exchange routing information. Initially this protocol is TCP but it may change to other reliable transport protocols.
To avoid loops in the RD path, all routing information is exchanged with a full RD path per Internet network number. At the same time, routing information is exchanged in incremental updates, that is that information which has not changed does not get retransmitted in the next update. The following features differentiate BGP from EGP:
Complete RD Path Trace
The complete RD path attached with the distributed routing information makes it possible to introduce methods for very sophisticated policy-based routing. For example, enough knowledge is retained in this information to determine whether a route would traverse specific mid-level networks or specific agency networks.
Use of Standard Reliable Transport Protocols
Use of typical preexisting transport protocols such as TCP help make BGP easy to implement. BGP is intended to work as a full inter-RD routing protocol and, at the same time, minimize the required changes to the existing Internet.
Incremental Updates
Only information which has changed is retransmitted in the updates.
Internet Topology Requirement
BGP does not require a spanning tree topology; a mesh topology, such as that of the NSFNET, can be supported.
The process flow of BGP can be described as follows:
BGP has been implemented in the NSS (NSFNET Nodal Switching Subsystem), Cisco routers as well as the public domain "gated" software. Currently in use on the NSFNET Research Network, Merit/NSFNET is planning to deploy BGP as a prototype Inter-Domain routing protocol on the operational NSFNET.
Several people from the IETF Interconnectivity Working Group are formulating a follow-up document to the BGP protocol specification. This paper, intended for publication as a RFC, will outline the application of the Border Gateway Protocol within the Internet environment.
During August, testing of BGP implementations between gated, Cisco, and NSS routers on the NSFNET Research Network continued. A BGP workshop was held in Ann Arbor and those attending represented a subset of the IETF Interconnectivity Working Group.
Taken from The Link Letter, 15 September 1989, Vol. 2 No. 4.