The Internet has recently been object of several studies concerning its structural properties and the behavior of routing protocols. One of the most interesting challenges is the inference of commercial relationships between Autonomous Systems. This knowledge would provide a deeper insight into the laws governing routing processes, and would constitute a useful guideline for choosing connection strategies and device configurations. Several algorithms have been proposed for inferring the relationships on the basis of the routing data of the Border Gateway Protocol (BGP). This work aims at performing an analysis of the results produced by state-of-the-art algorithms, with the purpose of investigating the meaningfulness of such results. This is achieved by running the algorithms extensively on several BGP data sets and by observing how assigned relationships change. Two kinds of analysis are used for doing this: one considers the relationships assigned by the same algorithm on data sets relative to different time instants; the second takes into account the relationships assigned by different algorithms on the same data set. We a methodology and implement some tools for performing the two kinds of analysis and apply the methodology to two well known algorithms, using publicly available data sets. What comes out is that the number of AS pairs whose relationship is steadily assigned never falls below 94% of the overall pairs, and that the solutions computed by the two algorithms overlap for more than 90% of the pairs. This is an evidence of the fact that the inference is well-founded, i.e., it is not heavily influenced by routing oscillations, and that following different approaches almost yields the same solution, which further validates its trustworthiness. -

Rimondini, M., Pizzonia, M., DI BATTISTA, G., Patrignani, M. (2004). Algorithms for the Inference of the Commercial Relationships between Autonomous Systems: Results Analysis and Model Validation. In IPS 2004, Inter-Domain Performance and Simulation, 22-23 March, Budapest, Hungary (pp.33-45). BUDAPEST : Budapest University of Technology and Economics.

Algorithms for the Inference of the Commercial Relationships between Autonomous Systems: Results Analysis and Model Validation

RIMONDINI, Massimo;PIZZONIA, MAURIZIO;DI BATTISTA, Giuseppe;PATRIGNANI, Maurizio
2004-01-01

Abstract

The Internet has recently been object of several studies concerning its structural properties and the behavior of routing protocols. One of the most interesting challenges is the inference of commercial relationships between Autonomous Systems. This knowledge would provide a deeper insight into the laws governing routing processes, and would constitute a useful guideline for choosing connection strategies and device configurations. Several algorithms have been proposed for inferring the relationships on the basis of the routing data of the Border Gateway Protocol (BGP). This work aims at performing an analysis of the results produced by state-of-the-art algorithms, with the purpose of investigating the meaningfulness of such results. This is achieved by running the algorithms extensively on several BGP data sets and by observing how assigned relationships change. Two kinds of analysis are used for doing this: one considers the relationships assigned by the same algorithm on data sets relative to different time instants; the second takes into account the relationships assigned by different algorithms on the same data set. We a methodology and implement some tools for performing the two kinds of analysis and apply the methodology to two well known algorithms, using publicly available data sets. What comes out is that the number of AS pairs whose relationship is steadily assigned never falls below 94% of the overall pairs, and that the solutions computed by the two algorithms overlap for more than 90% of the pairs. This is an evidence of the fact that the inference is well-founded, i.e., it is not heavily influenced by routing oscillations, and that following different approaches almost yields the same solution, which further validates its trustworthiness. -
2004
963-421-592-0
Rimondini, M., Pizzonia, M., DI BATTISTA, G., Patrignani, M. (2004). Algorithms for the Inference of the Commercial Relationships between Autonomous Systems: Results Analysis and Model Validation. In IPS 2004, Inter-Domain Performance and Simulation, 22-23 March, Budapest, Hungary (pp.33-45). BUDAPEST : Budapest University of Technology and Economics.
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/170879
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact