An extensive body of research deals with estimating the correlation and the Hurst parameter of Internet traffic traces. The significance of these statistics is due to their fundamental impact on network performance. The coverage of Internet traffic traces is, however, limited since acquiring such traces is challenging with respect to, e.g., confidentiality, logging speed, and storage capacity. In this work, we investigate how the correlation of Internet traffic can be reliably estimated from random traffic samples. These samples are observed either by passive monitoring within the network, or otherwise by active packet probes at end systems. We analyze random sampling processes with different inter-sample distributions and show how to obtain asymptotically unbiased estimates from these samples. We quantify the inherent limitations that are due to limited observations and explore the influence of various parameters, such as sampling intensity, network utilization, or Hurst parameter on the estimation accuracy. We design an active probing method which enables simple and lightweight traffic sampling without support from the network. We verify our approach in a controlled network environment and present comprehensive Internet measurements. We find that the correlation exhibits properties such as long range dependence as well as periodicities and that it differs significantly across Internet paths and observation times.
This paper considers the basic problem of "how accurate can we make Internet performance measurements". The answer is somewhat counter-intuitive in that there are bounds on the accuracy of such measurements, no matter how many probes we can use in a given time interval, and thus arises a type of Heisenberg inequality describing the bounds in our knowledge of the performance of a network. The results stem from the fact that we cannot make independent measurements of a system's performance: all such measures are correlated, and these correlations reduce the efficacy of measurements. The degree of correlation is also strongly dependent on system load. The result has important practical implications that reach beyond the design of Internet measurement experiments, into the design of network protocols.