TB2F: Tree-bitmap and bloom-filter for a scalable and efficient name lookup in Content-Centric Networking

Content-Centric Networking (CCN) is an entirely novel networking paradigm, in which packet forwarding relies upon lookup operations on content names directly instead of fixed-length host addresses. The unique features of CCN names, i.e., variable length, huge cardinality, and hierarchical structure, introduce new challenges that could hinder the deployment of such a new architecture at the Internet scale. In this paper, we make an in-depth study of characteristics of large-scale CCN names, and propose a simple yet efficient CCN-customized name lookup engine (named by TB²F), which capitalizes the strengths of Tree-Bitmap (TB) and Bloom-Filter (BF) mechanisms, while counteracts their main limitations. To this end, TB2F splits CCN prefix into a constant size T-segment and a variable length B-segment with a relative short length, which are treated using TB and BF, respectively. Furthermore, an optimal length of the T-segment is found to improve the lookup efficiency. Experimental comparisons with respect to the reference Name Prefix-Trie and Bloom-Hash have been also carried out. The results show that TB² F properly configured has good scalability and efficiency by (i) speeding up lookup operations and reducing the false positive rate with respect to Bloom-Hash; (ii) requiring less memory than Name Prefix-Trie; (iii) achieving a low overhead in updating operations in the large scale case.