Border Gateway Protocol (BGP)

The most common Exterior Gateway Protocol protocol in use on the Internet is the Border Gateway Protocol (BGP), ensuring that packets get to their destination network regardless of current network conditions.

Like RIP, the BGP algorithm provides great network stability, guaranteeing that if one Internet network line goes down, BGP routers can quickly adapt to send packets through another connection. The following subsections provide information on how BGP was invented, how BGP works, the BGP algorithm, and more BGP information

How BGP was invented. BGP was initially created in three different implementations. Then, in a standard Internet approach, they were used together to show that separate implementations of the protocol could interoperate without problems.

• Kirk Lougheed of Cisco systems developed a proprietary version of BGP for Cisco router equipment.

• Jeff Honig from Cornell University and Dennis Ferguson from the University of Toronto developed a BGP version called gated to run on Unix computers, enabling Unix machines to become BGP routers, and then put the code in the public domain for others to use.

• Yakov Rekhter from the IBM Thomas J. Watson Research Center wrote a BGP version for the NSFNET backbone.

How BGP works. When a BGP router first comes up on the Internet, either for the first time or after being turned off, it establishes connections with the other BGP routers with which it directly communicates. The first thing it does is download the entire routing table of each neighboring router. After that it only exchanges much shorter update messages with other routers.

BGP routers send and receive update messages to indicate a change in the preferred path to reach a computer with a given IP address. If the router decides to update its own routing tables because this new path is better, then it will subsequently propagate this information to all of the other neighboring BGP routers to which it is connected, and they will in turn decide whether to update their own tables and propagate the information further.

BGP uses the TCP/IP protocol on port 179 to establish connections. It has strong security features, including the incorporation of a digital signature in all communications between BGP routers.

Each BGP router contains a Routing Information Base (RIB) that contains the routing information maintained by that router. The RIB contains three types of information:

• Adj-RIBs-In. The unedited routing information sent by neighboring routers.

• Loc-RIB. The actual routing information the router uses, developed from Adj-RIBs-In.

• Adj-RIBs-Out. The information the router chooses to send to neighboring routers.

BGP routers exchange information using four types of messages:

• Open. Used to open an initial connection with a neighboring router.

• Update. These messages do most of the work, exchanging routing information between neighboring routers, and contain one of the following pieces of information.
  
  
  • Withdrawn routes. The IP addresses of computers that the router no longer can route messages to.
    
    
  • Paths. A new preferred route for an IP address. This path consists of two pieces of information -- the IP address, and the address of the next router in the path that is used to route messages destined for that address.
    
    
• Notification. Used to indicate errors, such as an incorrect or unreadable message received, and are followed by an immediate close of the connection with the neighboring router.

• Keepalive. Each BGP router sends a 19 byte Keepalive message to each neighboring router to let them know that it is still operational about every 30 seconds, and no more often than every three seconds. If any router does not receive a Keepalive message from a neighboring router within a set amount of time, it closes its connection with that router, and removes it from its Routing Information Base, repairing what it perceives as damage to the network.

Routing messages are the highest precedence traffic on the Internet, and each BGP router gives them first priority over all other traffic. This makes sense -- if routing information can't make it through, then nothing else will.

The BGP algorithm. The BGP algorithm is run after a BGP router receives an update message from a neighboring router, and consists of the following three steps performed for each IP address sent from the neighbor:

• Update. If the path information for an IP address in the update message is different from the information previously received from that router, then the Adj-RIBs-In database is updated with the newest information.

• Decision. If it was new information, then a decision process is run that determines which BGP router, of all those presently recorded in the Adj-RIBs-In database, has the best routing path for the IP address in the update message. The algorithm is not mandated, and BGP administrators can set local policy criteria for the decision process such as how long it takes to communicate with each neighboring router, and how long each neighboring router takes to communicate with the next router in the path. If the best path chosen as a result of this decision process is different from the one currently recorded in the Loc-RIB database, then the database is updated.

• Propagation. If the decision process found a better path, then the Adj-RIBs-Out database is updated as well, and the router sends out update messages to all of its neighboring BGP routers to tell them about the better path. Each neighboring router then runs their own BGP algorithm in turn, decides whether or not to update their routing databases, and then propagates any new and improved paths to neighboring routers in turn.

One of the other important functions performed by the BGP algorithm is to eliminate loops from routing information. For example, a routing loop would occur when router A thinks that router B has the best path to send messages for some computer and B thinks the best path is through C, but C thinks the best path is back through A. If these sort of routing loops were allowed to happen, then any message to that computer that passed through routers A, B, or C would circulate among them forever, failing to deliver the message and using up increasing amounts of network resources. The BGP algorithm traps and stops any such loops.

The BGP protocol has been periodically revised, and is now at version 4. Each version can support all earlier versions. Different BGP routers may run different versions of BGP, so the protocol includes the following clever method for ensuring that different versions can communicate. When one BGP router tries to communicate for the first time with a second BGP router, it sends it an Open message including the highest version of BGP that it supports. If the second router cannot support that version, it sends back a Notification message with the highest version that it can support. The first router then opens a connection using that lower version, so that the two routers can then communicate at the highest version of BGP they both support.

More information. Request For Comment documentation on BGP can be found below:

• RFC 1265; Rekhter, Y.; BGP Protocol Analysis, October 1991.

• RFC 1266; Rekhter, Y.; Experience with the BGP Protocol; October 1991.

• RFC 1771; Rekhter, Y.; Li, T.; A Border Gateway Protocol 4 (BGP-4), March 1995.

• RFC 1772; Gross, P.; Rekhter, Y.; Application of the Border Gateway Protocol in the Internet, March 1995.