Intelligent Routing for BGP Networks

BGP – the protocol that runs the Internet

Border Gateway Protocol (BGP) is a distance-vector routing protocol that is used on the Internet and allows information sent from one Internet point to another to find the right path and reach the recipient.

Protocol terminology:

When it comes to BGP, the first thing to explain is the concept of an Autonomous System (AS). An Autonomous System is a collection of routing points and the connection between them, united by a common interaction policy, which allows this system to exchange data with the nodes that are outside of the system.

An Autonomous System is characterized by a 16-bit or 32-bit Autonomous System Number (ASN) and a pool of IP addresses. Both are issued by IANA (Internet Assigned Numbers Authority), which in its turn delegates control over the distribution of ASNs and other Internet resources to regional registrars.

The connectivity of Autonomous Systems is achieved through static or dynamic routing.

Static routing is quite simple and requires an engineer to manually set the route to the nearest neighbor. In practice, however, connecting even 10 routers to each other becomes a real challenge.

Therefore, dynamic routing was invented for large networks, where devices automatically share information about the available routes with each other and adjust to any topology changes.

Dynamic routing protocols are classified according to the two main characteristics:

1) The way the protocol works in relation to the Autonomous Systems:

• IGP (Interior Gateway Protocol) – working inside the Autonomous System. These include: RIP, OSPF, EIGRP, IS-IS
• EGP (Exterior Gateway Protocol) – working outside of the Autonomous Systems and ensure their connectivity. This includes BGP

2)  The protocol’s operation algorithm:

• Distance-Vector – knows the routes only to the nearest neighbors and exchanges a routing table with them. (RIP, EIGRP)
• Link State – knows the entire topology of the network and exchanges the topology table with its neighbors (OSPF, IS-IS)

Clearly, BGP can not be a Link State protocol. Just imagine how many Autonomous Systems are out there on the Internet! Any router will simply fail if it receives this great amount of information.

Thus, BGP is a distance vector exterior gateway protocol that connects Autonomous Systems. A simplified scheme looks something like this:

Since BGP is entrusted with the task of connecting Autonomous Systems throughout the Internet, it must be very reliable. Nevertheless, the protocol does not have a reliable transport method. Instead it leverages TCPs reliability to ensure that the messages and updates are received. At the very beginning, the BGP router initiates the establishment of a TCP session on port 179 to its neighbor. The standard exchange of SYN and ACK takes place.

BGP connections must be carefully coordinated by the administrators of the Autonomous Systems willing to connect. If, for instance, the administrator of AS20 has initiated the BGP process on BR2 (Border Router), specifying BR1 and its ASN as a neighbor, but the AS30 administrator has not done anything, the TCP session will not be established and the systems will remain disconnected. Moreover, the following conditions must be met:

• port 179 is not blocked by the ACL (Access Control List)
• routers can ping each other
• the ASN of the distant Autonomous System was specified correctly
• RouterIDs do not match

If the TCP session is established successfully, the BGP routers start exchanging OPEN messages, in which they report their ASN, RouterID and Hold time. Hold timer is the time during which the TCP session will be supported. In case the conditions listed above are not met, for example, the information about the AS number does not match, then the router receiving the incorrect ASN will notify its neighbor by sending a NOTIFICATION message and will end the TCP session.

If all the conditions are met, the routers start sending each other KEEPALIVE messages with a certain interval, meaning they confirm the parameters accepted in OPEN and sending the notification “I’m still alive”.

Finally, the routers can begin to exchange routing information using the UPDATE message.

The structure of this message consists of the following parts:

• Unfeasible routes length indicates the length of the Withdrawn Routes field
• Withdrawn routes contains IP address prefixes for the routes being withdrawn
• Total path attribute length indicates the length of the path attributes field
• Path attributes contains the properties of the routes: the path origin, preference for the route, the multi-exit discriminator (MED), as well as the information about confederations, communities, aggregation, and route reflection.
• NRLI (Network Layer Reachability Information) contains the information about the networks which are to be added into the routing table – the IP address of the network and its mask.

The UPDATE message is transmitted each time one of the routers receives information about the new networks, while the KEEPALIVE message throughout the entire TCP session.

NOTIFICATION Message is sent when an error is detected. The BGP connection closes immediately after the message is sent. Such message includes error code, its subcode, and also data related to the error.

BGP is most certainly the most complex IP routing protocol currently deployed in the internet. The information above is aimed to provide only the basic understanding of how the protocol works. For more in depth information please consult our Blog or the Resource Center guides.