Analyzing network traces to identify long-term high rate flows

Abstract

In this thesis we look at a scalable way of identifying long-term high rate flows without maintaining per flow state information proportional to the number of flows. Identification of high-rate flows is useful at the time of congestion. This thesis proposes and evaluates a scheme for identifying high-rate flows without explicitly measuring the rates of the flows. Typical Internet traffic consists of a large fraction of flows that are ON/OFF in nature. Maintaining state information for every flow is unnecessary and expensive. We observe that this is a situation similar to the cache memory management in that we want to maintain information only on high rate flows (corresponding to frequently-referenced data items) using fixed space. We apply the LRU (least recent used) policy in selecting the high rate flows only. We observe that the single definition of a flow by the address/port/protocol quintuple unduly increases the observed number of flows, since approximately more than half of all flows so-defined are single-packet flows, i.e. about 50% of such quintuples are observed in only one packet over a timeout interval, e.g. of 100 seconds. We introduce a random decimator to filter them out statistically.