TY - JOUR
T1 - An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
AU - Lee, Chun Liang
AU - Lin, Guan Yu
AU - Chen, Yaw Chung
N1 - Publisher Copyright:
© 2022 by the authors. Licensee MDPI, Basel, Switzerland.
PY - 2022/7
Y1 - 2022/7
N2 - 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.
AB - 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.
KW - GPU
KW - conflict detection
KW - packet classification
UR - http://www.scopus.com/inward/record.url?scp=85133794597&partnerID=8YFLogxK
U2 - 10.3390/a15070237
DO - 10.3390/a15070237
M3 - 文章
AN - SCOPUS:85133794597
SN - 1999-4893
VL - 15
JO - Algorithms
JF - Algorithms
IS - 7
M1 - 237
ER -