\section{BGP}

The Border Gateway Protocol version 4 (BGP)\cite{FreedmanBGP} is a routing
protocol, as defined in RFC~1773\cite{rfc1773}.  BGP is used to communicate
routing information between different providers on the Internet and for
this reason reflects the path that traffic will take from a given point on
the Internet.


\subsection{Routing Protocols}

A \emph{route} is a a set of addresses and the next hop used to send
traffic to the addresses. A \emph{router} is nominally  a host that has
more than one network interface and makes decisions about to which
interface a given packet should be sent.  As network topologies become more
complex, the number of different routes increases, as does the frequency of
routes changing.  For this reason it is useful for routers to have a method
for dynamically updating routes as the network topology changes, that is,
as other routers come and go from the network either because of
administrative changes or failures of routers or links between routers.

Routing protocols are a mechanism for routers to communicate routes with
each other. Routers that communicate routes with each other are referred to
as \emph{peers}. When routes are sent between routers they contain
information in addition to the addresses that the route covers and the next
hop for this traffic. The additional information may be used to expire the
route and to determine the cost of the route relative to other routes. When
a router sends such a route it is said to be \emph{advertising}. A route
advertisement can be seen as a promise to deliver traffic for a given set
of addresses.  Advertising routes that cannot be satisfied leads to either
\emph{routing~loops} or \emph{black-holing}. A routing~loop refers to
traffic bouncing between routers until the maximum hop count is reached.
Black-Holing refers to receiving traffic and then discarding it.  In either
case the addresses covered by the route is effectively removed from the
network.

A \emph{prefix} is a set of network addresses that a given route covers. In
routing protocols this is given as either a classful network or in the case
of more recently developed routing protocols a CIDR network. Classless
Inter-Domain Routing (CIDR) is defined in RFC~1519 \cite{rfc1519}.
CIDR networks allow networks
to be defined as a network address and a netmask, enabling more flexible
division of networks than classful routing.

When peers are configured to communicate routes with each other they are
said to have a \emph{session} running. When the session is established the
routers advertise routes to each other and each router uses this
information to determine the best route for each prefix that has been
advertised to it or is advertised by it.  When a session goes down, either
administratively or because of a timeout, the prefixes advertised by the
peer in question are removed, enabling the network to adapt to failures.


Routing protocols are divided into two types: Interior~Gateway~Protocol
(IGP) and Exterior~Gateway~Protocol (EGP). An IGP is concerned with
managing routes within a single network, ensuring that each point of the
network is able to get to all other points in the network. An EGP
communicates information about which addresses are within a network or may
be accessed through a network. When BGP is used to communicate routes
between different networks on the Internet, it is being used as an EGP.

\subsection{Autonomous Systems}

\begin{figure}[!hbt]
  \begin{center}
    \includegraphics[width=13cm]{abc_transit.eps}
  \end{center}
  \caption{Network Diagram -- Transit}
  \label{abc-transit-figure}
\end{figure}

When networks communicate routes using BGP, individual networks are
identified using an Autonomous~System (AS) Number as defined in 
RFC~1930\cite{rfc1930}.  Each route communicated
using BGP contains an \emph{AS~path}, an ordered list of ASes that the
route has been advertised by.

As an example suppose that there are three networks, imaginatively named
Network A, B and C, as per figure~\ref{abc-transit-figure}. These Networks
have the AS numbers 64600, 64601 and 64602 respectively. Networks A and C
are each directly connected to B.  A \emph{border~router} is a router on
the edge of a network that communicates directly with routers on other
networks.  BGP peering sessions are run between border~routers in Networks
A and B and Networks B and C.  There is no direct link between Networks A
and C, rather these networks see routes to each other that transit through
Network~B.  This given, the AS~path on a router in Network~A for a prefix
advertised by Network~C would be 64601~64602, showing that the route
originated from AS64602 and was transited through AS64601.  In other words,
traffic will travel through Network~B to get to its ultimate destination,
Network~C.



\subsection{Finding The Peer Closest to a Client}
\label{bgp-algorithm}

\begin{figure}[!hbt]
  \begin{center}
    \includegraphics[width=13cm]{abc_pop.eps}
  \end{center}
  \caption{Network Diagram -- Points of Presence}
  \label{abc-pop-figure}
\end{figure}

Now suppose that a provider has two POPs, one on each of Network A and C,
called POP X and Y respectively. This is shown in
figure~\ref{abc-pop-figure}. By obtaining BGP information from upstream
networks and the other POP it is possible for a POP to determine which POP
is closest to a given IP address. That IP address could be that of a client
wanting to access a service available on both POPs. The result could be
used to determine which POP the client should connect to.

To do this each POP has an AS Number, this may be from the range 64512 to
65535, which is reserved for private use by the
Internet~Assigned~Numbers~Authority (IANA) as described in RFC~1930.  All
ASes used in theses examples are from this range. All IP addresses
used in examples are from ranges reserved for private use as per
RFC~1918\cite{rfc1918}.

Each POP sets up a BGP session with its upstream network or networks.  In
this example POP~X will have a BGP session with a router in Network~A.
Similarly for POP~Y and Network~C. As the POPs will not be originating any
valid routes it is important that the POPs are configured not to send any
routes to the upstreams and the upstreams are configured not to accept any
routes from the POPs. This is referred to as \emph{filtering}.  Once these
BGP sessions are established each POP has a view of all the routes that its
respective upstream has. This is extendible to POPs with multiple
upstreams by the POP in question establishing BGP sessions with each of
its upstreams.  By establishing a \emph{multi-hop~BGP~Session} between POPs
X and Y it is possible for each POP to see the view of the network that POP
has, and in turn the view that POP's upstream has. 

If the router running the BGP sessions to Network~A from POP~X is queried
for the prefix used to route traffic to an address in Network~C then there
are two probable answers; A prefix with the AS path 64600~64601~64602 as
learned through the BGP session with Network~A, or a prefix with AS path
64702~64602 as learned through the multi-hop BGP session with POP~Y.  The
latter prefix should be preferred as it has a shorter AS path, though it is
possible to change this using weights. As the preferred path contains the
AS number of POP~Y, this must be closer to the the queried address in terms
of the BGP routing topology.  This means that if the AS number for one of
the POPs appears in the AS path for a preferred prefix then the
corresponding POP must be closer to the addresses covered by the prefix
that the POP making the request. If the AS numbers of multiple POPs appear
in the AS path then the last POP in the AS path must be closest, as AS
numbers at the end of the AS path are closer to the origin than those at
the beginning.
