Beyond bloom filters: from approximate membership checks to approximate state machines

ABSTRACT

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.

REFERENCES

• 1: E. Amir, S. McCanne. M. Vitterli. A Layered DCT coder for Internet Video. In Proc. IEEE International Conference on Image Processing Lausanne, Switzerland, Sept 1996.
• 2: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 3: A. Broder and M. Mitzenmacher. Using multiple hash functions to improve IP Lookups. In Proceedings of IEEE INFOCOM pp. 1454--1463, 2001.
• 4: A. Broder and M. Mitzenmacher. Network applications of Bloom filters: A survey. Internet Mathematics 1(4):485--509, 2004.
• 5: Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , Ayellet Tal, The Bloomier filter: an efficient data structure for static support lookup tables, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 6: F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese. An Improved Construction for Counting Bloom Filters. To appear in the 2006 European Symposium on Algorithms.
• 7: S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood. Deep Packet Inspection using Parallel Bloom Filters. In IEEE Hot Interconnects 12 Stanford, CA, August 2003. IEEE Computer Society Press.
• 8: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 9: D. Forsgren, U. Jennehag. P. Osterberg, Objective Endtoend QoS Gain from Packet Prioritization and Layering in MPEG-2 streaming video. At http://amp.ece.cmu.edu/packetvideo2002/papers/61-ananhseors.pdf
• 10: Thomas Karagiannis , Andre Broido , Michalis Faloutsos , Kc claffy, Transport layer identification of P2P traffic, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028804]
• 11: Thomas Karagiannis , Konstantina Papagiannaki , Michalis Faloutsos, BLINC: multilevel traffic classification in the dark, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 12: A. Kirsch and M. Mitzenmacher. Simple Summaries for Hashing with Multiple Choices. In Proc. of the Forty-Third Annual Allerton Conference 2005.
• 13: Y. Lu, B. Prabhakar, and F. Bonomi. Bloom Filters: Design Innovations and Novel Applications. In Proc. of the Forty-Third Annual Allerton Conference 2005.
• 14: Steven Ray Mccanne , Martin Vetterli, Scalable compression and transmission of internet multicast video, 1996
• 15: Michael Mitzenmacher, Compressed bloom filters, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.604-612, October 2002 [doi>10.1109/TNET.2002.803864]
• 16: Michael Mitzenmacher , Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, New York, NY, 2005
• 17: Anna Pagh , Rasmus Pagh , S. Srinivasa Rao, An optimal Bloom filter replacement, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 18: A. Romanow and S. Floyd. Dynamics of TCP Traffic over ATM Networks. IEEE Journal on Selected Areas in Communications 13(4):633--641 (1995).
• 19: Subhabrata Sen , Oliver Spatscheck , Dongmei Wang, Accurate, scalable in-network identification of p2p traffic using application signatures, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988742]
• 20: Haoyu Song , Sarang Dharmapurikar , Jonathan Turner , John Lockwood, Fast hash table lookup using extended bloom filter: an aid to network processing, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 21: Alex C. Snoeren , Craig Partridge , Luis A. Sanchez , Christine E. Jones , Fabrice Tchakountio , Beverly Schwartz , Stephen T. Kent , W. Timothy Strayer, Single-packet IP traceback, IEEE/ACM Transactions on Networking (TON), v.10 n.6, p.721-734, December 2002 [doi>10.1109/TNET.2002.804827]
• 22: Tektronix FTP site, ftp://ftp.tek.com/tv/test/streams/Element/MPEG-Video/625/
• 23: K. Thomson, G. J. Miller, and R. Wilder. Wide-area traffic patterns and characteristics. IEEE Network December 1997.
• 24: Berthold Vöcking, How Asymmetry Helps Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.131, October 17-18, 1999

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

General Terms:
Algorithms, Design, Measurement

Keywords:
bloom filters, network flows, state machines