Classical measures of network connectivity are the number of disjoint paths between a pair of nodes and the size of aminimum 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 restric-tions 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 theadaptation of the classical connectivity measures to the valley-free path model, where it is NP-hard to compute them. Ourfirst main contribution consists of presenting algorithms for the computation of disjoint paths, and minimum cuts, in thevalley-free path model. These algorithms are useful for ASs that want to evaluate different options for selecting upstreamproviders to improve the robustness of their connection to the Internet. Our second main contribution is an experimen-tal evaluation of our algorithms on four types of directed graph models of the AS-level Internet produced by differentinference algorithms. Most importantly, the evaluation shows that our algorithms are able to compute optimal solutions toinstances of realistic size of the connectivity problems in the valley-free path model in reasonable time Furthermore, ourexperimental results provide information about the characteristics of the directed graph models of the AS-level Internetproduced by different inference algorithms. It turns out that (i) we can quantify the difference between the undirectedAS-level topology and the directed graph models with respect to fundamental connectivity measures, and (ii) the differentinference algorithms yield topologies that are similar with respect to connectivity and are different with respect to the typesof paths that exist between pairs of ASs.
展开▼
