How BGP Works

BGP is a path vector protocol used to carry routing information between autonomous systems. The term path vector comes from the fact that BGP routing information carries a sequence of AS numbers, which indicates the path a route has traversed. BGP uses TCP as its transport protocol (port 179). This ensures that all the transport reliability such as retransmission is taken care of by TCP and does not need to be implemented in BGP itself.

Two BGP routers form a transport protocol connection between each other. These routers are called neighbors or peers. Figure 4-8 illustrates this relationship. Peer routers exchange multiple messages to open and confirm the connection parameters, such as the BGP version running between the two peers (for example, version 3 for BGP3 and version 4 for BGP4). In case of any disagreement between the peers, notification errors are sent, and the peer connection does not get established.

Figure 4-8  BGP routers become neighbors.

Initially, all candidate BGP routes are exchanged, as illustrated in figure 4-9. Incremental updates are sent as network information changes. The incremental update approach has shown an enormous improvement as far as CPU overhead and bandwidth allocation compared with complete periodic updates used by previous protocols, such as EGP.

Figure 4-9  Exchanging all routing updates.

Routes are advertised between a pair of BGP routers in UPDATE messages. The UPDATE message contains, among other things, a list of <length, prefix> tuples that indicate the list of destinations reachable via each system. The UPDATE message also contains the path attributes, which include such information as the degree of preference for a particular route.

In case of information changes, such as a route being unreachable or having a better path, BGP informs its neighbors by withdrawing the invalid routes and injecting new routing information. As illustrated in figure 4-10, withdrawn routes are part of the UPDATE message. These are the routes no longer available for use. Figure 4-11 illustrates a steady state situation: if no routing changes occur, the routers exchange only KEEPALIVE packets.

Figure 4-10  N1 goes down; partial update sent.

Figure 4-11  Steady state; N1 is still down.

---

Troubleshooting:  
The meaning of rapidly incrementing table versions.

---

KEEPALIVE messages are sent periodically between BGP neighbors to ensure that the connection is kept alive. KEEPALIVE packets (19 bytes each) should not cause any strain on the router CPU or link bandwidth as they consume a minimal bandwidth (about 2.5 bits/sec for a periodic rate of 60 sec).

BGP keeps a table version number to keep track of the instance of the BGP routing table. If the table changes, BGP will increment the table version. A table version that is incrementing rapidly is usually an indication of instabilities in the network.

BGP Message Header Format

The BGP message header format is a 16-byte marker field, followed by a 2-byte length field and a 1-byte type field. Figure 4-12 illustrates the basic format of the BGP message header.

Figure 4-12  BGP message header format.

There may or may not be a data portion following the header, depending on the message type. KEEPALIVE messages, for example, consist of the message header only, with no following data.

The marker field is used to either authenticate incoming BGP messages or to detect loss of synchronization between two BGP peers. The marker field can have two formats:

•  If the type of the message is OPEN or if the OPEN message has no authentication information, the marker field must be all ones.

•  Otherwise, the marker field will be computed based on part of the authentication mechanism used.

The length indicates the total BGP message length including the header. The smallest BGP message is no less than 19 bytes (16+2+1) and no greater than 4,096.

The type indicates the message type, from the following possibilities:

•  OPEN

•  UPDATE

•  NOTIFICATION

•  KEEPALIVE

The following sections examine the purpose and format of each of the four message types in more detail.

BGP Neighbor Negotiation

One of the basic steps of the BGP protocol is establishing neighbors between BGP peers. Without successful completion of this step, no exchange of updates will ever take effect. Neighbor negotiation is based on the successful completion of a TCP transport connection, the successful processing of the OPEN message, and periodic detection of the KEEPALIVE messages.