People  Documentation  Software Download  Experiments  Contact Us  Grants  Related Projects 
Our work aims at developing novel techniques for inferring the relationships between Autonomous Systems (AS) in the Internet. This site provides a Technical Report describing our research. Further, we provide the software that implements the techniques described in the report and give details about our experimentations 
Software used in the Technical Report
bgpSat_2002_07_30.tar.gz  29KB  source code
A new optimized version (much faster than the previous one, with some more options)
bgpPathSat_2003_05.tar.gz
 36KB  source code
bgpPathSat.gz
 285KB  binary executable (2003_05 version), compiled using egcs 2.91.66 and LEDA 4.1 on an i686
Suppose to have a graph (AS graph) where each vertex is an AS and there is an edge between two ASes if there is a BGP peering between them. Given a set of AS paths from a BGP Routing Information Base (RIB) such a graph is naturally obtained by making the union of all the AS paths.
Think about an ideal world where routers are correctly configured and the only possible relationship between ASes is the customerprovider relationship. Since customer ASes never permit transit for their provider ASes, the BGP protocol rules impose that each path traverses the AS graph first uphill (from customers to providers) and then downhill (from providers to customers). That is, each path is "valley free".
We can label each edge of the AS graph with an appropriate relationship (e.g., customerprovider, peertopeer, siblingtosibling, etc). Suppose you have labeled the graph. We can consider each path and check if it respects the above mentioned rule. If this is not the case we say that there is an anomaly.
The
In the following we consider only the customerprovider relationship, so labeling the AS graph means to direct all edges of the AS graph from customers to providers.
In this section we analyze the effectiveness of our algorithm which is based on a reduction to the 2SAT problem. For brevity we call such an algorithm SAT.
We used the data sets dated 18 April 2001 that can be retrieved from Agarwal's website. Such data set contains 10 BGP RIB taken in the same day from distinct looking glasses. The lists of paths provided in the same site contain duplicated AS paths (but do not contain consecutive duplicates). Totally, the 10 lists of paths contain 3,423,460 paths. The following TABLE 1 shows statistics performed on the data. For each AS we show the number of paths available for such AS and the number of vertices and edges of the AS graph described by the paths.
AS #  AS Name  Paths (from Agarwal's website) 
Vertices (recomputed) 
Edges (recomputed) 

1  Genuity  58,156  10,203  13,001 
1740  CERFnet  70,830  10,007  13,416 
3549  Globalcrossing  60,409  10,288  13,039 
3582  Univ.of Oregon  2,584,230  10,826  22,440 
3967  Exodus Comm.  254,123  10,387  18,401 
4197  Global Online Japan  55,060  10,288  13,004 
5388  Energis Squared  58,832  10,411  13,259 
7018  AT&T  120,283  9,252  12,117 
8220  COLT Internet  46,606  8,376  10,932 
8709  Exodus, Europe  114,931  10,333  15,006 
First, we used SAT algorithm to test if the set of paths provided for each looking glass is orientable without anomalies. The result of such a test is shown in the third column of the TABLE 2 below.
AS #  AS Name  Orientable with no anomalies? (format is "provider customer") 

1  Genuity  yes 
1740  CERFnet  yes 
3549  Globalcrossing  yes 
3582  Univ.of Oregon  no 
3967  Exodus Comm.  yes 
4197  Global Online Japan  yes 
5388  Energis Squared  yes 
7018  AT&T  yes 
8220  COLT Internet  yes 
8709  Exodus, Europe  yes 
Further, we considered all the 3,423,460 paths
of the data set and we applied the heuristics described in the
Technical Report to compute a maximal subset
of paths orientable without anomalies. Also, such an algorithm
computes an orientation without anomalies for the maximal
subset computed. The maximal orientable subset computed
contains 3,399,389 paths. Such orientation compared with the
starting set of paths gives 24,071 anomalies.
The heuristics
works in two phases: in the first phase a big orientable set
is found of 3,176,625 paths; in the second phase each of the
remaining 246,835 paths is tested and added to the set of
valid paths if it does not affect orientability.
TABLE 3 reports the result of the heuristics.
Overall Data 

Relationships computed by algorithms SAT may be incomplete, that is not all the edges of the AS graph are labeled. We considered as errors all the paths that show anomalies (non valleyfree) and all the paths that contain at least one unlabeled edge. The following TABLE 4 reports for each data source X the percentage of errors detected within the path list of X over the number of paths in the path list of X.
AS #  AS Name  Invalid paths (%), SAT alg.  Valid paths (%), SAT alg. 

1  Genuity  263 (0.45)  57,893 (99.55) 
1740  CERFnet  261 (0.37)  70,569 (99.63) 
3549  Globalcrossing  76 (0.13)  60,333 (99.87) 
3582  Univ.of Oregon  14,746 (0.57)  2,569,484 (99.43) 
3967  Exodus Comm.  1,085 (0.43)  253,038 (99.57) 
4197  Global Online Japan  251 (0.46)  54,809 (99.54) 
5388  Energis Squared  270 (0.46)  58,562 (99.54) 
7018  AT&T  249 (0.21)  120,034 (99.79) 
8220  COLT Internet  104 (0.22)  46,502 (99.78) 
8709  Exodus, Europe  246 (0.21)  114,685 (99.79) 