The power of slicing in internet flow measurement (2005)

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 some of its problems.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, inspired from Smart Sampling and Adaptive NetFlow, introduces novel ideas such as -separating sampling rate adaptation from measurement bins; controlling the three resource bottlenecks at the router (CPU, memory, reporting bandwidth) using separate "tuning knobs"; basing smart sampling decisions on multiple factors; a flow measurement algorithm related to sample and hold; new estimators for the number of bytes and flows.The resulting solution has smaller resource requirements than current proposals and it enables more accurate traffic analysis results.We provide theoretical analyses of the unbiasedness and variances of the estimators based on Flow Slices and experimental comparisons with other flow measurement solutions such as Adaptive NetFlow. IssueSampled NetFlow Adaptive NetFlow Flow Slices Memory usage Variable Fixed Fixed Volume of flow data reported Variable Fixed Fixed Behavior under DDoS with spoofed sources Panicky flow Reduction in Small reduction and other traffic mixes with many flows expiration accuracy in accuracy Estimates of traffic in small time bins Less accurate Accurate Less accurate Reporting overhead when using small bins Unaffected Large increase Unaffected Lifetime of flow record in router memory Min(active timeout, Bin length Min(slice length, flow length + flow length + inactive timeout) inactive timeout) Resource usage at end of time bin N/A Reporting spike or N/A extra memory Processing intensive tasks Counting Counting and Counting renormalization Counting TCP flow arrivals (using SYNs) Yes Yes Yes Counting all active flows No Separate flow Yes counting extension Counting all active flows at high speeds No Hardware flow No counting extension Table 1: Sampled NetFlow, Adaptive NetFlow and Flow Slices differ in the types of measurements they support, in how they adapt to different traffic mixes, and in their resource consumption (memory usage and reporting traffic). Related workNetFlow [17], first implemented in Cisco routers, is the most widely used flow measurement solution today.Routers maintain flow records collecting various bits of information.Flows are identified by fields present in the header of every packet 1 : source and destination IP address, protocol, source and destination port, and type of service bits.The flow record keeps information such as the number of packets in the flow, the (total) number of bytes in those packets, the timestamp of the first and last packet, and protocol flag information such as whether any of those packets had the SYN flag set.NetFlow uses four rules to decide when to remove a flow record from router memory and report it to the collection station: 1) when TCP flags (FIN or RST) indicate flow termination, 2) 15 seconds (configurable "inactive timeout") after seeing the last packet with a matching flow ID, 3) 30 minutes (configurable "active timeout")' after the record was created to avoid staleness and 4) when the memory is full.On every new packet, NetFlow looks up the corresponding entry (creating a new entry if necessary) and updates that entry's counters and timestamps.Since for high speed interfaces, the processor and the memory holding the flow records cannot keep up with the packet rate, Cisco introduced Sampled NetFlow [22] which updates the flow cache only for sampled packets.For a configurable value of a parameter AE, a packet is sampled with one in AE probability.