Identifying Large Flow with Two-Level Replacement

F.-Y. Wang, X.-C. Yun, X.-F. Wang, Yong Wang, and J.-X. Liu (PRC)


network traffic measurement, large flow, replacement mechanism, LRU replacement, LEAST replacement


Due to the limitation of traffic measurement capability, it is valuable for some applications to identify the large flows correctly and timely in high-speed network. In this paper, we present an algorithm of identifying large flows with two-level replacement mechanism which combines LRU (Least Recently Used) replacement and LEAST replacement together. Those small flows can be evicted by the replacement mechanism and the large flows are left. LRU replacement can overcome the shortcoming of LEAST replacement, and vice versa. This algorithm efficiently utilizes the distribution characteristics of traffic flows. In small memory space, large flows can be identified accurately. Because the flow entries get more opportunities to reside in SRAM, the arriving packets can be processed rapidly. No more memory space is needed for more arriving traffic data, so the algorithm is scalable.

Important Links:

Go Back