• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Prefix Cuttings for Packet Classification with Fast Updates

Vol. 8, No.4, April 29, 2014
10.3837/tiis.2014.04.016, Download Paper (Free):

Abstract

Packet classification is a key technology of the Internet for routers to classify the arriving packets into different flows according to the predefined rulesets. Previous packet classification algorithms have mainly focused on search speed and memory usage, while overlooking update performance. In this paper, we propose PreCuts, which can drastically improve the update speed. According to the characteristics of IP field, we implement three heuristics to build a 3-layer decision tree. In the first layer, we group the rules with the same highest byte of source and destination IP addresses. For the second layer, we cluster the rules which share the same IP prefix length. Finally, we use the heuristic of information entropy-based bit partition to choose some specific bits of IP prefix to split the ruleset into subsets. The heuristics of PreCuts will not introduce rule duplication and incremental update will not reduce the time and space performance. Using ClassBench, it is shown that compared with BRPS and EffiCuts, the proposed algorithm not only improves the time and space performance, but also greatly increases the update speed.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Weitao Han, Peng Yi and Le Tian, "Prefix Cuttings for Packet Classification with Fast Updates," KSII Transactions on Internet and Information Systems, vol. 8, no. 4, pp. 1442-1462, 2014. DOI: 10.3837/tiis.2014.04.016

[ACM Style]
Han, W., Yi, P., and Tian, L. 2014. Prefix Cuttings for Packet Classification with Fast Updates. KSII Transactions on Internet and Information Systems, 8, 4, (2014), 1442-1462. DOI: 10.3837/tiis.2014.04.016