Scalable packet classification

ABSTRACT

Packet classification is important for applications such as firewalls, intrusion detection, and differentiated services. Existing algorithms for packet classification reported in the literature scale poorly in either time or space as filter databases grow in size. Hardware solutions such as TCAMs do not scale to large classifiers. However, even for large classifiers (say 100,000 rules), any packet is likely to match a few (say 10) rules. Our paper seeks to exploit this observation to produce a scalable packet classification scheme called Aggregated Bit Vector (ABV). Our paper takes the bit vector search algorithm (BV) described in [11] (which takes linear time) and adds two new ideas, recursive aggregation of bit maps and filter rearrangement, to create ABV (which can take logarithmic time for many databases). We show that ABV outperforms BV by an order of magnitude using simulations on both industrial firewall databases and synthetically generated databases.

REFERENCES

• 1: IETF - Differentiated Services (di .serv)Working Group http://www.ietf.org/html.charters/diffservcharter.html.
• 2: Cisco - ArrowPoint Communications . http://www.arrowpoint.com,2000.
• 3: IPMA Statistics. MeritInc.- http://nic.merit.edu/ipma, 2000.
• 4: Memory-memory. http://www.memorymemory.com, 2000.
• 5: Florin Baboescu , George Varghese, Aggregated Bit Vector Search Algorithms for Packet Filter Lookups, University of California at San Diego, La Jolla, CA, 2001
• 6: G.Banga,J.C.Mogul,and P.Druschel.A scalable and explicit event delivery echanism for UNIX.In Proc.USENIX Annual T chnical Conf.,June 1999.
• 7: Milind M. Buddhikot , Subhash Suri , Marcel Waldvogel, Space Decomposition Techniques for Fast Layer-4 Switching, Proceedings of the IFIP TC6 WG6.1 & WG6.4 / IEEE ComSoc TC on on Gigabit Networking Sixth International Workshop on Protocols for High Speed Networks VI, p.25-42, August 25-27, 1999
• 8: A.Feldman and S.Muthukrishnan.Tradeoffs for packet classi .cation.In Proc.Infocom ,vol.1,pages 397 - 413,March 2000.
• 9: Pankaj Gupta , Nick McKeown, Packet classification on multiple fields, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.147-160, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 10: P.Gupta and N.McKeown.Packet classi .cation using hierarchical intelligent cuttings.In Proc.Hot Interconnects VII ,Aug.1999.
• 11: T. V. Lakshman , D. Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.203-214, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 12: Robert Morris , Eddie Kohler , John Jannotti , M. Frans Kaashoek, The Click modular router, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.217-231, December 12-15, 1999, Charleston, South Carolina, United States
• 13: Marcel Waldvogel , George Varghese , Jon Turner , Bernhard Plattner, Scalable high speed IP routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.25-36, September 14-18, 1997, Cannes, France
• 14: C.Partridge.Locality and route caches.In Proc.of NSF Workshop,Internet Statistics Measurement and Analysis ,Feb.1999.
• 15: V. Srinivasan , G. Varghese , S. Suri , M. Waldvogel, Fast and scalable layer four switching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.191-202, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 16: V. Srinivasan , S. Suri , G. Varghese, Packet classification using tuple space search, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.135-146, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 17: J.Xu,M.Singhal,and J.Degroat.A novel cache architecture to support layer-four packet classi .cation at memory access speeds.In Proc.Infocom ,March 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications; Distributed networks
          Nouns: Internet

General Terms:
Design, Experimentation, Performance