Two-Dimensional Binary Search on Length Using Bloom Filter for Packet Classification 


Vol. 37,  No. 4, pp. 245-257, Apr.  2012


PDF
  Abstract

As one of the most challenging tasks in designing the Internet routers, packet classification is required to achieve the wire-speed processing for every incoming packet. Packet classification algorithm which applies binary search on trie levels to the area-based quad-trie is an efficient algorithm. However, it has a problem of unnecessary access to a hash table, even when there is no node in the corresponding level of the trie. In order to avoid the unnecessary off-chip memory access, we proposed an algorithm using Bloom filters along with the binary search on levels to multiple disjoint tries. For ACL, FW, IPC sets with about 1000, 5000, and 10000 rules, performance evaluation result shows that the search performance is improved by 21 to 33 percent by adding Bloom filters.

  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]

Y. Choe and H. Lim, "Two-Dimensional Binary Search on Length Using Bloom Filter for Packet Classification," The Journal of Korean Institute of Communications and Information Sciences, vol. 37, no. 4, pp. 245-257, 2012. DOI: .

[ACM Style]

Youngju Choe and Hyesook Lim. 2012. Two-Dimensional Binary Search on Length Using Bloom Filter for Packet Classification. The Journal of Korean Institute of Communications and Information Sciences, 37, 4, (2012), 245-257. DOI: .

[KICS Style]

Youngju Choe and Hyesook Lim, "Two-Dimensional Binary Search on Length Using Bloom Filter for Packet Classification," The Journal of Korean Institute of Communications and Information Sciences, vol. 37, no. 4, pp. 245-257, 4. 2012.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880