New directions in traffic measurement and accounting

By Cristian Estan, George Varghese. CCRV, 2002

699 citations recorded by the source corpus.

Measurement of various traffic aggregates is an indispensable tool of the operators of IP backbones. One of the obstacles t ha t prevents the use of measurement data for billing is its inaccuracy. The reason of this inaccuracy is how the measurement is done on high speed links: state of the art routers count only periodically sampled packets (e.g. Cisco's sampled NetFlow). On an OC-192 link , one has 32 nanoseconds to handle a 40 byte packet while access times to DKAMs are at least 50 nanoseconds. Previous work showed that at different granularities, a small number of "heavy hitters" accounts for a large share of the total tralilc. Our paper introduces a paradigm shift by concentrating the measurement efforts on only these large flows. By using smaller, faster memories we can measure them accurately. We propose two algorithms for identifying the large flows using little extra memory and a fixed small number of per packet memory accesses: sample and hold and multistage filter. We evaluate the algorithms analytically and on traces of actual traffic to show their accuracy and scalability. A flow is defined by a flow identifier (flow ID) tha t has to be contained in each packet belonging to a flow or be computable based on what the packet contains. Large flows are those tha t send more than a given threshold (say 1% of the link capacity) during a given measurement interval (1 second, 1 minute or even 1 hour). Ideally we would want our algorithm to give us at the end of the interval the list of the flow IDs of all the flows tha t exceeded the threshold and their exact size. Our algorithms work together with a small, fast flow memory. The number of active flows is significantly larger than the number of entries in the flow memory. At each packet arrival we can afford to look up a flow ID, update the counter(s) in the entry or allocate a new entry if there is no entry associated with the current packet. Ideally, the algorithms for identifying large flows would allocate an entry in the flow memory for each large flow and never allocate entries for flows below the threshold. After the entry is allocated, we exactly count the traffic of the flow it belongs to. Sample and hold has a very small probability of missing large flows by not adding them to the flow memory and multistage filter never misses one. Multistage filter provably adds very few small flows and we have bounds on the number of small flows added by sample and hold too. We report actual par.ket counts and therefore never overestimate the size of a flow. We underest imate it by the amount of traffic tha t passed by before the flow was added to the flow memory. Our estimates for the traffic of the identified large flows have smaller errors than those one can obtain from sampled NetFlow. Multistage filter is slightly more complex than sample and hold, but it uses less memory. A full description and analysis of the algorithms will be presented in the final paper which will be linked from http:/ /wtm-cse, ucsd. edu/users/varghe se/ . We envision many applications to our algorithms because they are quite generic. The flow identifier can be the 5-tuple of source IP address, destination IP address, protocol number, source port and destinat ion port. Or it can be the source network and the destination network, both of which can be computed through a lookup in the routing table. Alternately we can define the flow by only the destination IP address of the packets. Our algorithms can be used for real t ime traffic monitoring, detecting ongoing (distributed) denial of service attacks or billing. We propose scalable threshold accounting: accurately track the traffic tha t exceeds x% of the link, the customers exceeding the threshold are subject to usage based pricing while the others pay a fiat fee.

Subfields: Building and Construction

View Paper: https://www.semanticscholar.org/paper/123c48d636c18faf61339fe261f79108e2df802d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Building and Construction

Citations in the corpus

Taming the underlying challenges of reliable multihop routing in sensor networks (2003, methodology): “Heuristics are used in [7] to identify a set of most frequently occurring packet classes.”
Space efficient mining of multigraph streams (2005, background): “INTRODUCTION The past few years have witnessed an emergence of monitoring applications that has lead to the study of data streams, where data is generated rapidly and continuously in a stream and one needs to perform real-time analyses on the observed stream of data records.”
Heavy-Hitter Detection Entirely in the Data Plane (2016, methodology): “(1) Sample and Hold: We simulate sample and hold [17] with a flow table that is implemented as a list .”
Automated Worm Fingerprinting (2004, methodology): “Our prototype uses multi-stage filters with conservative update to dramatically reduce the memory footprint of the problem (see Figure 2 for a general description and [13, 10] for a thorough analysis).”
Software Defined Traffic Measurement with OpenSketch (2013, neutral): “As an alternative, many sketch-based streaming algorithms have been proposed in the theoretical research community [7] [12] [46] [8] [20] [47], which provide efficient measurement support for individual management tasks.”
Automatically inferring patterns of resource consumption in network traffic (2003, background): “In [6] Estan and Varghese present algorithms that automatically and efficiently identify large clusters, once the definition of clusters is fixed.”
Frequency Estimation of Internet Packet Streams with Limited Space (2002, background): “Estan and Varghese [9] identify supersets likely to”
Low-rate TCP-targeted denial of service attacks and counter strategies (2003, background): “While potentially quite harmful, the high-rate natur e of such attacks presents a statistical anomaly to network monitors such that the attack can potentially be detected, the attacker identi fi d, and the effects of the attack mitigated (see for example, [6, 22, 30]).”
Bitmap algorithms for counting active flows on high speed links (2003, background): “Identifying those addresses can be done using previous techniques [4] because those few source addresses must send a lot of traffic each for the attack to be effective.”
Sketch Algorithms for Estimating Point Queries in NLP (2012, methodology): “In this section, we review existing sketch algorithms from the literature, and propose novel variants based on the idea of conservative update (Estan and Varghese, 2002).”
An improved data stream summary: the count-min sketch and its applications (2004, methodology): “Lastly, we note that our Count-Min sketches appear similar in outline to both the uniscan algorithm due to Fang et al [13] and the parallel multistage filters of Estan and Varghese [11].”
Windows Azure Storage: a highly available cloud storage service with strong consistency (2011, methodology): “[7] Cristian Estan and George Varghese, "New Directions in Traffic Measurement and Accounting," in SIGCOMM, 2002.”
Issues in data stream management (2003, background): “for finding frequent items in a stream [27, 30].”