BGP Algorithm

Establishing a connection

Two BGP speakers form a TCP connection (using port 179). Each side sends an OPEN message. An OPEN message contains parameters needed for the BGP connection, including:

• BGP version (current version number is 4)
• Autonomous System Number - a unique identifier for the AS, which all BGP systems in that AS use
• Hold Time – specifies the maximum time allowed between KEEPALIVE or UPDATE messages
• BGP Identifier – set to the value of an IP address assigned to the sender, all connections from a BGP system carry the same BGP identifier
• Optional parameters for authentication purposes

A KEEPALIVE message is then sent to confirm the connection. A KEEPALIVE message consists only of a 19-byte header.

UPDATE messages are then sent between the BGP speakers to exchange routing information. UPDATE messages contain the path attributes used to make routing decisions. The BGP systems then adjust their routing tables if routes learned via the new connection are deemed better than existing routes. When changes are made, the system must send UPDATE messages to its peers.

Maintaining a connection

BGP peers periodically exchange KEEPALIVE message to maintain the connection. These messages are sent no more frequently than once per second. If the time between KEEPALIVE or UPDATE messages exceeds the Hold Time, the connection is assumed to be lost.

Whenever a BGP speaker finds new routes or determines old ones to be invalid, it must share this information with its neighbors. It consequently sends an UPDATE message containing new, updated, or withdrawn routes.

Closing a connection

When an error is detected, a NOTIFICATION message is sent to the neighbor at fault and the connection is then closed. The notification contains an error code informing the neighbor which error occurred.