Charging from sampled network usage
Nick G. Duffield, Carsten Lund, Mikkel Thorup · 2001
Abstract—IP flows have heavy-tailed packet and byte size distributions. This make them poor candidates for uniform sampling—i.e. selecting 1 in N flows—since omission or in-clusion of a large flow can have a large effect on estimated total traffic. Flows selected in this manner are thus unsuit-able for use in usage sensitive billing. We propose instead using a size-dependent sampling scheme which gives prior-ity to the larger contributions to customer usage. This turns the heavy tails to our advantage; we can obtain accurate es-timates of customer usage from a relatively small number of important samples. The sampling scheme allows us to control error when charging is sensitive to estimated usage only above a given base level. A refinement allows us to strictly limit the chance that a customers estimated usage will exceed their actual us-age. Furthermore, we show that a secondary goal, that of controlling the rate at which samples are produced, can be fulfilled provided the billing cycle is sufficiently long. All these claims are supported by experiments on flow traces gathered from a commercial network. I.