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
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.
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.