Binary Search on Levels Using Bloom Filter for IPv6 Address Lookup 


Vol. 34,  No. 4, pp. 403-418, Apr.  2009


PDF
  Abstract

IP version 6 (IPv6) is a new IP addressing scheme that has 128-bit address space. IPv6 is proposed to solve the address space problem of IP version 4 (IPv4) which has 32-bit address space. For a given IPv6 routing set, if a forwarding table is built using a trie structure, the trie has a lot more levels than that for IPv4. Hence, for IPv6 address lookup, the binary search on trie levels would be more appropriate and give better search performance than linear search on trie levels. This paper proposes a new IPv6 address lookup algorithm performing binary search on trie levels. The proposed algorithm uses a Bloom filter in pre-filtering levels which do not have matching nodes, and hence it reduces the number of off-chip memory accesses. Simulation has been performed using actual IPv6 routing sets, and the result shows that an IPv6 address lookup can be performed with 1-3 memory accesses in average for a routing data set with 1096 prefixes.

  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]

K. H. Park and H. Lim, "Binary Search on Levels Using Bloom Filter for IPv6 Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 34, no. 4, pp. 403-418, 2009. DOI: .

[ACM Style]

Kyong Hye Park and Hyesook Lim. 2009. Binary Search on Levels Using Bloom Filter for IPv6 Address Lookup. The Journal of Korean Institute of Communications and Information Sciences, 34, 4, (2009), 403-418. DOI: .

[KICS Style]

Kyong Hye Park and Hyesook Lim, "Binary Search on Levels Using Bloom Filter for IPv6 Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 34, no. 4, pp. 403-418, 4. 2009.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880