TORQUE is an abbreviation for Type Of Relationship Quality Evaluation toolkit. This is a set of four tools that allow you to compare graphs of Autonomous Systems whose edges are labelled (oriented) according to commercial relationships existing between them. This kind of comparisons is particularly useful when such relationships are obtained by means of an inference algorithm, because you can use the tools in order to validate the results of the algorithm itself. For more information about the need to use inference algorithms in order to discover relationships, read the About the commercial relationships section further on.
These tools form a little test environment in which you can perform various kinds of analysis. Typically, one should run an inference algorithm on some routing data, then build an Autonomous System graph including such information, and use the various modules of the TORQUE toolkit to compare the results of the execution of that algorithm on different data sets. The diagram below shows the typical sequence in which the tools should be used.
|Typical usage of the TORQUE environment|
First of all, the path extractor (whose name is tpathExtract) is used
in order to process a BGP table dump (resulting from the execution of the
show ip bgp command on a telnet looking glass server) and produce a plain
list of AS paths (which is usually the kind of input required by inference
algorithms). Then, such list is provided as input to an arbitrary inference
algorithm, whose typical output is an orientation for the graph of Autonomous
Systems that represents the commercial relationships they establish. Such
orientation, together with other information gained from the BGP dump and the
AS path list, is used to generate a graph (the tool that does this is
tmakeGraph) that includes all these data (by using opportune weights on
the edges), and that is called labelled because its edges are weighted
this way and directed in a manner that reflects the commercial relationships. Such
process can be iterated an arbitrary number of times, even using different inference
algorithms (this fact is underlined by the different colors used for the rounded
dashed boxes). For each run, a labelled graph is generated.
Once you have generated all the graphs that you need (which, for example, can derive from BGP table snapshots considered at different time instants), you can compare them by using the tdiffGraph tool, that can either consider couple of graphs for making strict comparisons or an arbitrary number of graphs, in which case a "history" of the directions of the edges is built.
Finally, all the generated graphs can be explored by using the tviewGraph tool, which also allows to compute distributions concerning the stability of the edges' orientations, the size of the (strongly) connected components and so on.
The blue boxes in the picture above represent the modules of the TORQUE toolkit.
The TORQUE toolkit can also be compiled as a library, for including basic graph support into your software. For more information, please read the documentation that comes with the TORQUE source package.
The following links bring you to the download section and to the documentation page of the TORQUE toolkit.
The problem of knowing the commercial relationships between Autonomous Systems has recently arisen because of its great interest in understanding many of the dynamics that control the evolution and behaviour of the Internet. In order to have a quick insight about this, just consider how useful it would be for a new ISP to know which surrounding providers is better to connect to, which can be decided on the basis of the connectivity level they can offer (which, in turn, can be deducted from the commercial relationships they established).
The most simple approach for learning which the relationships are would be to directly ask each ISP to provide them, but this, beyond to being too complicated, is also impossible, because most of them do not agree to supply such information to anyone. So, the next possible solution is to consider that, most of the times, each commercial relationship corresponds to a particular configuration of the routers involved in it, and this means that one could look at information stored in the Internet Registries to find out how each AS is configured. Unfortunately, even this is not possible, because not all the ASs publish their routing policies inside the registries (and, indeed, very few do this).
So, the most recently adopted approach is to just use BGP routing information (mostly AS paths inside the BGP tables) in order to infer what the relationships can be. For more information about how to do this, and which are the main algorithms that have been used up to now, you can start visiting the following web pages: