BGP

The Border Gateway Protocol (BGP) is the main inter-autonomous system routing algorithm used in the network layer’s control plane. It is a distributed and asynchronous protocol.

It allows a subnet to advertise its existence and the destinations it can reach to the rest of the Internet. BGP provides each AS a means to determine routes to other networks based on this reachability information and a specific policy (determining what information is propagated to other networks, i.e., maybe don’t advertise a particular path).

• In eBGP — obtain destination network reachability information from neighbouring AS, and advertise destination reachability information.
• In iBGP — propagate the reachability information to all AS-internal routers.

Specification

A single BGP session is between two BGP routers (peers, speakers) over a semi-permanent TCP connection on port 179. They advertise paths to different destination network prefixes (e.g., to a destination /16 network). BGP is a “path vector” protocol. When an AS’ gateway router advertises a path to a specific router, it essentially promises that it is able and willing to forward datagrams towards that router.

There are a few important types of messages:

• OPEN: opens a TCP connection to a remote BGP peer and authenticates the sending BGP peer.
• UPDATE: advertises a new path or withdraws an old path.
• KEEPALIVE: keeps the connection alive in the absence of UPDATE messages. Also used to ack an OPEN request.
• NOTIFICATION: reports errors in a previous message. Also used to close the connection.

Pathfinding

A BGP advertised path consists of a prefix (the CIDR destination being advertised) and a set of attributes associated with the path. The CIDR destination can condense how much information needs to be stored. There are 2 important attributes:

• AS-PATH is a list of AS through which the prefix advertisement has passed.
• NEXT-HOP: indicates the specific internal AS-router to the next-hop AS.

BGP uses policy-based routing. A router receiving a route advertisement to destination X uses a policy to decide whether or not to accept/reject a path (e.g., never route through AS W or country Y). It uses the policy to decide whether to advertise a path to a neighbouring AS (maybe we don’t want to forward some traffic from AS W). It’s possible for gateway routers to learn about multiple paths to a destination. The choice of which policy to take (and advertise further) is dependent again on policy.

Some ISPs actually want to avoid “transit traffic” that doesn’t originate/end at their networks because transit traffic doesn’t generate any income. So even though there may be a link for some datagrams, it doesn’t exist for others. Another case is where a customer is connected to 2 provider networks. If it doesn’t want to route traffic between these networks, then it doesn’t have to advertise the path!

Path advertisement is a simple set of steps:

• A gateway router receives a path advertisement ASw, X (where X is a router) via eBGP.
• If the policy is to accept it, then the gateway router propagates (via iBGP) to all of its intra-AS routers. So all internal routers find out about this path.
• Then, if the policy is to propagate it, then a gateway router with a connection to another AS will advertise the path ASself, ASw, X to another AS.
  • i.e., the AS is prepended to the advertisement.

Hot potato routing chooses the local gateway that has the least intra-domain cost, i.e., it is local within an AS. It tries to get the packet out of the AS with as least cost as possible.

This might result in a poorer global inter-domain cost. But policy in general can result in this, so this is fine to lose out on.