Traceroute divergence

Another metric to evaluate the proximity between the client and its local DNS server is the maximum number of disjoint network hops from a probe location to the client and its local DNS server. In [15], this metric is referred to as the traceroute cluster size. The smaller the cluster size or traceroute divergence, the closer the client is to the local DNS server. In many of our traceroute results, we found that the network routes from the probe site to the client and its LDNS diverge and converge multiple times due to router load balancing. We use the last point of divergence as the reference for calculating disjoint network hops. For example, Table 6 shows the network routes obtained by performing traceroute to the client 112.74.197.163⁵ and its LDNS 112.25.195.1. We use hop 11 instead of 2 as the point of divergence. Thus, the traceroute divergence in this example is $max(14-11, 13-11)=3$.

Table 6: Traceroute divergence

1 112.0.1.1 6 ms	1 112.0.1.1 5 ms
2 112.124.182.17 6 ms	2 112.124.182.17 15 ms
3 112.123.1.10 7 ms	3 112.123.1.22 14 ms
4 112.122.1.149 8 ms	4 112.122.5.246 7 ms
5 112.122.2.173 25 ms	5 112.122.2.2 24 ms
6 112.122.2.206 32 ms	6 112.122.2.206 31 ms
7 112.122.2.41 34 ms	7 112.122.2.41 35 ms
8 112.122.2.26 71 ms	8 112.122.2.26 68 ms
9 112.122.2.121 75 ms	9 112.122.2.121 77 ms
10 112.123.145.25 73 ms	10 112.123.145.25 72 ms
11 112.124.23.6 72 ms	11 112.124.23.6 73 ms
12 112.25.192.2 72 ms	12 * * *
13 112.25.192.181 73 ms	13 * 112.25.195.1 71 ms
14 112.74.197.163 92 ms

We selected four probe sites representing candidate CDN servers and performed traceroute to a sample of clients and local DNS servers from the log. The sample consists of 48,908 client-LDNS pairs or 66,975 IP addresses. It is obtained by randomly selecting one client-LDNS pair from the top half of the client network clusters generating the most HTTP requests. The number of client-LDNS pairs reached by an individual probe site ranges from 9,878 to 11,935. In about 20% of these, both the client and the LDNS belong to the same network cluster. And in about 75% of these, both the client and the LDNS belong to the same AS cluster.

Figure 2 shows the cumulative distribution of traceroute divergence for the sampled client-LDNS pairs. About 14% of them have traceroute divergence of 1. The mean divergence varies from 5.8 to 6.2 depending on the probe site, and the median traceroute divergence is 4 from all four probe sites. This means that a large fraction of clients are topologically quite close to their local DNS servers using the hop count metric. At most 30% of the client-LDNS pairs have traceroute divergence of size 8. This result is slightly inconsistent with the results described by Shaikh, et al. [15] considering 1,090 client-LDNS pairs of dial-up ISPs. We believe that the difference can be explained by the fact that our results are based on the analysis of a much larger set of populations visiting both commercial and educational sites.

Figure 2: Proximity evaluation using traceroute divergence

The absolute values of traceroute divergence may not be completely indicative of the proximity of a client to its local DNS server. In Figure 3, we plot the ratio of the common path length to the disjoint path length from a probe site. Using the terminology of Shaikh, et al. [15], the common path length is the minimum number of network hops of the shared path from the probe site to the local DNS server and the client before their paths diverge. For example, the common path length of client 112.74.197.163 and its LDNS 112.25.195.1 (shown in Table 6) is $min(11, 11)=11$. The disjoint path length is the maximum number of network hops of the diverging paths. In this example, the divergent path length is max(14-11, 13-11)=3. Again, we use the last point of the divergence as the reference point. For all probe sites, less than 34% of the client-LDNS pairs have disjoint paths at least as long as the common path. This means that at least 66% of client-LDNS pairs have a common path as long as or longer than their disjoint path. This metric implies that most clients are topologically close to their LDNS as viewed from a randomly chosen probe site.

Figure 3: Ratio of common to disjoint path length