BGP (Border Gateway Protocol) Border Gateway Protocol The protocol ISPs use to tell each other which destinations they can reach; its rules follow the customer-provider and peering relationships. introduced in ch. 5 lets every subnet announce that it exists. It carries that announcement across the whole Internet, one autonomous system at a time. Then it gives each router a fixed procedure for choosing between the routes it hears.
Words you will meet
-
BGP bgp Simple The protocol that tells every network how to reach every other network. Precise Border Gateway Protocol: the Internet's inter-autonomous system routing protocol, defined in RFC 4271. Every AS runs it. It advertises prefix reachability between autonomous systems and is decentralized and asynchronous, in the manner of distance-vector routing. introduced in ch. 5 — open in glossary — the one routing protocol every autonomous system runs.
-
Prefix prefix Simple A block of IP addresses written as one address and a length. Precise A CIDR-form address block such as 138.16.68/22, representing a subnet or a collection of subnets. BGP advertises reachability to prefixes, never to individual destination addresses, and a router's forwarding table holds entries of the form (x, I) where x is a prefix and I an interface. introduced in ch. 5 — open in glossary — a block of addresses like
138.16.68/22. BGP advertises these, never single addresses. -
Gateway router gateway router Simple A router on the edge of one organisation's network. Precise A router at the edge of an autonomous system that connects directly to one or more routers in other autonomous systems. Contrast an internal router, which connects only to hosts and routers inside its own AS. introduced in ch. 5 — open in glossary — a router on the edge of an AS, with a link to another AS. An internal router has no such link.
-
BGP connection bgp connection Simple A long-lived TCP connection two routers use to swap routes. Precise A semi-permanent TCP connection on port 179 between a pair of routers, together with all the BGP messages sent over it. A connection spanning two autonomous systems is an external BGP (eBGP) connection; one between routers in the same AS is an internal BGP (iBGP) connection. introduced in ch. 5 — open in glossary — a long-lived TCP (Transmission Control Protocol) Transmission Control Protocol The Internet transport protocol that delivers data reliably and in order, with flow control and congestion control. introduced in ch. 1 connection two routers use to exchange routes. eBGP crosses an AS boundary; iBGP stays inside one.
-
Route bgp route Simple A block of addresses, plus the facts BGP sends with it. Precise In BGP jargon, a prefix together with its attributes. Two of the more important attributes are AS-PATH, the list of autonomous systems the advertisement has crossed, and NEXT-HOP, the IP address of the router interface that begins that AS-PATH. Written as NEXT-HOP; AS-PATH; prefix. This is a different idea from the chapter-1 sense of the word route, which meant the sequence of links a packet traverses; from section 5.4 on, that idea is always called a path. introduced in ch. 5 — open in glossary — in BGP, a prefix plus its attributes. From here on, the word path is used for a sequence of links, and route only for this.
-
AS-PATH as-path Simple The list of autonomous systems a route has crossed. Precise A BGP route attribute recording every AS the advertisement has passed through. It is also how BGP detects and prevents routing loops. introduced in ch. 5 — open in glossary — the list of autonomous systems the advertisement has crossed.
-
NEXT-HOP next-hop Simple The router that begins this route. Precise A BGP route attribute giving the IP address of the router interface that starts the AS-PATH. introduced in ch. 5 — open in glossary — the address of the router interface that begins that AS-PATH.
-
Hot potato routing hot-potato routing Simple Get the packet out of my network as cheaply as possible. Precise Choosing, among all BGP routes to a destination, the one whose NEXT-HOP router is cheapest to reach within the router’s own AS — ignoring the cost of the path beyond it. introduced in ch. 5 — open in glossary — leave my own AS as cheaply as possible, and ignore what happens after that.
Why this matters
Section 5.3 filled a router’s forwarding table for every destination inside its own autonomous system. It said nothing about the rest of the Internet, which is almost all of it.
BGP fills in the rest. The book calls it arguably the most important of all Internet protocols. It says the only other contender is IP (Internet Protocol) Internet Protocol The network-layer protocol that defines the datagram format and addressing every Internet device must use. introduced in ch. 1 itself, because BGP is what holds thousands of separate ISP (Internet Service Provider) Internet Service Provider Connects hosts, and other ISPs, to the rest of the Internet. introduced in ch. 1 s together.
Without it, the book says, each subnet would be an isolated island: alone, unknown and unreachable. Every network you have ever visited was found for you by this protocol.
What BGP is for
Every router has a forwarding table, and it decides which link an arriving packet leaves by. Section 5.3 showed that an intra-AS protocol fills in the rows for destinations inside the AS. BGP fills in the rest.
BGP does not route to addresses. It routes to
prefixes prefix Simple A block of IP addresses written as one address and a length. Precise A CIDR-form address block such as 138.16.68/22, representing a subnet or a collection of subnets. BGP advertises reachability to prefixes, never to individual destination addresses, and a router's forwarding table holds entries of the form (x, I) where x is a prefix and I an interface.
introduced in ch. 5 — open in glossary
. A destination in BGP takes a form such as
138.16.68/22, which is the book’s example and covers 1,024 IP addresses. So a
forwarding table holds entries of the form (x, I), where x is a prefix and
I is the number of one of this router’s interfaces. That is
CIDR (Classless Interdomain Routing) Classless Interdomain Routing Address form a.b.c.d/x, where x says how many leading bits are the network prefix.
introduced in ch. 4 from section 4.3.2, reused unchanged.
BGP gives each router two things.
Prefix reachability information from neighbouring autonomous systems. BGP lets each subnet advertise that it exists to the rest of the Internet. The book puts it as a subnet shouting “I exist and I am here”, after which BGP makes sure every router in the Internet learns about it.
A way to determine the best routes to those prefixes. A router may learn two or more different routes to one prefix. It then runs a local route-selection procedure. The best route is decided by policy as well as by reachability.
In plain words
Two jobs, and the second is the harder one.
The first job is announcement: make sure everyone hears that this block of addresses is out there. The second is choice: when several announcements arrive for the same block, pick one.
Note the word policy in the second job. Section 5.2 computed least-cost paths and nothing else. From here on, cost is not the only thing that decides, and sometimes it is not the thing that decides at all.
Advertising route information
The ringed routers are the gateway routers: each has at least one link leaving its own AS. Everything faded is an internal router, whose links all stay inside.
Drag any device to rearrange the picture. Hover a link to see its rate, delay and length.
Drag any router. Each AS is a diamond of four routers. Only two links cross an AS boundary here: 1c–2a and 2c–3a.
Read this diagram as text
- 1a — wired link — 1b
- 1b — wired link — 1c
- 1a — wired link — 1d
- 1d — wired link — 1c
- 2a — wired link — 2b
- 2b — wired link — 2c
- 2a — wired link — 2d
- 2d — wired link — 2c
- 3a — wired link — 3b
- 3b — wired link — 3c
- 3a — wired link — 3d
- 3d — wired link — 3c
- 1c — wired link — 2a
- 2c — wired link — 3a
- 3d — wired link — subnet x
Three autonomous systems: AS1, AS2 and AS3. AS3 holds a subnet with prefix x.
Inside each AS, every router is one of two kinds.
- A gateway router gateway router Simple A router on the edge of one organisation's network. Precise A router at the edge of an autonomous system that connects directly to one or more routers in other autonomous systems. Contrast an internal router, which connects only to hosts and routers inside its own AS. introduced in ch. 5 — open in glossary sits on the edge of the AS and connects directly to one or more routers in other autonomous systems.
- An internal router internal router Simple A router with no link leaving its own organisation. Precise A router that connects only to hosts and routers within its own autonomous system. In Figure 5.8, routers 1a, 1b and 1d are internal routers and 1c is a gateway router. introduced in ch. 5 — open in glossary connects only to hosts and routers within its own AS.
In AS1, router 1c is a gateway router. Routers 1a, 1b and 1d are internal routers.
The idea, before the detail
At a high level, telling everyone about x is simple.
First, AS3 sends a BGP message to AS2 saying that x exists and is in AS3. Write that message as “AS3 x”. Then AS2 sends a BGP message to AS1 saying that x exists and that you reach it by passing through AS2 and then AS3. Write that one as “AS2 AS3 x”.
Each autonomous system learns two things: that x exists, and a path of autonomous systems that leads to it.
Autonomous systems do not send messages
That description is useful and it is not precise. An autonomous system is not a thing that can send anything. Routers send messages. The rest of this section replaces “AS3 sends to AS2” with the actual pair of routers involved.
Where the connections are
In BGP, pairs of routers exchange routing information over semi-permanent TCP connections using port 179. One such TCP (Transmission Control Protocol) Transmission Control Protocol The Internet transport protocol that delivers data reliably and in order, with flow control and congestion control. introduced in ch. 1 connection, together with all the BGP messages sent over it, is a BGP connection bgp connection Simple A long-lived TCP connection two routers use to swap routes. Precise A semi-permanent TCP connection on port 179 between a pair of routers, together with all the BGP messages sent over it. A connection spanning two autonomous systems is an external BGP (eBGP) connection; one between routers in the same AS is an internal BGP (iBGP) connection. introduced in ch. 5 — open in glossary .
- A BGP connection that spans two autonomous systems is an external BGP connection, written eBGP (external BGP) external BGP A BGP session between routers in two different autonomous systems. introduced in ch. 5 .
- A BGP session between routers in the same AS is an internal BGP connection, written iBGP (internal BGP) internal BGP A BGP session between routers inside one autonomous system, distributing what the eBGP sessions learned. introduced in ch. 5 .
Twelve routers, three diamonds, and two links crossing an AS boundary: 1c–2a and 2c–3a. Nothing here is BGP yet — these are cables.
Every BGP connection is a semi-permanent TCP connection on port 179. eBGP spans two autonomous systems; iBGP joins two routers inside one.
Read all steps as text
- First, the physical links — Twelve routers, three diamonds, and two links crossing an AS boundary: 1c–2a and 2c–3a. Nothing here is BGP yet — these are cables.
- One eBGP connection per inter-AS link — There is typically one external BGP connection for each link that directly connects gateway routers in different autonomous systems. So there are exactly two here, and they sit on top of the two physical links that cross a boundary.
- And a mesh of iBGP connections inside each AS — A common configuration is one BGP connection for every pair of routers internal to an AS. Four routers make six pairs, so each AS carries six internal BGP connections.
- iBGP connections do not have to follow cables — Two of AS1’s six iBGP connections join routers with no direct link between them: 1a–1c and 1b–1d. That is fine. A BGP connection is a TCP connection, and TCP runs over however many hops the intra-AS routing protocol needs.
There is typically one eBGP connection for each link that directly connects gateway routers in different autonomous systems. There are also iBGP connections inside each AS, and a common configuration is one for every pair of internal routers — a mesh of TCP connections.
In plain words
A BGP connection is not a cable. It is a TCP connection, and TCP does not care how many links lie between its two ends.
So two routers with no direct link between them can still hold an iBGP connection. The intra-AS routing protocol carries the packets between them, and BGP never notices. Two of AS1’s six iBGP connections are like this.
The advertisement, router by router
Autonomous systems do not send messages to each other. Routers do, and they alternate: eBGP across a boundary, iBGP to everyone inside.
Click any arrow to see what that message says and why it is sent.
Only the routers that act are drawn. Both AS2 and AS1 flood the advertisement to every one of their internal routers over the iBGP mesh.
Read this diagram as text
- 3a sends eBGP · “AS3 x” to 2c. Gateway router 3a sends an external BGP message to gateway router 2c. It says: x exists, and it is in AS3.
- 2c sends iBGP · “AS3 x” to 2a. Gateway router 2c passes it on by internal BGP to all the other routers in AS2, including gateway router 2a. Routers 2b and 2d receive the same message; only 2a is drawn, because only 2a acts on it next.
- 2a sends eBGP · “AS2 AS3 x” to 1c. AS2 has added its own AS number to the front of the AS-PATH. The message now says: to reach x, first pass through AS2, then AS3.
- 1c sends iBGP · “AS2 AS3 x” to 1d. Gateway router 1c floods it to all the routers in AS1 by internal BGP. Routers 1a and 1b receive it too. After this, every router in AS1 and AS2 knows x exists and knows an AS path that leads to it.
Lifelines, left to right: 3d (router), 3a (router), 2c (router), 2a (router), 1c (router), 1d (router).
Follow the first scenario. Gateway router 3a sends the eBGP message “AS3 x” to gateway router 2c. Router 2c sends the iBGP message “AS3 x” to all the other routers in AS2, including gateway router 2a. Router 2a sends the eBGP message “AS2 AS3 x” to gateway router 1c. Finally, router 1c uses iBGP to send “AS2 AS3 x” to all the routers in AS1.
After that, every router in AS1 and AS2 knows that x exists, and knows an AS path that leads to it.
Everyday picture
A rumour crossing a group of offices.
Inside an office, whoever hears it tells everyone else in the room. That is iBGP. When it crosses to the next office, one person carries it through the door, and adds their own office to the story: “we heard it from the office next door”. That is eBGP, and the growing list of offices is the AS-PATH.
Where the picture stops. A rumour gets distorted. A BGP advertisement does not: each AS adds its own number and changes nothing else. And rumours can circle back forever, which BGP prevents — see the AS-PATH loop check below.
Choosing the best route
In a real network there may be many paths to one destination, each through a different sequence of autonomous systems. Routers in the Internet often receive reachability information about dozens of different possible paths.
Figure 5.10 is Figure 5.8 with one extra physical link, from router 1d to router 3d. That single link gives AS1 two ways to reach x.
Drag any device to rearrange the picture. Hover a link to see its rate, delay and length.
One new physical link, 1d–3d, and now AS1 has two ways to reach x. Play either journey. The second crosses one AS boundary instead of two — and, as the last section of this page shows, that is what decides the winner.
Read this diagram as text
- 1a — wired link — 1b
- 1b — wired link — 1c
- 1a — wired link — 1d
- 1d — wired link — 1c
- 2a — wired link — 2b
- 2b — wired link — 2c
- 2a — wired link — 2d
- 2d — wired link — 2c
- 3a — wired link — 3b
- 3b — wired link — 3c
- 3a — wired link — 3d
- 3d — wired link — 3c
- 1c — wired link — 2a
- 2c — wired link — 3a
- 3d — wired link — subnet x
- 1d — wired link — 3d
Routes and attributes
When a router advertises a prefix across a BGP connection, it includes several BGP attributes bgp attribute Simple Extra facts sent along with an advertised prefix. Precise The values a router includes with a prefix when it advertises it across a BGP connection. A prefix together with its attributes is called a route. Two of the more important attributes are AS-PATH and NEXT-HOP. introduced in ch. 5 — open in glossary with it. In BGP jargon, a prefix together with its attributes is called a route bgp route Simple A block of addresses, plus the facts BGP sends with it. Precise In BGP jargon, a prefix together with its attributes. Two of the more important attributes are AS-PATH, the list of autonomous systems the advertisement has crossed, and NEXT-HOP, the IP address of the router interface that begins that AS-PATH. Written as NEXT-HOP; AS-PATH; prefix. This is a different idea from the chapter-1 sense of the word route, which meant the sequence of links a packet traverses; from section 5.4 on, that idea is always called a path. introduced in ch. 5 — open in glossary . Two attributes matter most here.
AS-PATH as-path Simple The list of autonomous systems a route has crossed. Precise A BGP route attribute recording every AS the advertisement has passed through. It is also how BGP detects and prevents routing loops. introduced in ch. 5 — open in glossary holds the list of autonomous systems the advertisement has passed through. When a prefix is passed to an AS, that AS adds its own ASN (Autonomous System Number) Autonomous System Number The globally unique number identifying an autonomous system. introduced in ch. 5 to the existing list. In Figure 5.10 there are two routes from AS1 to subnet x: one with AS-PATH “AS2 AS3”, and one with AS-PATH “AS3”.
AS-PATH has a second job. A BGP router that sees its own AS already in the path list rejects the advertisement. That is how BGP detects and prevents looping advertisements.
It is also exactly the information a distance vector lacked. In section 5.2.2 two routers could raise each other’s estimate forever, because neither could see that it was already on the other’s path.
NEXT-HOP next-hop Simple The router that begins this route. Precise A BGP route attribute giving the IP address of the router interface that starts the AS-PATH. introduced in ch. 5 — open in glossary is the IP address of the router interface that begins the AS-PATH. It provides the critical link between the inter-AS and the intra-AS routing protocols, and its use is subtle.
| NEXT-HOP | AS-PATH | prefix |
|---|---|---|
| Learned through gateway router 1c. Two autonomous systems to cross. | ||
| Learned through router 1d, over the peering link that Figure 5.10 added. | ||
Cells marked ⓘ have an explanation — click to read it.
A BGP route is written as three things: NEXT-HOP; AS-PATH; prefix. Click a cell marked ⓘ for the reason.
The NEXT-HOP is not in your own AS
Look at the first route. Its NEXT-HOP is an interface on router 2a, and 2a does not belong to AS1.
The book states the resolution directly: the subnet that contains this IP address attaches directly to AS1. So an AS1 router can reach that address using nothing but its own intra-AS routing, even though the address is not one of its own routers.
That is why NEXT-HOP is the joint between the two protocols. BGP supplies an address; the intra-AS protocol works out how to get there.
Hot potato routing
The simplest of BGP’s routing algorithms. Choose the route whose NEXT-HOP router is cheapest to reach, measured inside your own AS, and ignore everything beyond that.
Consider router 1b in Figure 5.10. It knows two routes to x, beginning at router 2a and at router 3d. Define cost as the number of links traversed, as the book does for this example.
Router 1b holds both BGP routes to x. One begins at router 2a, the other at router 3d. Hot potato routing chooses the route whose NEXT-HOP router is cheapest to reach — inside 1b’s own AS.
Cost is the number of links traversed, as the book defines it for this example. Both least costs are computed by the intra-AS protocol, not by BGP.
Read all steps as text
- Two routes, two NEXT-HOP routers — Router 1b holds both BGP routes to x. One begins at router 2a, the other at router 3d. Hot potato routing chooses the route whose NEXT-HOP router is cheapest to reach — inside 1b’s own AS.
- Least cost from 1b to NEXT-HOP router 2a — 1b to 1c is one link, 1c to 2a is a second. Cost 2. This is intra-AS routing information: 1b already has it from OSPF, and BGP contributes nothing to this number.
- Least cost from 1b to NEXT-HOP router 3d — 1b to 1a, 1a to 1d, then 1d across the peering link to 3d. Cost 3. Going by 1c instead of 1a is also 3, so 3 is the least.
- The smaller one wins — Two is smaller than three, so hot potato routing selects the route beginning at 2a — the route through AS2 — even though that route crosses one more autonomous system.
- And the forwarding table gets one new row — 1b consults its own forwarding table, which its intra-AS algorithm built, and finds the interface I on the least-cost path to 2a. It then adds the entry (x, I). BGP found the prefix; OSPF found the interface.
The least cost from 1b to router 2a is 2. The least cost from 1b to router 3d
is 3. So router 2a is selected, and 1b adds (x, I) to its forwarding table,
where I is the interface on the least-cost path to 2a.
A book error to know about
The 8th edition writes:
the least cost from router 1b to router 2a is 2, the least cost from router 1b to router 2d is 3, and router 2a would therefore be selected.
The two NEXT-HOP routers under discussion are 2a and 3d, as the same paragraph says two sentences earlier. There is no reason to measure the distance to 2d, which is an internal router of AS2 and begins no route.
The value 3 is right for 3d: 1b → 1a → 1d → 3d is three links. Confusingly, the distance to 2d also happens to be 3, which is probably how the slip survived. Verified against the page image of book page 404.
A second, smaller slip is on page 403: the AS-PATH of the route that bypasses AS2 is printed as “A3”. It is “AS3”.
Learn from the inter-AS protocol that subnet x is reachable via multiple gateways. This is the only step BGP does on its own.
The book’s own four boxes, in the book’s own words. Box 3 says "gateway" where this page says "gateway router" — figure labels reproduce the book.
Read all steps as text
- 1 · what BGP tells you — Learn from the inter-AS protocol that subnet x is reachable via multiple gateways. This is the only step BGP does on its own.
- 2 · what OSPF tells you — Use routing information from the intra-AS protocol to determine the costs of the least-cost paths to each of the gateways. Nothing about BGP is involved in this number.
- 3 · the choice — Hot potato routing: choose the gateway that has the smallest least cost. One comparison, and it ignores everything outside this AS.
- 4 · the row that gets written — Determine from the forwarding table the interface I that leads to the least-cost gateway, and enter (x, I) in the forwarding table. Both protocols were needed to write this one row.
Both protocols are needed to write that one row. BGP learned that x is reachable and through which gateway routers. The intra-AS protocol, OSPF (Open Shortest Path First) Open Shortest Path First The Internet’s intra-AS link-state routing protocol. Each router builds a complete map of its autonomous system and runs Dijkstra locally. introduced in ch. 5 for example, supplied every cost and the final interface.
Everyday picture
The name is the book’s own. A packet is like a hot potato burning in your hands. It is too hot to hold, so you pass it to another person as fast as you can.
You do not ask whether that person is near a table. You only care about getting it out of your hands quickly.
Where the picture stops. Passing a hot potato is instant; getting a packet out of an AS costs something, and the algorithm measures exactly that cost. The picture is about the motive, not the mechanism.
Hot potato routing is a selfish algorithm. It reduces the cost inside its own AS and ignores the rest of the end-to-end cost. One consequence is worth noticing: two routers in the same AS may choose different AS paths to the same prefix. In Figure 5.10, router 1b would send packets through AS2, while router 1d would bypass AS2 and hand them straight to AS3.
The real route-selection algorithm
In practice BGP uses something more complicated, which contains hot potato routing as one of its parts.
The input is the set of all routes to one prefix that this router has learned and accepted. If there is only one, BGP selects it. If there are two or more, BGP applies these elimination rules in order, until one route remains.
| # | What survives this rule |
|---|---|
| This is where money and contracts enter routing. Section 5.4.5 is about what operators put here. | |
Cells marked ⓘ have an explanation — click to read it.
The input is every route to one prefix that this router has learned and accepted. The rules run in order until one route remains. Click a cell marked ⓘ.
In plain words
The order is the whole message.
Policy first. Rule 1 is a number an operator sets by hand, and no measurement overrides it.
Then AS hops. Rule 2 counts autonomous systems, not routers.
Then selfishness. Rule 3 is hot potato routing, and by the time it runs, the first two rules have usually decided.
Apply this to router 1b. Hot potato routing on its own chose the route through AS2. But rule 2 runs before rule 3, and the route that bypasses AS2 has the shorter AS-PATH — one autonomous system instead of two. So BGP selects the route that bypasses AS2.
BGP is therefore not a selfish algorithm. It looks for short AS paths first, which likely reduces end-to-end delay, and only falls back on hot potato routing when that leaves a tie.
Check yourself
Check yourself
0 of 7 answered1.What does BGP advertise?
2.In Figure 5.8, routers 1a, 1b and 1d are internal routers and 1c is a gateway router. What makes 1c different?
3.Two routers in the same AS have no direct link between them, yet Figure 5.9 shows an iBGP connection joining them. Is that a mistake?
4.A BGP router receives an advertisement whose AS-PATH already contains its own AS number. What does it do?
5.predictIn Figure 5.10 router 1b knows two routes to x. Costs are counted in links: 1b to NEXT-HOP router 2a is 2, and 1b to NEXT-HOP router 3d is 3. If hot potato routing alone decided, which route wins?
6.Why is BGP's full route-selection algorithm not a selfish one, even though hot potato routing is?
7.The NEXT-HOP of one of AS1's routes is an interface on router 2a, which belongs to AS2. How can a router in AS1 use an address that is not in its own AS?
What to remember
- BGP advertises prefixes, not addresses. A forwarding-table row is
(x, I): a prefix and an interface. - AS-PATH also prevents loops: a router that finds its own AS in the list rejects the advertisement. That is the information a distance vector never had.
- The real algorithm runs four rules in order: local preference local preference Simple A number an operator sets to say which route it prefers. Precise A BGP route attribute whose value is a policy decision left entirely to the AS's network administrator. It may be set by the router or learned from another router in the same AS. Rule 1 of BGP's route-selection algorithm keeps only the routes with the highest local preference. introduced in ch. 5 — open in glossary , then shortest AS-PATH, then hot potato, then BGP identifiers. Because rule 2 beats rule 3, BGP is not selfish after all.