Packet classification in large ISPs: design and evaluation of decision tree classifiers

ABSTRACT

Packet classification, although extensively studied, is an evolving problem. Growing and changing needs necessitate the use of larger filters with more complex rules. The increased complexity and size pose implementation challenges on current hardware solutions and drive the development of software classifiers, in particular, decision-tree based classifiers. Important performance measures for these classifiers are time and memory due to required high throughput and use of limited fast memory.We analyze Tier 1 ISP data that includes filters and corresponding traffic from over a hundred edge routers and thousands of interfaces. We provide a comprehensive view on packet classification in an operational network and glean insights that help us design more effective classification algorithms.We propose and evaluate decision tree classifiers with common branches. These classifiers have linear worst-case memory bounds and require much less memory than standard decision tree classifiers, but nonetheless, we show that on our data have similar average and worst-case time performance. We argue that common-branches exploit structure that is present in real-life data sets.We observe a strong Zipf-like pattern in the usage of rules in a classifier, where a very small number of rules resolves the bulk of traffic and most rules are essentially never used. Inspired by this observation, we propose traffic-aware classifiers that obtain superior average-case and bounded worst-case performance. Good average-case can boost performance of software classifiers that can be used in small to medium sized routers and are also important for traffic analysis and traffic engineering.

REFERENCES

• 1: Controlling network access with access control lists, 2004. http://cisco.com/univercd/cc/td/doc/product/lan/cat6000/mod_icn/fwsm/fwsm_2_2/fwsm_cfg/mngacl.pdf
• 2: F. Baboescu, S. Singh, and G Varghese. Packet classification for core routers: Is there an alternative to cams? In Proc. of IEEE Infocom 2003, 2003.
• 3: Florin Baboescu , George Varghese, Scalable packet classification, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.199-210, August 2001, San Diego, California, United States
• 4: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 5: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 6: G. Cheung and S. McCanne. Optimal routing table design for IP address lookups under memory constraints. In Proc. of IEEE Infocom 1999, 1999.
• 7: E. Cohen, A. Fiat, and H. Kaplan. Associative search in Peer to Peer networks: Harnessing latent semantics. In Proceedings of the IEEE INFOCOM'03 Conference, 2003.
• 8: Edith Cohen , Amos Fiat , Haim Kaplan, Efficient sequences of trials, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: N. G. Duffield, C. Lund, and M. Thorup. Learn more, sample less: control of volume and variance in network measurements. IEEE Transactions on Information Theory. to appear.
• 10: Uriel Feige , László Lovász , Prasad Tetali, Approximating Min-sum Set Cover, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.94-107, September 17-21, 2002
• 11: A. Feldmann and S. Muthukrishnan. Tradeoffs for packet classification. In Proc. of IEEE Infocom 2000, 2000.
• 12: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.257-270, August 28-September 01, 2000, Stockholm, Sweden
• 13: P. Gupta, S. Lin, and N. McKeown. Routing lookups in hardware at memory access speeds. In Proc. of IEEE Infocom 1998, 1998.
• 14: 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
• 15: P. Gupta and N. McKeown. Packet classification using hierarchical intelligent cuttings. In Proc. of Hot Interconnects, 1999.
• 16: P. Gupta and N. McKeown. Algorithms for packet classification. IEEE Network, 15, 2001.
• 17: P. Gupta, B. Prabhakar, and S. Boyd. Near optimal routing lookups with bounded worst-case performance. In Proc. of IEEE Infocom 2000, 2000.
• 18: 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
• 19: J. F. McMullen. Get secure with Cisco extended IP access control lists, 2001. http://techrepublic.com.com/5102-6265-1058307.html.
• 20: Fast Firewall Implementations for Software and Hardware-Based Routers, Proceedings of the Ninth International Conference on Network Protocols, p.241, November 11-14, 2001
• 21: Sumeet Singh , Florin Baboescu , George Varghese , Jia Wang, Packet classification using multidimensional cutting, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863980]
• 22: 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
• 23: V. Srinivasan , George Varghese, Faster IP lookups using controlled prefix expansion, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.1-10, June 22-26, 1998, Madison, Wisconsin, United States
• 24: 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
• 25: T. Woo. A modular approach for packet classfication: algorithms and results. In Proc. of IEEE Infocom 2000, 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
      C.2.6 Internetworking

General Terms:
Algorithms, Design, Management, Performance, Security

Keywords:
access control lists, decision trees, packet filtering, routing