std::bodun::blog

BGP in a Nutshell

Border Gateway Protocol (BGP) protocol has a very simple purpose: choose the fastest and the most efficient route to deliver a message from one autonomous system (AS) to another. In layman’s term, BGP is the GPS for the internet. Many contents here are credit to Prof. Mohamed G. Gouda.

In a nutshell, BGP informs each router $$R$$ how to route packets to an IP prefix $$pf$$ (i.e. block of IP addresses) that is used in $$AS_i$$ different from $$AS_j$$, where $$R$$ is located:

BGP consists of two parts:

Gateway: A gateway is defined as a router that is connected to computer in two or more ASes.

Abstractly, each router has a BGP routing table in the form of:

$(\text{prefix in another AS},\ \text{best ngh (next gateway hop) to reach prefix})$

eBGP

First we will go over eBGP. We know BGP uses TCP to send messages and eBGP is no exception. The TCP connection exists between:

1. each two gateways in the same AS, and
2. each two ‘‘adjacent’’ gateways in different ASes.

These gateway pairs sent route advertisements in the following form (represented as a tuple):

$(prefix,\ AS\text{-}path,\ next\text{-}hop)$

The BGP next-hop attribute is the next hop IP address that is going to be used to reach a certain destination.

Here is an example illustrating how one AS lets other ASes know the route leading to itself. Assume we have three ASes. AS1 wants other ASes to know how to reach itself:

AS1 is trying to broadcast the path to reach itself, it sends the first route advertisement message (1) as:

$(pf,\ (AS1),\ x)$

Now AS2 receives the message from AS1, it updates the AS-path by appending itself to the path list. It also needs to update the next-hop attribute because an incoming message needs to find the best address to reach AS2 before reaching AS1. AS2 broadcasts the message (2) as:

$(pf,\ (AS1, AS2),\ y)$

Each gateway $$A_i$$ or $$B_j$$ will also add an entry to its BGP routing table, thus each gateway in the picture will have its routing table like: $$A_2:\ (pf,\ B_1)$$, $$B_2:\ (pf,\ \text{ngh to }x)$$, $$A_3:\ (pf,\ B_2)$$.

Notice $$B_2$$ doesn’t have an explicit next-gateway-hop in its routing table. This is because so far we’ve only covered eBGP which works across different ASes. For a message to go from $$B_2$$ to $$x$$, it must go through routers inside AS2 internally, which brings up internal BGP (iBGP).

iBGP

For iBGP, there is a TCP connection between each two routers in the same AS, given the only one of them is a gateway.

Here is an example. Suppose the gateway $$A$$ in $$AS_j$$ needs to broadcast its routing information to other routers in $$AS_j$$:

The normal eBGP advertisement will be something like $$(pf,\ (AS_1,\ …,\ AS_j),\ x)$$.

For iBGP, the protocol states that the next hop advertised by eBGP should be carried into iBGP. Therefore, for all routers $$C_1,\ …,\ C_n$$, the next hop to reach $$pf$$ will be $$x$$ which is provided by $$AS_i$$. It’s your job to make sure $$x$$ is reachable via IGP.

For the iBGP advertisement, it will only be $$(pf,\ x)$$. Intuitively, this makes sense, because we only need to worry about the next best hop to reach $$pf$$ without worrying about changing the AS. All the routers ($$C_1,\ …,\ C_n$$) receiving the advertisement from $$A$$ will add the information to their routing table as:

$(pf,\ \text{best ngh to }x)$

That is it. There’s really nothing difficult about BGP in general.