TB2F: Tree-bitmap and bloom-filter for a scalable and efficient name lookup in Content-Centric Networking
Wei Quan, Changqiao Xu, Athanasios V. Vasilakos, Jianfeng Guan, Hongke Zhang, Luigi Alfredo Grieco · 2014
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 TB2F), 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 TB2F 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.