Efficient Lookup Scheme for Non-aggregatable Name Prefixes and Its Evaluation


IEICE TRANSACTIONS on Communications   Vol.E96-B   No.12   pp.2953-2963
Publication Date: 2013/12/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.2953
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Network and System Technologies for Sustainable Society)
CCN,  forwarding,  FIB,  longest prefix match,  

Full Text: FreePDF

Content-Centric Networking (CCN) employs a hierarchical but location independent content naming scheme. While such a location independent naming brings various benefits including efficient content delivery, mobility, and multihoming, location independent name prefixes are hard to aggregate. This poses a serious scaling issue on the efficiency of looking up content names in a huge Forwarding Information Base (FIB) by longest prefix matching, which requires seeking the longest matching prefix through all candidate prefix lengths. We propose a new scheme for efficiently looking up non-aggregatable name prefixes in a large FIB. The proposed scheme is based on the observation that the bottleneck of FIB lookup is the random accesses to the high-latency off-chip DRAM for prefix seeking and this can be reduced by exploiting the information on the longest matching prefix length in the previous hop. Our evaluation results show that the proposed scheme significantly improves FIB lookup latency with a reasonable traffic parameters observed in today's Internet.