The explosion of network bandwidth poses greatchallenges to data-plane flow processing. Due to the variable andpoor worst-case performance, naive hash table is incapable ofwire-speed processing. State-of-the-art schemes rely on multiplehash functions for enhanced load balancing to improve the worst-case performance. These schemes exploit the memory hierarchyand allocate compact on-chip data structures as the off-chiphash table summaries. However, when the flow number inflates, they fail to scale the on-chip memory consumption gracefully. This work is inspired by modern DRAM's burst-transfer feature. Specifically, we propose bandwidth-greedy hashing which resolveshash collisions with just one DRAM burst. Besides, load balancingefforts are made in an "on-demand" fashion. This radicaldesign surmounts the major obstacle of mapping multiple choicehashing schemes to real-world hierarchical memory systems formassive-scale items. Essentially, this solution follows a designpattern of on-demand load balancing and can be regarded asa generalization of closed hashing. To establish its theoreticalbase, we analyze it via Poisson distribution approximation. Theevaluation on DRAMSim2 reports that our scheme requires onlyone DRAM burst access (in 99.999% cases) and minuscule on-chip memory (less than 16MB, or 1% of the previous) to supportlookups for 100M flows at a throughput of 122.82Mpps.

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.

Flow-based packet processing exists widely in a variety of network applications, where a large sized flow table is built to keep the alive flow records. To accelerate the search speed of the flow table, numerous systems employ cache mechanism to track the most recently referenced flows. However, network traffic exhibits some different characteristics from the workload of the general computational tasks, and classic replacement policies like LRU, Random, fail to perform well in the network scenarios. To develop a network-oriented flow cache replacement policy, we propose ALFE (Adaptive Least Frequently Evicted) based on the observations of traffic's heavy tailed feature and the statistically positive correlation between the flow size and the flow cache evict times. Specifically, the correlation helps us identify elephant flows at a tiny extra cost of a few more bits allocated to each flow entry. For those who are identified as possible elephant flows, ALFE favors their priorities in the cache, thus preventing them from being flooded by the massive mice flows. A prototype system employing ALFE policy is elaborately designed and implemented besides extensive simulations. Experimental results indicate that with 1K cache entries, ALFE can achieve up to 15% higher cache hit rate than LRU on real traces.

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.

Today's Internet applications exhibit increased diversity, while the Internet routers are still oblivious to this trend. To improve the end-to-end application QoS, one solution is to embed the application information explicitly in packet headers, but it will bring global changes. Another local solution is router-assisted traffic differentiation. To achieve this, the functionalities including packet identification and flow tracking inside the router are required. While most existing studies focus on the former, fewer efforts are put on the later. Given a large flow table is involved, how to track millions of concurrent flows in a cost-effective manner on a router's line card raises a great space-time challenge. To address this, we design an on-chip/off-chip flow tracking system to accommodate millions of flows and achieve the throughput at tens of Gigabits. By exploiting temporal locality and heavy-tailedness of Layer-4 traffic, we design the Adaptive Least Frequently Evicted (ALFE) replacement policy to catch elephant flows, therefore maintain a high cache hit rate. To alleviate performance penalty due to the cache misses, we organize the flow table in a fixed-allocated manner to fully utilize modern DRAM's burst feature. We have implemented a research prototype using FPGA for performance evaluation. The experiment results show that our system can reach 80% hit rate with a small-sized cache of 16K entries, while achieving 70Mpps throughput. This enables backbone line rate processing. Further, more than 40% power saving can be achieved by our system, which is fast and accurate with only 3% FPGA resource usage.