We investigate the problem of computing the types of the relationships between Internet Autonomous Systems. We refer to the model introduced by Gao [IEEE/ACM TRANSACTIONS ON NETWORKING, 9(6):733–645, 2001] and Subramanian et al. (IEEE Infocom, 2002) that bases the discovery of such relationships on the analysis of the AS paths extracted from the BGP routing tables. 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 approximation algorithms and heuristics based on a novel paradigm and show their effectiveness against publicly available data sets. The experiments provide evidence that our algorithms perform significantly better than state-of-the-art heuristics. -

DI BATTISTA, G., Thomas, E., Alexander, H., Patrignani, M., Pizzonia, M., Thomas, S. (2007). Computing the Types of the Relationships between Autonomous Systems. IEEE-ACM TRANSACTIONS ON NETWORKING, 15, 267-280 [10.1109/TNET.2007.892878].

Computing the Types of the Relationships between Autonomous Systems

DI BATTISTA, Giuseppe;PATRIGNANI, Maurizio;PIZZONIA, MAURIZIO;
2007-01-01

Abstract

We investigate the problem of computing the types of the relationships between Internet Autonomous Systems. We refer to the model introduced by Gao [IEEE/ACM TRANSACTIONS ON NETWORKING, 9(6):733–645, 2001] and Subramanian et al. (IEEE Infocom, 2002) that bases the discovery of such relationships on the analysis of the AS paths extracted from the BGP routing tables. 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 approximation algorithms and heuristics based on a novel paradigm and show their effectiveness against publicly available data sets. The experiments provide evidence that our algorithms perform significantly better than state-of-the-art heuristics. -
2007
DI BATTISTA, G., Thomas, E., Alexander, H., Patrignani, M., Pizzonia, M., Thomas, S. (2007). Computing the Types of the Relationships between Autonomous Systems. IEEE-ACM TRANSACTIONS ON NETWORKING, 15, 267-280 [10.1109/TNET.2007.892878].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/119909
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 57
  • ???jsp.display-item.citation.isi??? 32
social impact