Network traffic measurement is quite an important requirement for network administration for a variety of reasons, including traffic and capacity planning, accounting, billing, network forensics, and anomaly detection. Measurements need to be as nonintrusive as possible to avoid perturbing the normal traffic. In addition, measurements need to be fast enough to cope with the traffic. The latter is particularly a challenge in today’s fast networks.
A flow is commonly defined as a sequence of packets adhering to a chosen set of rules. For instance, the rule may dictate a common source address and a common destination address. Such a rule identifies packets transferred between two known networked entities. In typical network traffic, one will find several concurrent flows in operation. Given the number of flows, it is pertinent that measurements use as little space as possible to store measured data. This is particularly true when the data needs to be stored in fast memory, which is expensive and therefore not plentiful.
The authors present a compact and fast counter architecture, called randomized counter sharing, to measure flow sizes. This architecture is compared to counter braids, the best existing work in per-flow counting. Results show that braids require at least six memory accesses, while the architecture presented here requires only two. Like counter braids, randomized counter sharing “shares counters among flows to save space”; it does not require any space for mapping flows to counters. For every packet, randomized counter sharing updates just one counter as opposed to three or more in counter braids. The recorded flow size is not exact, but deemed to be a close approximation with a confidence interval to characterize its accuracy.
When the flow to counter mapping is one to one, large (“elephant”) flows may overflow and lose information, while small (“mouse”) flows underutilize the counter. To overcome this imbalance, randomized counter sharing stores the size of each flow in many counters, that is, an “elephant” is divided up into many “mice” that are stored in different counters. In addition, as the name of the scheme implies, multiple flows share counters. The end result is an efficient use of counters. Sharing the counters, however, introduces noise into the measured data. “Any two flows will have the same probability of sharing [a] counter.” In other words, every flow has “the same probability of introducing a certain amount of noise to any other flow.” However, with many flows and counters, the total noise will be uniformly distributed across the counters. This noise can therefore be measured and removed offline.
The authors start the paper with the rationale for their work and comprehensive coverage of related literature. They then informally describe their randomized counter sharing architecture and justify its functionality intuitively. This is followed by a formal presentation of online data encoding and offline processing (which is required for noise removal). A comprehensive set of experimental results show the effectiveness of randomized counter sharing empirically.
This paper is of interest to network measurement engineers and researchers. It is useful in other areas, too, such as the design of performance counters in fast central processing units (CPUs).
