Border Gateway Protocol – Finite State Machine (BGP-FSM)

Introduction

The BGP-FSM model presents different states during BGP neighbor negotiation: Idle, Connect, Active, OpenSent, OpenConfirm and Established. It also describes the events that launch changes from one state to another. This article is based on Based on RFC 4271 – A Border Gateway Protocol 4 (BGP-4).

There are 28 events, which are grouped into four categories.

• Administrative Events: Events that either start or stop the process.
• Timer Events: Expiration of HoldTimer, KeepaliveTimer or ConnectRetryTimer trigger this event.
• TCP connection based events: These events describe the different state of the TCP three-way handshake.
• BGP message based events: Receiving or sending BGP messages: OPEN, KEEPALIVE, UPDATE and NOTIFICATION launch this event.

A Complete list can be found in Appendix A.

Figure 1-1 shows the map of different states and related event numbers. Timers and counters are excluded from both the text part and picture to keep things as clear as possible.

Figure 1-1: Overview of BGP-FSM.

Start negotiation of the TCP connection

Idle

In the Idle state, the local BGP speaker is waiting for the Start-event. It does not accept incoming BGP connection from the peer, nor allocate any BGP resources to the peer.  For the reaction to the Start-event, the local BGP speaker will start initialization of TCP connection either actively or passively.

Connect

• ManualStart (event 1): an administrator starts BGP peer connection manually. After that, the local system starts sending and listening TCP SYN from/to port 179. This event can be started e.g. with basic BGP neighbor configuration under the BGP process.
• AutomaticStart (event 3): Same as Event 1, except the event starts automatically. This could happen for example if the administrator of the remote BGP speaker clears the BGP peering with the local system.

For the reaction to the event 1 “ManualStart” and event 3, “AutomaticStart”, the BGP-FSM changes state from Idle to Connect, where the local system is waiting for the TCP-connection to be completed.

Active

• ManualStart_with_PassiveTcpEstablishment (event 4): BGP connection started manually by an administrator, but the local system waits for a TCP SYN packet to port 179 from the remote BGP speaker. This can be done e.g. by setting transport mode to passive (1) or by using BGP Dynamic Neighbor solution (2). 

(1) neighbor 2001:DB8::915:9 transport connection-mode passive

(2) bgp listen range 10.15.9.0/24 peer-group DynNeigh_from_AS64502

• AutomaticStart_with_PassiveTcpEstablihment (event 5): The local system waits passively the TCP connection from a remote peer as in event 4. The start event happens automatically like in event 3.  

Reaction to either “ManualStart_with_PassiveTcpEstablishment” or “AutomaticStart_ with_PassiveTcpEstablishment” the state is changed from Idle to Active where local system is passively waiting for a TCP-connection to be completed.

If the local BGP speaker receives a TCP FIN packet (event-18 “TcpConnectionFail”) in Connect state, the state is changed either to Active or back to Idle depending on the DelayOpenTimer. If the DelayOpenTimer is running, the state will be changed to Active, otherwise back to Idle. If the ConnectRetryTimer expires (event “ConnectRetryTimer_Expires”) in Connect state, the state does not change. As a response to” “ConnectRetryTimer_Expires” event in the Active state, the state will be changed to Connect.

The reaction for the error/stop event or a NOTIFICATION message, the locals system will change BGP FSM state to Idle from Connect/Active states.

Figure 1-2: Moving from Idle either to Connect/Active.

Finalizing negotiation of the TCP connection

Finalizing the TCP connection from either Connect/Active state follows the same procedure. In our example there are four events related to the TCP three-way handshake:

• TcpConnection_Valid (Event 14): This event occurs when the local system receives a TCP Connection Request (TCP SYN) from the peer BGP speaker with a valid source address (configured as a neighbor) and it is destined to the address that the local system uses as a source in BGP negotiation. In addition, the destination TCP port should be 179.
• Tcp_CR_Invalid (Event 15): This event occurs when the local system receives a TCP Connection Request (TCP SYN) from the remote BGP speaker and the validity check does not pass.
• Tcp_CR_Acked (Event 16): This event indicates that the local system has sent ACK message to the remote peer as a confirmation of SYN ACK message sent by the remote peer.
• TcpConnectionConfirmed (Event 17): This event indicates that the local system has received ACK messages from the peer BGP speaker.

There is also BGP “Message Based Event” (event 20) and “Timer Event” (event 12) involving in these states:

• BGPOpen with DelayOpenTimer running (Event 20): This event happens if the local system received valid BGP OPEN message from the remote BGP speakers, while local systems own DelayOpenTimer is still running.
• DelayOpenTimer_Expires (Event 12): After TCP initialization, BGP speaker sends an OPEN message. If the DelayOpen -session attribute is set to TRUE, it can delay the sending of a BGP OPEN message by the time specified in DelayOpenTimer.

Figure 1-3: Moving to OpenSent or OpenConfirm.

When the local system receives a TCP SYN messages, it validates the packet. If the validity check is ok (event 14, “TcpConnection_Valid”), the local system will send the SYN ACK message to the remote peer. If the packet is not valid, (event 15, “Tcp_CR_Invalid”), the local system sends a TCP RST message and stays in the current state. When the remote peer receives the SYN ACK, it finalizes the TCP three-way handshake by replying with an ACK message (event 16“Tcp_CR_Acked”). When the local system receives the ACK message (event 17, “TcpConnectionConfirmed”), the TCP three-way handshake is complete.

After successful TCP negotiation, BGP peers will exchange BGP OPEN messages either right away or with a short delay defined by the time of DelayOpenTimer. If the timer is not running, the local system sends an OPEN message right away and the BGP FSM state will be changed to OpenSent. If the DelayOpenTimer is running and the local system has not yet received BGP OPEN message from the remote peer, the local host waits for the DelayOpenTimer expiration, (event 12, “DelayOpenTimer_Expires”). Then it will send an OPEN message to peer and the BGP-FSM state is changed to OpenSent.

If the local system receives an OPEN message while DelayOpenTimer is running (event 20 “BGPOpen with DelayOpenTimer running”), it sends both OPEN and KEEPALIVE messages to peer and BGP-FSM change state to OpenConfirm.

Validation of the BGP neighbor

After successful TCP negotiation, the BGP speakers exchange BGP OPEN messages to ensure that, they use the same version of BGP, their BGP identifiers do not overlap and they support the same set of capabilities. They also compare the HoldTime values and they choose the smaller one if values are not the same. If everything goes well, the state will be changed to OpenConfirm or Established. If the OPEN message check does not pass, the state will change to either Active or Idle.

In addition to previously introduced events, there are two BGP related events:

• BGPOpen (Event 19): When BGP speaker receives BGP OPEN messages, it validates the messages (BGP version has to be the same, correct AS number, BGP RID do not overlap, the same set of supported capabilities).
• KeepAliveMsg (Event 26): This event indicates that local system has received KEEPALIVE from the peer.

There is also two Timer based (11 and 12) events and one TCP Connection based event (18) related to this chapter:

• KeepaliveTimer_Expires (Event 11): As the name indicates, this event indicates that Keepalive timer has been expired.
• DelayOpenTimer_Expires (Event 12): This event is caused by the expiration of the DelayOpenTimer.
• TcpConnectionFail (Event 18): This event occurs if the local system receives a TCP FIN message from the remote BGP speaker or if the existing TCP connection is timed out and DelayOpenTimer is not running.

Following two events are related to the Established state.

• UpdateMsg (Event 27): This event occurs as a response to the valid update message.
• UpdateMsgErr (Event 28): This event occurs as a response to the invalid UPDATE message.

OpenSent and OpenConfirm

When the local system receives an OPEN message, while in the OpenSent state, the local system validates remote peers’ AS number, BGP Router-ID and supported capabilities. If everything is ok (event 19, “BGPOpen”), the local system sends OPEN and KEEPALIVE messages, after that it changes BGP-FSM state to OpenConfirm.

When the local system receives any TCP based events (14, 16 or 17), while in the OpenSent state, the second connection may be in progress. Then the local system will track the connection until it receives an OPEN message. If the local system receives a TCP SYN message during this state, it goes through the normal TCP three-way handshake process. If the local system receives a TCP FIN message from the remote peer, event 18 occurs and state is changed to Active.

When the BGP FSM of local system is in the OpenConfirm state, it sends a KEEPALIVE messages to the remote peer. After receiving KEEPALIVE message from the remote peer as a response (event 26 “KeepAliveMsg”), the local system finalizes the BGP connection and moves BGP-FSM state to Established. If the Keepalive timer expires (event 11 “KeepaliveTimer_Expires”) before the local system receives an OPEN message from the remote peer, the BGP-FSM state does not change. Reaction to the TCP based events 14, 16 or 17 is same than in OpenSent state.

Established

In Establish state, BGP FSM reacts to event14 “TcpConnection_Valid” in the same way as in the OpenSent or OpenConfirm state, the local system will track the connection until it receives an OPEN message. In this state, BGP peering is up and running and BGP neighbors can send and receive UPDATE, KEEPALIVE and NOTIFICATION messages.

In Established state, the local system validates all received UPDATE messages. An example of the validation is a next-hop reachability checking. The Next-hop address must be other than the receiving BGP speakers’ address. If peers are directly connected eBGP neighbors, the next-hop address has to be either senders IP- address that is used in BGP neighbor negotiation or it has to be from the same network segment than receivers IP-address (e.g. in the case of BGP redirect). Event 27 “UpdateMsg” indicates valid UPDATE message and while event 28 “UpdateMsgErr” indicates invalid UPDATE message.

Reaction to error/stop event or a NOTIFICATION message, the locals system will change BGP FSM state to Idle from OpenSent/OpenConfirm states.

When the local system receives a BGP message from the remote peer (not shown in the flow chart), it validates the header of the message by checking that all bits in the Marker field are set to one and the length field is in between 19 – 2096. Failure in either condition will cause event 21 “BGPHeaderErr”. Another check is only related to the OPEN message, if the length field is under minimum requirement 29 octets, event 22 “BGPOpenMsgErr” occurs. Both events, BGPHeaderErr” and “BGPOpenMsgErr” change the BGP FSM state to Idle.

Figure 1-4: Finalizing BGP neighbor negotiation.

Appendix A: List of additional NOTIFICATION message events and error events

Administrative Events:

Event 1. ManualStart

Event 2. ManualStop

Event 3. AutomaticStart

Event 4. ManualStart_with_PassiveTcpOpen

Event 5. AutomaticStart_with_PassiveTcpOpen

Event 6. AutomaticStart_with_DampPeerOscillations

Event 7. AutomaticStart_with_DampPeerOscillations_andPassiveTcpEstablishment

Event 8. AutomaticStop

Timer Events:

Event 9. ConnectRetryTimer_Expires

Event 10. HoldTimer_Expires

Event 11. KeepaliveTimer_Expires

Event 12. DelayOpenTimer_Expires

Event 13. IdleHoldTimer_Expires

TCP Connection-based Events

Event 14. TcpConnection_Valid

Event 15. Tcp_CR_Invalid

Event 16. Tcp_CR_Acked

Event 17. TcpConnectionConfirmed

Event 18. TcpConnectionFails

BGP Message-Based events:

Event 19. TcpConnection_Valid

Event 20. BGPOpen with DelayOpenTimer running

Event 21. BGPHeaderErr

Event 22. BGPOpenMsgErr

Event 23. OpenCollisionDump

Event 24. NotiMsgVerErr

Event 25. NotiMsg

Event 26. KeepAliveMsg

Event 27. UpdateMsg

Event 28. UpdateMsgErr