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:

• external BGP (eBGP): informs each gateway
• internal BGP (iBGP): informs each non-gateway router

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):...