Connectivity Measures for Internet Topologies on the Level of Autonomous Systems

Thomas Erlebach (), Linda S. Moonen (), Frits C. R. Spieksma () and Danica Vukadinović ()
Additional contact information
Thomas Erlebach: Department of Computer Science, University of Leicester, Leicester LE1 7RH, United Kingdom
Linda S. Moonen: Operations Research Group, Katholieke Universiteit Leuven, 3000 Leuven, Belgium
Frits C. R. Spieksma: Operations Research Group, Katholieke Universiteit Leuven, 3000 Leuven, Belgium
Danica Vukadinović: Computer Engineering and Networks Laboratory (TIK), ETH Zürich, Switzerland

Operations Research, 2009, vol. 57, issue 4, 1006-1025

Abstract: Classical measures of network connectivity are the number of disjoint paths between a pair of nodes and the size of a minimum cut. For standard graphs, these measures can be computed efficiently using network flow techniques. However, in the Internet on the level of autonomous systems (ASs), referred to as AS-level Internet, routing policies impose restrictions on the paths that traffic can take in the network. These restrictions can be captured by the valley-free path model, which assumes a special directed graph model in which edge types represent relationships between ASs. We consider the adaptation of the classical connectivity measures to the valley-free path model, where it is (N-script)(P-script)-hard to compute them. Our first main contribution consists of presenting algorithms for the computation of disjoint paths, and minimum cuts, in the valley-free path model. These algorithms are useful for ASs that want to evaluate different options for selecting upstream providers to improve the robustness of their connection to the Internet. Our second main contribution is an experimental evaluation of our algorithms on four types of directed graph models of the AS-level Internet produced by different inference algorithms. Most importantly, the evaluation shows that our algorithms are able to compute optimal solutions to instances of realistic size of the connectivity problems in the valley-free path model in reasonable time. Furthermore, our experimental results provide information about the characteristics of the directed graph models of the AS-level Internet produced by different inference algorithms. It turns out that (i) we can quantify the difference between the undirected AS-level topology and the directed graph models with respect to fundamental connectivity measures, and (ii) the different inference algorithms yield topologies that are similar with respect to connectivity and are different with respect to the types of paths that exist between pairs of ASs.

Keywords: networks; computer network modeling; integer programming; analysis of algorithms (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0677 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:57:y:2009:i:4:p:1006-1025

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().