BGP: How the Internet Routes Between Networks

The picture: signposts passed down a road#

Picture a chain of towns along a road. The town of Lakeside puts up a sign: “Lakeside: this way”. The next town, Millbrook, copies it and adds its own name: “Lakeside: via Millbrook, then Lakeside”. The town after that adds its name too. Soon every town has a sign listing the towns you pass through on the way to Lakeside.

Some towns have signs from two directions, and pick one. And some towns refuse to put up a sign at all, because they do not want strangers’ trucks driving through their streets.

That is BGP. Each sign is a route advertisement. The list of towns is the AS-PATH. The refusal is policy.

Vocabulary, before anything uses it#

What BGP does, and the two kinds of session#

BGP is the glue of the Internet. Without it, every AS would be an island. With it, a subnet anywhere can announce “I exist, and here is how to reach me”, and the rest of the Internet learns the way. BGP gives each router two jobs:

1. Learn which prefixes can be reached through each neighboring AS.
2. Pick the best route to each prefix, using policy and the routes’ attributes, and record it in the forwarding table.

Routers exchange BGP messages over semi-permanent TCP connections on port 179. TCP makes the messages reliable and in order, so BGP itself does not have to. The main message types are OPEN (start a session), UPDATE (advertise or withdraw routes), KEEPALIVE (“I am still here”) and NOTIFICATION (report an error and close).

Advertising a route through three ASes#

When a router advertises a prefix, it attaches attributes. The two that matter most:

• AS-PATH. Each AS that passes the advertisement to another AS adds its own number to the front. This also stops loops: if an AS sees its own number already in an AS-PATH, it rejects the advertisement.
• NEXT-HOP. The address of the interface where the path begins, on the router in the neighboring AS.

Now a router inside AS 64501, say 1d, knows two routes to the same prefix. One has AS-PATH 64502 64503, length 2, through 1c. The other has AS-PATH 64503, length 1, through 1b. With no policy saying otherwise, 1d picks the length-1 route. It then asks OSPF for the path to 1b and writes “203.0.113.0/24: send toward 1b” in its forwarding table.

Import policy and choosing among routes#

A gateway first applies import policy. The administrator may reject a route outright, for example because it passes through an AS they do not trust or do not pay. The routes that survive are ranked. A router with several routes to the same prefix runs them through a funnel. Each step only breaks ties left by the step before:

1. Highest local preference. This is pure policy, set by the administrator.
2. Shortest AS-PATH. Fewer ASes crossed.
3. Closest NEXT-HOP router, by intra-AS cost. This is hot-potato routing: get the packet out of your own network as cheaply as you can.
4. Additional criteria, such as the lowest BGP router ID (a unique number each BGP router is configured with), to break any tie still left.

Step 1: all three have local preference 100, so all survive. Step 2: A and B have length 2, so C is out. Step 3: B’s gateway costs 4, A’s costs 7, so R picks route B.

Notice that G3 was the cheapest exit of all, at cost 2. It did not matter, because C was already gone at step 2. Hot potato only breaks ties among the survivors. And if the administrator gives C a local preference of 200, C wins at step 1, despite its longer path.

Policy: who carries whose traffic#

Networks connect as customers and providers. A customer pays a provider to carry its traffic to and from the rest of the Internet. Two rules follow from the money.

A customer network carries no transit traffic

A stub network is one whose traffic always starts or ends inside it. Many are multi-homed: connected to two providers, for backup or to share load. Such a network must not let traffic flow between its two providers through itself. It enforces this through what it advertises: it tells each provider only about its own prefixes.

A provider carries traffic only for its customers

A common rule of thumb: traffic crossing a provider’s backbone should have its source or its destination (or both) in one of that provider’s customers. Say ISP North learns from ISP South a route to one of South’s customers. North does not pass that route on to a third provider, ISP East. If it did, traffic between East and South’s customer could cross North’s backbone, and nobody would be paying North for it. Large providers usually exchange traffic for free only for their own customers, through deals called peering.

Why intra-AS and inter-AS routing differ#

Practice#

For selection questions, run the funnel in order and cross out routes at each step. Never skip ahead to the step you like.

1. eBGP or iBGP? (a) A gateway in AS 64496 and a gateway in AS 64497, joined by a direct link. (b) Two routers in AS 64496 that are four hops apart.
2. AS 64507 owns 192.0.2.0/24. The advertisement passes from AS 64507 to AS 64508, then to AS 64509, then to AS 64511. What AS-PATH does AS 64511 receive?
3. AS 64508 receives an advertisement with AS-PATH 64509 64508 64507. What does it do, and why?
4. A router has four routes to one prefix. P: local pref 150, AS-PATH length 3, gateway cost 1. Q: 150, length 2, cost 9. R: 150, length 2, cost 3. S: 100, length 1, cost 2. Which route does it choose?
5. In question 4, the administrator changes S’s local preference to 300. Which route wins now?
6. Why is hot-potato routing called selfish?
7. A school district’s network is a customer of two providers. Should it re-advertise to one provider the routes it learns from the other? Why?
8. What transport protocol and port does BGP use, and what does that save BGP from doing?

Solutions#

1. (a) eBGP. (b) iBGP. Different ASes means external BGP. Same AS means internal BGP, and the session runs over TCP across the internal routers, so no direct link is needed.
2. 64509 64508 64507. Each AS adds its number to the front as it passes the route on. AS 64507 starts it, 64508 adds itself, and 64509 adds itself before sending to 64511.
3. It rejects the advertisement. Its own number, 64508, is already in the AS-PATH, so accepting it would create a routing loop.
4. R. Step 1: highest local pref is 150, so S is out (its short path does not save it). Step 2: Q and R have length 2, so P is out. Step 3: R’s gateway costs 3, Q’s costs 9, so R wins.
5. S. Its local preference, 300, is now the highest, so it is the only route left after step 1. Nothing later is checked.
6. It minimizes cost inside your own AS only. The router dumps the packet out of the nearest exit, the “hot potato”. It ignores how far the packet then has to travel in other networks, so the end-to-end path can be longer.
7. No. It is a stub customer, not a transit network. If it re-advertised, one provider could route traffic for the other through the district’s links. So it advertises only its own prefixes to each provider.
8. TCP, port 179. TCP delivers the messages reliably and in order, so BGP does not need its own retransmission or reordering, unlike OSPF, which runs straight over IP.

Test-readiness checklist#

• ☐  I can say what BGP lets a subnet do, and list each router’s two BGP jobs.
• ☐  I can tell eBGP from iBGP, and say BGP runs over TCP port 179.
• ☐  I can define a route as a prefix plus attributes, and explain AS-PATH and NEXT-HOP.
• ☐  I can trace an advertisement through several ASes and write the AS-PATH at each step.
• ☐  I can explain how AS-PATH prevents loops.
• ☐  I can run the selection funnel: local preference, shortest AS-PATH, closest NEXT-HOP, then other tie-breakers.
• ☐  I can explain why a stub customer does not carry transit traffic, and how it enforces that.
• ☐  I can give the three reasons intra-AS and inter-AS routing differ: policy, scale and performance.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written.