A Research Project from the ICREA/Complex Systems Lab

Main Researchers: Sergi Valverde , Ricard V. Solé
Related Projects: DELIS

Introduction: The majority of studies on Internet traffic focus on the local fluctuations and behaviour of a single link, an isolated router or a little network comprising few nodes. Another approach quantifies the differences in traffic and performance over a large number of routers and links. Here, we propose a unique class of models of traffic dynamics reproducing distributions of global performance measurements over the Internet. This model might be relevant to understand the behavior of Internet under attacks and/or global routing instabilities. This research is partly supported by the European DELISproject.

WARNING: You are allowed to download and use this software for research and educational purposes only. In any case, you must cite the following paper S. Valverde & Ricard. V. Solé, "Internet's Critical Path Horizon", European Physics Journal B, 38(2), pp. 245, March (2004) and/or this web page were appropiate. This global Internet simulator is a prototype and we are not responsible of any damage or loss of data caused by improper or accidental usage.


NEWS
17/02/2005   First public release and publication of this web page.
 

 

 

PARCHER: Real-Time Simulation of Global Internet Dynamics

It is widely recognized that traffic in any Internet's link is highly fluctuating. The analysis of fluctuations have revealed that self-similar nature of Internet traffic. In particular, signal burstiness is extremely persistent at very large resolutions. We have explained the origin of self-similarity in Internet traffic by invoking the presence of phase transition phenomenon (Solé and Valverde (2001), Valverde and Solé (2002)). The Internet is modeled as a network of hosts or traffic sources that control their own rate of packet injection and  routers that store and forward packets.   In a recent paper (Valverde and Solé, 2004), we have enhanced considerably our previous models by introducing a realistic Internet topology generator (Yook et al, 2002).


 

Figure: An snapshot taken from our realtime 3D simulator of global packet dynamics. Routers and Host are displayed according to their (generated) geographical locations (see Yook et al., 2002). The queue length at a node grows and shrinks dinamically depending on the amount of incoming traffic. Warm colors signal heavy packet loads. Notice how highly connected nodes (hubs) are more likely to get congested.

 

 

To download PARCHER application click here
(it works under Windows 98, 2000 and XP). This application requires OpenGL and a 3D graphics accelerator in order to run smoothly.

 

The PARCHER simulator fully implements the traffic model described in (Valverde and Solé, 2004). Our model has the following key features:

Realistic Topology: Our previous analyses do not take into account the heterogenous architecture of Internet. We have integrated the topology generator described in Yook et al. 2002, which reproduces the global Internet topology very well.  They have show how most existing Internet generators fall in a very different region of the phase space where real Internet is located.

Adaptative Traffic Sources (hosts): Sources inject packets depending on their perceived level of local congestion. This simple rule is enough to self-organize the system in the critical point where a highly efficient regime of traffic flow is achieved (Toroczkai and Bassler, 2004). At this point, the impredictability is also maximized (see Solé and Valverde, 2001) and the system displays a great diversity of behaviors.

Realistic router limitations: There is a limit in the maximum number of packets a router can store. Packets arriving at full queues are discarded as in the real Internet.

Path horizon: Routing tables can not store detailed information about the entire system. This will necessarily introduce an amount of disorder in the paths taken by packets when travelling from one host to another.  We have explored this cost/efficiency trade-off in this model by introducing a parameter defining the visibiliy scope of the router (or depth-of-routing paramter). This is closely related to the size of routing table. When depth-of-routing equals the network diameter the flow of paquets is maximized (see Valverde and Solé, 2004). Moreover, if the underlying network topology is small-world, then the previous assignment is optimal in terms of the required amount of routing information per node.

References

R. V. Solé and S. Valverde, 'Information Transfer and Phase Transitions in a model of Internet Traffic', Physica A 289 (2001), 595-695

S. Valverde and R. V. Solé, 'Self-Organized Critical Traffic in Parallel Computer Networks', Physica A 312 (2002), 636-648

S. Valverde and R. V. Solé, 'Internet's Critical Path Horizon', European Physics Journal B, 38(2), pp. 245, March (2004)

S.-H Yook, H. Jeong and A.L- Barabási, 'Modeling the Internet's Large-Scale Topology', Proc. Natl. Acad. Sci. USA 99, 13382 (2002)

Z. Toroczkai and K. E. Bassler,  'Jamming is Limited in Scale-Free Systems', Nature, 428 716 (2004)

 

 

Measurements on Models of Global Internet  Dynamics

Our models allow several types of performance measurements, which can be compared with real measurements taken from the Internet.  An example of measurement is the distribution of incoming/outgoing router flow (see figure below).

Figure: Relationship between fluctuations and the average incoming flow (Left) and a similar distribution for average outgoing router flow (right). The raw flow data was generated with the PARCHER simulator. The plot shows that both quantities are related by a power law of exponent 1/2, which is consistent with measurements taken from Internet routers (from Valverde and Solé, 2004).

When understanding the competition between a network's internal collective dynamics (i.e, Internet traffic) and external environmental changes (i.e. behavior of traffic sources or hosts, distribution of file sizes) it is useful to study the relationship between the average flow and the size of fluctuations around the average (Argollo de Menezes and Barabási, 2004).  Dispersion depends on the average flux following an scaling law, where the exponent can take the values 1/2 or 1. Argollo de Menezes and Barabási found that many different systems can be classified in two distinct dynamical classes depending on the value of this exponent.  The 1/2 exponent captures an endogenous behaviour, determined by the system's internal collective fluctuations. On the other hand, the 1 exponent indicates an exogenous dynamics driven by the environment.  Interestingly, the 1 exponent is universal, that is, independent of the nature of the internal dynamics or the network topology.

The analysis of flow from real Internet routers has revealed a 1/2 exponent, thus indicating the endogenous nature of Internet dynamics. This is consistent with measurements taken from our model that already predicts the same 1/2 exponent (see figure above and Valverde and Solé, 2004). Real data shows that global traffic dynamics can not be simply reduced as a superposition of many and high-variable (infinite variance) traffic sources or other external features like distribution of file sizes ( Willinger et al., 1995).

References

S. Valverde and R. V. Solé, 'Internet's Critical Path Horizon', European Physics Journal B, 38(2), pp. 245, March (2004)

M. Argollo de Menezes and A.-L. Barabási, 'Fluctuations in Network Dynamics', Physical Review Letters, 92(2), January (2004)

W. Willinger, M. S. Taqqu, R. Sherman, D. V. Wilson,  'Self-similarity through high-variability: statistical analysis of ethernet LAN traffic at the source level', IEEE/ACM Trans. on Networking,25, 4, pp. 100-113, October (1995)