Autonomous Systems

The graph of routers representing the Internet can be split into subgraphs, called Autonomous Systems (ASes) [10]. Each such subgraph takes care of its internal routing using any internal routing protocol it prefers (OSPF, for example [16]). More importantly, however, the subgraphs exchange routing information with each other using an external routing protocol. In this way they ensure global reachability of the networks they enclose (see Figure 4.3).

Figure 4.3: A network of routers split into 5 Autonomous Systems

Each Autonomous System is identified by a globally recognized 16-bit Autonomous System Number (ASN). It is also assigned a certain set of prefixes, and it is responsible for handling the traffic heading to them.

The relatively small number of ASes (currently around 13000) makes it possible to construct a graph with each node representing an AS, which can be treated as a map of the Internet. More importantly, because of the size of the graph, efficient global algorithms applied to it can give results within a reasonable time. Efficiency refers to the theoretical computational complexity of the algorithm.

We define a distance metric between two machines as the minimum number of (inter-AS) links between the ASes these machines belong to. This metric is used by the most common external routing protocol, BGP, which we discuss below. For example, in Figure 4.4 the distance between machines A (in AS64001) and B (in AS64004) is 2, as the shortest route between these ASes only goes through AS64003. This metric is commonly called the ``AS-path length metric'' [13]. It is the base of the AS-path length policy: given candidate replicas (to service a client) the policy chooses those which have a minimum distance from the client. Since the AS-path length metric is successfully exploited in external routing, we believe that it is suitable to determine the distance in the Internet.

Figure 4.4: The AS-based distance means the minimal number of AS-links between two nodes

We are aware that basing the distance estimations only on the number of AS boundaries the route crosses may not be sufficient. The problem is that Autonomous Systems significantly vary in size, which makes it hard to ensure that the AS-internal communication remains fast. There are ASes covering hundreds of prefixes, and ASes having only a few of them. Some ASes are distributed over several continents, and some consist of routers all placed in only a single city. Finally, some institutions manage many different ASes, whereas the other control only one AS, which can influence the experience of the AS-managing staff. All these differences may introduce new factors, which should be considered in latency estimations as well [22]. Still, exploiting the AS-based map of the Internet is a way of dealing with the problem of distance measurement. It is also likely to be more accurate than the geographical distance.