Understanding Autonomous Systems

Routing and Peering

Paul Krzyzanowski

March 21, 2016

Autonomous Systems

An Autonomous System (AS) is a collection of routers whose prefixes and routing policies are under common administrative control. This could be a network service provider, a large company, a university, a division of a company, or a group of companies. The AS represents a connected group of one or more blocks of IP addresses, called IP prefixes, that have been assigned to that organization and provides a single routing policy to systems outside the AS. An IP prefix is a group of IP addresses expressed in CIDR form (i.e., address/bits, such as 128.6.0.0/16). Autonomous Systems create a two-level hierarchy for routing in the Internet. Routing between Autonomous Systems (inter-AS routing) is external to the AS and allows one AS to send traffic to another AS. Note that most organizations do not interconect via autonomous systems but simply connect to a single ISP, which may be an autonomous system.

Routers within an AS use an Interior Gateway Protocol (IGP), which handles routing between nodes inside the AS. Common interior gateway protocols include RIP, OSPF, IS-IS, EIGRP, as well as some proprietary protocols such as IGRP. Routing within an Autonomous System (intra-AS routing) is internal to that AS and invisible to those outside it. The AS administrator decides what routing algorithm should run within it.

To get traffic from a host in one AS to a host in another AS, the autonomous systems need to be connected. Most ASes do not share a direct link with each other, in which case data traffic may be routed through the networks of other ASes that agree to carry the traffic. An Exterior Gateway Protocol (EGP) is a routing protocol that handles routing between Autonomous Systems (inter-AS routing). BGP version 4, the Border Gateway Protocol, is the standard EGP for inter-AS routing. At some point in the future, the Internet is expected to adopt IDRP, the OSI Inter-Domain Routing protocol.

Inter-AS Routing

Figure 1. Inter-AS routing
Figure 1. Inter-AS routing

A routing policy defines how routing information is exchanged between the ASes. For example, suppose two ASes, ASx and ASy, are connected to each other via a link between two gateway routers. Suppose that ASx knows how to reach some network, NET–1, that is defined by an IP prefix. This network may be within ASx or may be external to it. Suppose that ASy knows how to reach some other network, NET–2.

For systems on NET–1 to be able to send messages to systems on NET–2, and vice versa, traffic will need to flow between ASx and ASy. This means that ASx needs to announce to ASy that it has a route to NET–1 and ASy needs to announce to ASx that it has a route to NET–2. The exterior gateway protocol is used to do this. ASx and ASy can then decide whether to accept this information or discard it (if, for example, they have better routes to those networks).

AS assignment

An AS has a globally unique 32-bit number associated with it[1], called an ASN (Autonomous System Number). If an Autonomous System exchanges routing information with other Autonomous Systems on the public Internet, it needs to have a unique ASN. This number is used in exchanging exterior routing information, particularly in identifying paths through multiple ASes via BGP, the Border Gateway Protocol. AS numbers are assigned to organizations by the Regional Internet Registry (RIR) for their country (e.g., ARIN for the U.S. and Canada, for example, for a $500 fee). Each RIR gets blocks of available AS numbers from the IANA (Internet Assigned Numbers Authority). The process is similar to that of assigning IP addresses. There are currently over 42,000 autonomous systems. The top-level list of IANA assignments of AS numbers can be fond at http://www.iana.org/assignments/as-numbers/as-numbers.xml

An ASN is not needed for a network that has a single connection to an ISP and a single block of IP addresses (single prefix). The prefix of this network should be managed by the AS of the provider since the external routing policy of this network is the same as that of its provider.

Autonomous systems may be connected with multiple links and one autonomous system will often be connected to several others for fault tolerance, to access different parts of the network, and to route traffic between these different parts. Each autonomous system can decide who they will exchange traffic with (that is, whether they will allow another AS to route traffic through it).

Internet Tiers, Peering, and Transit

Since most ASes are not connected with each other, they need to route their traffic through other ASes.

Peering is when a pair of ASes establish a reciprocal agreement to connect with each other to exchange traffic with each other, without charge. The assumption that each has an interest in connecting to the other’s customers, similar to how postal systems throughout the world do not charge when mail is routed from one country to another.

Tier 1 ISPs are those that do not have to pay any other network for transit. They peer with all other tier 1 networks (there are only about fourteen of these worldwide). Given any IP address, a Tier 1 ISP will be able to connect directly to a top-level ISP that can route to that address. The United States has eight interconnection regions[2] that create a “default free zone” where Tier 1 ISPs connect their networks together in peering relationships.

Peering agreements are not necessarily transitive. If AS1 peers with AS2 and AS2 peers with AS3, AS2 is not necessarily obligated to carry traffic to AS3. Whether this is permitted or not is a business, rather than technical, decision.

A Transit relationship is when an ISP (an AS) sells access to the Internet. It is when an AS agrees to act as a router, carrying traffic from one AS and out to some other AS to which it has a link. The complete data path may, of course involve multiple transit hops through different ASes. An AS will typically meter the traffic on each link and charge a transit fee. Depending on policy, an organization in one AS may be charged for traffic even to the connected AS.

A Tier 2 ISP is one that needs to purchase Transit to connect to at least some part of the Internet. Because of transit fees, many Tier 2 ISPs will try to establish peering relations directly with as many Tier 1 and other Tier 2 ISPs as they can so they can exchange traffic with those ISPs for no fee (although, even in those cases, there may still be a peering fee — it’s a business decision). For example, it is common for cable and phone companies to peer with content providers such as Google, Amazon, and Microsoft.

Internet Backbone

The Internet Backbone is the collection of major connections (routers and links) that connects large autonomous systems, typically Tier 1 networks, together. Like the Internet, it s a distributed infrastructure that is managed by numerous companies, universities, and other organizations.

Categories of Autonomous Systems

Figure 2. Transit AS: Az handling traffic between Ax and Ay
Figure 2. Transit AS: Az handling traffic between Ax and Ay
Stub versus transit AS
A stub autonomous system is an AS that is connected to only one other AS. Service from an ISP is an example of this (or a lower-tier ISP that gets its service from another ISP). A transit autonomous system is one that offers the ability to route data from one AS to another AS. For example, if ASx can route date to ASy by going through ASz, ASz is a transit AS. Transit may have financial repercussions: an ISP might, for example, buy transit service from another ISP. At the AS level, we are not concerned what the policy arrangements are and whether the transit relationship is one of free peering or paid transit.
A single-homed stub Autonomous System
A home is the network connection of a computer system or, in this case, an organization’s network. A single-homed stub system is one that is connected with a single network link. Internet service from a single ISP is an example of a single-homed system. These systems generally do not need AS numbers.
A multi-homed stub Autonomous System
This is a network that has one or more prefixes that are connected to more than one service provider (more than one AS). The organization can define different policies and preferences among the different autonomous systems to which it is connected. It will not, based on policy, route data from one AS to another. Any traffic between the AS and outside either originates or terminates at the AS.

As with IP addresses, there are also ranges of AS numbers that are reserved for private use for organizations to use if they want to organize their internal systems into internal ASes and use BGP to compute routes between them.

References

This document is an updated version of one that was originally written on April 5, 2013.

  1. AS numbers used to be 16 bits until around 2009.  ↩

  2. Atlanta, Chicago, Dallas, New York City, San Jose, Seattle, and Washington DC  ↩