An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts

Chun Liang Lee, Guan Yu Lin*, Yaw Chung Chen

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

1 Scopus citations

Abstract

Advanced network services, such as firewalls, policy-based routing, and virtual private networks, must rely on routers to classify packets into different flows based on packet headers and predefined filter tables. When multiple filters are overlapped, conflicts may occur, leading to ambiguity in the packet classification. Conflict detection ensures the correctness of packet classification and has received considerable attention in recent years. However, most conflict-detection algorithms are implemented on a conventional central processing unit (CPU). Compared with a CPU, a graphics processing unit (GPU) exhibits higher computing power with parallel computing, hence accelerates the execution speed of conflict detection. In this study, we employed a GPU to develop two efficient algorithms for parallel conflict detection: the general parallel conflict-detection algorithm (the GPCDA) and the enhanced parallel conflict-detection algorithm (the EPCDA). In the GPCDA, we demonstrate how to perform conflict detection through parallel execution on GPU cores. While in the EPCDA, we analyze the critical procedure in conflict detection as to reduce the number of matches required for each filter. In addition, the EPCDA adopts a workload balance method to enable load balancing of GPU execution threads, thereby significantly improving performance. The simulation results show that with the 100 K filter database, the GPCDA and the EPCDA execute conflict detection 2.8 to 13.9 and 9.4 to 33.7 times faster, respectively, than the CPU-based algorithm.

Original languageEnglish
Article number237
JournalAlgorithms
Volume15
Issue number7
DOIs
StatePublished - 07 2022

Bibliographical note

Publisher Copyright:
© 2022 by the authors. Licensee MDPI, Basel, Switzerland.

Keywords

  • GPU
  • conflict detection
  • packet classification

Fingerprint

Dive into the research topics of 'An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts'. Together they form a unique fingerprint.

Cite this