The Border Gateway Protocol (BGP) is the protocol backing the core routing decisions on the Internet. It maintains a table of IP networks or 'prefixes' which designate network reachability among autonomous systems (AS). It is described as a path vector protocol. BGP does not use traditional Interior Gateway Protocol (IGP) metrics, but makes routing decisions based on path, network policies and/or rulesets. For this reason, it is more appropriately termed a reachability protocol rather than routing protocol.
BGP was created to replace the Exterior Gateway Protocol (EGP) protocol to allow fully decentralized routing in order to transition from the core ARPAnet model to a decentralized system that included the NSFNET backbone and its associated regional networks. This allowed the Internet to become a truly decentralized system. Since 1994, version four of the BGP has been in use on the Internet. All previous versions are now obsolete. The major enhancement in version 4 was support of Classless Inter-Domain Routing and use of route aggregationto decrease the size of routing tables. Since January 2006, version 4 is codified in RFC 4271, which went through more than 20 drafts based on the earlier RFC 1771 version 4. RFC 4271 version corrected a number of errors, clarified ambiguities and brought the RFC much closer to industry practices.
Most Internet service providers must use BGP to establish routing between one another (especially if they are multihomed). Therefore, even though most Internet users do not use it directly, BGP is one of the most important protocols of the Internet. Compare this with Signaling System 7 (SS7), which is the inter-provider core call setup protocol on the PSTN. Very large private IP networks use BGP internally. An example would be the joining of a number of large OSPF (Open Shortest Path First) networks where OSPF by itself would not scale to size. Another reason to use BGP is multihoming a network for better redundancy either to multiple access points of a single ISP (RFC 1998) or to multiple ISPs.
BGP neighbors, peers, are established by manual configuration between routers to create a TCP session on port 179. A BGP speaker will periodically send 19-byte keep-alive messages to maintain the connection (every 60 seconds by default). Among routing protocols, BGP is unique in using TCP as its transport protocol.
When BGP runs between two peers in the same autonomous system (AS), it is referred to as Internal BGP (IBGP or Interior Border Gateway Protocol). When it runs between autonomous systems, it is called External BGP (EBGP or Exterior Border Gateway Protocol). Routers on the boundary of one AS exchanging information with another AS are called border or edge routers. In the Cisco operating system, IBGP routes have an administrative distance of 200, which is less preferred than either external BGP or any interior routing protocol. Other router implementations also prefer EBGP to IGPs, and IGPs to IBGP.
Finite-state machine
In order to make decisions in its operations with other BGP peers, a BGP peer uses a simple finite state machine (FSM) that consists of six states: Idle; Connect; Active; OpenSent; OpenConfirm; and Established. For each peer-to-peer session, a BGP implementation maintains a state variable that tracks which of these six states the session is in. The BGP protocol defines the messages that each peer should exchange in order to change the session from one state to another. The first state is the “Idle” state. In the “Idle” state, BGP initializes all resources, refuses all inbound BGP connection attempts and initiates a TCP connection to the peer. The second state is “Connect”. In the “Connect” state, the router waits for the TCP connection to complete and transitions to the "OpenSent" state if successful. If unsuccessful, it starts the ConnectRetry timer and transitions to the "Active" state upon expiration. In the "Active" state, the router resets the ConnectRetry timer to zero and returns to the "Connect" state. In the "OpenSent" state, the router sends an Open message and waits for one in return. Keepalive messages are exchanged and, upon successful receipt, the router is placed into the “Established” state. In the “Established” state, the router can send/receive: Keepalive; Update; and Notification messages to/from its peer.
Idle State:
Refuse all incoming BGP connections
Start event triggers the initialization of
Initiates a TCP connection with its configured BGP peer.
Listens for a TCP connection from its peer.
Changes its state to Connect.
If an error occurs at any state of the FSM process, the BGP session is terminated immediately and returned to the Idle state. Some of the reasons why a router does not progress from the Idle state are:
TCP port 179 is not open.
A random TCP port over 1023 is not open.
Peer address configured incorrectly on either router.
AS number configured incorrectly on either router .
Connect State:
Waits for successful TCP negotiation with peer.
BGP does not spend much time in this state if the TCP session has been successfully established.
Sends Open message to peer and changes state to OpenSent.
If an error occurs, BGP moves to the Active state. Some reasons for the error are:
TCP port 179 is not open.
A random TCP port over 1023 is not open.
Peer address configured incorrectly on either router.
AS number configured incorrectly on either router.
If the router was unable to establish a successful TCP session, then it ends up in the Active state.
BGP FSM will try to restart another TCP session with the peer and, if successful, then it will send an Open message to the peer.
If it is unsuccessful again, the FSM is reset to the Idle state.
Repeated failures may result in a router cycling between the Idle and Active states. Some of the reasons for this include:
TCP port 179 is not open.
A random TCP port over 1023 is not open.
BGP configuration error.
Network congestion.
Flapping network interface.
OpenSent State:
BGP FSM listens for an Open message from its peer.
Once the message has been received, the router checks the validity of the Open message.
If there is an error it is because one of the fields in the Open message doesn’t match between the peers, e.g. BGP version mismatch, MD5 password mismatch, the peering router expects a different My AS. The router will then send a Notification message to the peer indicating why the error occurred.
If there is no error, a Keepalive message is sent, various timers are set and the state is changed to OpenConfirm.
OpenConfirm State:
The peer is listening for a Keepalive message from its peer.
If a Keepalive message is received and no timer has expired before reception of the Keepalive, BGP transitions to the Established state.
If a timer expires before a Keepalive message is received, or if an error condition occurs, the router transitions back to the Idle state.
Established State:
In this state, the peers send Update messages to exchange information about each route being advertised to the BGP peer.
If there is any error in the Update message then a Notification message is sent to the peer, and BGP transitions back to the Idle state.
If a timer expires before a Keepalive message is received, or if an error condition occurs, the router transitions back to the Idle state.
BGP was created to replace the Exterior Gateway Protocol (EGP) protocol to allow fully decentralized routing in order to transition from the core ARPAnet model to a decentralized system that included the NSFNET backbone and its associated regional networks. This allowed the Internet to become a truly decentralized system. Since 1994, version four of the BGP has been in use on the Internet. All previous versions are now obsolete. The major enhancement in version 4 was support of Classless Inter-Domain Routing and use of route aggregationto decrease the size of routing tables. Since January 2006, version 4 is codified in RFC 4271, which went through more than 20 drafts based on the earlier RFC 1771 version 4. RFC 4271 version corrected a number of errors, clarified ambiguities and brought the RFC much closer to industry practices.
Most Internet service providers must use BGP to establish routing between one another (especially if they are multihomed). Therefore, even though most Internet users do not use it directly, BGP is one of the most important protocols of the Internet. Compare this with Signaling System 7 (SS7), which is the inter-provider core call setup protocol on the PSTN. Very large private IP networks use BGP internally. An example would be the joining of a number of large OSPF (Open Shortest Path First) networks where OSPF by itself would not scale to size. Another reason to use BGP is multihoming a network for better redundancy either to multiple access points of a single ISP (RFC 1998) or to multiple ISPs.
BGP neighbors, peers, are established by manual configuration between routers to create a TCP session on port 179. A BGP speaker will periodically send 19-byte keep-alive messages to maintain the connection (every 60 seconds by default). Among routing protocols, BGP is unique in using TCP as its transport protocol.
When BGP runs between two peers in the same autonomous system (AS), it is referred to as Internal BGP (IBGP or Interior Border Gateway Protocol). When it runs between autonomous systems, it is called External BGP (EBGP or Exterior Border Gateway Protocol). Routers on the boundary of one AS exchanging information with another AS are called border or edge routers. In the Cisco operating system, IBGP routes have an administrative distance of 200, which is less preferred than either external BGP or any interior routing protocol. Other router implementations also prefer EBGP to IGPs, and IGPs to IBGP.
Finite-state machine
In order to make decisions in its operations with other BGP peers, a BGP peer uses a simple finite state machine (FSM) that consists of six states: Idle; Connect; Active; OpenSent; OpenConfirm; and Established. For each peer-to-peer session, a BGP implementation maintains a state variable that tracks which of these six states the session is in. The BGP protocol defines the messages that each peer should exchange in order to change the session from one state to another. The first state is the “Idle” state. In the “Idle” state, BGP initializes all resources, refuses all inbound BGP connection attempts and initiates a TCP connection to the peer. The second state is “Connect”. In the “Connect” state, the router waits for the TCP connection to complete and transitions to the "OpenSent" state if successful. If unsuccessful, it starts the ConnectRetry timer and transitions to the "Active" state upon expiration. In the "Active" state, the router resets the ConnectRetry timer to zero and returns to the "Connect" state. In the "OpenSent" state, the router sends an Open message and waits for one in return. Keepalive messages are exchanged and, upon successful receipt, the router is placed into the “Established” state. In the “Established” state, the router can send/receive: Keepalive; Update; and Notification messages to/from its peer.
Idle State:
Refuse all incoming BGP connections
Start event triggers the initialization of
Initiates a TCP connection with its configured BGP peer.
Listens for a TCP connection from its peer.
Changes its state to Connect.
If an error occurs at any state of the FSM process, the BGP session is terminated immediately and returned to the Idle state. Some of the reasons why a router does not progress from the Idle state are:
TCP port 179 is not open.
A random TCP port over 1023 is not open.
Peer address configured incorrectly on either router.
AS number configured incorrectly on either router .
Connect State:
Waits for successful TCP negotiation with peer.
BGP does not spend much time in this state if the TCP session has been successfully established.
Sends Open message to peer and changes state to OpenSent.
If an error occurs, BGP moves to the Active state. Some reasons for the error are:
TCP port 179 is not open.
A random TCP port over 1023 is not open.
Peer address configured incorrectly on either router.
AS number configured incorrectly on either router.
Active State:
If the router was unable to establish a successful TCP session, then it ends up in the Active state.
BGP FSM will try to restart another TCP session with the peer and, if successful, then it will send an Open message to the peer.
If it is unsuccessful again, the FSM is reset to the Idle state.
Repeated failures may result in a router cycling between the Idle and Active states. Some of the reasons for this include:
TCP port 179 is not open.
A random TCP port over 1023 is not open.
BGP configuration error.
Network congestion.
Flapping network interface.
OpenSent State:
BGP FSM listens for an Open message from its peer.
Once the message has been received, the router checks the validity of the Open message.
If there is an error it is because one of the fields in the Open message doesn’t match between the peers, e.g. BGP version mismatch, MD5 password mismatch, the peering router expects a different My AS. The router will then send a Notification message to the peer indicating why the error occurred.
If there is no error, a Keepalive message is sent, various timers are set and the state is changed to OpenConfirm.
OpenConfirm State:
The peer is listening for a Keepalive message from its peer.
If a Keepalive message is received and no timer has expired before reception of the Keepalive, BGP transitions to the Established state.
If a timer expires before a Keepalive message is received, or if an error condition occurs, the router transitions back to the Idle state.
Established State:
In this state, the peers send Update messages to exchange information about each route being advertised to the BGP peer.
If there is any error in the Update message then a Notification message is sent to the peer, and BGP transitions back to the Idle state.
If a timer expires before a Keepalive message is received, or if an error condition occurs, the router transitions back to the Idle state.
