A Packet Classification Method via Cascaded Circular-Run-Based Trie
Summary :
The packet classification problem to determine the behavior of incoming packets at the network devices. The processing latency of packet classification by linear search is proportional to the number of classification rules. To limit the latency caused by classification to a certain level, we should develop a classification algorithm that classifies packets in a time independent of the number of classification rules. Arbitrary (including noncontiguous) bitmask rules are efficiently expressive for controlling higher layer communication, achiving access control lists, Quality of Service and so on. In this paper, we propose a classification algorithm based on run-based trie [1] according to arbitrary bitmask rules. The space complexity of proposed algorithm is in linear in the size of a rule list. The time complexity except for construction of that can be regarded as constant which is independent the number of rules. Experimental results using a packet classification algorithm benchmark [2] show that our method classifies packets in constant time independent of the number of rules.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1171-1178
- Publication Date
- 2019/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.1171
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Classification
Authors
Takashi HARADA
Kochi University of Technology
Yuki ISHIKAWA
Suzuki Motor Corporation
Ken TANAKA
Kanagawa University
Kenji MIKAWA
Niigata University
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
Takashi HARADA, Yuki ISHIKAWA, Ken TANAKA, Kenji MIKAWA, "A Packet Classification Method via Cascaded Circular-Run-Based Trie" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1171-1178, September 2019, doi: 10.1587/transfun.E102.A.1171.
Abstract: The packet classification problem to determine the behavior of incoming packets at the network devices. The processing latency of packet classification by linear search is proportional to the number of classification rules. To limit the latency caused by classification to a certain level, we should develop a classification algorithm that classifies packets in a time independent of the number of classification rules. Arbitrary (including noncontiguous) bitmask rules are efficiently expressive for controlling higher layer communication, achiving access control lists, Quality of Service and so on. In this paper, we propose a classification algorithm based on run-based trie [1] according to arbitrary bitmask rules. The space complexity of proposed algorithm is in linear in the size of a rule list. The time complexity except for construction of that can be regarded as constant which is independent the number of rules. Experimental results using a packet classification algorithm benchmark [2] show that our method classifies packets in constant time independent of the number of rules.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1171/_p
Copy
@ARTICLE{e102-a_9_1171,
author={Takashi HARADA, Yuki ISHIKAWA, Ken TANAKA, Kenji MIKAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Packet Classification Method via Cascaded Circular-Run-Based Trie},
year={2019},
volume={E102-A},
number={9},
pages={1171-1178},
abstract={The packet classification problem to determine the behavior of incoming packets at the network devices. The processing latency of packet classification by linear search is proportional to the number of classification rules. To limit the latency caused by classification to a certain level, we should develop a classification algorithm that classifies packets in a time independent of the number of classification rules. Arbitrary (including noncontiguous) bitmask rules are efficiently expressive for controlling higher layer communication, achiving access control lists, Quality of Service and so on. In this paper, we propose a classification algorithm based on run-based trie [1] according to arbitrary bitmask rules. The space complexity of proposed algorithm is in linear in the size of a rule list. The time complexity except for construction of that can be regarded as constant which is independent the number of rules. Experimental results using a packet classification algorithm benchmark [2] show that our method classifies packets in constant time independent of the number of rules.},
keywords={},
doi={10.1587/transfun.E102.A.1171},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - A Packet Classification Method via Cascaded Circular-Run-Based Trie
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1171
EP - 1178
AU - Takashi HARADA
AU - Yuki ISHIKAWA
AU - Ken TANAKA
AU - Kenji MIKAWA
PY - 2019
DO - 10.1587/transfun.E102.A.1171
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - The packet classification problem to determine the behavior of incoming packets at the network devices. The processing latency of packet classification by linear search is proportional to the number of classification rules. To limit the latency caused by classification to a certain level, we should develop a classification algorithm that classifies packets in a time independent of the number of classification rules. Arbitrary (including noncontiguous) bitmask rules are efficiently expressive for controlling higher layer communication, achiving access control lists, Quality of Service and so on. In this paper, we propose a classification algorithm based on run-based trie [1] according to arbitrary bitmask rules. The space complexity of proposed algorithm is in linear in the size of a rule list. The time complexity except for construction of that can be regarded as constant which is independent the number of rules. Experimental results using a packet classification algorithm benchmark [2] show that our method classifies packets in constant time independent of the number of rules.
ER -
English
