Project Topics
Get Complete Project Material File(s) Now! »
Causes of the observed dynamics
It is acknowledged that load-balancing routers play a significant role in the observed dynamics of routes with traceroute-like measurements [71, 61]. Previous work also suggests that routing dynamics play a key role in the continuous discovery of new IP addresses in our measurements [64]. This section identifies the strong role played by these factors in our observations.
These two factors play different roles. Suppose first that there is no load balancing. In this case, a measurement will discover routing changes as they occur, and the longer a measurement lasts, the more IP addresses it will observe (because more changes will occur). If on the contrary there are no routing changes but load balancing is used, then performing more measurement rounds will lead to observe more IP addresses, independently of the time elapsed between consecutive rounds5. The observed dynamics is a combination of these factors. In order to study this rigorously, we use the woolthorpe data set and simulate slower measurements by considering only one out of every two rounds. Fig. 2.3 presents the number of distinct IP addresses observed with both these measurements, as a function of time elapsed since the beginning of the measurement, and the number of measurement rounds performed.
As expected, less IP addresses are observed over time with the slow measurements than with the faster ones. Fig. 2.3a shows that in a given time interval, performing more measurement rounds therefore allows us to discover more IP addresses. This confirms that several measurement rounds are needed to discover all existing routes. This is caused by factors such as load balancing. Conversely, Fig. 2.3b shows that the slow measurements discover more IP addresses at each round than the faster ones. Therefore if more time elapses between two consecutive rounds, then each round discovers more IP addresses. This indicates that routes evolve with time.
In both cases, the gap between the plots for the slow and faster measurements are significant, which shows that both factors play an important role in the observed dynamics. This is why we propose a model that incorporates load balancing and route dynamics.
Preliminary results of simulation
In this section we show that this model is relevant to explain the dynamic properties presented in Section 2.1. To that purpose, we perform several simulations varying the parameters of the model: the numbers n of nodes, m of links, d of destinations, and s of swaps per round. Our goals are to find (1) whether the simulations reproduce the observations and (2) how the different parameters impact the results and what are the relations between them.
Evolution of the number of distinct nodes.
In order to answer the first question, we present in Figure 2.4 the evolution of the number of distinct nodes observed over time for Erdös-Rényi random graphs with n “ 500, 000, m “ 1, 000, 000, d “ 3, 000 and various values of the number s of swaps. It shows a similar behaviour to the one we observed in real data (see Fig. 2.2a). In particular all the curves present clearly a fast initial growth7 and then a more or less linear progression. Moreover, the slopes of the curves increase with the number of swaps. This is due to the fact that with a higher number of swaps, the paths to the destinations change more quickly and thus more nodes are discovered at each step.
This figure also shows that when the underlying graph does not evolve (s “ 0), there is only an initial growth in which all shortest paths are explored. Once all nodes on these paths have been discovered, the curve becomes constant. This confirms the intuition that the regular discovery of new IP addresses in real data may stem from route dynamics.
Coefficients of segmented linear regression
Using a simple linear regression we can fit a straight line C “ αr ` β through the set tpri, Ciqu of data points by minimising the sum of squared residuals, i.e. squared vertical distances between the original points and the fitted line. For detailed explanations and formulæ see [9].
Let us divide our curve into several segments, compute the linear fit for each segment, and check that all obtained values for the slopes are consistent. The results are similar for real and simulated data. Let us discuss here only the woolthorpe dataset. Figure 3.3 presents the number of observed routers (black curve) and corresponding slopes of segmented linear regression (blue points). Each blue point corresponds to the slope of one segment of the black curve. Each segment has a length of 200 rounds, and starts at the abscissa of the corresponding blue point. We see clearly that after an initial fast decrease, the value of the slope stabilises around an average. Between round 25000 and 30000 we observe an outlier. This happens because our curve is not completely linear, and sometimes there are sharp increases at some points. Such increases may have a strong impact on the local slope but a very small impact on the overall slope.
Table of contents :
1 Brief history and state of the art
1.1 Graphs and complex networks
1.2 Network metrology
1.3 Dynamic networks and metrology
1.4 Models of networks
2 Model
2.1 Motivation: tracetree measurements
2.2 Causes of the observed dynamics
2.3 Model description
2.4 Preliminary results of simulation
2.4.1 Evolution of the number of distinct nodes.
2.4.2 Observation number vs. block number.
List of definitions
3 Characterising the dynamics
3.1 Linearity of the evolution
3.1.1 Correlation coefficient
3.1.2 Coefficients of segmented linear regression
3.2 Characterisation of the slope
3.2.1 Random graphs
3.2.2 Power-law graphs
3.3 In search of unified laws
3.3.1 Impact of the size of the shortest path subgraph
3.3.2 Probability of shortest path subgraph modifications
3.4 Real-world measurements
3.4.1 Frequency of measurements
3.4.2 Size of the shortest path tree vs slope
4 Size of shortest path subgraphs
4.1 Definitions
4.2 Complete and quasi-complete graphs
4.3 Dense random graphs (p is fixed, n Ñ 8)
4.4 Sparse random graphs with unbounded mean degree (p Ñ 0 and np Ñ 8 as n Ñ 8)
4.4.1 Approximated expectation of the size
4.4.2 Classification of sparse graphs according to the distance distribution
5 Real and observed dynamics
5.1 Impact of the measurement frequency
5.2 Inferring the evolution speed
5.2.1 Poisson process
5.2.2 sps-process
5.2.3 spt-process
5.3 Nonuniform dynamics
Conclusion
A Résumé
Bibliography
