Micro-Benchmarks of the AS-path Length Policy

After investigating the simple policies, we started experimenting with the AS-path length policy. We measured whether (and how) the AS graph search time varies, since this search constitutes the main source of overhead generated by the AS-path length policy. Intuitively, the more distant a client is from its closest replica, the longer it will take for the BSF algorithm to explore the AS graph before finding the replica.

The simulation we performed was as following. First, for each existing AS, we configured the redirector to service one non-replicated site located in this AS. Then, for each of those sites, we measured the time that the BSF needs to find it in the AS graph, assuming that the search always starts from the same AS, representing the location of a fictitious client. To measure only the delays due to the search (and not delays due to Apache), we removed the replica-selecting function of the AS-path length policy from Apache, and embedded it into a single-threaded C program. The measured delays included the time spent on the IP-to-ASN translation, which turned out to be negligible (mean translation time was below 1 microsecond). Since the test was run outside Apache and focused on the AS-path length policy function, the overhead generated by the DNS transport layer was not measured.

The above simulation was executed for 16 different fictitious clients, located at various academic sites throughout the world. In general, each client was ``located'' on the Web server of a certain university. As for the US clients, we placed them in Berkeley, in MIT, and at Washington University. Non-US clients were placed at universities in their respective capital cities. We present a selection of our results in Figure 5.2.

Figure 5.2: The AS graph search times for 6 representative clients

a. The AS-graph search times for a client inside the *.nl domain	b. The AS-graph search times for a client inside the *.pl domain
c. The AS-graph search times for a client inside the *.ru domain	d. The AS-graph search times for a client inside the *.mit.edu domain
e. The AS-graph search times for a client inside the *.za domain	f. The AS-graph search times for a client inside the *.br domain

As expected, all the figures look similar. When the replica is very close to the client, the search algorithm needs to explore only a few nodes of the AS graph before finding the replica. When the distance grows, the number of nodes to explore dramatically increases, leading to bigger and more scattered delays. Finally, only a few nodes are located at a very long distance from the client. Searches for these nodes are long but all the same: they correspond to a full exploration of the AS graph.

We support this interpretation by looking at distributions of distances between the client and each node in the graph. Figure 5.3 shows that most nodes are indeed located at distances 3 to 5 from the clients.

Figure 5.3: The inter-AS distance distribution for 6 representative clients

Using these results, we can derive the delay for locating $n$ closest replicas for a replicated site. Basically, the time that is needed to generate a list of $n$ replicas for the client is equal to the search time of the $n$-th closest replica. For example, if the $n$-th closest replica for a client at Vrije Universiteit Amsterdam is located at distance 3, then it will be found in between 0.05 and 1.2 milliseconds (see Figure 5.2a). Similarly, finding the replicas distant from a Polish client at Warsaw University by at most 6 inter-AS links will take between 0.8 and 2.5 milliseconds (see Figure 5.2b).

As we can see, the closer a client is to the replicas, the less time the AS-path length policy needs to generate a DNS response for him. More importantly, however, the search never lasts longer than 3.1 milliseconds, and the mean search time equals 0.64 milliseconds. These values are very low compared to the latency caused by any non-local network transmission.

Having the above search times, we may also conclude on the theoretical server throughput. In a pessimistic case, when all queries require exploring the entire map, a server running the redirector can handle about 320 queries per second. In a typical case, however, the throughput will be over 1500 queries per second, since the mean search time equals 0.64 millisecond. Note that the above values only refer to the AS-path length policy implementation, and do not consider the cost introduced by DNS message processing. This theoretical throughput is likely to be ample enough for most sites. Moreover, CDNs that need to service more queries can always combine several machines running identically configured redirectors to increase the overall throughput to any desired level.