Equilibrium Networks

A paper by Karagiannis et al. that appeared around the same time as Veitch et al. and called “A Nonstationary Poisson View of Internet Traffic” provided concrete evidence to support the convergence to Poissonian packet interarrivals. Mindful of the same short-timescale issues as Veitch et al., Karagiannis et al. remarked that “the packet interarrival time distribution may deviate from the Poisson model for very small values because of multiple-packet deterministic sequences” due primarily to buffered packets in the upstream router. However, this should not be a factor except as the link becomes saturated, which is precisely the caveat of Cao et al. detailed earlier.

Karagiannis et al. examined traces from multiple links, including an OC-48 backbone link and a 100 Mbps trans-Pacific backbone link in 2003, and concluded that (formatting as in the original)

•    Packet arrivals appear Poisson at sub-second time scales: The packet interarrivals follow an exponential distribution. In addition, packet sizes and interarrival times appear uncorrelated…
•    Internet traffic is nonstationary at multi-second time scales: We demonstrate that traffic oscillates around a global mean, in a piecewise linear manner.
•    Internet traffic exhibits long-range dependence (LRD) at large time-sacles: In agreement with previous findings, we observe that Internet traffic is LRD at scales of seconds and above.

They went on to note that

…Our work suggests that Poisson models should not be abandoned especially in the Internet backbone with high speeds, and huge levels of traffic multiplexing.

With respect to the OC-48 data, Karagiannis et al. also showed that

For interarrival times, independence holds for 20,000 consecutive packet arrivals…

Moreover,

To stress-test the claim for the memoryless properties of Poisson arrivals and independence, we studied bursts of packets…We find that the distributions of the duration of the busy/idle period…are well approximated by exponential distributions. This is irrespective of the interarrival time that is used as the boundary for distinguishing between idle and busy periods.

Karagiannis et al. concluded by noting that

this type of traffic model (i.e., Poisson with nonstationarity at multi-second scales) is consistent with the kind of long-range dependence that is commonly observed in network data over larger time scales…we expect the traffic characteristics for the Internet backbone to continue to grow even better behaved in the future.

The coup de grâce in the fifteen-year saga of packet interarrival behavior may have been delivered in early 2009, when Gÿorgy Terdik and Tibor Gyires delivered a paper called “Does the Internet Still Demonstrate Fractal Nature?” In this paper Terdik and Gyires noted the work of Veitch et al. and remarked that

a Poisson cluster process could model the aggregate traffic where the packet interarrivals within individual clusters of each flow could be characterized by an overdispersed Gamma distribution.

Analyzing data from an OC-192 link in 2008 with this in mind, Terdik and Gyires found that

the burstiness of the interarrival times decreased significantly compared to earlier traces…Furthermore, we found that in many traces the distribution was Poisson deviating from previous observations. Therefore in answering our original question, we can conclude that based on the sample traces, the Internet is losing its self-similar nature that was so prevalent for years.

And there you have it. It is a subtle picture of evolving behavior for network packet interarrival times, but the central point is clear: network traffic is becoming increasingly (and at high speeds already appears to be) Poissonian. This simplification means that a lot of elegant and powerful mathematical techniques that were not ever considered for profiling network traffic because of earlier results in the nineties are actually increasingly likely to be the appropriate way to handle things now and in the future. It may also mean that the debates you hear now about network capacity are not going to continue for many more years, because the telcos will be able to plan better. (Or they may continue simply because it’s to the telcos’ advantage to have such debates.)

In the next post in this series, I’ll discuss some mathematically oriented ideas that seek to exploit the emergence of Poisson traffic to provide a lasting foundation for scalable network profiling algorithms.