BGP: Internet Routing Architectures, Part I

HOW BGP WORKS

• BGP is a path vector protocol used to carry routing information between autonomous sytems.
• Path vector signifies that BGP carries a sequence of AS numbers that identifies the AS path. Also used for loop prevention.
• BGP uses TCP port 179.
• All the transport reliability is taken care of by TCP. No need to design this feature into the protocol itself.
• BGP speakers = routers that run BGP.
• BGP neighbors or peers = routers that form a TCP connection to exchange routing information.
• Initially, all BGP routes are exchanged. Only incremental updates are sent as the network information changes.
• Four message types: OPEN, NOTIFICATION, KEEPALIVE, and UPDATE.
• BGP neighbors exchange OPEN messages to determine the connection parameters.
• NOTIFICATION is sent in case of disagreement between the peers, and as a result, the session is not established or is torn down if already established.
• UPDATE messages advertise BGP routes. Indicate a list of destinations that can be reached through that BGP speaker, and the related path attributes.
• KEEPALIVE messages are sent periodically (every 60 seconds by defaut) between the BGP peers to ensure that the connection stays up.
• A table version number keeps track of the current instance of the BGP routing table. Incremented at each change. A rapidly incrementing table version is usually an indication of network instability.

BGP MESSAGE HEADER FORMAT

+++++++++++++++++++++++++++++++++++++++++++
|       Marker       |   Length  |  Type  |
+++++++++++++++++++++++++++++++++++++++++++

• Depending on the message type, there might or might not be a data portion following the header.
• For example, KEEPALIVE messages consist of the message header only.

• The Marker field (16 bytes) is used to either authenticate incoming BGP messages or detect loss of synchronization between two BGP peers.

1. If the type is OPEN or OPEN+no authentication, the Marker field must be all 1s.
2. Otherwise, the Marker field will be computed based on part of the authentication mechanism.

• The Length field (2 bytes) indicates the total BGP message length.
• The Type field (1 byte) indicates the message type (OPEN, UPDATE, NOTIFICATION, KEEPALIVE).

BGP NEIGHBOR NEGOTIATION

• The OPEN Message.
• BGP peers agree on a BGP version number. BGP tries to negotiate the highest common version.
• The AS number is advertised in the OPEN message.
• The Hold time indicates the maximum amount of time in seconds that may elapse between the receipt of successive KEEPALIVE or UPDATE messages.
• The BGP neighbors negotiate to select the Hold time value which is lower.
• The Hold timer could be 0, in which case the timers are never reset. The minimum Hold timer is 3 seconds.
• BGP ID is also transported in the OPEN message. Typically the highest loopback IP address.
• Optional parameters include the authentication information parameter.

BGP FINITE STATE MACHINE

 

1. Idle.
BGP initializes its resources, initiates a TCP transport connection, and starts listening for a connection that may be initiated by a remote peer.

2. Connect.
BGP is waiting for the transport protocol connection to be completed. If successful, the state transitions to OpenSent (the OPEN message is sent). If unsuccessful, the state transitions to Active.

3. Active.
BGP tries to acquire a peer by initiating a transport protocol connection. If expired, BGP restarts the ConnectRetry timer and falls back to the Connect state. The state might go back to Idle in case of other events, such as Stop event. A neighbor state that is oscillating between Connect and Active typically indicates a problem with the TCP transport connection.

4. OpenSent.
BGP is waiting for an OPEN message from its peer. In case of errors, an error NOTIFICATION is sent and the state goes back to Idle. If no errors, BGP starts sending KEEPALIVE messages.

5. OpenConfirm.
BGP waits for a KEEPALIVE message. If a KEEPALIVE is received, the state goes to Established, and the neighbor negotiation is complete.

6. Established.
The final stage in the neighbor negotiation. BGP starts exchanging UPDATE packets with its peers.

NOTIFICATION MESSAGE

• Always sent whenever an error is detected.
• After that, the peer connection is closed.

++++++++++++++++++++++++++++++++++++++++++
|  Error  | Error subcode |     Data     |
++++++++++++++++++++++++++++++++++++++++++

• The Error code indicates the type of the notification.
• The Error subcode provides more information about the nature of the error.
• The Data field contains data relevant to the error, such as a bad header or an illegal AS number.

KEEPALIVE MESSAGE

• Periodic messages exchanged between peers to determine whether peers are reachable.
• The Hold time is the maximum amount of time that may elapse between the receipt of successive KEEPALIVE or UPDATE messages.
• A recommended KEEPALIVE rate is 1/3 of the Hold time.
• If the Hold timer is 0, periodic KEEPALIVE messages are not sent.
• The KEEPALIVE message is a BGP header with no data following it.

UPDATE MESSAGE AND ROUTING INFORMATION

• Basic blocks of an UPDATE message:

1. Network Layer Reachability Information (NLRI).
2. Path Attributes.
3. Unfeasible Routes.

+++++++++++++++++++++++++++++++++++
|   Unfeasible routes length      |
+++++++++++++++++++++++++++++++++++
|   Withdrawn routes              |
+++++++++++++++++++++++++++++++++++
|   Total path attribute length   |
+++++++++++++++++++++++++++++++++++
|   Path attributes               |
+++++++++++++++++++++++++++++++++++
|     Length     |    Prefix      |
+++++++++++++++++++++++++++++++++++
|                                 | 
|      <length, prefix>           |  
|                                 |
+++++++++++++++++++++++++++++++++++

• The NLRI (IP prefix route) indicates the networks being advertised.
• The Path Attribute list enables BGP to detect routing loops and gives it flexibility to enforce local and global routing policies.

NETWORK LAYER REACHABILITY INFORMATION (NLRI)

• The NLRI is the part of the BGP UPDATE message that lists the set of destinations about which BGP is trying to inform its other BGP neighbors.
• The NLRI consists of one or more instances of the 2-tuple format <length, prefix>, where length is the number of the subnet mask that a particular prefix has.
• Example: <19, 198.24.160.0> = 198.24.160.0/19.
• Withdrawn routes have the same format.
• An UPDATE message with no new NLRI or Path Attribute information is used to advertise only routes to be withdrawn from service.

PATH ATTRIBUTES

• A set of parameters used to keep track of route-specific information.
• Format: <attribute type, attribute length, attribute value>.
• Four categories:

1. Well-known mandatory.
2. Well-known discretionary.
3. Optional transitive.
4. Optional non-transitive.

• Well-known attributes are always transivite.
• Well-known mandatory: Has to exist in the BGP UPDATE packet. Must be recognized by all BGP implementations. If missing, a NOTIFICATION error is generated, and the session is closed.
• Well-known dicretionary: Recognized by all BGP implementations but might or might not be sent in the BGP UPDATE message.
• Optinal transitive: The BGP implementation should accept the attribute and pass it along to other BGP speakers.
• Optional non-transitive: The attribute is quietly ignored and not passed along to other BGP peers.

BGP CAPABILITIES NEGOTIATION

• The purpose is to introduce a new optional parameter to BGP-4 called Capabilities.
• Supported capabilites are included in the OPEN message.
• If a peer supports a given capability, the speaker can use the capability with the peer.
• If not supported, the BGP speaker receives a NOTIFICATION error message and attempts to reestablish the connection without sending the Capabilities parameter to the peer.

MULTIPROTOCOL EXTENSIONS FOR BGP

• MP-BGP is negotiated via BGP capabilities.
• Provides a backward-compatible extension to the BGP-4 protocol that let it carry information fro network layer protocols other than IPv4, such as IPv6 and IPX.
• Two new attributes: Multiprotocol Reachable NLRI (MP_REACH_NLRI) and Multiprotocol Unreachable NLRI (MP_UNREACH_NLRI).
• MP_REACH_NLRI and MP_UNREACH_NLRI are optional non-transitive attributes.
• Interdomain multicast routing is the most common use of BGP's multiprotocol extensions.

TCP MD5 SIGNATURE OPTION

• Help BGP protect itself from spoofed TCP segments and TCP resets in particular.
• The TCP segment carries a digest message based on information known only to the connection end points.
• When TCP receives a signed segment, the receiver must validate it by using its local key to
  calculate its own digest and compare the value with that of the received digest. 
• If the comparison results in unequal values, the segment should be discarded and must not produce any response to the sender.
• The MD5 key is never exchanged via the connection and that only the end points should be aware of the value.
• There are performance implications that result in significantly increased delay with BGP message processing and generation.