Internet Routing: Autonomous Systems, OSPF, and BGP Fundamentals

Autonomous Systems

Sections 4.8 and 4.9 treated the whole network as one graph on which every router runs the same routing algorithm. That does not work in the real Internet:

1. Scale. The Internet has hundreds of millions of destination networks. If every router had to store the complete topology and flood link states to the whole network, the storage and communication overhead would be unbearable, and distance-vector routing would never converge in a network this large.
2. Administrative autonomy. The Internet is a "network of networks" built from many ISPs. Each ISP wants to run its network as it sees fit, choose its own routing algorithm, and hide its internal structure from outsiders.

The solution is to organize routers into autonomous systems (ASes). An AS is a group of routers under the control of one administrative authority, typically an ISP or a large organization's network, identified by a globally unique AS number (ASN). Routers inside one AS run the same intra-AS routing protocol; between different ASes, everyone uses the inter-AS routing protocol BGP. Routers that connect their AS to other ASes are called gateway routers.

Open Shortest Path First (OSPF)

OSPF is one of the most widely used intra-AS routing protocols. It is a link-state protocol:

• Each router floods link-state advertisements to all routers in its AS, so every router obtains the complete topology and runs Dijkstra's algorithm locally to build a shortest-path tree rooted at itself.
• Link costs are set by the network administrator. Setting all costs to 1 yields minimum-hop routing; making costs inversely proportional to link bandwidth steers traffic toward high-bandwidth links.
• Changes are flooded immediately, and advertisements are refreshed periodically (at least every 30 minutes) even without changes. OSPF messages are carried directly in IP datagrams with protocol number 89.
• It supports message authentication, so malicious routers cannot inject false information, and multiple equal-cost paths, so traffic can be shared among them.
• It supports hierarchy: an AS can be divided into areas, and link-state advertisements flood only within an area. A special backbone area (area 0) connects all areas, and area border routers summarize routes between areas.

Border Gateway Protocol (BGP)

BGP is the only inter-AS routing protocol used in the Internet, often described as the protocol that glues tens of thousands of ASes together. In BGP, destinations are not individual hosts but CIDR prefixes such as 138.16.64.0/22. BGP gives each router two capabilities:

1. Obtain prefix reachability information from neighboring ASes. BGP lets every subnet announce to the rest of the Internet: "I am here."
2. Determine the "best" routes to each prefix based on that reachability information and on the AS's policy.

Gateway routers in neighboring ASes establish external BGP (eBGP) sessions over TCP (port 179); routers inside one AS propagate learned routes over internal BGP (iBGP) sessions. A BGP route consists of a prefix and several attributes. Two important attributes are:

• AS-PATH: the list of ASes the advertisement has passed through. When an advertisement enters a new AS, that AS prepends its own number. A router that finds its own AS number in the AS-PATH rejects the advertisement, which prevents loops.
• NEXT-HOP: the IP address of the router interface where the AS-PATH begins, that is, the router to hand traffic to when leaving the AS.

Hot-Potato Routing and BGP Route Selection

A router often learns several routes to the same prefix. If they differ only in the gateway through which they leave the AS, the simplest choice is hot-potato routing: choose the gateway with the least cost inside the AS (the cost to NEXT-HOP computed by the intra-AS protocol) and get the packet out of the AS as quickly as possible, without caring how far it still must travel outside.

Real BGP compares routes in the following order until only one remains:

1. Highest local preference. Local preference is set by the AS administrator according to policy.
2. Shortest AS-PATH.
3. Least cost to NEXT-HOP, that is, hot-potato routing.
4. BGP identifiers (router IDs) break any remaining tie.

In BGP, policy often matters more than performance. For example, a customer network connected to two ISPs (a multi-homed network) does not want to carry transit traffic between them, so it should not re-advertise routes learned from one ISP to the other. ISPs likewise usually carry transit traffic only for their own customers, not free of charge for other ISPs.