Traffic analysis is important to the operation of IP networks. The input to the analysis is raw data such as packet header traces or NetFlow records and the output is often the size aggregates such as the traffic generated by various applications or by individual customers. Storing the raw data allows the flexibility of running arbitrary new analyses in the future, but the sheer amount of raw data is often a challenge. Sampling based techniques such as smart sampling aim at reducing the amount of raw data while preserving the ability of future analyses to accurately estimate the traffic of any large aggregate. There are three important measures of the traffic of an aggregate: the number of bytes, the number of packets and the number of flows. Current data reduction solutions allow estimating only one of these measures. In this paper we propose the idea of unified summaries that allow the analyses to get unbiased estimates for all three measures. Our unified summary that takes as input flow records is based on smart sampling and the one that reads in packet header traces is based on sample and hold. The most important contributions of this paper are the development of novel unbiased statistical estimators for the number of flows, the development of methods for combining summaries measuring bytes and packets using less memory than separate summaries, and experimental evaluation of the proposed solutions based on traces of traffic.

Pre-2018 CSE ID: CS2004-0793

The purpose of this technical report is to compare multistage filters and sketches with respect to their ability to identify heavy hitters. In a nutshell, the conclusion is that multistage filters identify heavy hitters using less memory than sketches, but some sketches support important other operations, more specifically they can be added and subtracted without any need to re-read the data stream(s).

Pre-2018 CSE ID: CS2004-0784

Useful measurement data is badly needed to help onitor and control large networks. Current approaches to solving measurement problems often assume minimal support from routers and protocols (e.g., tomography) or place the entire burden on the router to support heavyweight mechanisms (e.g. NetFlow, per-prefix counters). The thesis of this paper is that systems approaches to such problems can yield more efficient intermediate solutions by considering the ultimate use of the data, understanding implementation costs, and by distributing aspects of the solution among routers, protocols, and tools. We briefly show how these principles are indirectly applied in existing proposals for new measurement primitives. We then show how these principles can be used to derive new systems solutions to two separate problems: measuring route stability (by modifying route computation) and measuring traffic matrices (by implementing per-class counters that can yield traffic matrices with much smaller memory requirements than per-prefix counters). Beyond specifictechniques, we hope the principles in this position paper can provide a focus for discussion among researchers, router vendors, protocol designers, and network operators (the stakeholders in the measurement enterprise) to yield effective solutions to measurement problems.

Pre-2018 CSE ID: CS2003-0747

While the number of concurrent flows passing through backbone routers is large (more than 250,000), measurements show a small number of flows (say 10%) represent a large fraction of the traffic. Thus a desirable goal for a measurement algorithm at a backbone router is to identify (say) the top 10% of the flows using not much more than 10% of the memory needed to keep track of all flows. A similar goal would be to determine any flows that use more than (say) 1% of the link bandwidth (to catch hot spots) using only a small amount of high speed memory. Keeping state for each flow (to tell whether a flow is ``large'') is ruled out. Our paper describes an algorithm for identifying large flows using small memory and small per packet processing bounds. Our algorithm scales well even with increases in bandwidth and number of flows.

Pre-2018 CSE ID: CS2001-0666

Accurate network traffic measurement is required for accounting, bandwidth provisioning and detecting DoS attacks. These applications see the traffic as a collection of flows they need to measure. As link speeds and the number of flows increase, keeping a counter for each flow is too expensive (using SRAM) or slow (using DRAM). The current state-of-the-art methods (Cisco's sampled NetFlow) which log periodically sampled packets are slow, inaccurate and resource-intensive. Previous work showed that at different granularities a small number of ``heavy hitters'' accounts for a large share of traffic. Our paper introduces a paradigm shift by concentrating on measuring only large flows --- those above some threshold such as 0.1\% of the link capacity. We propose two novel and scalable algorithms for identifying the large flows: sample and hold and multistage filters, which take a constant number of memory references per packet and use a small amount of memory. If M is the available memory, we show analytically that the errors of our new algorithms are proportional to 1/M; by contrast, the error of an algorithm based on classical sampling is proportional to 1/sqrt(M), thus providing much less accuracy for the same amount of memory. We also describe further optimizations such as early removal and conservative update that further improve the accuracy of our algorithms, as measured on real traffic traces, by an order of magnitude. Our schemes allow a new form of accounting called threshold accounting in which only flows above a threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes usage-based and duration based pricing.

Pre-2018 CSE ID: CS2002-0699

Flow measurement evolved into the primary method for measuring the composition of Internet traffic. Large ISPs and small networks use it to track dominant applications, dominant users, and traffic matrices. Cisco's NetFlow is a widely deployed flow measurement solution that uses a configurable static sampling rate to control processor and memory usage on the router and the amount of reporting traffic generated. Proposed enhancements to the basic sampled NetFlow solve various problems. For example, smart sampling reduces the overhead of reporting and storing the flow records generated by NetFlow by sampling them with probability proportional to their byte counts. Adaptive NetFlow limits memory and CPU consumption at the router by dynamically adapting the sampling rate used by NetFlow. In this paper we propose ``flow slices'', a flow measurement solution that can be deployed through a software update at routers and traffic analysis workstations. Flow slices borrows ideas from smart sampling and adaptive NetFlow, but it introduces significant new ideas too: a flow measurement algorithm related to sample and hold; new estimators for the number of active flows; basing smart sampling decisions on multiple factors; separating sampling rate adaptation from measurement bins; controlling the three resource bottlenecks at the router (CPU, memory, reporting bandwidth) using independent ``tuning knobs''. The resulting solution has smaller resource requirements than current proposals and it enables more accurate traffic analysis results. We provide theoretical analyses of the variances of the estimators based on the flow slices and experimental comparisons with other flow measurement solutions.

Pre-2018 CSE ID: CS2005-0822

In this paper we address the problem of counting the number of distinct header patterns (flows) seen on a high speed link. Such counting can be used to detect DoS attacks and port scans, and to solve measurement problems. The central difficulty is that count processing must be done in a packet arrival time (8 nsec at OC-768 speeds) and hence must take a small number of memory references to limited, fast memory. A naive solution that maintains a hash table requires several Mbytes because the number of flows can be more than a million. By contrast, our new algorithms take very little memory and are fast. The reduction in memory is particularly important for applications that run multiple concurrent counting instances. For example, we used one of our new algorithms to replace the port scan detection component of the popular intrusion detection system Snort. Doing so reduced the memory usage on a ten minute trace from 51 Mbytes to 5.7 Mbytes while maintaining a 99.78% probability of alarming on a scan within 6 seconds of when the large-memory algorithm would alarm. By contrast, the best known prior algorithm (probabilistic counting) takes 4 times more memory on the port scan application and 8 times more memory on a measurement application. Fundamentally, this is because our algorithms can be customized to take advantage of special features of applications such as a large number of instances that have very small counts, or prior knowledge of the likely range of the count.

Pre-2018 CSE ID: CS2002-0705

Good performance under excessive workloads and isolation between the resource consumption of concurrent jobs are perennial design goals of computer systems ranging from multitasking servers to network routers. In this paper we present a system that computes multiple summaries of IP traffic in real time and achieves these design goals in a novel way: by automatically adapting parameters of the summarization algorithms. Anomalous network behavior, such as denial of service attacks or worms could push CPU or memory consumption beyond the limits of the hardware exactly when measurement is needed the most. Our measurement system reacts by gracefully degrading the accuracy of the affected summaries. The types of summaries we compute are widely used by network administrators monitoring the workloads of their networks: the ports sending the most traffic, the IP addresses sending or receiving the most traffic or opening the most connections, etc. We propose a new solution: ``flow sample and hold''. Compared to previous solutions, these new solutions offer better memory versus accuracy tradeoffs and have more predictable resource consumption. Finally, we evaluate the actual implementation of a complete system that combines the best of these algorithms.

Pre-2018 CSE ID: CS2003-0766

In this paper we present a family of algorithms that address the problem of counting the number of distinct header patterns (flows) seen on a high speed link. Such counting can be used to detect DoS attacks and port scans, and to solve measurement problems. The central difficulty is that count processing must be done within a packet arrival time (8 nsec at OC-768 speeds) and, hence, must require only a small number of memory references to limited, fast memory. A naive solution that maintains a hash table requires several Mbytes because the number of flows can be more than a million. By contrast, our new algorithms take very little memory and are fast. The reduction in memory is particularly important for applications that run multiple concurrent counting instances. For example, we used one of our new algorithms to replace the port scan detection component of the popular intrusion detection system Snort. Doing so reduced the memory usage on a ten minute trace from 50 Mbytes to 5.6 Mbytes while maintaining a 99.5% probability of alarming on a scan within 9 seconds of when the large-memory algorithm would alarm. By contrast, the best known prior algorithm (probabilistic counting) takes 4 times more memory on the port scan application and 8 times more memory on a measurement application. Our algorithms also lead to a reduction by a factor of seven in the total memory usage of a traffic analysis application from the CoralReef suite. Fundamentally, this is because our algorithms can be customized to take advantage of special features of applications such as a large number of instances that have very small counts or prior knowledge of the likely range of the count.

Pre-2018 CSE ID: CS2003-0738

The Internet service model emphasizes flexibility -- any node can send any type of traffic at any time. While this design has allowed new applications and usage models to flourish, it also makes the job of network management significantly more challenging. This paper describes a new method of traffic characterization that automatically groups traffic into minimal clusters of conspicuous consumption. Rather than providing a static analysis specialized to capture flows, applications, or network-to-network traffic matrices, our approach dynamically produces hybrid traffic definitions that match the underlying usage. For example, rather than report five hundred small flows, or the amount of TCP traffic to port 80, or the ``top ten hosts'', our method might reveal that a certain percent of traffic was used by TCP connections between AOL clients and a particular group of Web servers. Similarly, our technique can be used to automatically classify new traffic patterns, such as network worms or peer-to-peer applications, without knowing the structure of such traffic a priori. We describe a series of algorithms for constructing these traffic clusters, minimizing their representation and the design of our prototype system, AutoFocus. In addition, we describe our experiences using AutoFocus to discover the dominant and unusual modes of usage on several different production networks.

Pre-2018 CSE ID: CS2003-0746