| 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 customer-provider 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., customer-provider, peer-to-peer, sibling-to-sibling, 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 customer-provider 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 valley-free) 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) |