Sezione di informatica e automazione - Statistics and ...compunet/files/ToR-solutions...Such...

Massimo Rimondini Dipartimento di Informatica e Automazione

Università degli Studi Roma Tre

For more information, please visit http://www.dia.uniroma3.it/~compunet

Statistics and comparisons about two solutions for computing the types of relationships between Autonomous

Systems

––– WORK IN PROGRESS –––

October 2002

Document structure

This document is organized as follows:

• data, graphs and other similar information are placed on odd-numbered pages;

• descriptions, definitions, comments and other observations regarding the above mentioned stuff are reported on the even-numbered pages that face those containing the data they refer to.

Data sets

The following reports work on data that has been downloaded from the web site of Sharad Agarwal, Lakshminarayanan Subramanian, Jennifer Rexford, and Randy H. Katz (http://www.cs.berkeley.edu/~sagarwal/research/BGP-hierarchy). In particular, the SAT and VANTAGE graphs have been calculated using the data extracted on April 18th, 2001, and, in order to make correct comparisons, also the other statistics have been calculated using the same data. The information that have been used include BGP tables and AS paths lists from 10 different looking glasses (1, 1740, 3549, 3582, 3967, 4197, 5388, 7018, 8220, 8709).

http://www.dia.uniroma3.it/~compunet

http://www.cs.berkeley.edu/~sagarwal/research/BGP-hierarchy

AS graph

An AS graph is a graph representing logical adjacency relationships between couples of ASes. The term “logical” refers to the fact that two ASes are considered mutually adjacent if any of them exchanges routing information (i.e. a set of IP prefixes) with the other. Adjacency is not usually influenced by physical (geographical) contiguity properties.

The AS graph is here built on the basis of a list of AS paths that is the catenation of all the AS paths lists from the 10 looking glasses.

SAT graph

A SAT graph is a graph containing the same nodes and edges of the AS graph, but in which the latter are all oriented in compliance with a set of customer-provider relationships between ASes. Such relationships are inferred using algorithms and tools developed by G. Di Battista, M. Pizzonia and M. Patrignani (from now onwards, referenced as “bgpSat”), which work on a set of paths extracted from BGP tables and give as result a possible orientation of the AS graph. The orientation is always “from customer to provider”, meaning that an edge from AS x to AS y represents a situation in which x is a customer of y and y is a provider for x. The inferred graph contains no peering (i.e. unoriented) edges, but some edges (that existed in the AS graph) may be missing: this means that the algorithm could not infer an orientation for the corresponding couple of ASes.

The representation of the SAT graph chosen in this report is the following: SAT graph is a (purely) oriented graph, using an orientation that complies with the above described convention (from customer to provider), with no representation of missing edges (with respect to the AS graph), and that may miss some nodes (of the AS graph); that is, the SAT graph is here re-built (for statistical purposes) by exclusively parsing the output of the software that generated it (that contains only successfully oriented edges and the ASes that appear at their ends). Reports concerning missing edges are generated by subsequently processing an AS path list to check for missing adjacencies.

The original (inferred) SAT graph has been built by working on a complete list of AS paths from all the looking glasses; the latter has been obtained by simply catenating the AS paths lists belonging to each looking glass. The building process also included a phase of invalid paths reinsertion, to try to get a maximal set.

Number of unoriented path edges

This is the number of AS adjacencies (drawn from the complete AS paths list – i.e. the catenation of the AS paths lists belonging to all the looking glasses –) that don’t have a corresponding edge (orientation) on the SAT graph. This number may include repetitions: if a couple of ASes whose edge could not be given an orientation is repeated more than one time, the value is increased for each instance.

Number of candidate peerings

This is the number of possible peerings produced by bgpSat. It just counts the number of lines starting with candidate peering.

Path covering distribution

This value is taken directly from bgpSat’s output, and shows how many paths traverse each of the graph’s edges, regardless of the orientations (both of the paths and of the edges). More precisely, each path causes all the edges it traverses to increase by 1 their path covering.

Advertised space distribution

This is computed by parsing a catenation of the BGP tables of all the looking glasses (after making sure that each of them includes the looking glass that receives the route as first AS in all the AS paths). Each prefix that is advertised over a certain edge (i.e. from an AS to another) causes that edge’s advertised space to increase by a quantity that corresponds to the number of IP addresses that have been communicated. Like in the case of path covering distribution, no distinction is made as far as the advertisement’s direction is concerned.

Since the data is taken from a catenation of BGP tables, in order to avoid eventual repetitions in taking account of each prefix, the shown value is calculated as explained above but then (before computing the distribution) divided by 10 (the number of looking glasses), in order to attempt to report a mean value over all the looking glasses.

The smaller italic values show the same values when the division by 10 is not performed.

Strongly connected components (scc’s)

The reported sizes only consider the number of nodes.

2

AS graph

NUMBER OF NODES: 10916 NUMBER OF EDGES: 23761

CONNECTED COMPONENTS: total number: 1 cc’s to edges ratio: 0,0000042 size distribution: 1 cc of size 10916

SAT graph

NUMBER OF NODES: 10897 NUMBER OF EDGES: 23690 number of unoriented path edges: 643 number of candidate peerings: 4148

PEERING EDGES: number: 0 percentage of total: 0 %

OTHER EDGES: number: 23690 percentage of total: 100 %

PATH COVERING DISTRIBUTION: minimum: 1 average: 80 maximum: 19918

ADVERTISED SPACE DISTRIBUTION: minimum: 0

8 (~ /29) average: 1128501 (~ /12)

11285020 (~ /9) maximum: 382845158 (~ /4)

3828451584 (~ /1) STRONGLY CONNECTED COMPONENTS: total number: 10312 scc’s to edges ratio: 0,4352892 size distribution (nodes): 10311 scc’s of size 1 1 scc of size 586

3

VANTAGE graph

A VANTAGE graph is a graph which provides a possible orientation of the edges of the AS graph by using the algorithms and tools developed by S. Agarwal, L. Subramanian, J. Rexford and R. H. Katz. This graph is made up of both oriented and unoriented edges. The first start from a node that is considered a customer and end on its supposed provider (the orientation is “from customer to provider”, like for the SAT graph); the latter indicate the presence of a possible peering relationship between the ASes they connect. Again, like in the SAT graph, some edges may be missing (with respect to the AS graph), thus showing a failed attempt to give them an orientation.

The VANTAGE graph has been re-built (for statistical purposes), using a representation that is wholly similar to that of the SAT graph: oriented edges go from the customer to the provider, missing edges are not represented at all and peering edges are considered as unoriented edges. This fully corresponds to the definition of VANTAGE graph.

There is only one important (even if not so relevant on the computed values) difference in comparison with the SAT graph: the latter just contains all the nodes that appear as the ends of successfully oriented edges; in this case, the VANTAGE graph also considers all the nodes that appear at the ends of missing edges. This is due to the availability of a list of pairs of ASes whose relationship remains unknown. For example, if the relationship between AS x and AS y could not be inferred, AS y appears in the graph even if it is an isolated node (which has no inferred relationships with other nodes), because its adjacency with AS x is known by means of the mentioned list.

This could be done also in the case of the SAT graph (by analysing the paths list); anyway, the incidence of this choice is really limited: building a “pure” VANTAGE graph (which, of course, also considers some missing orientations) and then adding the isolated nodes requires the addition of just 8 nodes, which are really few in comparison with the total number of nodes.


This value is computed exactly as in the case of the SAT graph: for each path, the path covering distribution of the edges it traverses is increased by 1, regardless of orientations. Anyway, the value has been subsequently divided by 10 in order to avoid considering eventual repetitions and to try to get a mean value over all the looking glasses. Again, the AS paths file is the catenation of all the AS paths lists provided by Agarwal et al.

The smaller italic values show the same values if the division by 10 is not performed.

The value 0 as minimum path covering distribution is a clear hint (and this conjecture has been later verified) that some ASes do not appear in the paths lists provided by Agarwal. This means that they were filtered out for some reason (most probably, path incompleteness) while extracting them from the BGP tables. Nevertheless, the VANTAGE graph also contains these missing ASes (most probably, it was built directly on the basis of the BGP tables themselves).


The computation of this value is quite the same as SAT graph’s, including the division by 10, the source data set and the meaning of the smaller italic values.

Strongly connected components

The definition of “strongly connected components” remains exactly the same, with a little change: the paths leading from a node to another can traverse an unoriented (peering) edge in any direction; in other words, peering edges are considered as if they were doubly oriented.

Unoriented edges

This is the number of adjacencies on which VANTAGE failed to assign an orientation. It corresponds to the number of edges contained in the file of unknown relationships, even if it has been recomputed for better confidence.

4

VANTAGE graph

NUMBER OF NODES: 10923 NUMBER OF EDGES: 23757 number of unoriented path edges: 43242 number of candidate peerings: 0

PEERING EDGES: number: 1136 percentage of total: 5 %

OTHER EDGES: number: 22621 percentage of total: 95 %

PATH COVERING DISTRIBUTION: minimum: 0

0 average: 50

506 maximum: 22327

223277

ADVERTISED SPACE DISTRIBUTION: minimum: 0

8 (~ /29) average: 1121286 (~ /12)

11212880 (~ /9) maximum: 382845158 (~ /4)

3828451584 (~ /1) STRONGLY CONNECTED COMPONENTS: total number: 10302 scc's to edges ratio: 0,4336406 size distribution: 10096 scc's of size 1 176 scc's of size 2 21 scc's of size 3 4 scc's of size 4 1 scc of size 6 1 scc of size 7 1 scc of size 19 1 scc of size 86 1 scc of size 278

UNORIENTED EDGES: 178

5

UNORIENTED graph for SAT graph

The UNORIENTED graph is a graph that is built in the following way: for each couple of nodes whose orientation could not be inferred by bgpSat, an unoriented edge is added on the UNORIENTED graph, and the ASes at its ends are added too, if necessary. In other words, it is a representation of all the missing edges on the SAT graph.


As always, this value is computed by parsing the complete list of paths (from all the looking glasses) and adding 1 to an edge each time a path traverses it. Like in the case of the SAT graph, no division by 10 has been performed.


The computing process for this number is the usual one. Like in the case of the SAT graph, the advertised space of each edge has been divided by 10 before computing the distribution, while the values in small italic font do not include this operation.

6

UNORIENTED graph (for SAT graph)


PATH COVERING DISTRIBUTION: minimum: 0 average: 8 maximum: 103

ADVERTISED SPACE DISTRIBUTION: minimum: 25 (~ /28)

256 (~ /24) average: 3812 (~ /21)

38121 (~ /17) maximum: 66892 (~ /16)

668928 (~ /13) CONNECTED COMPONENTS: total number: 19 cc's to edges ratio: 0,2676056 size distribution: 15 cc's of size 2 1 cc of size 3 1 cc of size 4 1 cc of size 23 1 cc of size 26

7

Differences between SAT and VANTAGE

These analyses have been performed in order to show how many nodes/edges are missing in either graph; an even more important value is the one that counts how many oppositely oriented edges are there: they are quite few if compared to the total number of common edges, and this is a good hint of the quality of the orientation.

8

Differences between SAT and VANTAGE

NODES ONLY IN SAT GRAPH: 0 NODES ONLY IN VANTAGE GRAPH: 26 NODES IN BOTH GRAPHS: 10897 EDGES ONLY IN SAT GRAPH: total: 178 peering edges: number: 0 percentage of total: 0 %

other edges: number: 178 percentage of total: 100 %

EDGES ONLY IN VANTAGE GRAPH: total: 245 peering edges: number: 25 percentage of total: 10 %

other edges: number: 220 percentage of total: 90 %

EDGES IN BOTH GRAPHS: total: 23512 consistently oriented: number: 21253 percentage of total: 90 %

differently oriented: number: 2259 percentage of total: 10 %

oppositely oriented: number: 1148 percentage of total: 5 % percentage of diff. oriented: 51 %

peers only in SAT graph: number: 0 percentage of total: 0 % percentage of diff. oriented: 0 %

peers only in VANTAGE graph: number: 1111 percentage of total: 5 % percentage of diff. oriented: 49 %

peers in both graphs: number: 0 percentage of total: 0 % percentage of cons. oriented: 0 %

9

DIFFERENTIAL graph

A DIFFERENTIAL graph is a graph which highlights different orientations between SAT and VANTAGE. In particular, for each of the edges that are common to the SAT and the VANTAGE graph (i.e. edges linking the same couples of ASes), their orientation in SAT and in VANTAGE is compared, and, if found to be different, an unoriented edge is inserted in the DIFFERENTIAL graph. The nodes at its ends are inserted too, if necessary.

This shows that the DIFFERENTIAL graph takes into account all kinds of differences in orientation: both oppositely oriented edges and edges that are peerings on only one graph.


These data follow the same rules as those for the other graphs: when derived from the VANTAGE graph, the path covering of each edge is preliminarily (before computing the distribution) divided by 10; when derived from the SAT graph, this operation is not performed. As always, small italic values represent the situation in which the division is not performed.

The choice to report data from both the two graphs is due to small gaps that have been pointed out between the information contained in each of them. These might be due to different methods used by bgpSat and by the tools that performed the reported analyses to compute the path covering and to approximation faults while computing the means of advertised spaces.


The process is similar to that for path covering distribution, except that the division by 10 is performed both for data from SAT graph and for data from VANTAGE graph. Small italic values show the same quantities when the division is not performed.

Connected components

Because of the way in which the graph is built (edges are its “primary components”), the smallest connected component must be made up of at least 2 nodes.

DIFFERENTIAL graph’s edges distribution by Looking Glass

This report shows how many of the DIFFERENTIAL graph’s edges are visible from each looking glass.

10

DIFFERENTIAL graph


PATH COVERING DISTRIBUTION (data from SAT graph): minimum: 1 average: 237 maximum: 19918

PATH COVERING DISTR. (data from VANTAGE graph): minimum: 0

1 average: 162

1627 maximum: 16615

166153

ADVERTISED SPACE DISTR. (data from SAT graph): minimum: 0

8 (~ /29) average: 4027047 (~ /11)

40270400 (~ /7) maximum: 382845158 (~ /4)

3828451584 (~ /1) ADVERTISED SPACE DISTR. (data from VANTAGE graph): minimum: 0

8 (~ /29) average: 4027048 (~ /11)

40270484 (~ /7) maximum: 382845158 (~ /4)

3828451584 (~ /1) CONNECTED COMPONENTS: total number: 169 cc's to edges ratio: 0,0748119 size distribution: 143 cc's of size 2 20 cc's of size 3 4 cc's of size 4 1 cc of size 5 1 cc of size 646

DIFFERENTIAL graph’s edges distribution by Looking Glass

AS 1 sees 263 of the differently oriented edges AS 1740 sees 293 of the differently oriented edges AS 3549 sees 320 of the differently oriented edges AS 3582 sees 1883 of the differently oriented edges AS 3967 sees 580 of the differently oriented edges AS 4197 sees 290 of the differently oriented edges AS 5388 sees 299 of the differently oriented edges AS 7018 sees 301 of the differently oriented edges AS 8220 sees 408 of the differently oriented edges AS 8709 sees 426 of the differently oriented edges

11

INCONSISTENCY graph

The INCONSISTENCY graph (or graph of the incompatibilities) is a subgraph of the differential graph, which only considers edges that are oppositely oriented in SAT and VANTAGE. In other words, every time an oppositely oriented edge is detected on the two graphs, an edge (and, if necessary, the nodes at its ends) is added to this graph.

Path covering distribution and Advertised space distribution

They both follow the criteria shown for the DIFFERENTIAL graph.

INCONSISTENCY graph’s edges distribution by Looking Glass

This shows how many edges of the INCONSISTENCY graph can be seen from each looking glass.

12

INCONSISTENCY graph




1 average: 29

296 maximum: 3043

30436

ADVERTISED SPACE DISTR. (data from SAT graph): minimum: 0

8 (~ /29) average: 682912 (~ /13)

6829110 (~ /10) maximum: 71274521 (~ /6)

712745216 (~ /3) ADVERTISED SPACE DISTR. (data from VANTAGE graph): minimum: 0

8 (~ /29) average: 682911 (~ /13)

6829125 (~ /10) maximum: 71274521 (~ /6)

712745216 (~ /3) CONNECTED COMPONENTS: total number: 19 cc's to edges ratio: 0,0165505 size distribution: 18 cc's of size 2 1 cc of size 453

INCONSISTENCY graph’s edges distribution by Looking Glass


13

Complement of the INCONSISTENCY graph

This graph is built on edges that have all but opposite orientations in SAT and in VANTAGE. (namely, edges that are peerings in VANTAGE and customer-provider in SAT). In this sense it is the complement (on the edges) of the INCONSISTENCY graph.

Path covering distribution and Advertised space distribution

They both follow the criteria shown for the DIFFERENTIAL graph.

Complement of the INCONSISTENCY graph’s edges distribution by Looking Glass

This list shows how many edges of the complement of the INCONSISTENCY graph can be seen from each looking glass.

14

Complement of the INCONSISTENCY graph




1 average: 300

3002 maximum: 16615

166153

ADVERTISED SPACE DISTR. (data from SAT graph): minimum: 6 (~ /30)

64 (~ /26) average: 7482548 (~ /10)

74825480 (~ /6) maximum: 382845158 (~ /4)

3828451584 (~ /1)

ADVERTISED SPACE DISTR. (data from VANTAGE graph): minimum: 6 (~ /30)

64 (~ /26) average: 7482542 (~ /10)

74825472 (~ /6) maximum: 382845158 (~ /4)

3828451584 (~ /1) CONNECTED COMPONENTS: total number: 197 cc's to edges ratio: 0,1773177 size distribution: 168 cc's of size 2 20 cc's of size 3 4 cc's of size 4 1 cc of size 5 1 cc of size 7 1 cc of size 19 1 cc of size 81 1 cc of size 255

Complement of the INCONSISTENCY graph’s edges distribution by Looking Glass


15

ISP hierarchy according to SAT

This hierarchical distribution is inferred on the basis of information provided by the SAT graph. The algorithm used is the following: an arbitrary node is labelled with an arbitrary layer (which will not influence the final distribution); then, the choice is spread around on its neighbouring nodes, in the following way: if the current node and the neighbouring one are linked by an edge that goes towards the neighbouring node, the latter is assigned a layer that is the one of the current node plus 1; conversely, if the edge is directed towards the current node, the neighbouring one is assigned a layer that is one unit smaller than the one of the current node. Each node that is assigned a new layer or that must change its old one spreads its status on its neighbours, until a stable assignment is reached (i.e. no more layer updates must be performed). Nodes belonging to the same strongly connected components are forced to have the same layer.

The so obtained hierarchy is really different from VANTAGE’s.

ISP hierarchy according to VANTAGE

Agarwal et al. suggest not to build a hierarchy by assigning a layer to each node, but to point out those sets of nodes that satisfy a certain property (for example, inner core nodes should have a good connectivity each other).

Warning: in considering the two hierarchies you must be aware that they are computed on different data sets with different methods.

16

ISP hierarchy according to SAT

1 = highest layer (large ISPs, "dense core") 12 = lowest layer (small ISPs, "customers") 9 ASes in layer 1

(12095, 4553, 8526, 8627, 12315, 4589, 8356, 8652, 8914) 586 ASes in layer 2 5 ASes in layer 3 (13126, 8513, 4005, 18477, 12976) 155 ASes in layer 4 7333 ASes in layer 5 1905 ASes in layer 6 629 ASes in layer 7 215 ASes in layer 8 48 ASes in layer 9 9 ASes in layer 10

(6880, 17147, 16780, 16990, 13161, 12591, 5467, 8530, 23004)

2 ASes in layer 11 (5461, 9056) 1 ASes in layer 12 (2643) ISP hierarchy according to VANTAGE

1 = highest layer (large ISPs, “dense core”) 5 = lowest layer (small ISPs, “customers”) 20 ASes in layer 1

(1, 1239, 174, 1755, 1833, 209, 2548, 2828, 2914, 3356, 3549, 3561, 3967, 4006, 4200, 5511, 6453, 701, 7018, 8918)

129 ASes in layer 2 897 ASes in layes 3 971 ASes in layer 4 8898 ASes in layer 5

17

DIFFERENTIAL graph’s hierarchical node distribution according to VANTAGE

This is the distribution of node layers in the classification provided by Agarwal et al.

Numbers between brackets show the distribution only for the nodes of the largest connected component of the DIFFERENTIAL graph.

INCONSISTENCY graph’s hierarchical node distribution according to VANTAGE

Exactly the same as DIFFERENTIAL graph’s.

VANTAGE peering hierarchical distribution according to VANTAGE

This shows how many nodes in each layer have at least one peering relationship with any other node, where the layers are those provided by Agarwal et al.

VANTAGE’s inner core

These values are reported just to show that no core AS has a non-peering relationship with other core ASes (conversely, all the core ASes only have peering relationships among themselves), and that core ASes almost form a clique. It is also shown how many of the peerings involve at least one core AS.

18

DIFFERENTIAL graph’s hierarchical node distribution according to VANTAGE

20 (20) ASes in layer 1 127 (127) ASes in layer 2 708 (358) ASes in layer 3 113 (102) ASes in layer 4 45 (39) ASes in layer 5 INCONSISTENCY graph’s hierarchical node distribution according to VANTAGE

18 (18) ASes in layer 1 96 (91) ASes in layer 2 217 (204) ASes in layer 3 113 (101) ASes in layer 4 45 (39) ASes in layer 5 VANTAGE peering hierarchical distribution according to VANTAGE

20 ASes in layer 1 124 ASes in layer 2 663 ASes in layer 3 0 ASes in layer 4 0 ASes in layer 5 VANTAGE’S inner core (layer 1 according to VANTAGE)

PEERING EDGES: 156 OTHER EDGES: 0

PEERING EDGES IN WHOLE VANTAGE GRAPH: total: 1136 with at least one core AS: 368 others: 768

19

Largest SCC’s of SAT and VANTAGE

This report shows what happens inside the largest strongly connected components both of SAT and of VANTAGE.

Common zone

These values represent statistics about nodes and edges that appear in the largest strongly connected components of both the SAT and the VANTAGE graph.

20

Largest SCC’s of SAT and VANTAGE

SAT LARGEST SCC: number of nodes: 586 number of edges: 4148

VANTAGE LARGEST SCC: number of nodes: 278 number of edges: 2345

COMMON ZONE: number of nodes: 249 number of edges: total: 2236 consistently oriented: number: 917 percentage of total: 41 %

oppositely oriented: number: 587 percentage of total: 26 %

peers only in VANTAGE: number: 732 percentage of total: 33 %

21

Total number of distinct paths

This is the number of distinct paths taken from the full list of AS paths (the catenation of the AS paths lists from all the 10 looking glasses).

Paths traversing >x edges of the INCONSISTENCY graph

This value is computed considering only distinct paths.

Number of subsequent crossings

This considers the number of times that a path traverses an edge of the INCONSISTENCY graph after having already traversed one. Therefore, this value is not a number of paths, but a number of crossings. The value is computed as follows: for each path (taken from the full list of distinct paths), if it traverses an edge of the INCONSISTENCY graph for the 2nd, 3rd time and so forth, the value is increased by 1 for each crossing subsequent to the first.

Crossing point distribution

This report shows, for each path, the position in which it traverses an edge of the INCONSISTENCY graph. The value is calculated as follows: for each path, a list of positions in which it traverses edges of the INCONSISTENCY graph is built; for example, path A B C D E traverses edge A B (if any) in position 0, edge B C (if any) in position 1, edge C D (if any) in position 2 and edge D E (if any) in position 3; then, all the values are normalized between 0 and 10 (in the example, position 0 remains 0, position 1 becomes 3, position 2 becomes 7 and position 3 becomes 10) and the distribution is built. The normalization is performed in order to make the positions be independent from path length.

Paths of length 2 are explicitly reported, because it is difficult to determine if the crossing takes place at their beginning or at their ending.

The first report (1st crossing only) only considers the first time that a path traverses an edge of the INCONSISTENCY graph (disregarding any further crossing); the second one also takes into account crossings that are subsequent to the first, and, as such, the values that are shown are number of crossings instead of number of paths.

Paths traversing Ig’s largest cc’s core ASes

The paths considered here are those that traverse at least one core AS (according to the hierarchy provided by Agarwal et al.) belonging to the largest connected component of the INCONSISTENCY graph. Values are computed on the basis of the full list of distinct paths.

“Ig” stands for INCONSISTENCY graph.

Paths traversing Ig’s edges

These are paths that traverse at least one edge of the INCONSISTENCY graph.

Also traversing unoriented edges

These values show how many missing (not oriented) adjacencies in the SAT and in the VANTAGE graph are crossed by paths traversing edges of the INCONSISTENCY graph. The value 0 for SAT means that none of the paths that traverse at least one edge of the INCONSISTENCY graph also runs across missing edges of the SAT graph. The value 38 for VANTAGE shows that 38 missing adjacencies are hit (possibly more than one time) by the paths that traverse at least one edge of the INCONSISTENCY graph.

22

Paths traversing edges of the INCONSISTENCY graph

TOTAL NUMBER OF DISTINCT PATHS: 502517 PATHS TRAVERSING >x EDGES OF THE INCONSISTENCY GRAPH: x = 0: 43884 x = 1: 917 x = 2: 67 x = 3: 0

NUMBER OF SUBSEQUENT CROSSINGS: 984 CROSSING POINT DISTRIBUTION (1st crossing only) 8324 paths in position 0 248 paths in position 1 4187 paths in position 2 7223 paths in position 3 1384 paths in position 4 14041 paths in position 5 5193 paths in position 6 661 paths in position 7 275 paths in position 8 0 paths in position 9 2094 paths in position 10 254 paths of length 2

CROSSING POINT DISTRIBUTION (all crossings) 8431 crossings in position 0 253 crossings in position 1 4358 crossings in position 2 7460 crossings in position 3 1529 crossings in position 4 14266 crossings in position 5 5273 crossings in position 6 671 crossings in position 7 279 crossings in position 8 0 crossings in position 9 2094 crossings in position 10 254 paths of length 2

Mixed analyses

PATHS TRAVERSING IG’S LARGEST CC’S CORE ASES: number: 454523 not traversing any Ig edge: 421093

PATHS TRAVERSING IG’S EDGES: number: 43884 not traversing any Ig’s largest cc’s core AS: 10454 not traversing any core AS: 10433 also traversing unoriented edges: on SAT: 0 on VANTAGE: 38

23

Paths slope on SAT graph

An ascending leg of a path is a (possibly empty) subset of its edges (considered in the order in which they appear in the path) that includes the first node of the path and considers all edges that are assigned an ascending orientation by SAT. In other words, the ascending leg of a path AS

1, AS

2, ..., AS

n is a subset S of edges AS

1-AS

2, AS

2-AS

3, ..., AS

x-1-AS

x such that AS

1 appears in S, all the

edges in S are contiguous and correspond to customer-provider edges of the SAT graph (SAT orientation is AS

1AS

2, AS

2AS

3, etc.).

A descending leg of a path is a (possibly empty) subset of its edges (considered in the order in which they appear in the path) that includes the last node of the path and considers all edges that are assigned a descending orientation by SAT. In other words, the descending leg of a path AS

1, AS

2, ..., AS

n is a subset S of edges AS

n-k-AS

n-k+1, ..., AS

n-2-AS

n-1, AS

n-1-AS

n such that AS

n appears in S, all

the edges in S are contiguous and correspond to provider-customer edges of the SAT graph (SAT orientation is AS

n-2AS

n-1, AS

n-1AS

n, etc.).

The considered paths are those from the full list of paths (the catenation of all the AS paths lists from the 10 looking glasses), without repetitions.

24

Paths slope on SAT graph

DISTINCT PATHS: total: 502517 ascending leg longer than descending: number: 167059 percentage of total: 33 %

same ascending and descending leg length: number: 140364 percentage of total: 28 %

descending leg longer than ascending: number: 195094 percentage of total: 39 %

25

Samples

These drawings show various situations of different orientations assigned by SAT and by VANTAGE. Circled and underlined AS numbers identify core ASes according to the hierarchy provided by Agarwal et al.

The choice of the paths is made as follows: a first group of paths is taken from the list of those that traverse at least one core AS; the remaining ones also transit over edges of the INCONSISTENCY graph (i.e. they are considered in order to show what happens when the assigned orientations are opposing).

These examples also consider invalid paths (those that have a “valley”, or a chain of peerings, or a peering that is not located at “top level”). There is also one instance of missing orientation (that is represented with a missing edge).

In some cases it is difficult to say whether one solution is better than the other, but there are situations that clearly enhance the quality of either orientation. Of course, these are only a few samples of what happens all over the graphs, but they can provide an idea about the “behaviour” of the two inference systems (SAT’s and VANTAGE’s).

26

Samples

PATH: 3582 10764 1 3549 14345

10764

3582

1

3549

14345

SAT

10764 3582

1 3549

VANTAGE

14345

PATH: 3549 4648 2764 17536 10203

4648

3549

2764

17536

10203

SAT

VANTAGE

4648

3549

2764

17536

10203

27

PATH: 3582 1 701 702 3246 12352 3220 286 1901 5424 13042

1

3582 701

702

3246

SAT

VANTAGE

3220

12352

286

1901

5424

13042 1

3582

701 702 3246 3220 12352 286

1901

5424

13042

PATH: 1740 701 6347 7431 6571

701

1740 6347

7431

6571

SAT

VANTAGE

701

1740

6347

7431

6571

28

PATH: 3582 267 2914 1833 1299 2118 5568 3316 8409 13161 9056 2643

267

3582

2914

1833

1299

SAT

VANTAGE

5568

2118

3316

8409

13161

9056

2643

267 3582

2914 1833 1299

5568

2118

3316

8409

13161

9056

2643

29

PATH: 3582 6066 3549 1833 1299 2118 5568 3316 8409 13161 9056

6066

3582

3549

1833

1299

SAT

VANTAGE

5568

2118

3316

8409

13161

9056 6066

3582

3549 1833 1299

5568

2118

3316

8409

13161

9056

30

PATH: 1740 701 4513 13646 6730 680 1754 8756 2683 12925

701

1740 4513

13646

6730

SAT

VANTAGE 1754

680

8756

2683

12925

701

1740 4513 13646 6730

1754

680

8756 2683

12925

31

PATH: 1740 701 702 3246 12352 3220 286 1901 5424 13042

1740

701

702

3246

SAT

VANTAGE

3220

12352

286

1901

5424

13042

1740

701 702 3246 3220 12352 286

1901

5424

13042

32

PATH: 3582 2685 7018 1833 1299 2118 5568 3316 8409 13161 9056

2685

3582 7018

1833

1299

SAT

VANTAGE

5568

2118

3316

8409

13161

9056

2685

3582

7018 1833 1299

5568

2118

3316

8409

13161

9056

33

PATH: 4197 3549 10910 14707 9109 15381

3549

4197

10910

14707

9109

SAT

VANTAGE

15381 3549

4197

10910 14707 9109

15381

PATH: 7018 1239 1800 1257 12563

1239

7018

1800

1257

12563

SAT

VANTAGE

1239 7018

1800

1257

12563

34

PATH: 3582 1 1239 8043 6395 13951

1

3582 1239

8043

6395 SAT

VANTAGE

13951

1

3582

1239

8043

6395

13951

PATH: 8709 9057 3356 13649 6114 18928

9057

8709

3356

13649

6114

SAT

VANTAGE

18928

9057

8709

3356

13649

6114

18928

35

PATH: 8709 8297 5377 3261 13107 15416

8297

8709

5377

3261

13107

SAT

VANTAGE

15416

8297

8709 5377

3261

13107

15416

PATH: 1 2548 7132 7290 6922 10812

2548

1

7132

7290

6922

SAT

VANTAGE 10812

2548 1

7132

7290

6922

10812

36

PATH: 1 701 14103 174 6453 4755

701

1

14103

174

6453

SAT

VANTAGE 4755

701 1

14103

174 6453 4755

PATH: 1 5696 13646 12684

5696

1

13646

12684

SAT

VANTAGE

5696

1

13646

12684

37

PATH: 5388 8938 7176 1 8043 6395 14503

8938

5388

7176

1

8043

SAT

VANTAGE

6395

14503

8938

5388

7176

1

8043

6395

14503

PATH: 4197 3967 8709 2856 4983

3967

4197 8709

2856

4983

SAT

VANTAGE

3967

4197 8709

2856

4983

38

Sketches

These drawings are reported with the purpose of providing a raw idea of how some graphs would appear. Nodes displacement does not follow a particular order.

39

Sketches

INCONSISTENCY graph

2685

13505

3578

4565

5056

5696

6395

6983

7754

8043

10355

10911

11853

13374

13646

14265

16724

7018

6259

2828

7922

3549

6467

297

3932

4183

4436

4969

6261

6402

6939

10514

5727

6461

8918

3967

4006

3356

3561

2914

1239

14172

8011

3789

4550

6325

7194

5000

11547

13706

5462

6113

4725

6079

6082

6553

6555

9156

11466

14455

2548

701

209

11303

6667

9922

9057

8709

7170

3257

1746

2381

2497

3292

3303

3320

3407

3491

577

1842

2500

2907

4197

4323

4540

4544

4689

5650

6172

6716

7176

7501

7911

9680

4513

600

1668

1785

3557

5006

6123

6730

7132

7474

15477

2110

3209

3742

4694

5097

5430

1740

517

680

683

1273

1299

1853

1901

2200

2686

3328

3344

3976

4688

4693

5385

5400

5403

5413

5423

5424

5466

5496

5539

5571

5607

5673

6067

6327

6727

6774

6805

6894

7091

7514

7518

7529

7960

8002

8196

8210

8251

8327

8333

8365

8379

8406

8437

8469

8472

8477

8553

8560

8650

8741

8785

8881

8966

9013

9132

10557

10614

10790

12095

12111

12322

12382

12614

12781

12793

13768

7473

8220

8938

2516

12956

3220

719

1257

2603

2874

3246

3336

4637

5377

5515

5574

5669

6728

8001

8235

8647

12352

1290

5594

2529

2871

5621

6735

6754

8426

8656

8939

702

1755

1835

12546

8297

5511

286

6762

5378

5388

5409

174

8355

2856

12394

2818

12909

2611

5427

5519

5597

6659

8247

8743

8840

8851

9145

12306

12390

12606

13269

15385

9193

293

3333

8782

8761

1267

3914

6705

6847

1653

3269

4589

5392

5410

5556

5602

6830

8228

8277

8586

8736

8914

9027

12552

12761

13129

6320

2116

13127

6675

8653

2863

3302

3313

3701

3741

3856

4222

4319

4780

5051

5102

5394

5499

5549

5631

5705

6316

6427

6785

6893

6971

7203

7397

8070

8245

8319

8434

8473

8582

8622

8815

8968

8984

9004

9031

11422

11423

12357

12359

12435

12541

12721

12797

15803

16631

7660

10364

1221

1270

10764

6509

4713

7270

1836

5551

13389

668

6465

715

3259

5492

5595

6848

8209

8404

8447

8627

8903

9126

12077

15623

137

559

786

1103

2647

3228

3304

3352

5483

5493

8237

8289

9177

12429

12457

12554

12715

12852

15482

12308

3301

4134

145

568

6660

12424

2134

6895

12885

226

1784

5106

5089

12215

14384

5676

5693

5707

11341

11846

11908

17075

4908

5536

6057

13791

14940

11817

7610

7066

10024

10749

513

4538

11537

195

1742

5050

549

12216

13649

15206

1800

6064

7915

11195

11889

9656

6453

703

5425

8006

3764

6598

6941

13431

13944

14103

13001

3107

2514

173

2687

9370

9824

2527

4702

4680

7828

10780

13347

18512

3462

4761

4766

4788

9505

9716

3608

8651

7617

5583

12315

9318

2648

3404

12179

11485

4223

4039

6062

18560

8610

12480

3394

1327

2118

2578

4005

4230

14758

4314

10530

4926

12259

6103

15270

13678

4862

9304

4789

7497

10881

10412

2715

1916

2848

2683

9121

8705

2685

13505

3578

4565

5056

5696

6395

6983

7754

8043

10355

10911

11853

13374

13646

14265

16724

7018

6259

2828

7922

3549

6467

297

3932

4183

4436

4969

6261

6402

6939

10514

5727

6461

8918

3967

4006

3356

3561

2914

1239

14172

8011

3789

4550

6325

7194

5000

11547

13706

5462

6113

4725

6079

6082

6553

6555

9156

11466

14455

2548

701

209

11303

6667

9922

9057

8709

7170

3257

1746

2381

2497

3292

3303

3320

3407

3491

577

1842

2500

2907

4197

4323

4540

4544

4689

5650

6172

6716

7176

7501

7911

9680

4513

600

1668

1785

3557

5006

6123

6730

7132

7474

15477

2110

3209

3742

4694

5097

5430

1740

517

680

683

1273

1299

1853

1901

2200

2686

3328

3344

3976

4688

4693

5385

5400

5403

5413

5423

5424

5466

5496

5539

5571

5607

5673

6067

6327

6727

6774

6805

6894

7091

7514

7518

7529

7960

8002

8196

8210

8251

8327

8333

8365

8379

8406

8437

8469

8472

8477

8553

8560

8650

8741

8785

8881

8966

9013

9132

10557

10614

10790

12095

12111

12322

12382

12614

12781

12793

13768

7473

8220

8938

2516

12956

3220

719

1257

2603

2874

3246

3336

4637

5377

5515

5574

5669

6728

8001

8235

8647

12352

1290

5594

2529

2871

5621

6735

6754

8426

8656

8939

702

1755

1835

12546

8297

5511

286

6762

5378

5388

5409

174

8355

2856

12394

2818

12909

2611

5427

5519

5597

6659

8247

8743

8840

8851

9145

12306

12390

12606

13269

15385

9193

293

3333

8782

8761

1267

3914

6705

6847

1653

3269

4589

5392

5410

5556

5602

6830

8228

8277

8586

8736

8914

9027

12552

12761

13129

6320

2116

13127

6675

8653

2863

3302

3313

3701

3741

3856

4222

4319

4780

5051

5102

5394

5499

5549

5631

5705

6316

6427

6785

6893

6971

7203

7397

8070

8245

8319

8434

8473

8582

8622

8815

8968

8984

9004

9031

11422

11423

12357

12359

12435

12541

12721

12797

15803

16631

7660

10364

1221

1270

10764

6509

4713

7270

1836

5551

13389

668

6465

715

3259

5492

5595

6848

8209

8404

8447

8627

8903

9126

12077

15623

137

559

786

1103

2647

3228

3304

3352

5483

5493

8237

8289

9177

12429

12457

12554

12715

12852

15482

12308

3301

4134

145

568

6660

12424

2134

6895

12885

226

1784

5106

5089

12215

14384

5676

5693

5707

11341

11846

11908

17075

4908

5536

6057

13791

14940

11817

7610

7066

10024

10749

513

4538

11537

195

1742

5050

549

12216

13649

15206

1800

6064

7915

11195

11889

9656

6453

703

5425

8006

3764

6598

6941

13431

13944

14103

13001

3107

2514

173

2687

9370

9824

2527

4702

4680

7828

10780

13347

18512

3462

4761

4766

4788

9505

9716

3608

8651

7617

5583

12315

9318

2648

3404

12179

11485

4223

4039

6062

18560

8610

12480

3394

1327

2118

2578

4005

4230

14758

4314

10530

4926

12259

6103

15270

13678

4862

9304

4789

7497

10881

10412

2715

1916

2848

2683

9121

8705

40

COMMON EDGES IN SAT/VANTAGE’S LARGEST SCC

112179

13646

13789

13790

1913

2548

2685

2914

4565

5056

5696

6395

10530

11908

2828

3967

4323

6461

6667

701

7473

8918

8938

9057

10857

7018

10910

1239

209

3549

3561

11341

1755

6453

11422

11423

11466

6427

11588

3908

3356

1221

16779

1833

2516

3786

4637

4766

5727

6939

7474

9505

12306

12313

1273

12352

3220

3246

702

1800

3608

852

12390

5388

5519

7176

12421

12530

12432

8220

3216

1257

2863

2874

1270

517

5549

1299

3300

5413

8297

8709

12781

4513

12885

5378

6728

6847

1290

174

5551

12956

6813

13129

5511

14707

15100

15251

15254

7222

15412

15643

15862

16422

1691

286

4200

6730

8656

1740

2497

293

297

3320

4000

4006

4544

5462

568

6172

7170

3292

5400

5430

5466

9193

1784

4969

1785

1901

2110

2134

2200

2381

2500

2907

4459

4689

7660

2513

2514

2521

4197

4694

9225

2529

5417

600

6347

7132

7911

2603

2647

3257

4713

5409

703

3914

5650

6259

6402

6467

7922

2686

3303

4540

5089

5673

6079

6716

2856

2871

3491

2915

5669

9010

9156

3209

3328

3344

5006

5377

5496

5539

5571

5594

5607

6659

6705

6735

6754

680

6805

8001

8196

8210

8319

8379

8406

8437

8472

8477

8582

8650

8743

8785

8851

8881

8966

9109

9126

6841

9680

3602

9494

6123

4058

4732

7514

7439

5631

5705

6517

6971

7091

8469

8560

9132

4716

4755

6762

9498

4926

6660

786

5683

6113

6122

6539

683

8213

8647

8933

9304

9502

8198

9145

9318

112179

13646

13789

13790

1913

2548

2685

2914

4565

5056

5696

6395

10530

11908

2828

3967

4323

6461

6667

701

7473

8918

8938

9057

10857

7018

10910

1239

209

3549

3561

11341

1755

6453

11422

11423

11466

6427

11588

3908

3356

1221

16779

1833

2516

3786

4637

4766

5727

6939

7474

9505

12306

12313

1273

12352

3220

3246

702

1800

3608

852

12390

5388

5519

7176

12421

12530

12432

8220

3216

1257

2863

2874

1270

517

5549

1299

3300

5413

8297

8709

12781

4513

12885

5378

6728

6847

1290

174

5551

12956

6813

13129

5511

14707

15100

15251

15254

7222

15412

15643

15862

16422

1691

286

4200

6730

8656

1740

2497

293

297

3320

4000

4006

4544

5462

568

6172

7170

3292

5400

5430

5466

9193

1784

4969

1785

1901

2110

2134

2200

2381

2500

2907

4459

4689

7660

2513

2514

2521

4197

4694

9225

2529

5417

600

6347

7132

7911

2603

2647

3257

4713

5409

703

3914

5650

6259

6402

6467

7922

2686

3303

4540

5089

5673

6079

6716

2856

2871

3491

2915

5669

9010

9156

3209

3328

3344

5006

5377

5496

5539

5571

5594

5607

6659

6705

6735

6754

680

6805

8001

8196

8210

8319

8379

8406

8437

8472

8477

8582

8650

8743

8785

8851

8881

8966

9109

9126

6841

9680

3602

9494

6123

4058

4732

7514

7439

5631

5705

6517

6971

7091

8469

8560

9132

4716

4755

6762

9498

4926

6660

786

5683

6113

6122

6539

683

8213

8647

8933

9304

9502

8198

9145

9318

41

Missing (unoriented) edges

This graph, together with the following one, shows (in a much more readable way than the preceding ones) which are the ASes whose adjacencies are most difficult to be oriented.

42

MISSING (UNORIENTED) EDGES ON SAT GRAPH

17315

8709

7049

4926

14232

5555

721

5378

2874

174

5511

2686

6762

16130

11403

3043

6993

10912

11853

10913

10910

12179

7168

7790

14752

6467

9057

5400

14215

15202

17351

11862

13947

65002

13791

7623

3786

4663

9768

9318

3976

9958

9316

9581

9948

10156

9643

9644

10060

7563

9972

9705

9687

10183

9457

9321

10170

10166

1901

13646

14009

4550

5574

3220

8650

5549

12450

12512

2529

3549

1290

1299

3597

4387

10277

10834

10068

4745

10197

1237

3303

1836

17571

9494

17572

9277

17315

8709

7049

4926

14232

5555

721

5378

2874

174

5511

2686

6762

16130

11403

3043

6993

10912

11853

10913

10910

12179

7168

7790

14752

6467

9057

5400

14215

15202

17351

11862

13947

65002

13791

7623

3786

4663

9768

9318

3976

9958

9316

9581

9948

10156

9643

9644

10060

7563

9972

9705

9687

10183

9457

9321

10170

10166

1901

13646

14009

4550

5574

3220

8650

5549

12450

12512

2529

3549

1290

1299

3597

4387

10277

10834

10068

4745

10197

1237

3303

1836

17571

9494

17572

9277

43

MISSING (UNORIENTED) EDGES ON VANTAGE GRAPH

5696

13646

7515

4713

1740

1800

2548

4323

1741

3343

721

1913

10097

4634

2856

5669

1916

17379

14744

12182

2907

2513

9145

6754

15742

6703

10207

7568

13480

11647

7483

4747

2516

3352

3582

11537

7170

3257

4513

3786

6395

7660

1221

5056

4200

2828

6172

2685

5650

6939

4969

10764

1103

293

6667

9156

11422

8651

174

1836

6730

7176

4565

2497

4694

6695

5413

5594

2603

6427

1280

6453

701

3320

715

9010

8657

8269

5089

6113

2551

145

2041

7911

3491

14384

11485

1784

11423

4006

683

10530

7291

4544

6079

3932

10490

6066

668

6509

297

59194

104

513

1224

4600

3701

16779

3464

2200

1829

2901

15296

382818

4553

6467

852

6716

9057

8356

8355

1299

8220

517

8656

10364

7091

6461

1746

9225

4635

4000

8918

8652

4538

10834

11058

13835

8526

3246

1668

8213

12308

3327

3249

6895

702

8647

8198

8327

8785

12419

12843

8966

5621

7194

5648

6123

4689

4688

9304

8653

11608

4134

9306

4680

1901

15454

3407

7474

4740

8709

8938

5400

6728

4197

7501

4725

5388

8586

5539

5696

13646

7515

4713

1740

1800

2548

4323

1741

3343

721

1913

10097

4634

2856

5669

1916

17379

14744

12182

2907

2513

9145

6754

15742

6703

10207

7568

13480

11647

7483

4747

2516

3352

3582

11537

7170

3257

4513

3786

6395

7660

1221

5056

4200

2828

6172

2685

5650

6939

4969

10764

1103

293

6667

9156

11422

8651

174

1836

6730

7176

4565

2497

4694

6695

5413

5594

2603

6427

1280

6453

701

3320

715

9010

8657

8269

5089

6113

2551

145

2041

7911

3491

14384

11485

1784

11423

4006

683

10530

7291

4544

6079

3932

10490

6066

668

6509

297

59194

104

513

1224

4600

3701

16779

3464

2200

1829

2901

15296

382818

4553

6467

852

6716

9057

8356

8355

1299

8220

517

8656

10364

7091

6461

1746

9225

4635

4000

8918

8652

4538

10834

11058

13835

8526

3246

1668

8213

12308

3327

3249

6895

702

8647

8198

8327

8785

12419

12843

8966

5621

7194

5648

6123

4689

4688

9304

8653

11608

4134

9306

4680

1901

15454

3407

7474

4740

8709

8938

5400

6728

4197

7501

4725

5388

8586

5539

44

Sezione di informatica e automazione - Statistics and ...compunet/files/ToR-solutions...Such...

Documents

Transcript of Sezione di informatica e automazione - Statistics and ...compunet/files/ToR-solutions...Such...