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.
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.
Valverde and R. V. Solé,
'Internet's Critical Path Horizon',
Physics Journal B, 38(2), pp. 245, March (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).
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)