Computer Networking › Section E · The network layer: control plane › Topic E.3

Routing among ISPs: BGP

OSPF finds paths inside one network, but a packet from Lagos to Lima crosses many networks owned by companies that compete, cooperate and bill each other. The Border Gateway Protocol glues them together, and its choices are driven as much by business as by distance.

What BGP must do

Inside an AS, a router can reach any internal subnet using OSPF or IS-IS, as Intra-AS routing: OSPF showed. For destinations outside the AS it needs something else, because every AS chooses its own internal protocol and hides its internal design. The Border Gateway Protocol (BGP) is the one inter-AS routing protocol that every AS runs. BGP-4, specified today in RFC 4271, lets each AS do two things: learn from its neighbouring ASes which destination prefixes they can reach, and decide the best route to each prefix. Routes are advertised per prefix, such as 203.0.113.0/24, not per host, and BGP is a decentralised, asynchronous protocol in the distance-vector family.

Sessions: eBGP and iBGP

A router at the edge of an AS that links directly to a router in another AS is a gateway router. Routers exchange BGP messages over semi-permanent TCP connections on port 179, called BGP sessions. A session between routers in different ASes is external BGP (eBGP); a session between routers in the same AS is internal BGP (iBGP). Typically a gateway learns a route over eBGP from a neighbouring AS and then spreads it over iBGP to every other router in its own AS, so all of them know which gateway leads to that prefix. iBGP is not a separate protocol, just BGP between routers of the same AS.

Attributes: AS-PATH and NEXT-HOP

A BGP route is a prefix plus attributes. AS-PATH lists the ASes the advertisement has passed through: when an AS forwards an advertisement to a neighbour, it prepends its own AS number. That gives loop detection for free, since a router that finds its own AS number already in the path rejects the route. NEXT-HOP gives the address of the neighbouring gateway's interface where the advertised path begins, telling routers which exit to aim for. A router combines BGP and OSPF: BGP says that a prefix is reached via a next hop, and the intra-AS protocol says which local interface leads to that next hop. That pair becomes the forwarding-table entry.

Hot potato routing

Suppose a router learns two routes to a prefix through two different gateways of its own AS. A simple rule, hot potato routing, picks whichever gateway is cheapest to reach by intra-AS cost, that is, the route whose NEXT-HOP is closest. The idea is to hand the traffic, like a hot potato, to another AS as soon as possible, cutting the cost of carrying it inside one's own network. It is selfish: the route chosen may be much longer end to end, and two routers in the same AS may pick different gateways for the same prefix, each closest to itself.

The route-selection procedure

In practice BGP uses hot potato only as a later tie-breaker. When a router has several routes to the same prefix, it eliminates candidates in order until one remains. 1. Highest local preference, a value set by the AS's own policy. 2. Among those, the shortest AS-PATH. 3. Among those, the closest NEXT-HOP router by intra-AS cost, which is hot potato routing. 4. If several still remain, BGP identifiers break the tie. Real routers check a few more attributes along the way, but these four steps capture the logic: policy first, then path length, then internal cost.

Worked example: choosing among three routes

A router in AS 64500 has three routes to 198.51.100.0/24. Route X: local preference 100, AS-PATH 64510 64520, next hop 4 intra-AS cost units away. Route Y: local preference 100, AS-PATH 64530, next hop 9 units away. Route Z: local preference 80, AS-PATH 64540, next hop 1 unit away. 1. Highest local preference is 100, so Z is out despite its nearby next hop. 2. Between X and Y, Y's AS-PATH has 1 AS and X's has 2, so Y wins. 3. Hot potato is never reached. Check: had Y's path also had 2 ASes, step 3 would pick X, the closer next hop.

Policy: customers, peers and providers

ISPs relate in three ways. A customer pays a provider to carry its traffic to and from the rest of the internet. Two peers swap traffic for free, each carrying only traffic to and from its own customers. To earn money and avoid carrying traffic for free, an AS usually gives highest local preference to routes learned from customers, then peers, then providers. It also filters what it advertises. Routes from customers go to everyone, since that traffic is paid for. Routes from a peer or a provider go only to its customers. An AS with several providers, called multihomed, therefore never offers itself as a transit path between them.

Worked example: who hears which route?

AS 64501 has a customer, AS 64502, a peer, AS 64503, and a provider, AS 64504. 1. It learns 203.0.113.0/24 from its customer 64502. It advertises this to its peer and its provider, because it is paid to carry traffic to that customer. 2. It learns 192.0.2.0/24 from its peer 64503. It advertises it to customer 64502 only; telling its provider would invite traffic it must carry without payment. 3. It learns a route from provider 64504 and advertises it only to 64502. Check: 64501 carries traffic between two other networks only when at least one of them is its paying customer.

Anycast, getting online, and security

BGP also enables IP anycast. Many sites, such as copies of a DNS root server or a CDN, announce the same prefix, and each router's ordinary route selection sends traffic to a nearby one. To put a new company online, it obtains a prefix, often from its ISP, and that ISP announces it into BGP. BGP originally believed every announcement, so a mistaken or malicious origin can hijack a prefix: in February 2008 a Pakistan Telecom announcement for part of YouTube's address space spread worldwide and cut YouTube off for about two hours. Resource Public Key Infrastructure (RPKI) lets routers check that an AS is authorised to originate a prefix.

Common mistakes to avoid

First, assuming BGP always picks the shortest AS-PATH; local preference, set by business policy, is checked first. Second, thinking BGP advertises individual hosts; it advertises prefixes. Third, confusing eBGP, between ASes, with iBGP, which spreads routes within one AS and is not an intra-AS routing protocol like OSPF. Fourth, forgetting that BGP runs over TCP, port 179. Fifth, believing an AS passes on every route it hears; export filtering keeps it from carrying traffic between its providers or peers for free. Sixth, thinking hot potato routing minimises end-to-end distance; it minimises cost inside one's own AS.

Key takeaways

BGP-4 (RFC 4271) is the inter-AS routing protocol every AS runs. Routers exchange prefix advertisements over TCP port 179, using eBGP between ASes and iBGP within one. AS-PATH lists the ASes passed through and blocks loops; NEXT-HOP names the gateway, reached by intra-AS routing. Route selection runs: highest local preference, shortest AS-PATH, closest NEXT-HOP (hot potato), then identifiers. Policy prefers customer routes over peer over provider routes and exports peer and provider routes only to customers. Anycast uses BGP to reach the nearest copy of a service; prefix hijacks motivate RPKI origin validation.

Flashcards

Flashcard

BGP

Border Gateway Protocol, the inter-AS routing protocol

BGP-4, RFC 4271.

Test your understanding

Question 1 of 5

Route A has local preference 120 and AS-PATH of 3 ASes; route B has local preference 100 and AS-PATH of 1 AS. Which does BGP select?

Question 2 of 5

A BGP router receives an advertisement whose AS-PATH already contains its own AS number. What does it do?

Question 3 of 5

An AS learns a route from one of its providers. To which neighbours does it normally advertise that route?

Question 4 of 5

Two routes tie on local preference and AS-PATH length. Their NEXT-HOP routers are 3 and 7 intra-AS cost units away. Which rule decides, and what is chosen?

Question 5 of 5

Many copies of a DNS root server announce the same prefix from different places. What BGP-based technique is this?

← Previous topicNext topic →