Dimitri Papadimitriou, Davide Careglio, Fabien Tarissan and Piet
Analysis of real datasets to characterize the local
stability properties of the Internet routing paths suggests that
extending the route selection criteria to account for such
property would not increase the routing path length.
Nevertheless, even if selecting a more stable routing path could
be considered as valuable from a routing perspective, it does not
necessarily imply that the associated forwarding path would be
more stable. Hence, if the dynamics of the Internet routing and
forwarding system show different properties, then one can not
straightforwardly derive the one from the other. If this
assumption is verified, then the relationship between the stability
of the forwarding path (followed by the traffic) and the
corresponding routing path as selected by the path-vector routing
algorithm requires further characterization. For this purpose, we
locally relate, i.e., at the router level, the stability properties of
routing path with the corresponding forwarding path. The
proposed stability model and measurement results verify this
assumption and show that, although the main cause of instability
results from the forwarding plane, a second order effect relates
forwarding and routing path instability events. This observation
provides the first indication that differential stability can safely
be taken into account as part of the route selection process.
Xiaomin Wang, Matthieu Latapy, Michèle Soria
The degree distribution of the Internet topology is considered as one of its main properties. However, it is only known through a measurement procedure which gives a biased estimate. This measurement may in first approximation be modeled by a BFS (Breadth-First Search) tree. We explore here our ability to infer the type (Poisson or power-law) of the degree distribution from such a limited knowledge. We design procedures which estimate the degree distribution of a graph from a BFS of it, and show experimentally (on models and real-world data) that this approach succeeds in making the difference between Poisson and power-law degree distributions.
Bénédicte Le Grand et Matthieu Latapy
L’objectif des travaux présentés dans ce papier est de faciliter la détection visuelle d’événements dans des réseaux d’interaction dynamiques de grande taille.
Deux méthodes de visualisation classiques et «exhaustives» ont été étudiées, qui repré-sentent l’évolution des liens du réseau au fil du temps. Les limites liées au facteur d’échelle nous ont conduits à proposer deux métaphores restreintes au suivi des noeuds du réseau. Les forces, les limites et la complémentarité de ces quatre métaphores nous ont permis de déga-ger une ébauche de méthodologie de détection d’événements dans la dynamique de grands réseaux d’interaction.
Les visualisations et la méthodologie présentées dans cet article sont génériques et appli-cables à tout type de noeuds et de liens ; elles sont ici appliquées pour illustration à un sous-ensemble du réseau Internet.
Posted in Papers Also tagged radar, visualization
Matthieu Latapy, Clémence Magnien and Frédéric Ouédraogo
Mapping the internet's topology is a challenge in itself, and studying its dynamics is even more difficult. Achieving this would however provide key information on the nature of the internet, crucial for modeling and simulation. Moreover, detecting anomalies in this dynamics is a key issue for security. We introduce here a new measurement approach which makes it possible to capture internet dynamics at a scale of a few minutes in a radar-like manner. By conducting and analyzing large-scale measurements of this kind, we rigorously and automatically detect events in the observed dynamics, which is totally out of reach of previous approaches.
Posted in Papers Also tagged measurement, radar
Thomas Aynaud and Jean-Loup Guillaume
Complex networks can usually be divided in dense subnetworks called communities. In evolving networks, the usual way to detect communities is to find several partitions independently, one for each time step.
However, this generally causes troubles when trying to track communities from one time step to the next. We propose here a new method to detect only one decomposition in communities that is good for (almost) every time step. We show that this unique partition can be computed with a modification of the Louvain method and that the loss of quality at each time step is generally low despite the constraint of global maximization. We also show that some specific modifications of the networks topology can be identified using this unique partition in the case of the Internet topology.
Christophe Crespelle and Fabien Tarissan
Many contributions rely on the degree distribution of the Internet topology. However, current knowledge of this property is based on biased and erroneous measurements and is subject to much debate. Recently, a new approach, referred to as the Neighborhood Flooding method, was proposed to avoid issues raised by classical measurements. It aims at measuring the neighborhood of Internet core routers by sending traceroute probes from many monitors distributed in the Internet towards a given target router. In this paper, we investigate the accuracy of this method with simulations. Our results show that Neighborhood Flooding is free from the bias highlighted in the classical approach and is able to observe properly the exact degree of a vast majority of nodes in the core of the network. We show how the quality of the estimation depends on the number of monitors used and we carefully examine the influence of parameters of the simulations on our results. We also point out some limitations of the Neighborhood Flooding method and discuss their impact on the observed distribution.
Posted in Papers Also tagged Metrology
Frédéric Ouédraogo, Clémence Magnien
Maps of the internet topology are generally obtained by measuring the
routes from a given set of sources to a given set of destinations
(with tools such as traceroute). It has been shown that this
approach misses some links and nodes. Worse, in some cases it can
induce a bias in the obtained data, i.e. the properties of
the obtained maps are significantly different from those of the real
topology. In order to reduce this bias, the general approach
consists in increasing the number of sources. Some works have
studied the relevance of this approach. Most of them have used
theoretical results, or simulations on network models. Some papers
have used real data obtained from actual measurement
evaluate the importance of the number of sources and
destinations, but no work to our knowledge has studied extensively
the importance of the choice of sources or destinations.
Here, we use real data from internet topology measurements to study this question: by comparing partial measurements to
our complete data, we can evaluate the impact of adding sources or
destinations on the observed properties.
We show that the number of sources and destinations used plays a
role in the observed properties, but that their choice, and not only
their number, also has a strong influence on the observations. We
then study common statistics used to describe the internet topology,
and show that they behave differently: some can be trusted once the
number of sources and destinations are not too small, while others
are difficult to evaluate.
Posted in Papers Also tagged Metrology, radar
Assia Hamzaoui, Matthieu Latapy and Clémence Magnien
Detecting events such as major routing changes or congestions in the dynamics of the internet topology is an important but challenging task. We explore here a top-down approach based on a notion of statistically significant events. It consists in identifying statistics which exhibit a homogeneous distribution with outliers, which correspond to events.
We apply this approach to ego-centerd measurements of the internet topology (views obtained from a single monitor) and show that it succeeds in detecting meaningful events.
Finally, we give some hints for the interpretation of such events in terms of network events.
Christophe Crespelle, Matthieu Latapy, Elie Rotenberg
Many contributions use the degree distribution of IP-level internet topology. However, current knowledge of this property relies on biased and erroneous measurements, and so it is subject to much debate. We introduce here a new approach, dedicated to the core of the internet, which avoids the issues raised by classical measurements. It is based on the measurement of IP-level neighborhood of internet core routers, for which we design and implement a rigorous method. It consists in sending traceroute probes from many monitors distributed in the internet towards a given target router and carefully selecting the relevant information in collected data. Using simulations, we provide strong evidence of the accuracy of our approach. We then conduct real-world measurements illustrating the practical effectiveness of our method. This constitutes a significant step towards reliable knowledge of the IP-level degree distribution of the core of the internet.
Posted in Papers Also tagged Metrology
> By Elie Rotenberg, Christophe Crespelle and Matthieu Latapy Here, we aim at measuring the IP-level neighborhood of internet core routers in a rigorous way. We proceed as follows. First, we send traceroute probes from many monitors distributed in the internet towards a given target router. Then we consider the last but one IP adress […]
Posted in Plots Also tagged Metrology