ACM SIGCOMM Computer Communication Review · 2006 · 184 citations · 21 references
ComputingComputer EngineeringComputer ScienceFault ToleranceNetwork SecurityQueuing TheoryCongestion ControlHash FunctionsHash TablesQueueing SystemsState ManagementActive Queue ManagementBloom FiltersHashingSimulation AnalysisSimulation-based AnalysisState Machine DesignState Machine ModelsState Machines
Many networking applications require fast state lookups in a concurrent state machine,which tracks the state of a large number of flows simultaneously.We consider the question of how to compactly represent such concurrent state machines. To achieve compactness,we consider data structures for Approximate Concurrent State Machines (ACSMs)that can return false positives,false negatives,or a "don 't know "response.We describe three techniques based on Bloom filters and hashing,and evaluate them using both theoretical analysis and simulation.Our analysis leads us to an extremely efficient hashing-based scheme with several parameters that can be chosen to trade off space,computation,and the pact of errors.Our hashing approach also yields a simple alternative structure with the same functionality as a counting Bloom filter that uses much less space.We show how ACSMs can be used for video congestion control.Using an ACSM,a router can implement sophisticated Active Queue Management (AQM)techniques for video traffic (without the need for standards changes to mark packets or change video formats),with a factor of four reduction in memory compared to full-state schemes and with very little error.We also show that ACSMs show promise for real-time detection of P2P traffic.
21
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Network Applications of Bloom Filters: A Survey
Andrei Broder, Michael Mitzenmacher · Internet Mathematics · 2004 · 2K citations · Full text
Wide-area Internet traffic patterns and characteristics
Kevin Thompson, G.J. Miller, R. Wilder · IEEE Network · 1997 · 1.1K citations
Thomas Karagiannis, Konstantina Papagiannaki, Michalis Faloutsos · 2005 · 1K citations