PBC: Effective Prefix Caching for Fast Name Lookups

Zhang，Chuwen1; Feng，Yong1; Song，Haoyu2; Zhang，Beichuan3; Wang，Yi4,5; Wan，Ying1; Xu，Wenquan1; Liu，Bin1,5

2020-06-01

978-1-7281-6710-7

IFIP Networking 2020 Conference and Workshops, Networking 2020

440-448

22-26 June 2020

Paris, France

Name lookup based on the Longest Prefix Match (LPM) is a basic function in many network applications. Caching is usually used to speed up the lookups. However, caching prefixes for LPM has a unique challenge: one needs to guarantee a cached prefix is indeed the longest for correctness. To achieve this, existing solutions have to cache either the entire prefix triebranch or only the leaf nodes, which undermines cache utilization and thus reduce the hit ratio. In this paper, we propose PlusBitmap Caching (PBC), which associates a bitmap to each cached prefix to denote the existence or absence of any longer prefix in the main table. This bitmap not only guarantees the correctness of LPM lookup, but also minimizes the extra information stored in cache. Meanwhile, cache consistency for prefix updates can be efficiently maintained. Experimental results show that, compared with previous work, PBC increases cache hit ratio by 16% over a wide range of cache size, and exhibits a more steady performance when more non-leaf prefixes are hit or a prefix is hit by more different names. PBC is a general approach that can be applied to other LPM-based applications.

IP networks Memory management Data structures Scalability Throughput Time complexity

其他

英语

EI

20203609128466

2-s2.0-85090040332

Scopus

1.Department of Computer Science and Technology,Tsinghua University,China
2.Futurewei Technologies,United States
3.University of Arizona,United States
4.Southern University of Science and Technology,China
5.Peng Cheng Lab,Shenzhen,China

Zhang，Chuwen,Feng，Yong,Song，Haoyu,et al. PBC: Effective Prefix Caching for Fast Name Lookups[C],2020:440-448.