Search

As a key component in implementing Named Data Networking (NDN), Pending Interest Table (PIT) requires an efficient exact-matching algorithm for a scalable and fast PIT lookup. A Bloom filter (BF) is a memory-efficient data structure for performing exact matching operations. In this paper, three different BF-based PIT architectures are proposed: PIT using functional Bloom filters (FBF-PIT), PIT using counting Bloom filters with return values (rCBF-PIT), and a refined rCBF-PIT with signatures (R-rCBF-PIT). The proposed BF-based PITs incrementally allocate a new BF for storing multiple incoming faces of Interest packets with the same content name. For a Data packet lookup, the proposed PIT architectures simultaneously access every BF structure to find matching faces and delete the faces (i.e., matching Interest packet information). The functional Bloom filter (FBF) used in an FBF-PIT is a key-value data structure that stores values only without keys. However, because the number of non-reusable conflict cells in the FBF increases as the number of stored packets increases in the FBF-PIT, the indeterminable rate increases. To decrease the indeterminable rate, we propose the rCBF-PIT, which uses counting Bloom filters with return values (rCBFs), allowing reusable conflict cells. False positives for Interest packets lead to incorrect deletions that can cause false negatives for incoming Data packets. Because most of the false positives occur in the first BF structure, we finally propose the R-rCBF-PIT, in which the first rCBF is replaced with an rCBF with a signature field. The proposed PITs also provide an aging mechanism using a valid bit and a hit bit for entry expiration. Simulation results show that rCBF-PIT and R-rCBF-PIT both reduce the indeterminable rate by more than 81% compared with FBF-PIT. The results also show that R-rCBF-PIT resolves false negatives caused by incorrect deletions by including the signature fields in the first rCBF.

The minimum spanning tree (MST) problem is a fundamental problem in computer science and operations research, which has many real-life network design applications. Given a graph G with n vertices and m edges, starting from an MST (denoted by T) covering a subgraph of G, it is usually needed to reconstruct a new MST after swapping two vertices v ∈ T and v' ∉ T. For this purpose, the most popular choice is to reconstruct an MST from scratch, for which the current fastest algorithm (Kruskal's algorithm based on Fibonacci heap) requires a time complexity of O(m + n · log n), implying that a high time complexity of O(n2) · O(m + n · log n) is needed to evaluate all the O(n2) possible swapping-based moves. In order to evaluate these moves more efficiently, we integrate a series of dynamic techniques to develop a fast dynamic swap-vertex move operator, which significantly reduces the overall time complexity from O(n2) · O(m + n · log n) to O(n) · O(m · log n). We also strictly prove the correctness of the introduced method. Finally, we choose three well-studied Steiner/spanning tree problems as our test bed and carry out extensive experiments on 140 representative instances to show the effectiveness and efficiency of the proposed method. More importantly, as a general-purpose method, the dynamic swap-vertex move operator could be easily adapted to many other tree-related problems.