skip to main content
10.1145/2486001.2491709acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
poster
Free access

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
  • (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
  • (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
  • Show More Cited By

Index Terms

  1. Replication free rule grouping for packet classification

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      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
      • 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
      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.

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 27 August 2013

      Check for updates

      Author Tags

      1. algorithms
      2. packet classification
      3. rule replication

      Qualifiers

      • Poster

      Conference

      SIGCOMM'13
      Sponsor:
      SIGCOMM'13: ACM SIGCOMM 2013 Conference
      August 12 - 16, 2013
      Hong Kong, China

      Acceptance Rates

      SIGCOMM '13 Paper Acceptance Rate 38 of 246 submissions, 15%;
      Overall Acceptance Rate 462 of 3,389 submissions, 14%

      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
      • (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
      • (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

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Login options

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media