Branch tire packet classification algorithm based on single-linkage clustering

Xia-an Bi, Xianhao Luo and Qi Sun

Mathematics and Computers in Simulation (MATCOM), 2019, vol. 155, issue C, 78-91

Abstract: As the core of network devices is the packet classification technology, the performance influences the development of computer networks. Therefore, researches on the packet classification are of principal theoretical and practical significance. This paper presents a branch trie packet classification algorithm based on the single-linkage clustering (BTSLC). The algorithm includes the preprocessing stage and the matching stage. In the preprocessing stage, packets and rules are firstly mapped to rectangular areas in the two-dimensional space by the formalization method. Then the single-linkage algorithm is used to cluster the formalized rules. In the matching stage, a branch trie is firstly constructed then the matching process is followed. The structure of the branch trie in the algorithm not only wipes out the backtracking by employing the trie path compression but also solves the trie update inefficient problem, which would enhance the performance of the algorithm to a large extent. Finally, the simulation experiments and the actual environmental experiments are carried out to evaluate our algorithm’s performances, and some algorithms are used as the comparison groups. The experimental findings indicate that our algorithm has better performance in the searching speed, memory requirement and rule update.

Keywords: Packet classification; Clustering; Single-linkage; Branch trie (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475417303713
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:155:y:2019:i:c:p:78-91

DOI: 10.1016/j.matcom.2017.11.003

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().