FCTree: A Space Efficient FIB Data Structure for NDN Routers

摘要

Named Data Networking (NDN) is a future Internet architecture that replaces IP addresses with namespaces of contents that are searchable at the network layer. A challenging task for NDN routers is to manage forwarding-information bases (FIBs) that store next-hop routes to contents using their stored usually long names or name prefixes. In this paper, we propose FCTree, a compressed FIB data structure that significantly reduces the required storage space at the router and can efficiently meet the demands of having routes that are orders of magnitude larger than IP-based ones in conventional routing tables. FCTree employs a localized front-coding compression to buckets containing partitions of the routes. The top routes in these buckets are then organized in B-ary self-balancing trees. By adjusting the size of the buckets, the router can reach an optimal tradeoff between the latency of the longest prefix matching (LPM) operation and the FIB storage space. In addition, in contrast to existing hash and bloom-filter based solutions, the proposed FCTree structure can significantly reduce the latency required for range and wildcard searches (e.g., for latency sensitive streaming applications or network-layer search engines) where up to k routes are returned if they are prefixed by a requested name. Performance evaluation results demonstrate the significant space savings achieved by FCTree compared to traditional hash-based FIBs.