K.U.Leuven - Departement toegepaste economische wetenschappen
DTEW Research Report 0550 pages:1-39
The topology of the Internet has initially been modelled as an undirected graph, where vertices correspond to so-called Autonomous Systems (ASs),and edges correspond to physical links between pairs of ASs. However, in order to capture the impact of routing policies, it has recently become apparent that one needs to classify the edges according to the existing economic relationships (customer-provider, peer-to-peer or siblings) between the ASs. This leads to a directed graph model in which traffic can be sent
only along so-called valley-free paths. Four different algorithms have been proposed in the literature for inferring AS relationships using publicly available
data from routing tables. We investigate the differences in the graph models produced by these algorithms, focussing on connectivity measures.
To this aim, we compute the maximum number of vertex-disjoint valley-free paths between ASs as well as the size of a minimum cut separating a pair of ASs. Although these problems are solvable in polynomial time for ordinary
graphs, they are NP-hard in our setting. We formulate the two problems as integer programs, and we propose a number of exact algorithms for solving them. For the problem of finding the maximum number of vertex-disjoint paths, we discuss two algorithms; the first one is a branch-and-price algorithm based on the IP formulation, and the second algorithm is a non LP based branch-and-bound algorithm. For the problem of finding minimum cuts we use a branch-and-cut algo rithm, based on the IP formulation of this problem. Using these algorithms, we obtain exact solutions for both
problems in reasonable time. It turns out that there is a large gap in terms
of the connectivity measures between the undirected and directed models.
This finding supports our conclusion that economic relationships need to be
taken into account when building a topology of the Internet.