Fast Conflict Detection for Multi-Dimensional Packet Filters
To support advanced network services, Internet routers must perform packet classification based on a set of rules called packet filters. If two or more filters overlap, a filter conflict will occur and lead to ambiguity in packet classification. Further, it may affect network security or even the co...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-08-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/15/8/285 |
| _version_ | 1797411639958437888 |
|---|---|
| author | Chun-Liang Lee Guan-Yu Lin Yaw-Chung Chen |
| author_facet | Chun-Liang Lee Guan-Yu Lin Yaw-Chung Chen |
| author_sort | Chun-Liang Lee |
| collection | DOAJ |
| description | To support advanced network services, Internet routers must perform packet classification based on a set of rules called packet filters. If two or more filters overlap, a filter conflict will occur and lead to ambiguity in packet classification. Further, it may affect network security or even the correctness of packet routing. Hence, it is necessary to detect conflicts to avoid the above problems. In recent years, many conflict detection algorithms have been proposed, but most of them detect conflicts for only prefix fields (i.e., source/destination IP address fields) of filters. For greater practicality, conflict detection must include non-prefix fields such as source/destination IP port fields and the protocol field. In this study, we propose an efficient conflict detection algorithm for five-dimensional filters, which include both prefix and non-prefix fields. In the proposed algorithm, a tiny lookup table is created for quickly filtering out a large portion of non-conflicting filter pairs, thereby reducing the overall conflict detection time. Experimental results show that our algorithm reduces the detection time by 10% to 28% compared with other conflict detection algorithms for 20 K filter databases. More importantly, our algorithm can be used to extend any existing conflict detection algorithms for two-dimensional filters to support fast conflict detection for five-dimensional filters. |
| first_indexed | 2024-03-09T04:49:03Z |
| format | Article |
| id | doaj.art-9d3707b26579438ea54e0d50c4ea3dc5 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T04:49:03Z |
| publishDate | 2022-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-9d3707b26579438ea54e0d50c4ea3dc52023-12-03T13:12:25ZengMDPI AGAlgorithms1999-48932022-08-0115828510.3390/a15080285Fast Conflict Detection for Multi-Dimensional Packet FiltersChun-Liang Lee0Guan-Yu Lin1Yaw-Chung Chen2Department of Computer Science and Information Engineering, School of Electrical and Computer Engineering, College of Engineering, Chang Gung University, Taoyuan 33302, TaiwanDepartment of Computer Science, National Yang Ming Chiao Tung University, Hsinchu 30010, TaiwanDepartment of Computer Science, National Yang Ming Chiao Tung University, Hsinchu 30010, TaiwanTo support advanced network services, Internet routers must perform packet classification based on a set of rules called packet filters. If two or more filters overlap, a filter conflict will occur and lead to ambiguity in packet classification. Further, it may affect network security or even the correctness of packet routing. Hence, it is necessary to detect conflicts to avoid the above problems. In recent years, many conflict detection algorithms have been proposed, but most of them detect conflicts for only prefix fields (i.e., source/destination IP address fields) of filters. For greater practicality, conflict detection must include non-prefix fields such as source/destination IP port fields and the protocol field. In this study, we propose an efficient conflict detection algorithm for five-dimensional filters, which include both prefix and non-prefix fields. In the proposed algorithm, a tiny lookup table is created for quickly filtering out a large portion of non-conflicting filter pairs, thereby reducing the overall conflict detection time. Experimental results show that our algorithm reduces the detection time by 10% to 28% compared with other conflict detection algorithms for 20 K filter databases. More importantly, our algorithm can be used to extend any existing conflict detection algorithms for two-dimensional filters to support fast conflict detection for five-dimensional filters.https://www.mdpi.com/1999-4893/15/8/285conflict detectionfirewall policypacket classificationpacket filtersnetwork security |
| spellingShingle | Chun-Liang Lee Guan-Yu Lin Yaw-Chung Chen Fast Conflict Detection for Multi-Dimensional Packet Filters Algorithms conflict detection firewall policy packet classification packet filters network security |
| title | Fast Conflict Detection for Multi-Dimensional Packet Filters |
| title_full | Fast Conflict Detection for Multi-Dimensional Packet Filters |
| title_fullStr | Fast Conflict Detection for Multi-Dimensional Packet Filters |
| title_full_unstemmed | Fast Conflict Detection for Multi-Dimensional Packet Filters |
| title_short | Fast Conflict Detection for Multi-Dimensional Packet Filters |
| title_sort | fast conflict detection for multi dimensional packet filters |
| topic | conflict detection firewall policy packet classification packet filters network security |
| url | https://www.mdpi.com/1999-4893/15/8/285 |
| work_keys_str_mv | AT chunlianglee fastconflictdetectionformultidimensionalpacketfilters AT guanyulin fastconflictdetectionformultidimensionalpacketfilters AT yawchungchen fastconflictdetectionformultidimensionalpacketfilters |