Network virtualization allows multiple virtual routers to coexist in the same physical router but offer independent routing services. Each virtual router needs to perform millions of lookups and thousands of updates per second to meet the requirements of high-speed Internet. The coexistence of these virtual routers intensifies scalability challenges to the routing lookup scheme: Can it scale well in storage, lookup speed and update performance as the number of virtual routers increases? In this paper, we propose Layer-based Overlay and Optimized Polymerization (LOOP) which has favorable scalability regardless of the number of virtual routers. Experiments on the general-purpose CPU show that LOOP achieves efficient storage, fast lookup, and fast incremental update. It compacts 18 FIBs with about 7M prefixes in total to only 4.6MB. One single thread can perform about 50M lookups per second on real-world traces. LOOP allows an update thread to run in parallel with lookup threads and barely interrupt them, and pure update testing indicates it can perform about 1M updates per second. One of the key advantages of LOOP is that it supports inserting and deleting virtual routers incrementally so it is ideal for fast and dynamic configuration of virtual networks.

In this paper we design, implement and evaluate NameFilter, a two-stage Bloom filter-based scheme for Named Data Networking name lookup, in which the first stage determines the length of a name prefix, and the second stage looks up the prefix in a narrowed group of Bloom filters based on the results from the first stage. Moreover, we optimize the hash value calculation of name strings, as well as the data structure to store multiple Bloom filters, which significantly reduces the memory access times compared with that of non-optimized Bloom filters. We conduct extensive experiments on a commodity server to test NameFilter's throughput, memory occupation, name update as well as scalability. Evaluation results on a name prefix table with 10M entries show that our proposed scheme achieves lookup throughput of 37 million searches per second at low memory cost of only 234.27 MB, which means 12 times speedup and 77% memory savings compared to the traditional character trie structure. The results also demonstrate that NameFilter can achieve 3M per second incremental updates and exhibit good scalability to large-scale prefix tables.

With the rapid growth of the Internet, the update messages in backbone routers become more and more frequent due to the ever-increasing dynamic changes on network topologies and new emerging functionalities of the Internet. In addition, update messages often come as a burst. Update action interrupts the packet lookup operation in the router's data plane, thus inefficient incremental update algorithm slows down IP lookup speed, and potentially badly degrades the system performance during bursty updates. Among trie-based routing lookup algorithms, binary trie has the best update complexity O(W) (W is the maximum depth of the trie), but exhibits slow lookup speed, failing to be competent for forwarding tens of gigabit-per-second traffic in backbone routers. Therefore, various improved routing lookup algorithms are proposed to pursue high speed based on binary trie, but sacrificing the performance of incremental update. To minimize the interruption time that update operation incurs, we propose Blind Spot (BS) algorithm by picking out those updating nodes which would have produced domino effect, achieving an update complexity of O(lookup+h), meanwhile keeping the lookup speed almost unchanged. Blind Spot algorithm is a universal methodology, which is applicable to all the trie-based lookup algorithms. To evaluate the performance of BS algorithm, we applied it to Lulea [1] and LC-trie [2] algorithms as two representatives. Extensive experimental results show that both Lulea+BS and LC+BS algorithms achieve a much faster update speed than binary trie, while keeping the same lookup speed as the original Lulea and LC-trie algorithms.

Virtual router research has drawn increasing attention in recent years, and the most challenging issues of virtual routers are compression, lookup, and incremental update of 10∼200 routing tables. In this paper, we propose a set of solutions to achieve that storage, lookup time, and update time don't expand to 10∼200 times, but reduce to 1∼2 times.