Name lookup is a core function of the Named Data Networking (NDN) forwarding plane. It performs a name-based longest prefix match lookup against a large amount of variable-length, hierarchical name prefixes. NDN name lookup suffers a scalability challenge and needs to satisfy three key requirements: high-speed lookups, low memory cost, and fast updates. However, no existing work satisfies these requirements. Hash-based linear search schemes achieve fast updates and low memory cost but not high-speed lookups. Binary search (BS) schemes achieve high-speed lookups but slow updates with high memory cost. In this paper, we propose CBS, a hash-based counting binary search scheme for scalable high-speed NDN name lookup. CBS achieves fast updates and low memory cost, while sustaining high-speed lookups. The key to CBS is using a counter for each slot in a hash table to keep track of the number of markers that direct a search to find longer matching prefixes. This design not only allows fast updates by incrementing and decrementing counters, but also reduces the additional memory cost. Our experimental results demonstrate that CBS outperforms BS in update throughput, memory cost, and lookup throughput.

Name prefix lookup is a core function in Named Data Networking (NDN). It is challenging to perform high-speed name-based longest prefix match lookups against a large amount of variable-length, hierarchical name prefixes in NDN. However, prior work concentrates on software-based name prefix lookup, and can't satisfy the scalability demands of high-speed lookups, low memory cost, and fast incremental updates. In this paper, we propose a hybrid approach to scalable name prefix lookup with hardware and software. We propose SACS, a shape and content search framework with ternary content addressable memories (TCAMs) and static random memory access memories (SRAMs). SACS aims to achieve high-speed lookups and low memory cost, while sustaining fast incremental updates. In SACS, a TCAM-based shape search module is first used to determine a subset of possible matching prefixes, and then a SRM-based content search module is used on the subset to find the longest matching prefix. For SACS, we propose a first shrinking least load algorithm to pack large amounts of shapes of name prefixes in a small TCAM. A shape of a name prefix is a sequence of its component lengths. We also propose a dual fingerprint-based hash table to improve the content search performance in SRAMs. Experimental results demonstrate that SACS outperforms state-of-the-art schemes by achieving up to 2.4X higher lookup throughput, up to 53% lower memory cost, and up to 96% higher insert throughput.

Regular expression (RegEx) matching is a core function of deep packet inspection in modern network devices. Previous TCAM-based RegEx matching algorithms a priori assume that a deterministic finite automaton (DFA) can be built for a given set of RegEx patterns. However, practical RegEx patterns contain complex terms like wildcard closure and repeat character, and it may be impossible to build a DFA with a reasonable number of states. This results in prior work to being infeasible in practice. Moreover, TCAM-based RegEx matching is required to scale to a large-scale set of RegEx patterns. In this paper, we propose a compressed finite automaton implementation called (CFA) for scalable TCAM-based RegEx matching. CFA is designed to reduce TCAM space by using three compression techniques: transition, character, and state compressions. Experiments on realistic RegEx pattern sets show CFA highly outperforms previous solutions in terms of TCAM space, matching throughput, and TCAM power consumption.

Bloom filters are space-efficient data structures for fast set membership queries. Counting Bloom Filters (CBFs) extend Bloom filters by allowing insertions and deletions to support dynamic sets. The performance of CBFs is critical for various applications and systems. This paper presents a novel approach to building a fast and accurate data structure called Multiple-Partitioned Counting Bloom Filter (MPCBF) that addresses large-scale data processing challenges. MPCBF is based on two ideas: reducing the number of memory accesses from k (for k hash functions) in the standard CBF to only one memory access in the basic MPCBF-1 case, and a hierarchical structure to improve the false positive rate. We also generalize MPCBF-1 to MPCBF-g to accommodate up to g memory accesses. Our simulation and implementation in MapReduce show that MPCBF outperforms the standard CBF in terms of speed and accuracy. Compared to CBF, at the same memory consumption, MPCBF significantly reduces the false positive rate by an order of magnitude, with a reduction of processing overhead by up to 85.9%.

This paper presents a novel offset encoding scheme for memory-efficient IP address lookup, called Offset Encoded Trie (OET). Each node in the OET contains only a next hop bitmap and an offset value, without the child pointers and the next hop pointers. Each traversal node uses the next hop bitmap and the offset value as two offsets to determine the location address of the next node to be searched. The on-chip OET is searched to find the longest matching prefix, and then the prefix is used as a key to retrieve the corresponding next hop from an off-chip prefix hash table. Experiments on real IP forwarding tables show that the OET outperforms previous multi-bit trie schemes in terms of the memory consumption. The OET facilitates the far more effective use of on-chip memory for faster IP address lookup.

With the rapid development of the network, deep packet inspection systems are faced with the challenge of high performance. On one hand, they try to reduce the memory consumption in the process of regular expression matching; on the other hand, they must provide a worst-case matching speed guarantee. The existing state merging finite automata algorithm reduces the number of states in the deterministic finite automata (DFA). But there are still a large amount of transitions. In this paper, we introduce a transition merging finite automata algorithm, which merges several transitions in the DFA, based on the state merging algorithm. The experiments show that the transition merging algorithm reduces the memory consumption by 15%~31% compared to the state merging algorithm, when compared to the original DFA, it reduces the memory consumption by 25%~42%. At the same time, the transition merging algorithm ensures the matching speed. It is a memory efficient regular expression matching algorithm.