Each BGP routing table represents a partial view of the Internet's topology. It reflects the routes that are likely to be taken by traffic starting from the router that holds the table. Having such a view, the router knows enough to deliver packets, but has little clue about the structure of the complete network. This subset of all available paths is extremely likely to cover only a small part of all existing inter-AS connections [6].
On the other hand, our aim is to build a graph of Autonomous Systems that is as complete as possible. Therefore, we need to gather routing tables from several routers all over the world, and extract a view of the Internet from each of them. Once we merge all these views together, we obtain a map of the Internet that is more complete than any of the original views. Also, the more places we take views from, the less chance that we miss existing inter-AS connections.
An important observation here is that it would be sufficient to collect the views coming from ASes that contain our replicas. The only inter-AS links we really have to know are the ones that can be used on the path to and from our service. Therefore, we do not need to bother with the links that cannot be found in any of these views. Unfortunately, the weakness of this approach lies in its main requirement: the ability to extract views from multiple routing tables, downloaded from BGP routers in several Autonomous Systems. BGP routers can seldom be accessed by unprivileged users, and arranging an access to hundreds of them is difficult. Moreover, failing to retrieve routing tables from the AS of only one replica would affect the entire system: if this replica cannot be located on the generated graph, clients cannot access the service using this replica.
Although we cannot gather a reasonable set of BGP tables ourselves, we can still use data that are publicly available. One of the most prominent projects that publishes BGP routing tables is RouteViews [2]. On its Web site we can find a huge set of routing tables, gathered from a special RouteViews BGP router. It is configured to communicate with many BGP routers all over the world and build its own, huge routing table. Moreover, the RouteViews BGP router does not perform any data compression, thus avoiding possible information loss. In this way, its table is a composition of all the routing tables of its peers, and contains many alternative routes to each prefix. This gives an effect similar to having many separate routing tables, each coming from different parts of the Internet. Although these parts are probably not exactly the ones that contain our replicas, they are still representative enough to provide the global picture that we need.
Using the RouteViews BGP routing table has two fundamental advantages. Firstly, it relieves us of the necessity of downloading several routing tables ourselves, and offers everything we need in a single file. The compressed version of this file is 17 MB large, which makes it feasible to download it from the RouteViews site. Secondly, a new snapshot of the complete BGP routing table is added to the collection every 2 hours, and made instantly publicly available. As long as the redirector periodically downloads and processes the most recent version of the RouteViews data, it can claim to always have an up-to-date map of the Internet. Moreover, people who need to retrieve the data more frequently can use special, differential BGP routing table snapshots. They are made every 15 minutes, and published on the RouteViews site as well. Since the routes in the Internet are relatively stable, updating the graph every 15 minutes should be frequent enough for most applications [17].