skip to main content
poster

Replication free rule grouping for packet classification

Published: 27 August 2013 Publication History

Abstract

Most recent works demonstrate that grouping methodology could bring significant reduction of memory usage to decision-tree packet classification algorithms, with insignificant impact on throughput. However, these grouping techniques can hardly eliminate rule-replication completely. This work proposes a novel rule grouping algorithm without any replication. At each space decomposition step, all rules projecting on the split dimension form the maximum number of non-overlapped ranges, which guarantees the modest memory usage and grouping speed. Evaluation shows that the proposed algorithm achieves comparable memory size with less pre-processing time.

References

[1]
J. Pettit, J. Gross, B. Pfaff, M. Casado and S. Crosby. "Virtual Switching in an Era of Advanced Edges", in Proc. of DC CAVES, 2010.
[2]
B. Vamanan, G. Voskuilen and T. Vijaykumar. "EffiCuts: Optimizing Packet Classification for Memory and Throughput", in Proc. of SIGCOMM, 2010.
[3]
J. Fong, X. Wang, Y. Qi, J. Li and W. Jiang. "ParaSplit: A Scalable Architecture on FPGA for Terabit Packet Classification," in Proc. of HOTI, 2012.
[4]
Y. Qi, L. Xu, B. Yang, Y. Xue and J. Li. "Packet Clas-sification Algorithms: From Theory to Practice", in Proc. of INFOCOM, 2009.

Cited By

View all
  • (2018)Hybrid firefly bat algorithm (HFBA)–based network security policy enforcement for PSAInternational Journal of Communication Systems10.1002/dac.374031:14Online publication date: 11-Jul-2018
  • (2018)Non‐dominated sorting particle swarm optimization (NSPSO) and network security policy enforcement for Policy Space AnalysisInternational Journal of Communication Systems10.1002/dac.355431:10Online publication date: Mar-2018
  • (2016)Efficient Network Security Policy Enforcement With Policy Space AnalysisIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2015.250240224:5(2926-2938)Online publication date: 1-Oct-2016
  • Show More Cited By

Index Terms

  1. Replication free rule grouping for packet classification

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM SIGCOMM Computer Communication Review
      ACM SIGCOMM Computer Communication Review  Volume 43, Issue 4
      October 2013
      595 pages
      ISSN:0146-4833
      DOI:10.1145/2534169
      Issue’s Table of Contents
      • cover image ACM Conferences
        SIGCOMM '13: Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM
        August 2013
        580 pages
        ISBN:9781450320566
        DOI:10.1145/2486001
      Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 27 August 2013
      Published in SIGCOMM-CCR Volume 43, Issue 4

      Check for updates

      Author Tags

      1. algorithms
      2. packet classification
      3. rule replication

      Qualifiers

      • Poster

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)45
      • Downloads (Last 6 weeks)4
      Reflects downloads up to 20 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2018)Hybrid firefly bat algorithm (HFBA)–based network security policy enforcement for PSAInternational Journal of Communication Systems10.1002/dac.374031:14Online publication date: 11-Jul-2018
      • (2018)Non‐dominated sorting particle swarm optimization (NSPSO) and network security policy enforcement for Policy Space AnalysisInternational Journal of Communication Systems10.1002/dac.355431:10Online publication date: Mar-2018
      • (2016)Efficient Network Security Policy Enforcement With Policy Space AnalysisIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2015.250240224:5(2926-2938)Online publication date: 1-Oct-2016
      • (2016)Efficient Network Security Policy Enforcement With Policy Space AnalysisIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2015.250240224:5(2926-2938)Online publication date: 1-Oct-2016

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media