HP Labs Technical Reports

Click here for full text: PDF

Traffic Estimation for the Largest Sources on a Network, Using Packet Sampling with Limited Storage

Jedwab, Jonathan



Abstract: In the management of networks it is often important to know the largest traffic sources and corresponding packet counts, but impractical to examine every packet due to processing and storage constraints. By sampling packets it is possible instead to estimate the actual packet counts statistically for each source. We present an algorithm for choosing which samples to discard when limited processing and storage allows only a restricted list of sources and their packet counts to be maintained. Subject to modest assumptions on the behaviour of the network traffic, we show that the probability of miscounting sampled packets originating from the t largest sources is negligible for small t, and we bound the probability of misranking these t sources. This method also applies to traffic estimation for the largest destinations or source-destination pairs, for example.

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map][Home] [Hewlett-Packard]