A short explanation of how to use the four tools follows. If you need more complete
instructions, you can have a look at the MANUAL file inside the source code archive or
use any of the tools with the --help option.
tpathExtract
tmakeGraph
tdiffGraph
tviewGraph
tpathExtract is the tool for extracting AS paths from a BGP table dump. This tool
takes as input a raw BGP table, that is one resulting from the execution of the show
ip bgp command on a telnet looking glass router; you do not need to change it by
removing comments and/or headers: the tool should do that for you. The output is a plain
list of AS paths, that are derived from the last field (AS path) of each of the routes in
the BGP table.
Beyond doing this, the program can also perform some elaborations on the paths themselves. Basically, it can analyze them and filter out/correct those paths that have a particular characteristic. Such characteristics include the presence of cycles in the paths (which can derive from configuration errors), the presence of prepending and so on.
The following is the possible layout of a BGP table dump:
spawn telnet route-views.oregon-ix.net Trying 198.32.162.100...^M Connected to route-views.oregon-ix.net.^M Escape character is '^]'.^M ###################################################################### route-views.oregon-ix.net -- Oregon Exchange BGP Route Viewer route views data is archived on http://archive.routeviews.org This hardware is part of a grant from Cisco Systems. Please contact help@routeviews.org if you have questions or comments about this service, its use, or if you might be able to contribute your view. This router has views of the full routing table from several ASes. The list of ASes is documented under "Current Participants" on http://www.routeviews.org/. ####################################################################### route-views.oregon-ix.net>term len 512 route-views.oregon-ix.net>sh ip bgp BGP table version is 1505710, local router ID is 198.32.162.100 Status codes: s suppressed, d damped, h history, * valid, > best, i - internal Origin codes: i - IGP, e - EGP, ? - incomplete Network Next Hop Metric LocPrf Weight Path *> 2.0.0.0 167.142.3.6 0 5056 701 3491 20485 5547 ? * 3.0.0.0 203.194.0.5 0 9942 1 7018 80 i * 217.75.96.60 0 16150 8434 3257 1239 7018 80 i * 213.200.87.254 80 0 3257 1239 7018 80 i * 144.228.241.81 4294967294 0 1239 7018 80 i * 204.42.253.253 0 267 2914 7018 80 i * 209.123.12.51 0 8001 7018 80 i * 129.250.0.11 47 0 2914 7018 80 i * 216.140.14.186 1974 0 6395 7018 80 i * 216.140.8.59 3 0 6395 7018 80 i ...
If you use tpathExtract with such an input, what you get is the following:
5056 701 3491 20485 5547 9942 1 7018 80 16150 8434 3257 1239 7018 80 3257 1239 7018 80 1239 7018 80 267 2914 7018 80 8001 7018 80 2914 7018 80 6395 7018 80 6395 7018 80 ...
or, with the --group option:
669 9942 1 664 16150 8434 3257 1239 1 626 267 2914 1 664 3257 1239 1 665 8001 15036 16631 174 1 2040 6395 1 622 11608 2914 1 681 1221 4637 1 679 19092 701 1 1250 2914 1 1 12956 3356 1 679 6066 701 1 2714 4513 701 1 679 14608 701 1 ...
that is, each path appears with the number of occurrences in the BGP table,
which, if you want, can be completed with a list of the prefixes that have been
announced over each path (--group and --prefixes=show
options):
669 9942 1 4.0.0.0 24.96.0.0/17 63.244.0.0/16 63.246.224.0/20 ... 664 16150 8434 3257 1239 1 4.0.0.0 24.96.0.0/17 63.244.0.0/16 ... 626 267 2914 1 4.0.0.0 24.96.0.0/17 63.244.0.0/16 63.246.224.0/20 ... 664 3257 1239 1 4.0.0.0 24.96.0.0/17 63.244.0.0/16 63.246.224.0/20 ... 665 8001 15036 16631 174 1 4.0.0.0 24.96.0.0/17 63.244.0.0/16 ... 2040 6395 1 4.0.0.0 4.0.0.0 4.0.0.0 24.96.0.0/17 24.96.0.0/17 ... 622 11608 2914 1 4.0.0.0 24.96.0.0/17 63.244.0.0/16 63.246.224.0/20 ... 681 1221 4637 1 4.0.0.0 24.96.0.0/17 63.244.0.0/16 63.246.224.0/20 ... ...
The last output has been generated using the following command line:
$ tpathExtract --group --prefixes=show oix-full-snapshot-2003-03-27-0600.dat
It is also possible to label the paths with letters that identify their properties
('P' for paths with prepending, 'I' for incomplete paths, etc.). For a complete list
of such tags and some more information about usage and options, either look at the
MANUAL file (included with the source code) or use the --help option.
The software is quite robust to format mismatches in the input file, which include carriage returns within a route or misalignments of the fields (both occurring when the network/netmask field is too large).
This tool takes as input a set of files containing various types of information and builds a graph according to these information. The output is an ASCII file that represents the graph itself. Its format is quite complex, but you should not worry about this, because you do not need to directly deal with it. The generated graph can be saved to a file for further processing through the other tools, like already explained.
You can build the graph on the basis of different kinds of information. The minimal input consists of a file to get the nodes from; then, you can specify files containing edges, edge directions (which are only applied to existing edges), some special edge weights and so on. Each of these files can be provided in different formats (for a complete list of recognized formats, please consult the MANUAL file or the online help). The so called special weights are the path covering and the IP covering; the first one is the number of paths traversing the edge being considered, while the second one is the number of IP addresses that have been announced over it.
Just to make a simple example, here is how to build an unoriented graph whose nodes are Autonomous Systems got from a list of AS paths and whose edges represent adjacencies of the ASs within the paths:
$ tmakeGraph --file:nep pathList -o graph
tmakeGraph 1.0 Reading nodes, edges file (step 1 of 1) `pathList' [****************************************] (100.0 %) Saving graph to file...
And here is how the contents of the generated file look like (if you want to exactly know their meaning, please read the FILE_FORMAT text file included with the source code distribution):
TGR 1 pathList 15045 31227 1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 20 ... 28844 28849 28852 28855 28863 1 3 0 0 0 0 0 0 1 23 0 0 0 0 0 0 1 32 0 0 0 0 0 0 1 57 0 0 0 0 0 0 1 63 0 0 0 0 0 0 1 70 0 0 0 0 0 0 1 71 0 0 0 0 0 0 1 90 0 0 0 0 0 0 ...
Please notice that by addressing the orientation of an edge we refer to the fact that the edge has been assigned a commercial relationship (i.e., an unoriented edge has not been assigned a direction/relationship at all), while the direction is the type of relationship itself (a directed edge represents a customer-provider relationship and an undirected - but oriented! - one represents a peering one; no other relationships are supported).
it allows you to simply compare two graphs and return numerical differences between them (like the number of common nodes/edges, that of differently directed edges, etc.), as you can see in the following output:
$ tdiffGraph graph1 graph2 tdiffGraph 1.0 Reading graph file `graph1'... Reading graph file `graph2'... Computing differences... Nodes in 1st graph: 15041 - only in 1st graph: 6 Nodes in 2nd graph: 15038 - only in 2nd graph: 3 Common nodes: 15035 Edges in 1st graph: 31204 - peering: 0 - directed: 31204 - unoriented: 0 - only in 1st graph: 71 * peering: 0 * directed: 71 * unoriented: 0 Edges in 2nd graph: 31178 - peering: 0 - directed: 31178 - unoriented: 0 - only in 2nd graph: 45 * peering: 0 * directed: 45 * unoriented: 0 Common edges: 31133 - oppositely dir.: 55 - differently dir.: 55 - consistently dir.: 31078
it can be used to build a so called differential (or overlap) graph, which is a graph containing all the edges that are common to the input graphs (again exactly two) and that obey some user provided conditions; such conditions concern edge directions, and can be supplied using a syntax that resembles that of a disjunctive normal form (DNF) formula. The following example generates a graph that contains all the edges that have a different direction in the two source graphs and those that are only oriented in either one of them:
$ tdiffGraph --over:x,oU,uO graph1 graph2 -o diffgraph
it can generate a complementary graph, that is quite similar to the overlap graph, apart from the fact that edges are only inserted if they appear in only one of the source graphs. The following example generates a graph with all the unoriented edges of both the input graphs but those that are common to them:
$ tdiffGraph --comp:u,U graph1 graph2 -o diffgraph
finally, it can compare an arbitrary number of graphs, and then create, for each edge, a sort of "history" of its orientation; the output is, once more, a graph whose edge set is the union of all the edge sets of the input graphs, and whose edges are labelled with statistics about their directions' stability; this can be achieved by issuing a command like:
$ tdiffGraph --multi graph* -o diffgraph
The resulting graph is also called multi-differential graph.
The diagram above makes no difference among these kinds of graphs, so by "differential graph" we address any kind of graph that has been created using this tool.
This module provides you with the capability of analyzing the graphs that have been produced using any of the other tools. Such analysis includes the possibility to count nodes/edges within single (strongly) connected components or in the whole graph, the ability to list them together with their properties (i.e., edges directions and weights), and that of building distributions over some characteristics of the graph itself. The tool can both consider simple graphs (that is, neither differential/multi-differential nor complementary) and any kind of differential graph (produced with the tdiffGraph tool). According to the type of graph that is being analyzed, some information can or can not be significant; for example, those concerning the stability of edge directions are senseless if the input graph is not a multi-differential one.
The tool can either accept a script file as input or provide an interactive command-line
interface. The set of commands is very simple, but it allows to perform all the above
mentioned operations and some more. For a full list of available commands and of their
syntax, just start the program with no arguments: the command line prompt tgv>
will appear; then, just type help <command name> for information about
the syntax and effect of that command, or just help for a list of commands.
Below you can see an example of a tviewGraph interactive session:
tviewGraph 1.0
Interactive mode; type `help' to get a list of available commands
tvg> load diff.graph
tvg> show graph information
Graph file: diff.graph
Graph type: (multi)differential
Graph comment:
Graph has been generated using 84 files:
oix-full-snapshot-2003-03-25-0000/final.graph
oix-full-snapshot-2003-03-25-0200/final.graph
oix-full-snapshot-2003-03-25-0400/final.graph
oix-full-snapshot-2003-03-25-0600/final.graph
oix-full-snapshot-2003-03-25-0800/final.graph
oix-full-snapshot-2003-03-25-1000/final.graph
...
tvg> show graph nodes
15150
tvg> show graph edges
32534
tvg> show anycc nodes
Connected components are 1
1 CCs with 15150 nodes
Index of the first largest CC: 1
Index of the first smallest CC: 1
tvg> show anycc edges
Connected components are 1
1 CCs with 32534 edges
Index of the first largest CC: 1
Index of the first smallest CC: 1
tvg> show anycc index
CC 1 has 15150 nodes and 32534 edges
tvg> dump graph differences
1 --- 3 84 0 84.0 <--: 84 -->: 0 <->: 0 ---: 0
1 --- 23 84 0 84.0 <--: 84 -->: 0 <->: 0 ---: 0
1 --- 32 84 0 84.0 <--: 84 -->: 0 <->: 0 ---: 0
1 --- 57 84 0 84.0 <--: 84 -->: 0 <->: 0 ---: 0
1 --- 63 84 0 84.0 <--: 84 -->: 0 <->: 0 ---: 0
1 --- 70 84 0 84.0 <--: 84 -->: 0 <->: 0 ---: 0
1 --- 71 84 0 84.0 <--: 0 -->: 84 <->: 0 ---: 0
1 --- 90 84 0 84.0 <--: 84 -->: 0 <->: 0 ---: 0
1 --- 103 84 0 84.0 <--: 84 -->: 0 <->: 0 ---: 0
...
tvg> show graph differences attendances
303 edges appeared in 1 graphs
113 edges appeared in 2 graphs
72 edges appeared in 3 graphs
57 edges appeared in 4 graphs
45 edges appeared in 5 graphs
31 edges appeared in 6 graphs
31 edges appeared in 7 graphs
34 edges appeared in 8 graphs
24 edges appeared in 9 graphs
28 edges appeared in 10 graphs
37 edges appeared in 11 graphs
15 edges appeared in 12 graphs
13 edges appeared in 13 graphs
...