Inter-AS routing (BGP)

To route packets between Autonomous Systems (ASs), the Internet uses a routing protocol called the Border Gateway Protocol (BGP) (RFC 4271).

BGP is a key Internet protocol that connects all ISPs.

It is decentralized and operates asynchronously, in the style of distance-vector routing.

The institutions that operate ASs make business agreements to interconnect their networks and exchange BGP routing information.

The role of BGP

BGP does not forward packets directly.

It selects and installs routes into the forwarding tables.

BGP operates on CIDR prefixes:

• each prefix represents a contiguous block of IP addresses (a subnet or aggregation of subnets)
• e.g., a destination could be 138.16.68/22 (1,024 IPv4 addresses) or 2001:db8::/32 (IPv6 prefix)

BGP allows routers to:

1. learn prefix reachability from other ASs:
   • ASs advertise reachability to their IP prefixes
   • BGP propagates this information across the Internet according to policy
2. select the best route to each prefix:
   • routers may learn multiple routes to the same prefix
   • BGP runs a best-path selection process
   • policy, rather than shortest path, is the primary driver of selection

Advertising BGP route information

This network has three autonomous systems: AS1, AS2 and AS3.

Each router in an AS is either:

1. a gateway router (e.g., 1.c): a router on the edge of an AS that connects to one or more routers in other ASs
2. an internal router (e.g., 1.a, 1.b, 1.d): only connects inside its own AS

We want all routers to learn how to reach prefix x in AS3:

Step	Details
1. AS3 announces x to AS2	a gateway router in AS3 (3a) sends an eBGP (external BGP) message to AS2 AS3 x → "x exists in AS3"
2. AS2 forwards the information internally	gateway router 2c receives it it shares the information with all routers in AS2 using iBGP (internal BGP)
3. AS2 announces x to AS1	gateway router 2a sends a message to AS1 AS2 AS3 x → "to reach x, go through AS2 then AS3"
4. AS1 distributes the information internally	gateway router 1c shares AS2 AS3 x with all routers in AS1 using iBGP

After these steps:

• every router in AS1 and AS2 knows that x exists
• they also know an AS path to reach x (AS2 → AS3 → x)

Routers exchange BGP messages over TCP connections (port 179).

Determining the best routes

In a real network, a router can learn multiple possible paths to the same destination.

For example, if a new link is added, there may now be two ways for AS1 to reach subnet x:

• via AS2 → AS3 → x
• directly via AS3 → x

How does a router choose between several possible routes to the same destination?

When a router advertises a prefix via BGP, it includes additional information called BGP attributes. A destination prefix together with its attributes is called a route.

Each route includes a prefix and several attributes, such as:

1. AS-PATH:
   • the sequence of ASs the route has traversed
   • in this example, there are two routes from AS1 to subnet x:
     1. AS-PATH = AS2 AS3
     2. AS-PATH = AS3
   • helps routers:
     • compare paths (shorter or preferred ones may be chosen)
     • avoid routing loops (if a router sees its own AS in the list, it rejects the route)
2. NEXT-HOP:
   • the IP address of the first router on the path to the next AS
   • this links inter-AS routing with intra-AS routing
   • example:
     • NEXT-HOP for route AS2 AS3 x = IP address of router 2a
     • NEXT-HOP for route AS3 x = IP address of router 3d

Each router in AS1 learns two BGP routes to prefix x:

NEXT-HOP                 | AS-PATH  | destination prefix
----------------------------------------------------------
IP address of router 2a; | AS2 AS3; | x
IP address of router 3d; | AS3;     | x

Each BGP route consists of three components:

1. NEXT-HOP
2. AS-PATH
3. destination prefix

In practice, a BGP route contains additional attributes.

Hot potato routing

In hot potato routing, a router forwards traffic through the closest exit point from its AS.

For router 1b:

1. it checks the cost of reaching each NEXT-HOP using its intra-AS routing information
2. it compares:
   • cost to router 2a
   • cost to router 3d
3. it selects the route with the lower cost

Since 2a is closer, router 1b chooses the route through 2a.

The idea behind hot-potato routing is to get packets out of the AS as quickly as possible.

A packet is like a hot potato in your hands: you want to pass it to another AS as soon as you can, without worrying about what happens after it leaves your network.

Hot potato routing is a selfish algorithm:

• it minimizes costs inside the local AS
• it ignores costs outside the AS

As a result, two routers in the same AS may choose two different AS paths to the same prefix.

For example:

• router 1b sends traffic through AS2 to reach x
• router 1d sends traffic directly to AS3 to reach x

Route-selection algorithm

BGP uses a route-selection algorithm that includes hot potato routing, but also considers other factors.

When multiple routes exist for the same prefix, BGP applies the following rules in order until only one route remains:

Step	Description
1. Highest local preference	keep the routes with the highest local preference value local preference is a policy value set by the network administrator or learned from another router in the same AS
2. Shortest AS-PATH	among the remaining routes, keep those with the shortest AS-PATH this favors routes that pass through fewer ASs
3. Lowest intra-AS cost to the NEXT-HOP (hot potato routing)	among the remaining routes, keep those whose NEXT-HOP has the lowest intra-AS cost
4. Lowest BGP Identifier	if multiple routes still remain, BGP picks the route with the lowest "BGP Identifier" the BGP Identifier is a unique router ID (usually derived from an IP address) it has no impact on performance or path quality and is only used to ensure a deterministic choice when all other attributes are equal

Consider router 1b:

• there are two BGP routes to prefix x:
  • one through AS2
  • one through AS3
• if only hot potato routing were used, 1b would choose the route through AS2 because its NEXT-HOP is closer
• however, BGP applies the shortest AS-PATH rule before hot potato routing
• since the route through AS3 has a shorter AS-PATH, BGP selects that route instead

As a result, BGP is not purely selfish:

• it considers the overall path through the Internet before considering the cost within its own AS
• this often leads to shorter end-to-end routes

A more realistic decision process includes additional steps such as:

1. Highest weight (Cisco-specific)
2. Highest local preference
3. Locally originated route
4. Shortest AS-PATH
5. Lowest origin type
6. Lowest MED
7. eBGP over iBGP
8. Lowest IGP cost to NEXT-HOP (hot potato routing)
9. Various tie-breakers (router ID, neighbor address, etc.)

IP-Anycast

BGP is also used to implement IP anycast (RFC 7094), a routing technique used by systems such as DNS and CDNs.

During the IP-anycast configuration stage:

• the same IP address (or IP prefix) is assigned to multiple servers in different locations
• BGP advertises this same IP address from multiple physical sites
• each router on the Internet:
  • receives multiple BGP routes to the same IP address
  • uses the BGP route-selection algorithm to choose the preferred route

After the BGP address-advertisement phase, when a client sends a request:

• the client sends packets to the same anycast IP address
• Internet routing automatically forwards the packets along the best BGP path
• the request is delivered to the server instance selected by BGP routing (often the geographically closest one)

IP anycast is heavily used in the DNS system:

• the DNS root system has 13 logical root server identities (A–M)
• each root server identity is not a single machine, but a service that is replicated globally
• that service is run by many independent physical server instances distributed around the world
• these instances advertise the same IP addresses using BGP anycast
• as a result, when you query a root DNS server:
  • your request is routed to one of the replicated root server instances
  • the instance you reach depends on Internet routing, not on DNS itself

Routing policy

When a router selects a route, routing policy can override all other route-selection criteria.

This happens because routes are first ranked using the "local-preference" attribute, which is set by each AS according to its own policies.

Example with two types of networks:

1. backbone providers A, B, C (connected to each other)
2. customer networks (access ISPs) W, X, Y:
   • routing rules:
     • traffic entering must be destined for the ISP
     • traffic leaving must originate from the ISP
   • X is multi-homed (connected to two providers)

Network	Behavior	Image
Customer network (X)	X must not act as a transit network between B and C to prevent this, X uses a selective route advertisement policy: it advertises only its own prefixes even if X learns a route to Y, it does not advertise it to B, so B never considers X a path to Y this ensures X is used only for traffic to or from itself
Backbone provider (B)	B learns a route to W via A (path: BAW) B advertises this route BAW to its customer X B does not advertise it to C otherwise, C could send traffic to W via B: making B carry traffic between non-customer networks A and C this creates cost without benefit

There are no strict global standards for inter-provider routing, but commercial ISPs generally follow this principle:

An ISP should only carry traffic if either the source or destination is a customer of that ISP.

Otherwise, the ISP is providing free transit, which is avoided unless explicitly agreed upon.

These arrangements are governed by peering agreements, which are often confidential.

BGP vulnerabilities

BGP relies on trust rather than built-in verification.

While this design allows the Internet to scale efficiently, it also enables accidental misconfigurations or false route announcements that can redirect or intercept traffic.

Real-world incidents demonstrate how BGP weaknesses can cause service outages, traffic diversion, and security breaches:

• Google (2017): accidental routing error and service disruption
• Amazon Route 53 (2018): malicious route hijacking and traffic interception
• Verizon (2019): large-scale route leak and misrouting

Because BGP was not originally designed with strong security controls, these failures have driven efforts to improve routing security through measures such as RPKI-based route validation, stronger route filtering, improved monitoring, and greater coordination among network operators.

Why are there different inter-AS and intra-AS routing protocols?

Because of the differences between the goals:

• routing within an AS: the goal is to optimize performance and speed (OSPF/IS-IS)
• routing among ASs: the goal is to enforce policy, business rules (control traffic exchange), and scalability (BGP)