People Documentation Software Download Experiments Contact Us Grants Related Projects

Computing the Types of the Relationships between Autonomous Systems

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

Documentation

Software Download

We provide the software used to perform the experimentation shown in the Technical Report. The software permits to compute an orientation without invalid as-paths (i.e. all paths are Type 1 paths according to Subramanian et al.) if such orientation exists for the provided set of as-paths. Otherwise it permits to apply the heuristics described in the Technical Report.

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

Sketch of the Problem

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 ToR (Type of Relationship) problem is the problem of labeling each edge of the AS graph such that the number of anomalous paths is minimized.

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.

Experimental Results

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
TABLE 1

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
TABLE 2

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

TABLE 3

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)
TABLE 4

Related Projects

The classification of AS relationships in the Internet is a hot research topic. Its relevance has been confirmed by the interest of other research groups on the same subject. In particular, independently of our work, the Theory of Communication Networks Group of Zurich discovered analogous results concerning the time complexity of the general problem and the linearity in the case of all valid paths. However, while they put more emphasys on the approximability of the problem, we focus more on the engineering and the experimentation of an effective heuristic approach.
A Technical Report describing the results of the Theory of Communication Networks Group of Zurich is the following: Other links to related projects can be found in the AS Topology Inference Section of the links page of the Compunet Website.

Grants

European Commission - Fet Open project COSIN - COevolution and Self-organisation In dynamical Networks - IST-2001-33555.

People Involved

Giuseppe Di BattistaMaurizio PatrignaniMaurizio Pizzonia

Contact Us

This site is maintained by Maurizio Pizzonia and Maurizio Patrignani. Please contact them for information or suggestions about software, documents, and data provided in this site.