A Study on Parallel Conflict Detection for Packet Filters Using Gpus

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 ID:PB10708-1624
External Project ID:MOST107-2221-E182-029