| Title |
Weighted Binary Search Tree for NDN Lookup |
| Authors |
김규빈(Gyubin Kim) ; 임혜숙(Hyesook Lim) |
| DOI |
https://doi.org/10.5573/ieie.2026.63.8.3 |
| Keywords |
Named 이Data Networking (NDN); Name Prefix Trie (NPT); Binary Search Tree (BST); Weighted Binary Search Tree (WBST) |
| Abstract |
Today’s IP-based host-centric routing paradigm suffers from inefficiencies in large-scale content deliveries and repetitive traffic transmissions. Even when the same data is repeatedly requested by multiple users, it should be transmitted from the origin server each time, leading to increased network latency and congestion. Named Data Networking (NDN) has emerged as a promising future Internet architecture to address these issues by forwarding packets based on data names rather than IP addresses, while enabling in-network caching and data-centric security. These features provide reduced latency and improved robustness, particularly in highly dynamic or intermittently connected environments. However, one of the core operations inside NDN routers, Longest Name Prefix Matching (LNPM), becomes inefficient when implemented using the conventional Name Prefix Trie (NPT) structure. As the tree depth grows linearly with the number of name components, numerous empty internal nodes and frequent off-chip memory accesses significantly increase lookup cost. To mitigate structural bias and reduce memory access overhead, this study explores a name-based Weighted Binary Search Tree (nWBST) lookup structure. The proposed nWBST adopts a new structure based on half-weight pivot rule, in which the prefix list is sorted in a specialized lexicographic order and the first prefix whose cumulative weight exceeds half of the total weight is selected as the pivot, thereby recursively balancing the weights of the left and right sub-trees. This structure suppresses the expected search depth even under skewed name distributions and minimizes the average number of memory accesses, ultimately enabling the LNPM function, which is directly tied to network performance, to operate stably at line rate. |