Scalable Measurement: Finding some Elephants in a Swarm of Ants

Cristian Estan and George Varghese
CS2001-0666
February 12, 2001

While the number of concurrent flows passing through backbone routers is large (more than 250,000), measurements show a small number of flows (say 10%) represent a large fraction of the traffic. Thus a desirable goal for a measurement algorithm at a backbone router is to identify (say) the top 10% of the flows using not much more than 10% of the memory needed to keep track of all flows. A similar goal would be to determine any flows that use more than (say) 1% of the link bandwidth (to catch hot spots) using only a small amount of high speed memory. Keeping state for each flow (to tell whether a flow is ``large'') is ruled out. Our paper describes an algorithm for identifying large flows using small memory and small per packet processing bounds. Our algorithm scales well even with increases in bandwidth and number of flows.


How to view this document


The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.


[ Search ]


NCSTRL
This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu