General table statisticsWe first calculate the following statistics for each routing table collected from Routeviews and RIPE:
1) The address space coverage provided by the table, in terms
of the number of IP addresses.
2) The number of prefixes seen in the table.
2) The number of unique AS paths seen in the table.
3) The number of AS links seen in the table.
3) The number of origin ASes seen in the table.
4) The mean APA which is the mean of the distribution of the number of IP addresses owned by an AS.
5) The std deviation of APA, which is a measure of the diversity of the IP-AS mapping provided by the table.
The entries of the table are color-coded, such that the entry in red indicates the largest value across a column. If a particular row (corresponding to a routing table) has red entries all through, then it indicates that that routing table is the best with respect to each metric of interest.
|table||coverage||AS paths||prefixes||AS links||origin ASes||APA mean||APA std dev|
|table||coverage||AS paths||prefixes||AS links||origin ASes||APA mean||APA std dev|
We find that in the case of Routeviews, the table RV2 is the best in terms of the number of AS paths, unique prefixes, unique AS links and origin ASes. RV_linx, however, provides the most address space coverage. For RIPE, we find that no single table is best with respect to all metrics. RRC01 gives the most coverage of address space. The currently used table (RRC12) does not seem to be the best with respect to any particular metric.
The utility of adding additional tables
Here, we study the utility of adding additional routing tables. We start with a base table, and keep adding new tables successively. We then measure how the following metrics change due to the addition of the new table.
1) Additional address space coverage provided by the new table.
2) Address space allocation changed due to the new table.
3) Unique ASes and origin ASes provided by the new table.
4) Unique AS links provided by the new table.
5) Unique prefixes provided by the new table.
6) Unique more specific prefixes provided by the new table.
7) More specific prefixes with different origin AS provided by the new table.
Tables ordered by overall address space coverage
In the first comparison, we use the table with the largest address space coverage as the starting (base) table. We then successively add additional tables in the decreasing order of address space coverage, measuring the change in the aforementioned properties caused by the additional table.
We find that additional tables lead to less than 1% increase in address space coverage, address allocation change, the number of unique ASes and unique origin ASes. The largest change caused by additional tables is in the number of unique AS links, unique prefixes and more specific prefixes. In those cases, additional tables can result in between 1% and 10% increase in the number of unique AS links, prefixes and more specific prefixes.
Adding additional routing tables leads to less than 1% increase in address space coverage. Also, less than 1% of the IP-AS allocations change when we add successive tables.
Adding additional routing tables leads to less than 1% increase in the number of unique ASes that we see. This confirms previous observations that most ASes are seen from even a small number of vantage points.
The effect of adding additional tables is larger in the case of unique AS links. We find that additional tables can yield up to 7% more AS links than seen in the base table.
We study the number of additional prefixes that we gain by adding more routing tables. We find that additional tables yield up to 8% more prefixes. The fraction of more specific new prefixes closely follows the fraction of new prefixes.
Finally, we study how many of the more specific new prefixes yield a differnt origin AS. We find that for most of the tables, between 10% and 70% of the more specific prefixes actually give a different origin AS.
Tables ordered by current usage
We study our current usage, which consists of one table from Routeviews (RV2), and one table from RIPE (RRC12). We use these tables as the starting point, and add successive tables in decreasing order of the address space coverage.
We find that adding additional tables starting from our current usage causes less than 1% change in the address space coverage, address space allocation, the number of unique ASes and unique origin ASes. The change in the number of unique AS links, unique prefixes and unique more specific prefixes is between 1% and 10%.
Choosing the best additional table
In this section, we determine the best next table to add, in order to optimize a certain metric in the aggregate. The metric we use is the change in address space allocation caused by the new table. At a particular point, let tcuml be the cumulative prefix-AS mapping up to that point. We now have a set of remaining tables, and must determine the best table to add to tcuml, i.e., the table that would cause the largest change in address space allocation. This can be done in parallel for each possible table t to add.
We find that considering all tables, adding the best possible next table still results in less than 1% change in the address space coverage and address allocation. We see the same trend when we start with the currently used tables (RV2+RRC12) and successively add the best possible tables.
Comparison with Team Cymru's WHOIS service
We compare the IP-AS mapping obtained from Routeviews and RIPE BGP dumps with the IP-AS mapping service provided by Team Cymru. For this purpose, we construct a sample list of 24M IP addresses collected from Ark traces seen in January 2010. To limit the load on Cymru servers, we query only one address per /24 (the *.1 address), thus reducing the set of queried addresses to 2.7M. For each address, we compare the AS returned by Cymru with the AS obtained from the prefix-AS mappings derived from Routeviews and RIPE tables. (Cym = mapping from Cymru's service, and Tab = mapping from RV+RIPE tables).
|table||addresses||mismatch||mismatch %||Single Cym undef||%||Single Tab undef||%||Single mismatch||%||MOAS missing in Tab||%||MOAS missing in Cym||%||MOAS missing both||%|
The "single Cym undef" column refers to the number of mismatches that were because Cymru did not have a matching prefix for that IP address. "Single Tab undef" is for mismatches where our combination of routing tables did not have a match for the IP address. "Single mismatch" refers to the case where both the table and Cymru found a matching AS, but the ASes differred. "MOAS missing in Tab" refers to the cases where the IP address mapped to multiple origin ASes, and one of the ASes was missing in our tables. "MOAS missing in Cym" refers to the cases where the IP address mapped to multiple origin ASes, and one of the ASes was missing in the Cymru lookup. "MOAS missing in both" refers to the cases where the IP address mapped to multiple origin ASes, and some AS from that set was missing in both the table dumps and Cymru lookups. Overall, the difference between our current prefix-AS data (RV2+RRC12) and Cymru mapping is around 0.3%. The largest fraction of mismatches are caused due to addresses which have a single, but different matching AS in the Cymru mapping and our tables. A significant fraction of mismatches is also caused due to MOASes. In particular, we find that our BGP tables find origin ASes for the same prefix that are not seen in the Cymru mapping. The overal mismatch fraction increases as we go from the currrent subset of tables (RV2+RRC12) to a combination of all Routeviews and RIPE tables.
Temporal analysisIn this section, we study how the previously defined metrics change as we use routing tables separated in time. For this purpose, we collected 10 routing tables from one Routeviews and one RIPE collector over the duration of one month. We then compare the same metrics defined previously for the following cases:
1) Compare consecutive tables - Consider Table i as the base table, and study the effect of combining table i+1 with respect the previous metrics.
2) Compare the first table with each successive table -- Consider Table 0 as the base table, and study the effect of combining each table i with respect to the previous metrics.
Comparing consecutive tablesWe first compare consecutive tables from Routeviews and RIPE with respect to the difference in address space allocation, number of unique ASes and origin ASes, and the number of unique AS links. We use each pair of consecutive tables, and consider the first of those as the base table. Then we study the the changes in the previously enumerated properties if the second table were combined with the first. (Note that consecutive tables are themselves 3 days apart)
Overall, we find that the metrics do not change significantly across consecutive tables. Over all pairs of consecutive tables, we see < 2% increase in the address space coverage, < 3% change in address allocation, < 1% of unique ASes, < 1% of unique origin ASes, and < 3% of unique AS links.
Comparing additional tables with the first table
In this comparison, we consider the first table collected in the month as the base table. Now, we add successive tables collected over the month, and find the change in address space allocation, number of unique ASes and AS links over the duration of the month. Note that we still only consider pairs of tables, with the first table fixed.
As expected, the difference from comparing the first table with each subsequent table in the month is greater than when we compare consecutive tables. Also, the difference increases as we combine the first table with tables later in the month. We see the largest difference in the number of unique AS links, where the difference between the first and the last table of the month is about 5%.