2-Dimensional Bitmap Tries for Fast Packet Classification 


Vol. 40,  No. 9, pp. 1754-1766, Sep.  2015


PDF
  Abstract

Packet classification carried out in Internet routers is one of the challenging tasks, because it has to be performed at wire-speed using five header fields at the same time. In this paper, we propose a leaf-pushed AQT bitmap trie. The proposed architecture applies the leaf-pushing to an area-based quad-trie (AQT) to reduce unnecessary off-chip memory accesses. The proposed architecture also applies a bitmap trie, which is a kind of multi-bit tries, to improve search performance and scalability. For performance evaluation, simulations are conducted by using rule sets ACL, FW, and IPC, with the sizes of 1k, 5k, and 10k. Simulation results show that the number of off-chip memory accesses is less than one regardless of set types or set sizes. Additionally, since the proposed architecture applies a bitmap trie, the required number of on-chip memory accesses is the 50% of the leaf-pushed AQT trie. In addition, our proposed architecture shows good scalability in the required on-chip memory size, where the scalability is identified by the stable change in the required memory sizes, as the size of rule sets increases.

  Statistics
Cumulative Counts from November, 2022
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]

J. Seo and H. Lim, "2-Dimensional Bitmap Tries for Fast Packet Classification," The Journal of Korean Institute of Communications and Information Sciences, vol. 40, no. 9, pp. 1754-1766, 2015. DOI: .

[ACM Style]

Ji-hee Seo and Hye-sook Lim. 2015. 2-Dimensional Bitmap Tries for Fast Packet Classification. The Journal of Korean Institute of Communications and Information Sciences, 40, 9, (2015), 1754-1766. DOI: .

[KICS Style]

Ji-hee Seo and Hye-sook Lim, "2-Dimensional Bitmap Tries for Fast Packet Classification," The Journal of Korean Institute of Communications and Information Sciences, vol. 40, no. 9, pp. 1754-1766, 9. 2015.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880