concl.tex
\section{Conclusion}

In this work we conducted periodic measurements of  ego-centered views of the Internet topology
and studied their dynamics.
We isolated  invariant characteristics of these dynamics,
and identified load balancing and evolution of the routing topology as key factors in the observed properties.

Based on this observation, we proposed a model for the dynamics of the topology,
which integrates both load balancing and routing changes.
Simulations show that this model captures the main characteristics of the dynamics of the ego-centered views.

Our model is based on simple mechanisms, both for the topology generation and the characteristics of route dynamics.
It is therefore not suitable for generating realistic time-evolving topologies.
However, the fact that it captures the main characteristics of the observed ego-centered views
shows that the factors it mimics play a strong role in the Internet routing topology dynamics,
which offers key insight on the understanding  of these dynamics.
We therefore consider this model as a key step towards the realistic modeling of the Internet topology dynamics,
as well as towards its understanding.

\medskip

Future work lies in two main directions.
First, the field of Internet topology modeling is very active,
and models far more realistic than random graphs are available.
One should explore the combination of our routing mechanisms principles with
these topology models, 
to investigate the role played by the topology structure on the observed dynamics.
%and if the observations are better with more accurate graph models.
In particular, our model does not take into account the long term topology evolution,
since it does not model node birth or death.
Coupling the ingredients of our routing dynamics with, e.g., a growing model for the
Internet topology which would reflect its long term dynamics would surely lead to insightful results.

Second,
since it is based on random graphs and simple mechanics for load balancing and routing dynamics,
our model lends itself well to formal analysis.
Obtaining analytical results for the empirical observations we made 
would be an important step towards quantifying formally
the role played by the different factors in the Internet topology dynamics.


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "paper"
%%% End: 

data.tex
%%%%%%%%%%%%FIGURE%%%%%%%%%%%%%%%%%
%\begin{figure*}[!t]
%	\centering
%	\epsfig{file=/Users/ameliemedem/Documents/Post-doc/Plot_figure/Drawings/graph-serie-creationprocess,width=3cm, angle=90} 
%	\caption{Simulation process.}
%	\label{fig:total_ips_perdistance_real}
%\end{figure*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Approach and data} 

To analyze the dynamics of the Internet, we use different snapshots of
the network around a single node at successive time. Each snapshot
represents a routing tree and the data are collected with
\tracetree{} and \emph{radar} available at~\cite{radar:08}.
\tracetree{} is an active measurement tool that discovers a path
between two network nodes~\cite {latapy-radar:2008}. A
\tracetree{} measurement between a single \emph{monitor} node and
a set of \emph{destination} nodes gives a tree of routing paths with
the monitor as the root and the destinations as the leaves. The
routing tree represents an \emph{ego-centered} view of the network
around the monitor. It is composed of all routing paths discovers
between the monitor and all the destinations.

Using the tool \emph{radar}, each \tracetree{} measurement were
iterated many times from the same monitor to the same set of
destinations~\cite{latapy-radar:2008}. One measurement round lasts
about $10$ $min$ and the frequency between a pair of rounds is about
$5$ $min$. Each iteration output is a routing
tree. In~\cite{latapy-radar:2008}, data are available for around $150$
monitors.  

We use here two datasets, which were obtained with different measurement parameters.
The \wdata{} was measured from the Pierre and Marie Curie University in Paris.
{\bf Parameters}.
It started in {\bf May. 21, 2007} and ended in {\bf Jul. 11, 2007}, which represents a total of {\bf 4993} rounds.

The \ovhdata{} was measured from a French hosting company.
{\bf Parameters, dates, number of rounds...}


%Mon, 21 May 2007 12:23:41 GMT
%Wed, 11 Jul 2007 10:30:41 GMT
%for Sep. 19, 2006 to Apr. 16, 2007 for the \vpn{} and Aug. 8, 2004 to Apr. 6, 2007 for Internet2~\cite{abilene:tt}.

%realizes periodic \emph{tracetree}  from the same monitor to a fixed set of destinations~\cite{latapy-radar:2008}. E

% It is inspired by \emph{traceroute} but uses a backward process for path discovering with less redundancy. This highly reduces the overload of measurement data. 

%We use data collected with \emph{tracetree} and available at~\cite{radardata}.  The  \emph{tracetree} tool aims at discovering a routing path between two nodes in the network~\cite{LatapyClemence:2008}. A \emph{tracetree} measurement between a single monitor node and a set of destination nodes gives a tree of routing paths with the monitor as the root and the destinations as the leaves of the tree. The routing tree represents an \emph{ego-centered} view of the network around the monitor. In~\cite{radardata}, data are available for around $150$ monitors. Each \emph{tracetree} measurement were iterated many times from the same monitor to the same set of destinations. One measurement round lasts about $10$ $min$ and the frequency between a pair of rounds is about $5$ $min$. Each iteration output is a routing tree. In this paper, we only present the results of our experiments with a single monitor ($3,000$ destinations and $5,000$ rounds). We use the large set of $5,000$ routing trees as input for our analysis of  the dynamics of Internet. % routing paths. 


% A \emph{tracetree} measurement data consists of a large set of routing trees observed from a single monitor to a fixed set of destination continuously during time. A routing tree represents an \emph{ego-centered} view of the network around the monitor. 
%
%The \emph{tracetree}~\cite{LatapyClemence:2008} tool aims at discovering a routing path between two nodes in the network. We use \emph{tracetree} to build a tree of routing paths from a single monitor toward a fixed set of destination nodes. In our work, a routing tree represents an \emph{ego-centered} view of the network around the monitor. 
%
%Ego-centered \emph{tracetree} measurement were iterated many times from one monitor to the same set of destinations. One measurement round lasts about $10$ $min$ and the frequency between a pair of rounds is about $5$ $min$. Each iteration produces a routing tree. Data are available for around $150$ monitors. In this paper, we only present the results of our experiments with a single monitor and $3000$ destinations. At the end of the measurement, we have about thousands of routing trees that we use to analyze the dynamics of Internet routing paths. 
%
%Measurements  are conducted during many months and from around $150$ monitors. Using the Radar tool for Internet topology measurement, we obtain large sets of routing trees observed from various monitors and continuously during time. 
% 
%In this paper, we only present the results of our experiments with a single monitor and $3000$ destinations. At the end of the measurement, we have about thousands of routing trees that we use to analyze the dynamics of Internet routing paths. 



%Using the radar approach to internet topology measurement (LMOradar) we obtained large sets of routing trees observed from various monitors and in continuous (frequency approximately 15 minutes) during time. We have shown several properties of the dynamics of these trees (HLMevent) in particular the stability of their number of nodes, although new nodes are continuously observed. 

%We conducted measurements from about $150$ monitors to thousands of destination nodes.  to destination set of $3000$ nodes.

%While \emph{traceroute} starts to discover the first hop until the last hop through the destination, \emph{tracetree} inversely first discover the last hop until the first hop trough the destination. This has the advantage of generating less control routing messages because we do not discover a given hop many times.

%a tool that provides an ego-centered view of the routing dynamics. Radar uses the technique \emph{tracetree}~\cite{LatapyClemence:2008} to discover the network around a single monitor. Like \emph{traceroute}, \emph{tracetree} helps to discover the path between two nodes in the network. While \emph{traceroute} starts to discover the first hop until the last hop through the destination, \emph{tracetree} inversely first discover the last hop until the first hop trough the destination. This has the advantage of generating less control routing messages because we do not discover a given hop many times.  


%utilise les donne de radar
%radar utilise la technique tracetree pour decouvrir le reseau autour dun unique monitor. 
%tracetree permet de connaitre le chemin qui exite du moniteur vers une destination
%a la difference de traceroute on lon decouvre de mani�re recursive les 1er, 2e, 3e saut jusquau dernier
%A l'inverse, tracetree decouvre le dernier, avant dernier, jusqu' permier saut
%
%A partir d'un monitoer et de 3000 destinations cibles, nous ex�cution loutil radar.
%Cela permet de decouvrir toutes les routes du moniteur au destinations


%From a source to a destination, \emph{tracetree} first discovers the last hop through the destination, t
%
% In opposition to the \emph{traceroute} tool that discovers each hop of a path from a source to a destination, from the closest to the source to the farthes trough the destination. 
%
%The method aims at discovering the network as seen from one node, and is best described by the following excerpts of (LMOradar), to which the reader is refered for more details. The tracetree tool performs ego-centered measurement, and Radar measurements consist in iterating ego-centered measurement with tracetree, fro ma monitor to a given set of destiniation.
%This part relies on data generated by Radar, a tool providing an partial and ego-centered view of the routing dynamics. It consists in monitoring the paths between one monitor and a set of (thousands of) targets and their evolution during time. Although a set of data is already available, it still requires to carefully analyse those data in order to describe the structure of ego-centered views and their dynamic properties, as well as (dynamic) properties of routes contained in them. The challenge here stands in the description and categorization of the observed dynamics. This first step will lead to identify a model enabling to generate similar data in a second step. \\

%	- What data ?
%	- How are they obtained
%	- What information we can get from that data


%\subsection{Data : \emph{Tracetree}}
%\subsection{Dynamics of Internet}
%The traceroute tool discovers a path by sending a series of probes towards the destination in a forward manner: the first probe discovers the rst link, the second probe discovers the second link, and so on. Instead, the tracetree tool discovers a tree by sending probes towards all destinations in parallel in a backward manner and avoids redundancy by stopping probing towards some destinations when paths collapse: given a set of destinations, it first discovers the last link on the path to each of them, then the previous link on each of these paths, and so on; when two (or more) paths reach the same node then it stops probing towards all corresponding destinations except one.
%
%The tracetree tool performs ego-centered measurements very efficiently, both regarding time and network load. It sends exactly one probe for each link to discover, and thus induces a perfectly balanced load. Radar measurements then consist in iterating ego-centered measurements with tracetree, from a monitor to a given set of destinations.

%Using the Radar approach to Internet topology measurement, we obtained large sets of routing trees observed from various moniors and in courinuous during time. We have already shown several properties of the dnamics of these trees in particular the stability of their numbr of nodes, alhough new nodes are continuously observed.

intro.tex

\section{Introduction}
%motivation

\noteperso{Mettre complètement au format (style biblio)}


% The Internet is a complex structure with millions of nodes and
% links. Many studies have already characterized its topology and showed
% for instance that the nodes' degree distribution follows a power
% law. However few of these studies have asked the question of how this
% topology evolves in time. Indeed, it is well known that the Internet
% is also a living organism with thousands of nodes and links added and
% removed everyday. Therefore, characterizing the Internet dynamics can
% provide interesting insights that may help in the design of future
% routing protocols or the conception of new types of applications that
% make use of its evolving topology.

Studying the structure of the Internet topology is an important and difficult
question. No official map being available, researchers have to conduct costly
measurement campaigns, and deal with the fact that the obtained data can be biased~\cite{Lakhina:2003,Achlioptas2009Bias}.
Studying the dynamics of this topology is therefore an equally hard, if not harder, problem.

%some related and problem

% In this work, we use a combination of analysis and simulation to
% understand the dynamics of the Internet. We use real data to extract
% various properties that characterize this dynamics. A challenge of the
% analysis of the Internet dynamics lies on the choice of an appropriate
% data set. We need many snapshots of the network at different times to
% understand how it changes during time.


% We use data from \emph{tracetree} measurements conducted from a single
% monitor to a large set of destinations~\cite{radardata}. Each
% measurement result is a tree of routing paths from the monitor to the
% destinations. A routing tree represents a snapshot or an
% \emph{ego-centered} view of the network around the monitor at a given
% time. Several successive measurements over time result in a collection
% of routing trees that we use to analyze the
% dynamics. %et links as a simple edge swaps.

In this paper, we use an orthogonal approach to obtain insight on the dynamics of the routing  topology
observed at the  \ip{}-level.
We study {\em ego-centered views} of this topology.
Given a monitor and a fixed set of destinations,
 one such view is obtained by measuring the routes from the monitor to the destinations.
This can be performed quickly and with low network load with the {\tracetree} tool~\cite{latapy-radar:2008}.
Repeating this measurement periodically therefore allows to study the dynamics of this view.
%  i.e. routing trees
% from a given monitor to a given set of destinations.
% These trees can be measured quickly with small network load,
% allowing to repeat their measurement periodically at a high frequency,
% thus capturing their dynamics~\cite{latapy-radar:2008}.

Previous work has shown that ego-centered views exhibit strong dynamics,
and in particular that the set of observed nodes evolves much more quickly than what was previously expected~\cite{Magnien:2009}.
%and that they evolve much more quickly than what was previously expected~\cite{Magnien:2009}.
Here, we analyze in depth this dynamics (Section~\ref{dyn-prop}),
% of the ego-centered views (Section~\ref{dyn-prop}).
and find that two factors play a key role in the observed dynamics:
load-balancing routers, and the evolution of the routing topology (Section~\ref{sec:motivation}).

Based on these observations, we propose in Section~\ref{sec:modeling} a baseline model for the routing dynamics in the Internet that incorporates routing modifications
and load balancing.
We use the most simple choices for modeling these factors, 
and show in Section~\ref{sec:results} that this model is able to accurately reproduce the behaviors observed in real data.
This shows that simple mechanisms such as the ones we take into account play a key role in the Internet routing topology dynamics,
giving a strong
explanatory value to our model.
%This model does not allow  precise and realistic simulations,
%In particular, it does not take into account the long term evolution of the topology,
%with the additions and removals of nodes.
%However, it 
%but
As such, it represents a significant first step towards the modeling of the Internet \ip{}-level  topology and its dynamics.





% %approach and goal

% Recall that our goal is to understand the observed dynamics and
% propose relevant explanations to them. The challenge here lies on the
% fact that the structure of the Internet is still unknown. Many studies
% have proposed tools and mechanisms to discover the Internet
% structure~\ref{}. However, in general these can only reveal a portion
% of this large network. Using simulation, we want to understand the
% dynamic properties of virtual graphs (biais vers Internet). Typically,
% we simulate ego-centered measurements on virtual graphs and then,
% analyze their behavior.

% It is a difficult task mainly because the real topology of the Internet, nowadays, is still unknown. Therefore, we do not have the appropriate parameters to simulate it. 

% We will find explanation of these observation on simulation.
% Our goal : find with one is part of its graph model and which is a measurement artifact.

% %plan and contribution

% By means of simulation, we investigate whether and when the Internet
% dynamics are part of its graph model. For that, we need a model of the
% Internet topology, a model of its dynamics and a model of the
% routing. As a preliminary step, we model the Internet as a random
% graph with \emph{edge-swap} dynamics and the \emph{shortest-path}
% routing. Internet are subject to changes due to maintenance works or
% unexpected events. Operators have to plan work to maintain their
% network in good shape. Besides, network are daily subject to various
% kind of disruptions that altered the equipments and therefore the
% global communication~\cite{me}(CHECK). Our results show that with
% appropriate values of the random graph parameters, we are able to
% reproduce a dynamic behavior of Internet.


%%% Local Variables:     
%%% mode: latex          
%%% TeX-master: "paper.tex"   
%%% End:   

related.tex

 %\clearpage

 %\clearpage


\section{Related work}\label{sec:relatedwork}


Study of the
dynamics of the Internet topology has been tackled both by analyzing
the dynamics of individual
routes~\cite{Paxson1997Ton,Schwartz2010Diversity,Labovitz1999Origins,medem:07}
and from a more global perspective, mainly at the {\sc as}- or 
{\sc  ip}-level~\cite{Govindan1997,chen2002origin,Oliveira2007Observing,Park2003,Pansiot2007Local}.
% Some
% work investigate the causes of route and link flapping, and find that
% they may come from unexpected failures or maintenance
% work~\cite{}.
Load balancing
has also been acknowledged for playing an important role in the dynamics of routes as measured with traceroute-like
tools~\cite{Augustin2008Traceroute}.  Cunha et
\emph{al.}~\cite{Cunha2011Measuring} used a method for measuring
load-balanced routes, i.e. routes containing one or more
load-balancing routers,
and study their dynamics.
% In the analysis of the dynamics of the whole Internet topology, much
% work have focused on the dynamics at the {\sc as}
% level~\cite{Govindan1997,chen2002origin,Oliveira2007Observing,Park2003}
% or on the dynamics of the multicast
% topology~\cite{Pansiot2007Local}. Of these works, researchers propose
% various topological properties, for example the degree distribution,
% and analyzed their variation over time~\cite{Govindan1997}. Some
% verify the connectivity process of the AS
% topology~\cite{chen2002origin}.
 Most related to our
characterization of the evolution of the Internet topology is the work
by Oliveira et \emph{al.}~\cite{Oliveira2007Observing}, which
analyzed the {\sc as} topology  and
shows that real topology dynamics can be modeled as constant-rate
birth and death of links and nodes.

%\medskip

%  Three main
% families for modeling network topology exist such as regular,
% well-known and randomly generated topologies. Much
% work usually uses them to verify some properties of Internet measured
% graphs~\cite{Medina:2000,Lakhina:2003,Jaiswal:2004} or to compare
% topology
% generators~\cite{Tangmunarunkit2002Network,Park2004Comparing}. Other
% surveys on this topic are available
% at~\cite{Tangmunarunkit2002Network,Haddadi2008Network}.

% In our work, we make use of Erd\"{o}s-R\'enyi random graphs to model
% the Internet, but with the goal of analyzing how it evolves over time.


Work on modeling the Internet topology and its dynamics can be roughly divided
between approaches aiming at reproducing global network characteristics
through simple mechanisms,
and approaches aiming at realistically mimicking the evolution mechanisms of
the topology, e.g. reproducing the criteria taken into account by ASes for creating peering or customer-provider
links~\cite{Chang2006Peer,Wang2006Wealth,Park2004Comparing}.
Tangmunarunkit et \emph{al.}~\cite{Tangmunarunkit2002Network}
found that network generators based on local properties, such
as the degree distributions of nodes, can capture global properties of
the topology, such as its hierarchical structure. This shows that simple,
non realistic mechanisms such as the ones we introduce
may be relevant for capturing important properties.


Whereas most existing works focus on the long-term evolution (i.e. from the Internet birth to current times)
of the {\em physical} AS topology,
we are concerned here with the short- to medium-term evolution of the {\em routing} topology at the \ip{}-level.
The routing and physical topology are closely linked but not identical objects.
In particular,
routing changes can occur in the absence of physical changes.
Finally, our model does not take into account
node appearance and disappearance, 
which would be necessary for modeling the  long-term topology evolution.


% Most related to ours is
% the work by Park et \emph{al.}~\cite{Park2004Comparing} which studies
% several growing models for the Internet topology, i.e. models in which
% nodes and links are progressively added over time. They compare the
% evolution of these induced networks with the evolution of the real
% topology, and use this to distinguish between the quality of the
% different models.
% \cite{Haddadi2008Modeling,Park2003} argue that the topology
% dynamics should be taken into account in order to produce realistic
% models. 



%\subsection{Analyzing the dynamics of the topology}

%Study of the dynamics of the Internet topology has been tackled both
%from studying the dynamics of individual routes and from a more global perspective,
%at the {\sc as}- or {\sc ip}-level.
%
%Load-balancing has been acknowledged for playing an important role in the observed dynamics
%of routes as measured with traceroute-like tools~\cite{Augustin2008Traceroute}.
%Various works have studied the dynamics of routes.
%
%\cite{Paxson1997Ton} studied the dynamics of routes, and quantified the stability of routes,
%\emph{i.e.} how long does a route between a given (source, destination) pair stay unchanged,
%and the route {\em prevalence}, \emph{i.e.} the existence of a preferred route between a source
%and a destination, and what fraction of time this preferred route occupies.
%Some works have since then studied route dynamics~\cite{Feamster2003Measuring,Zhang2004PlanetSeer,Schwartz2010Diversity}.
%
%\cite{Cunha2011Measuring} use a method for measuring load-balanced routes,
%\emph{i.e.} routes containing one or more load-balancing routers.
%These routes may therefore contain more than one interface per hop.
%They then study routes persistence and prevalence.
%
%\cite{Labovitz1999Origins} and \cite{iannaccone:02} focus on routing messages  (BGP, IS-IS) to analyze the causes of routes and link flapping. % Routage BGP, \'etude des causes des fluctuations des routes
%
%Italo
%
%{\bf À compléter}
%
%Some works have also studied the dynamics of the whole Internet topology. Much of them have focused on the dynamics at the AS level~\cite{Govindan1997,chen2002origin,Oliveira2007Observing} or at the multicast topology~\cite{Pansiot2007Local}. The early work of Govindan et \emph{al.}~\cite{Govindan1997} proposed various topological properties of the Internet such as the degree distribution, the diameter and the connectivity, and analyzed their variation over time. In their work, Chen et \emph{al.}~\cite{chen2002origin} show that the connectivity process of the Internet AS topology does not follow a preferential attachment model. Oliveira et \emph{al.}~\cite{Oliveira2007Observing} show that the real topology dynamics consist of a constant-rate birth process and a constant-rate death process. \cite{Park2003} analyze the dynamic susceptibility of the Internet to faults and attacks. Changements de routage : travaux d'Amélie.

%\cite{chen2002origin}: \'etude de l'attachement pr\'ef\'erentiel; AS level. Key idea: Internet might not evolve according to the BA model due to the incompleteness of the measurement data. The Internet topology at the AS level does not follow a strict power law, and so the connectivity process of the BA model.
%
%\cite{Govindan1997}: Dynamique de la topologie au niveau AS
%
%\cite{Oliveira2007Observing}: Dynamique topologie AS, biais
%
%\cite{Park2003} : Dynamique de la topologie AS
%
%Dynamics of the multicast router topology~\cite{Pansiot2007Local}: stats globales sur la topolgie
%
%Changements de routage : travaux d'Amélie



%\subsection{Modeling - routing trees / routes}
%%{\bf Checker la ref pr\'ec\'edente pour voir si \c{c}a parle de dynamique}
%
%1998 - Pansiot et~\emph{al}~\cite{Pansiot:1998} propose a characterization of multicast routing trees in terms of delay, weight, state information and traffic concentration. 
%2007 - Leguay et~\emph{al}~\cite{Leguay:2007} proposes various models for the description of Internet routes, such as route length, hop direction and degree evolution along route.



% In their work, Lakhina et \emph{al.}~\cite{Lakhina:2003} use of Erd\"{o}s-R\'enyi and power-law graphs to prove that graphs obtained through {\tt traceroute} measurements may differ, in degree distribution, from the underlying Internet graph. 
%Researchers usually use any of these topologies to verify static or dynamics properties of the Internet. 
%Medina et al.~\cite{Medina:2000} use them to study the relevance of factors, such as the preferential connectivity and the incremental growth, in causing power laws inferred on the Internet. 
%Tangmunarunkit2002Network : ...
%Lakhina et \emph{al.}~\cite{Lakhina:2003} use $ER$ and power-law random graphs to prove that graphs obtained through {\tt traceroute} measurements may differ, in degree distribution, from the underlying graph. 
%Jaiswal et \emph{al.}~\cite{Jaiswal:2004} compare the structure of power-law graphs with that of the Internet AS graph. 
%Other related work can be found on the surveys of \cite{Tangmunarunkit2002Network,Chakrabarti2006Graph,Haddadi2008Network}. 
%\cite{Tangmunarunkit2002Network} find that network generators based on simple, local properties, such as the degree distributions of nodes, can capture global, important properties of the topology, such as its hierarchical structure. This shows that a bottom-up approach such as ours is relevant.
%{\bf Checker le type de modèle qu'ils utilisent pour les degrés}. %RAndom generators (Waxman)/Structural (Transit-stub,Tiers)/degree-based generator (Power law)
%Waxman extend ER graph, Transit-stub and Tiers with structural generatos


%{\bf Est-ce qu'il y a des modèles qui font la supposition qu'il y a des disparitions de nœuds/de liens~?}




%\subsection{Modeling - global topology}
%
%Different propositions exist in the literature for modeling the global topology of the Internet. 
%
%1997 - Paxson et~\cite{Paxson:1997} discuss keys strategies for meaningful simulation of the Internet in the face of difficulties such as the heterogeneity of links or the heterogeneity of various protocols and applications.  
%
%1997 - Zegura at al.~\cite{Zegura:1997} realize a quantitative comparison of various methods for generating graphs to model Internet topology. They distinguish three main families of network modeling, namely regular topologies, well-known topologies and randomly generated topologies. Well-known and regular topologie reflect only parts of current or past real networks; random topologies may not reflect any real network. Three classes of graph generation methods : flat random, regular and hierarchical. 
%
%
%2000 - Medina et al.~\cite{Medina:2000} propose some causes to these observed power laws (ask the question wether the powar laws come from the ways Internet grows). They consider fours factors in the formation of Internet topologies: preferential connectivity of a new node to existing nodes, incremental growth of the network; geographical distributions of nodes and locality of edge connections. In synthetically generated network topologies (BRITE, random topologies, Transit-Stub and regular grid), they study the relevance of each factor in causing power laws. 
%
%Suggest preferential connectivity and incremental growth to be possible causes of some power laws, with node placement (the way nodes are distributed in space) and connection locality (new nodes connect to existing nodes that are close-by in distance). The rank and outdegree power laws are the most effective in distinguishing different kinds of topologies. In respect to rank and outdegree power laws, random and Transit-Stub topologies are not representative of Internet topologies.

%2002 - Chen et al~\cite{Chen:2002} \\


%Surveys: \cite{Chakrabarti2006Graph,Tangmunarunkit2002Network,Haddadi2008Network}.
%
%
%\cite{Tangmunarunkit2002Network} find that network generators based on simple, local properties,
%such as the degree distributions of nodes,
%can capture global, important properties of the topology,
%such as its hierarchical structure.
%This shows that a bottom-up approach such as ours is relevant.
%
%{\bf Checker le type de modèle qu'ils utilisent pour les degrés}.
%

%\subsection{Topologie evolution model}
%R. Albert and A.-L. Barabasi. Topology of evolving networks: local
%events and universality. Physical Review Letters, 85(24):5234�5237,
%2000.
%H. Chang, S. Jamin, and W. Willinger. Internet connectivity at the
%AS-level: an optimization-driven modeling approach. In Proc ACM
%SIGCOMM MoMeTools workshop, 2003.
%H. Chang, S. Jamin, and W. Willinger. To peer or not to peer:
%modeling the evolution of the Internet�s AS-level topology. In Proc.
%of IEEE INFOCOM, 2006.
%X. Wang and D. Loguinov. Wealth-based evolution model for the
%Internet AS-level topology. In Proc. of IEEE INFOCOM, 2006.


%\subsection{Modeling - Dynamics}
%
%\cite{Haddadi2008Modeling,Park2003} argues that the the topology dynamics should be taken into account 
%in order to produce realistinc models.
%
%\cite{Park2004Comparing} studies several growing models for the Internet topology,
%\emph{i.e.} models in which nodes and links are progressively added over time.
%They compare the evolution of these induced networks with the evolution of the real topology,
%and use this to distinguish between the quality of the different models.
%However, none of these models takes into account the process of link death which we include in our model.
%
%{\bf Est-ce qu'il y a des modèles qui font la supposition qu'il y a des disparitions de nœuds/de liens~?}

%The previous section provides a set of statistical tools to capture some non-trivial properties of routes in the Internet. The statistics on route lengths and hop directions are sufficient to demonstrate that the shortest path model is inadequate for generating realistic simulated routes on a graph of the Internet. The statistics on node degree evolution provide another measure of what realistic routes should look like. We now propose three simple models (only two of which we eventually retain) designed to capture these features.

%Our approach is as follows: we design a model as simple as possible which focuses on one of the properties of interest, and then we use the other statistics to evaluate the model (in the next section). This ensures that the models stay very simple, and this makes it possible to study the relations between the observed properties: are they independent or on the contrary can some of them be seen as consequences of others?


paper.bbl
\begin{thebibliography}{10}

\bibitem{Lakhina:2003}
A.~Lakhina, J.~Byers, M.~Crovella, and P.~Xie, ``Sampling biases in {I}{P}
  topology measurements,'' in {\em INFOCOM 2003. Twenty-Second Annual Joint
  Conference of the IEEE Computer and Communications. IEEE Societies}, vol.~1,
  pp.~332 -- 341 vol.1, 2003.

\bibitem{Achlioptas2009Bias}
D.~Achlioptas, A.~Clauset, D.~Kempe, and C.~Moore, ``On the bias of traceroute
  sampling,'' {\em Journal of the ACM}, vol.~56, no.~4, 2009.

\bibitem{latapy-radar:2008}
M.~Latapy, C.~Magnien, and F.~Ou{\'e}draogo, ``A radar for the internet,'' {\em
  Complex Systems}, vol.~20, no.~1, pp.~23--30, 2011.

\bibitem{Magnien:2009}
C.~Magnien, F.~Ouedraogo, G.~Valadon, and M.~Latapy, ``Fast dynamics in
  internet topology: Observations and first explanations,'' in {\em Proceedings
  of the Fourth IEEEE International Conference on Internet Monitoring and
  Protection}, pp.~137--142, 2009.

\bibitem{Xia2005Flooding}
J.~Xia, L.~Gao, and T.~Fei, ``Flooding attacks by exploiting persistent
  forwarding loops,'' in {\em Proceedings of the ACM SIGCOMM Internet
  Measurement Conference}, 2005.

\bibitem{radardata}
``{A Radar for the Internet -- Publicly available datasets}.''
  \texttt{http://data.complexnetworks.fr/Radar/}.

\bibitem{Augustin2008Traceroute}
B.~Augustin, X.~Cuvellier, B.~Orgogozo, F.~Viger, T.~Friedman, M.~Latapy,
  C.~Magnien, and R.~Teixeira, ``{Traceroute Anomalies: Detection and
  Prevention in Internet Graphs},'' {\em Computer Networks}, vol.~52,
  pp.~998--1018, 2008.

\bibitem{Cunha2011Measuring}
I.~Cunha, R.~Teixeira, and C.~Diot, ``{Measuring and Characterizing End-to-End
  Route Dynamics in the Presence of Load Balancing},'' in {\em Proceedings of
  Passive and Active Measurement Conference}, 2011.

\bibitem{Erdoreni:1959}
P.~Erd\"{o}s and A.~R\'{e}nyi, ``{On random graphs, I},'' {\em Publicationes
  Mathematicae (Debrecen)}, vol.~6, pp.~290--297, 1959.

\bibitem{Paxson1997Ton}
V.~Paxson, ``{End-to-end routing behavior in the Internet},'' {\em IEEE/ACM
  Transactions on Networking}, vol.~5, no.~5, pp.~601--615, 1997.

\bibitem{Schwartz2010Diversity}
Y.~Schwartz, Y.~Shavitt, and U.~Weinsberg, ``{On the Diversity, Stability and
  Symmetry of End-to-End Internet Routes},'' in {\em Proceedings of Global
  Internet}, 2010.

\bibitem{Labovitz1999Origins}
C.~Labovitz, G.~Malan, and F.~Jahanian, ``{Origins of Internet routing
  instability},'' in {\em Proceedings of IEEE INFOCOM '99}, pp.~218--226 vol.1,
  1999.

\bibitem{medem:07}
A.~M. Kuatse, R.~Teixeira, and M.~Meulle, ``Characterizing network events and
  their impact on routing,'' in {\em CoNEXT '07: Proceedings of the 2007 ACM
  CoNEXT conference}, pp.~1--2, 2007.

\bibitem{Govindan1997}
R.~Govindan and A.~Reddy, ``{An Analysis of Internet Inter-Domain Topology and
  Route Stability},'' in {\em Proceedings of IEEEE INFOCOM}, 1997.

\bibitem{chen2002origin}
Q.~Chen, H.~Chang, R.~Govindan, S.~Jamin, S.~Shenker, and W.~Willinger, ``{The
  Origin of Power-Laws in Internet Topologies Revisited},'' in {\em IEEE
  Infocom}, IEEE, 2002.

\bibitem{Oliveira2007Observing}
R.~Oliveira, B.~Zhang, and L.~Zhang, ``{Observing the Evolution of Internet AS
  Topology},'' in {\em Proceedings of ACM SIGCOMM}, 2007.

\bibitem{Park2003}
S.-T. Park, A.~Khrabrov, D.~Pennock, S.~Lawrence, C.~Giles, and L.~Ungar,
  ``{Static and dynamic analysis of the Internet's susceptibility to faults and
  attacks},'' pp.~2144--2154, 2003.

\bibitem{Pansiot2007Local}
J.-J. Pansiot, ``{Local and Dynamic Analysis of Internet Multicast Router
  Topology},'' {\em Annales des t\'{e}l\'{e}communications}, vol.~62,
  pp.~408--425, 2007.

\bibitem{Chang2006Peer}
H.~Chang, S.~Jamin, and W.~Willinger, ``To peer or not to peer: modeling the
  evolution of the internet's {A}{S}-level topology,'' in {\em Proceedings of
  IEEE INFOCOM}, 2006.

\bibitem{Wang2006Wealth}
X.~Wang and D.~Loguinov, ``Wealth-based evolution model for the internet
  {A}{S}-level topology,'' in {\em Proceedings of IEEE INFOCOM}, 2006.

\bibitem{Park2004Comparing}
S.-T. Park, D.~M. Pennock, and C.~L. Giles, ``{Comparing static and dynamic
  measurements and models of the Internet's {A}{S} topology},'' in {\em
  Proceedings of IEEE Infocom}, 2004.

\bibitem{Tangmunarunkit2002Network}
H.~Tangmunarunkit, R.~Govindan, S.~Jamin, S.~Shenker, and W.~Willinger,
  ``{Network topology generators: degree-based vs. structural},'' in {\em
  Proceedings of ACM SIGCOMM}, 2002.

\end{thebibliography}
