Final Algorithm of the AS-path Length Policy

It is now time to describe more precisely the selection algorithm our policy uses. Given the IP addresses of the client and all replicas, it first determines which ASes they belong to. Then, it runs a Breadth Search First (BSF) graph search algorithm on the AS graph to identify the $n$ replicas that are closest to the client. That is why in Figure 4.7, the client in AS 64006 will be given the addresses of replicas B, C, and D (in this order). Replica A is more distant than any of these three.

Figure 4.7: The AS-path length policy finds $n$ client-closest replicas

Possible optimizations to the above algorithm include precomputing (or caching) the ASNs of replicas, precomputing complete responses, and reordering peer ASes lists in our map of the Internet so that it becomes faster to search through. All these modifications are left for future work, as well as the investigation of the correspondence between the AS-specific features (e.g., number of peer ASes and prefixes connected) and their position in the optimal ordering in the peer ASes lists.