Weighted Binary Search Tree to NDN Name Lookup

The current Internet architecture based on IP addresses to identify routers and hosts is inefficient for large-scale content delivery. Named Data Networking (NDN), proposed as a future Internet architecture, enables efficient data dissemination through name-based data forwarding and in-network caching. A key challenge in realizing NDN lies in the fast processing of Longest Name Prefix Match (LNPM) operation for Forwarding Information Base (FIB), given variable-length hierarchical names. A Name Prefix Trie (NPT) conventionally used for name lookup results in increased trie depth and empty nodes as the number of name components increases, leading to inefficiencies in both memory usage and lookup latency. A Binary Search Tree (BST), which eliminates empty nodes by comparing the magnitudes of variable-length prefixes, encounters degraded lookup performance due to the structural imbalance of the tree. To address these limitations, this paper proposes a Weighted Binary Search Tree (WBST), which selects a pivot based on the cumulative weights of prefixes, where the weight of each prefix is derived from prefix nesting relationships. This enables balanced tree construction, and hence the average depth of the tree and lookup cost are reduced. Experimental results demonstrate that the proposed scheme outperforms both NPT and BST in terms of memory efficiency and lookup performance.