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

Bitmap-based Prefix Caching for Fast IP Lookup

Vol. 8, No. 3, March 30, 2014
10.3837/tiis.2014.03.009, Download Paper (Free):


IP address lookup is very crucial in performance of routers. Several works have been done on prefix caching to enhance the performance of IP address lookup. Since a prefix represents a range of IP addresses, a prefix cache shows better performance than an IP address cache. However, not every prefix is cacheable in itself. In a prefix cache it causes false hit to cache a non-leaf prefix because there is possibly the longer matching prefix in the routing table. Prefix expansion techniques such as complete prefix tree expansion (CPTE) make it possible to cache the non-leaf prefixes as the expanded forms, but it is hard to manage the expanded prefixes. The expanded prefixes sometimes incur a great deal of update overhead in a routing table. We propose a bitmap-based prefix cache (BMCache) to provide low update overhead as well as low cache miss ratio. The proposed scheme does not have any expanded prefixes in the routing table, but it can expand a non-leaf prefix using a bitmap on caching time. The trace-driven simulation shows that BMCache has very low miss ratio in spite of its low update overhead compared to other schemes.


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]
J. Kim, M. Ko, J. Nam, J. Kim, "Bitmap-based Prefix Caching for Fast IP Lookup," KSII Transactions on Internet and Information Systems, vol. 8, no. 3, pp. 873-889, 2014. DOI: 10.3837/tiis.2014.03.009.

[ACM Style]
Jinsoo Kim, Myeong-Cheol Ko, Junghyun Nam, and Junghwan Kim. 2014. Bitmap-based Prefix Caching for Fast IP Lookup. KSII Transactions on Internet and Information Systems, 8, 3, (2014), 873-889. DOI: 10.3837/tiis.2014.03.009.

[BibTeX Style]
@article{tiis:20476, title="Bitmap-based Prefix Caching for Fast IP Lookup", author="Jinsoo Kim and Myeong-Cheol Ko and Junghyun Nam and Junghwan Kim and ", journal="KSII Transactions on Internet and Information Systems", DOI={10.3837/tiis.2014.03.009}, volume={8}, number={3}, year="2014", month={March}, pages={873-889}}