A Study on Parallel Conflict Detection for Packet Filters Using Gpus

Project: National Science and Technology CouncilNational Science and Technology Council Academic Grants

Project Details


Advanced network services, such as firewalls, policy-based routing, and virtual private networks (VPNs), require routers to classify packets into different flows based on their header fields and pre-defined packet filters. When two or more filters overlap, a conflict may occur and lead to ambiguity in packet classification. There are two kinds of filter conflicts: subset conflict and overlapping conflict. In our previous work (supported by MOST 104-2221-E-182-005), we has analyzed the conditions that conflicts hold, the source IP and the destination IP address fields are first processed using the tuple space. Then, the remaining fields are encoded to speed up the processing. Through a pre-built lookup table, the time required to access the memory and operations can be significantly reduced. In this one-year research project, we plan to continue our research on conflict detection algorithms using graphic processing unit (GPU), which has a parallel processing power superior to that of central processing unit (CPU). In order to design a parallel conflict detection algorithm, we first analyze how conflict detection can be executed efficiently through parallelism, and propose a filtering mechanism that can reduce the number of comparisons for each filter. With the proposed filtering mechanism, each filter may experience different number of comparisons, resulting in imbalanced workload while performing parallel computing. Thus, we propose a scheme for workload balance so as to further improve the performance of parallel computing.

Project IDs

Project ID:PB10708-1624
External Project ID:MOST107-2221-E182-029
Effective start/end date01/08/1831/07/19


  • Packet classification
  • conflict detection
  • tuple space search
  • graphics processing unit
  • parallel computing


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.