Patent ID: 8335160

Claim:
A method in a network device for performing sampling-based monitoring of flows in a plurality of buckets, the method comprising the steps of: receiving a packet at a forwarding plane of the network device; determining whether the packet is part of an existing flow already tracked in one of the plurality of buckets ranging from a least-significant bucket to a most-significant bucket in terms of a predetermined criteria that identifies top talkers, wherein the top talkers are the flows that most impact traffic of the network device, wherein each of the plurality of buckets sort the flows tracked therein by order of least recently used at a tail of each bucket and most recently used at a head of each bucket; upon determination that the packet is part of the existing flow already tracked in one of the plurality of buckets, performing the following steps: adding the packet to that existing flow; and moving that existing flow to the head of a bucket of the plurality of buckets, the bucket for that existing flow is selected based on the predetermined criteria; upon determination that the packet is not part of any existing flows already tracked in one of the plurality of buckets, performing the following steps: determining whether a total number of flows tracked in the plurality of buckets of the forwarding plane has reached a maximum limit; discarding a flow from the tail of the least-significant bucket only when the total number of flows in the plurality of buckets of the forwarding plane has reached a maximum limit, whereby the flow is discarded to allow a new flow to be created without causing the total number of flows to exceed the maximum limit and because the flow to be discarded is the least recently used flow in the least-significant bucket; and creating a new flow for the packet at the head of the least-significant bucket; reporting information on the flows tracked in the plurality of buckets upon the flows' expiration from the forwarding plane to a control plane of the network device, wherein the information includes at least one of source IP address, destination IP address, source port number, destination port number, number of packets in the flow, number of bytes in the flow, time of first packet of the flow, or time of last packet of the flow, whereby reporting only the information on those flows that remain tracked in any of the plurality of buckets by not being discarded upon the flows' expiration ensures that information on the top talkers is reported and also guarantees that information on at least one flow is reported because all flows created by the network device are reported up to the maximum limit; and exporting the information on the flows reported to the control plane from the control plane to an external collector for further analysis or processing by the external collector.