Skip to main navigation Skip to search Skip to main content

Weighted Binary Search Tree to NDN Name Lookup

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original languageEnglish
Title of host publication2026 International Conference on Electronics, Information, and Communication, ICEIC 2026
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798331580773
DOIs
StatePublished - 2026
Event2026 International Conference on Electronics, Information, and Communication, ICEIC 2026 - Macau, China
Duration: 18 Jan 2026 → 21 Jan 2026

Publication series

Name2026 International Conference on Electronics, Information, and Communication, ICEIC 2026

Conference

Conference2026 International Conference on Electronics, Information, and Communication, ICEIC 2026
Country/TerritoryChina
CityMacau
Period18/01/26 → 21/01/26

Bibliographical note

Publisher Copyright:
© 2026 IEEE.

Fingerprint

Dive into the research topics of 'Weighted Binary Search Tree to NDN Name Lookup'. Together they form a unique fingerprint.

Cite this