Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, piano secondo
Aula C2

Abstract:
The analysis of data extracted from the Internet poses new challenges to the research community. Here we investigate the problem of determining the types of the relationships between Internet Autonomous Systems. An Autonomous System (AS) is a portion of the Internet under a single administrative authority, using the Border Gateway Protocol (BGP) to exchange routing information with adjacent ASes and thus contributing to the IP traffic delivery. We follow the approach introduced in [Gao 2001], which uses BGP routing information to infer the Autonomous System relationships. Such approach is based on the observation that each AS-path (sequence of ASes that must be traversed in order to reach a destination) contained in a BGP routing table must be "valley free", that is, without a provider-customer link followed by a customer-provider one. In [Subramanian et al. 2002] the problem of determining the relationship of each pair of adjacent ASes while maximizing the number of valley-free AS-paths was formally introduced and left open. We characterize the time complexity of the above problem, showing both NP-completeness results and efficient algorithms for solving specific cases. Motivated by the hardness of the general problem, we propose heuristics based on a novel paradigm and show their effectiveness against publicly available data sets. The experiments put in evidence that our heuristics performs significantly better than state of the art heuristics.