The Border Gateway Protocol (BGP) is an exterior gateway protocol. Routers use it to exchange routing information between Autonomous Systems. In 1989, the Internet Engineering Task Force (IETF) defined this protocol in the RFC 1105. Since 1994, it has been the building block of the Internet.
Moreover, this protocol is:
- A path vector routing protocol that selects routes by exchanging lists of Autonomous Systems’ Paths (AS_PATH’s). Each AS_PATH lists all the Autonomous Systems that a packet needs to traverse to reach a destination network.
- Uses Classless Inter-Domain Routing (CIDR) to allocate IP addresses efficiently with variable-length subnet masks (VLSMs). This helps to reduce the size of routing tables and allows for more flexible address management across autonomous systems.
Internal and External Peering
Routers exchange Network Layer Reachability Information (NLRI), which contains details about the network prefixes that are reachable. This information helps routers make decisions about the best paths for routing data across the network.
The peering relationship between two routers can be internal or external BGP. If the two routers have the same Autonomous System Number, it’s internal (iBGP), otherwise it’s external (eBGP). Another difference between internal and external peering is on the connection.
Generally two internal peers don’t reside on the same subnet. They can reach each other by using an internal gateway protocol, such as open shortest path first (OSPF). On the other hand, two external peers need to connect directly and reside on the same subnet.
The type of peering dictates the method based on which routers exchange AS_PATH updates. For example: updates received by eBGP peers propagate to other eBGP and iBGP peers. A router propagates routes received from iBGP peers to eBGP routers only. This strategy prevents causing routing loops.
This mechanism, split horizon, enables distance vector protocols to avoid routing loops. In this case, split horizon requires iBGP routers to be fully-meshed together to assure proper route propagation.
Message Types
BGP establishes peering relationships between routers using the TCP protocol port 179. Routers exchange five message types:
- Open – To exchange application parameters.
- Update – To exchange AS_PATH information.
- Notification – To transmit error messages.
- Keepalive – A router regularly sends this message to maintain a peering relationship.
- Route-Refresh – To request route re-advertisement.
Timers
A peering relationship between two border routers follows a finite state machine with six peering states. Moreover, the peering states follow three timers:
Connect Retry timer defaults to 120 seconds. The routing process tries to reconnect to the configured peer when this timer expires.
Hold Time timer defaults to 90 seconds. This is the longest time to wait for a Keepalive or Update message before closing a peering connection.
Keep Alive timer defaults to 30 seconds. A router sends a Keepalive message each time this timer expires.
Peering States
The six peering states are the following ones:
- Idle – This is the initial state where the router refuses all connections.
- Connect – The router is waiting for the completion of the TCP/IP connection:
- If the TCP connection is successful, the router sends an Open message, and the state will transition to Open Sent.
- If the TCP connection fails, the state will transition to Active and continue to listen for incoming TCP connections.
- If the Connect Retry time expires, the routing process resets the time and loops back to the Connect state.
- If any other event, BGP goes to Idle.
- Active – The router is listening for and accepting TCP connections:
- If the TCP connection succeeds, BGP sends a Passive Open, moves to the Open Sent state, and then sends an additional Open message.
- If the Connect Retry timer expires, BGP restarts the timer. It then initiates a connection to the peer and moves to the Connect state.
- If the peer is not an expected one, the router rejects the connection attempt and stays in the Active state.
- Open Sent – The routing process is waiting for an Open message from its peer:
- If the BGP process detects an error in the Open message, it sends a notification message and moves to the Idle state.
- If the Open message is valid, BGP sends a Keepalive message. It then compares the parameters in the message and moves to the Open Confirm state.
- If the TCP connection ends, BGP closes the connection and moves to the Active state.
- If any other event occurs, the BGP process sends a Notification message and moves to the Idle state.
- Open Confirm – The routing process is waiting for a Keepalive or Notification message:
- If the BGP process receives a Keepalive message, it moves to the Established state.
- If the Keep Alive timer expires, BGP sends a Keepalive message and resets its Keep Alive timer.
- Established – This is BGP’s operational state during which BGP exchanges Update, Notification, and Keepalive messages:
- If the Keep Alive timer expires, the BGP process sends a Keepalive message and resets the timer.
- Each time BGP sends Keepalive and Update messages, it resets the Keep Alive and the Hold Time timer.
- If an unexpected event occurs, BGP sends a Notification message and switches to the Idle state.
Putting it all together, we get to the BGP finite state machine, as depicted in the following picture:
Figure 1: The BGP finite state machine (not all transitions listed)
Path Attributes
An attribute defines the characteristics of the paths that an Update message carries. The path attributes fall into the four categories:
- Well-known mandatory
- Well-known discretionary
- Optional transitive
- Optional non-transitive
Every Update message must include a Mandatory attribute. Discretionary ones don’t have to.
A router should always accept path updates with a transitive attribute. This applies to updates that includes unsupported optional attributes. A router should send these updates to its neighbors. A router can quietly ignore and not advertise non-transitive updates.
Update messages attributes
| Type Code | Name | Details | Category |
|---|---|---|---|
| 1 | ORIGIN | Set by the originating AS to i for IGP, e for EGP, and ? if incomplete. | Well-known mandatory |
| 2 | AS_PATH | Set by the border router when the update leaves the AS, the leftmost enter is the AS that sent the prefix to you, while the rightmost entry is the originator of the prefix. | Well-known mandatory |
| 3 | NEXT_HOP | Set by the router to the local interface address used to reach the neighbor. In iBGP peering is not changed, in eBGP peering is changed. Set when an update crosses an AS boundary. | Well-known mandatory |
| 4 | MULTI_EXIT_DISC | Defines the preferred entry point to the local AS. | Optional non-transitive |
| 5 | LOCAL_PREF | Included in Update messages that a BGP speaker sends to its iBGP neighbors. Updates with higher local preferences are used. | Well-known discretionary |
| 6 | ATOMIC_AGGREGATE | When presented with a set of overlapping routes, a router selects a less specific route and BGP attaches this attribute. | Well-known discretionary |
| 7 | AGGREGATOR | AS number and router ID of the router that creates the aggregate route. | Optional transitive |
| 8 | COMMUNITY | Group of destinations which share some common property. | Optional transitive |
| 9 | ORIGINATOR_ID | Carries the router ID of the router originator in the local AS while route reflection is deployed. | Optional non-transitive |
| 10 | CLUSTER_LIST | A cluster is represented by a CLUSTER_ID. A CLUSTER_LIST is a sequence of CLUSTER_ID values that represents the path that the route has passed along. | Optional non-transitive |
The Path Selection Criteria
The BGP path selection criteria defines the selections of routers, or paths, to reach a specific destination network. BGP manages this process by using three routing tables:
- Adj RIB-IN – Routing information learned from inbound Update messages.
- Local RIB – Local routing information that BGP has selected by applying its local policies to the Adj RIB-IN.
- Adj RIB-OUT – Routing information that BGP has selected for advertisement to its peers.
The BGP route selection criteria is the following:
- Highest local preference.
- Shortest AS_PATH.
- Lowest origin code where IGP = 0, EGP = 1, Incomplete = 2.
- Lowest MULTI_EXIT_DISC.
- Prefer eBGP over iBGP paths.
- Lowest IGP cost to next-hop.
- Lowest BGP router ID.
- Shortest CLUSTER_LIST.
- Lowest peer IP address.
Worth noting that networking vendors might use different criteria for path selection. They may also include extra checks in their algorithms. For example, Cisco adds step 0 with a proprietary weight attribute. Other implementations may also add a step in the process that prioritizes older routes over newer ones.
To verify what routes a BGP process is using, routers have commands in place that will mark routes with the following flags:
- Used: The Forwarding Information Base (FIB) uses these routes. The routing table manager chose them as the best or active routes. Routers propagate these routes to their neighbors.
- Best: It’s the best route based on the path selection criteria.
- Valid: The entry is present in the RIB.
Also in this case, each networking vendor may implement its own way of reporting this information.
Conclusion
In conclusion, the Border Gateway Protocol is a foundational component of the Internet. It enables routing between Autonomous Systems through a path vector approach.
By distinguishing between internal and external connections, this protocol prevents routing loops and ensures stable path selection. BGP operates through a finite state machine governed by timers and message exchanges. Each peering state dictates how to establish and maintain connections. Path attributes—mandatory, discretionary, transitive, and non-transitive—play a critical role in route advertisement and selection.
Ultimately, its route selection has a defined hierarchy of criteria. Although implementations may vary by vendor, BGP is a robust and flexible protocol for inter-domain routing.
