H‐LCFST: a hash lowest cost first search tree for flexible packet classification

Xiaohong Huang, Qiong Sun, Maode Ma and Yan Ma

International Journal of Network Management, 2016, vol. 26, issue 4, 286-307

Abstract: Packet classification (PC) categorizes incoming packets into multiple forwarding classes in a router based on predefined filters. It is one of the most important enabling technologies for next generation network services, for example, firewall, quality of service routing, load balancing, and virtual private network. IPv6 technology has posed a great challenge on the wire‐speed router for the PC because of its longer IP addresses. In this paper, we propose a new algorithm to support both IPv4 and IPv6, called hash lowest cost first search tree (H‐LCFST) for the PC. The H‐LCFST combines the advantages of the hash tree and a novel LCFST to achieve a better lookup performance. More important, the H‐LCFST algorithm is able to utilize the features of distinct IPv4 and IPv6 classifiers and design corresponding data structure for different characteristics of the classifiers, with which it is able to avoid the performance degrade because of the longer address of the IPv6. The experiment results show that our proposed algorithm has only approximately seven times of memory accesses for the IPv4/IPv6 PC, which make it to be the fastest PC solutions so far. Moreover, it occupies extremely small memory and supports incremental update at the same time. Copyright © 2016 John Wiley & Sons, Ltd.

Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nem.1938

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:wly:intnem:v:26:y:2016:i:4:p:286-307

Access Statistics for this article

More articles in International Journal of Network Management from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().