Dimitri Papadimitriou, Davide Careglio, Fabien Tarissan and Piet Demeester
Proceedings of the the 9th International Conference on Design of Reliable Communication Networks (DRCN), Budapest, Hungary, 2013
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
International Journal of Computer Networks & Communications (IJCNC), May 2012, Volume 4. Number 3
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
Atelier EGC 2011 Visualisation et Extraction de Connaissances, Brest, France, Janvier 2011.
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.
Matthieu Latapy, Clémence Magnien and Frédéric Ouédraogo
Complex Systems, 20 (1), 23-30, 2011.
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.
Thomas Aynaud and Jean-Loup Guillaume
Latin-American Workshop on Dynamic Networks (LAWDN), Buenos Aires, 2010
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
in Complex Networks, special issue of Computer Communications, 34-5, pp. 635-648 (2011), DOI: 10.1016/j.comcom.2010.06.006
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.
Frédéric Ouédraogo, Clémence Magnien
Computer Communications, 34, 670-679, 2011
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.
Assia Hamzaoui, Matthieu Latapy and Clémence Magnien
Proceedings of International Workshop on Dynamic Networks (WDN), in conjunction with WiOpt 2010
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
Proceedings of the third International Workshop on Network Science for Communication Networks (NetSciCom 2010), In conjunction with IEEE Infocom 2010.
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.
Guillaume Valadon, Clémence Magnien and Ryuji Wakikawa
Computer Communications, 32, 2009
The Mobile IPv6 protocol is a major solution to supply mobility services on the Internet. Many networking vendors have already implemented it in their operating systems and equipments. Moreover, it was recently selected to provide permanent IP addresses to end users of WiMAX and 3GPP2. Mobile IPv6 relies on a specific router called the home agent that hides location changes of the mobile nodes from the rest of the Internet. To do so, the mobile nodes’ traffic must flow through the home agent. This mandatory deviation produces longer paths and higher communication delays.
In order to solve these problems, we describe a new approach to address deployments of Mobile IPv6 based on graph theory and could be applied to any operator’s network. In particular, we use notions of centrality in graphs to quantify increases of communication distances induced by dogleg routing and identify relevant home agents locations. We evaluate this approach using real-world network topologies and show that the obtained Mobile IPv6 performance could be close to direct paths ones. The proposed algorithm is generic and can be used to achieve efficient deployments of Mobile IPv6 as well as Home Agent Migration: a new Mobile IPv6 architecture using several distributed home agents.
Clémence Magnien, Frédéric Ouedraogo, Guillaume Valadon, Matthieu Latapy
Fourth International Conference on Internet Monitoring and Protection (ICIMP 2009), May 24-28, 2009, Venice, Italy
By focusing on what can be observed by running traceroute-like measurements at a high frequency from a single monitor to a fixed destination set, we show that the observed view of the topology is constantly evolving at a pace much higher than expected. Repeated measurements discover new IP addresses at a constant rate, for long period of times (up to several months). In order to provide explanations, we study this phenomenon both at the IP, and at the Autonomous System levels.
We show that this renewal of IP addresses is partially caused by a BGP routing dynamics, altering paths between existing ASes. Furthermore, we conjecture that an intra AS
routing dynamics is another cause of this phenomenon.