Lingyue Fu, Hao Guan, Bolun Zhang, Haowei Yuan, Yaoming Zhu, Lin Qiu, ZongYu Wang, Xuezhi Cao, Xunliang Cai, Weiwen Liu, Weinan Zhang, Yong Yu. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Name-based forwarding is a core component in information-centric networks. Designing scalable name-based forwarding solutions is challenging because name prefixes are of variable length and the forwarding tables can be much longer than seen with IP. Recently, the speculative forwarding method has been proposed, in which the forwarding structure size is proportional to the information-theoretic differences between the name prefixes rather than their lengths. In this paper, our goal is to enhance name-based forwarding performance with memory-and time-efficient data structures. We first define the string differentiation problem, based on the behavior of speculative forwarding in core networks, and then propose fingerprint-based solutions for both trie-based and hash table-based data structures. We experimentally demonstrate that the proposed solutions reduce the lookup latency and memory requirements. The proposed fingerprint-based Patricia trie decreases the average leaf-node depth and thus reduces the lookup latency. The proposed fingerprint-based hash table design requires only 3.2 GB of memory to store 1 billion names where each name has only one name component, and the measured lookup latency of the software-based single-threaded implementation is 0.29 microseconds. What's more, the distributed forwarding scheme presented in this paper makes name-based forwarding truly scalable.

Collapsed forwarding has long been used in cache systems to reduce the load on servers by aggregating requests for the same content. Named Data Networking (NDN) as a future Internet architecture incorporates this technique through a data structure called Pending Interest Table (PIT). The request aggregation feature suggests that PIT can be viewed as a nonreset time-to-live (TTL) based cache. The Content Store (CS) is a content cache placed in front of the PIT on the NDN forwarding path, so they make up a tandem cache network. To investigate the metrics of interest in this network, like the hit probability for the PIT and the CS, the expected PIT size, non-zero download delay (non-ZDD) should be taken into consideration. Caching policies usually assume zero download delay (ZDD), i.e., request and object arrive simultaneously, and numerous analytical methods have been proposed to study the ZDD caching policies. In this paper, after dissecting the LRU policy, we for the first time propose two LRU variants considering non-ZDD by defining separate operations for the request and object arrivals. When CS adopts the proposed LRU variants, the analysis of the CS-PIT network can still take advantage of the existing models, so the metrics of interest can be computed. Especially, the distribution for the “inter-miss” time of this network can be derived, which has not been achieved by prior works. Finally, the analytical results are verified through simulations.

Name prefix lookup is a core building block of information-centric networking (ICN). In ICN hierarchical naming schemes, each packet has a name that consists of multiple variable-length name components, and packets are forwarded based on longest name prefix matching (LNPM). LNPM is challenging because names are longer than IP addresses and the namespace is unbounded. Recently proposed solutions have shown encouraging performance, however, most are optimized for or evaluated with a limited number of URL datasets that may not fully characterize the forwarding information base (FIB).What's more, the worst-case scenarios of several schemes require O(k) string lookups, where k is the number of components in each prefix. Thus, the sustained performance of existing solutions is not guaranteed. In this paper, we present a LNPM design based on the binary search of hash tables, which was originally proposed for IP lookup. With this design, the worst-case number of string lookups is O(log(k)) for prefixes with up to k components, regardless of the characteristics of the FIB. We implemented the design in software and demonstrated 10 Gbps throughput with one billion synthetic longest name prefix matching rules, each containing up to seven components. We also propose level pulling to optimize the average LNPM performance based on the observation that some prefixes have large numbers of next-level suffixes in the available URL datasets.

Named Data Networking (NDN) routers can cache previously forwarded Data packets, and those can be reused when a matching Interest packet arrives. Unlike traditional IP routers and HTTP caches that exist as separate devices, designing a scalable NDN router is a new challenge because it should perform fast forwarding and massive-scale caching at the same time. This paper proposes a design of an NDN router with unique forwarding and caching mechanisms featuring terabyte-scale caching with solid-state drives (SSD) while still forwarding packets at line speed.

A Pending Interest Table (PIT) is a core component in Named Data Networking. Scalable PIT design is challenging because it requires per-packet updates, and the names stored in the PIT are long, requiring more memory. As the line speed keeps increasing, e.g., 100 Gbps, traditional hash-table based methods cannot meet these requirements. In this paper, we propose a novel Pending Interest Table design that guarantees packet delivery with a compact and approximate storage representation. To achieve this, the PIT stores fixed-length fingerprints instead of name strings. To overcome the classical fingerprint collision problem, the Interest aggregation feature in the core routers is relaxed. The memory requirement and network traffic overhead are analyzed, and the performance of a software implementation of the proposed design is measured. Our results show that 37 MiB to 245 MiB are required at 100 Gbps, so that the PIT can fit into SRAM or RLDRAM chips.

Content distribution is a primary activity on the Internet. Name-centric network architectures support content distribution intrinsically. Named Data Networking (NDN), one recent such scheme, names packets rather than end-hosts, thereby enabling packets to be cached and redistributed by routers. Among alternative name-based systems, HTTP is the most significant by any measure. A majority of today's content distribution services leverage the widely deployed HTTP infrastructure, such as web servers and caching proxies. As a result, HTTP can be viewed as a practical, name-based content distribution solution. Of course, NDN and HTTP do not overlap entirely in their capabilities and design goals, but both support name-based content distribution. This paper presents an experimental performance evaluation of NDN-based and HTTP-based content distribution solutions. Our findings verify popular intuition, but also surprise in some ways. In wired networks with local-area transmission latencies, the HTTP-based solution dramatically outperforms NDN, with roughly 10× greater sustained throughput. In networks with lossy access links, such as wireless links with 10% drop rates, or with non-local transmission delays, due to faster link retransmission brought by architectural advantages of NDN, the situation reverses and NDN outperforms HTTP, with sustained throughput increased by roughly 4× over a range of experimental scenarios.

Named Data Networking (NDN) is a recently proposed general- purpose network architecture that leverages the strengths of Internet architecture while aiming to address its weaknesses. NDN names packets rather than end-hosts, and most of NDN's characteristics are a consequence of this fact. In this paper, we focus on the packet forwarding model of NDN. Each packet has a unique name which is used to make forwarding decisions in the network. NDN forwarding differs substantially from that in IP; namely, NDN forwards based on variable-length names and has a read-write data plane. Designing and evaluating a scalable NDN forwarding node architecture is a major effort within the overall NDN research agenda. In this paper, we present the concepts, issues and principles of scalable NDN forwarding plane design. The essential function of NDN forwarding plane is fast name lookup. By studying the performance of the NDN reference implementation, known as CCNx, and simplifying its forwarding structure, we identify three key issues in the design of a scalable NDN forwarding plane: 1) exact string matching with fast updates, 2) longest prefix matching for variable-length and unbounded names and 3) large- scale flow maintenance. We also present five forwarding plane design principles for achieving 1 Gbps throughput in software implementation and 10 Gbps with hardware acceleration.

The recently proposed Named Data Networking (NDN) architecture and the widely deployed HTTP infrastructure both support content distribution in a name-centric fashion. In this paper, we evaluated the content distribution performance of NDN-based and HTTP-based content distribution solutions.

URL matching is used in many network applications, including URL blacklisting, URL-based forwarding and URL shortening services. These applications need fast URL queries and updates, thus requiring an efficient updateable data structure. As the processing power of general-purpose multi-core processors increases, software-based approaches are better able to meet the speed requirements of URL matching. In this paper, we present our preliminary performance study of finite-automata- and hash-based URL matching implementations on commodity PCs. The impacts of the cache and memory allocation methods are discussed.

We describe the implementation of a URL-based forwarding function on a network processor-based programmable router (NPR). URL-based forwarding is an important tool for overlay networks. This paper presents a data path for overlay networks and the effectiveness of a programmable router.

Network applications often require large data storage resources, fast queries, and frequent updates. Hash tables support these operations with low costs, yet they cannot provide worst-case guarantees because of hash collisions. Also, the widely used, low-cost Dynamic Random Access Memory (DRAM) cannot suitably accommodate hash tables because DRAMs provide full bandwidth only if accessed in bursts, whereas hash tables require random access. In this paper, we propose a hash co-processor to support hash tables on DRAMs. The co-processor provides a load-balancing method to reduce the impact of hash collisions on the worst-case behavior by moving multiple keys within the hash table in constant time. This leads to a balanced distribution of keys in the hash table despite the collisions. Furthermore, the coprocessor guarantees the full DRAM bandwidth is always utilized by defining all fundamental hash table operations, namely insert, query, and delete, in terms of burst accesses. In the worst case, the query, delete, and insert operations take one, two, and three burst accesses, respectively. The proposed architecture reduces hash overflows by 35% compared to a naive hash table and for each key uses 6.42 bits of on-chip memory.