Patent ID: 7746808

Claim:
A computer-readable storage medium comprising instructions that, when executed by a computing device, cause the device to: aggregate sampled packets in accordance with a flow associated with the sampled packets, the packets being sampled from the packet stream at a sampling rate; count the aggregated packets using Adaptive Sample-and-Hold ( A SH); adjust the sampling rate based on a quantity of flows to obtain a sketch having a predetermined size, the sampling rate being adjusted in steps; and transfer the count of aggregated packets from SRAM to DRAM, initialize the count in SRAM following adjustment of the sampling rate; and calculate an adjusted weight of each flow using: A sSH ⁡ ( n ) = ( 1 - p 1 ) + ∑ i = 1 r ⁢ n i ( 1 - ∑ h = 1 i ⁢ c h , h ) 1 - ∑ h = 1 r ⁢ c h , h r being a total quantity of steps, n=(n 1 , . . . , n r ) such that n i is the number of packets counted from the flow in step i, and c h,h (h=1, . . . , r) are defined by: c 1,j =(1−p j ) for 1≦j≦r, c 2,j =(1−p j ) n 1 −1 (c 1,j −c 1,1 ) for 2≦j≦r, c i,j =(1−p j ) n 1 −1 (c i−1,j −c i−1, i−1 ) for 3≦i≦j≦r, p 1 > . . . >p r is the sampling rate at step i=1, . . . r, the adjusted weight of the flow representing an estimate of the size of the flow.