An Efficient Conflict Detection Algorithm for Packet Filters
Summary :
Packet classification is essential for supporting advanced network services such as firewalls, quality-of-service (QoS), virtual private networks (VPN), and policy-based routing. The rules that routers use to classify packets are called packet filters. If two or more filters overlap, a conflict occurs and leads to ambiguity in packet classification. This study proposes an algorithm that can efficiently detect and resolve filter conflicts using tuple based search. The time complexity of the proposed algorithm is O(nW +s), and the space complexity is O(nW), where n is the number of filters, W is the number of bits in a header field, and s is the number of conflicts. This study uses the synthetic filter databases generated by Class-Bench to evaluate the proposed algorithm. Simulation results show that the proposed algorithm can achieve better performance than existing conflict detection algorithms both in time and space, particularly for databases with large numbers of conflicts.
- Publication
- IEICE TRANSACTIONS on Information Vol.E95-D No.2 pp.472-479
- Publication Date
- 2012/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E95.D.472
- Type of Manuscript
- Special Section PAPER (Special Section on Architectures, Protocols, and Applications for the Future Internet)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Chun-Liang LEE, Guan-Yu LIN, Yaw-Chung CHEN, "An Efficient Conflict Detection Algorithm for Packet Filters" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 2, pp. 472-479, February 2012, doi: 10.1587/transinf.E95.D.472.
Abstract: Packet classification is essential for supporting advanced network services such as firewalls, quality-of-service (QoS), virtual private networks (VPN), and policy-based routing. The rules that routers use to classify packets are called packet filters. If two or more filters overlap, a conflict occurs and leads to ambiguity in packet classification. This study proposes an algorithm that can efficiently detect and resolve filter conflicts using tuple based search. The time complexity of the proposed algorithm is O(nW +s), and the space complexity is O(nW), where n is the number of filters, W is the number of bits in a header field, and s is the number of conflicts. This study uses the synthetic filter databases generated by Class-Bench to evaluate the proposed algorithm. Simulation results show that the proposed algorithm can achieve better performance than existing conflict detection algorithms both in time and space, particularly for databases with large numbers of conflicts.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.472/_p
Copy
@ARTICLE{e95-d_2_472,
author={Chun-Liang LEE, Guan-Yu LIN, Yaw-Chung CHEN, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient Conflict Detection Algorithm for Packet Filters},
year={2012},
volume={E95-D},
number={2},
pages={472-479},
abstract={Packet classification is essential for supporting advanced network services such as firewalls, quality-of-service (QoS), virtual private networks (VPN), and policy-based routing. The rules that routers use to classify packets are called packet filters. If two or more filters overlap, a conflict occurs and leads to ambiguity in packet classification. This study proposes an algorithm that can efficiently detect and resolve filter conflicts using tuple based search. The time complexity of the proposed algorithm is O(nW +s), and the space complexity is O(nW), where n is the number of filters, W is the number of bits in a header field, and s is the number of conflicts. This study uses the synthetic filter databases generated by Class-Bench to evaluate the proposed algorithm. Simulation results show that the proposed algorithm can achieve better performance than existing conflict detection algorithms both in time and space, particularly for databases with large numbers of conflicts.},
keywords={},
doi={10.1587/transinf.E95.D.472},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - An Efficient Conflict Detection Algorithm for Packet Filters
T2 - IEICE TRANSACTIONS on Information
SP - 472
EP - 479
AU - Chun-Liang LEE
AU - Guan-Yu LIN
AU - Yaw-Chung CHEN
PY - 2012
DO - 10.1587/transinf.E95.D.472
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2012
AB - Packet classification is essential for supporting advanced network services such as firewalls, quality-of-service (QoS), virtual private networks (VPN), and policy-based routing. The rules that routers use to classify packets are called packet filters. If two or more filters overlap, a conflict occurs and leads to ambiguity in packet classification. This study proposes an algorithm that can efficiently detect and resolve filter conflicts using tuple based search. The time complexity of the proposed algorithm is O(nW +s), and the space complexity is O(nW), where n is the number of filters, W is the number of bits in a header field, and s is the number of conflicts. This study uses the synthetic filter databases generated by Class-Bench to evaluate the proposed algorithm. Simulation results show that the proposed algorithm can achieve better performance than existing conflict detection algorithms both in time and space, particularly for databases with large numbers of conflicts.
ER -
English
