Existing data-plane verifiers face severe performance challenges in verifying hyper-scale underlay data center networks (DCNs) – centralized verifiers often fail to fully exploit the parallelism offered by the modern multi-core CPUs, while distributed verifiers suffer from high overhead due to task distribution and inter-node communication. To overcome these limitations, this paper introduces HeTu, a high-performance centralized parallel data-plane verifier specifically for verifying hyper-scale underlay DCNs. HeTu achieves ultra-fast verification through three key designs: (1) a fully parallel verification framework with small graph construction overhead, (2) a new binary decision diagram management strategy that enables full parallelism by using separated storage and selectively indexing and caching network-level predicates to reduce redundant operations, and (3) an optimized forwarding graph model that aggregates parallel tasks to eliminate redundant computation. Extensive evaluations on synthetic FatTree and large-scale production datasets show that HeTu outperforms state-of-the-art algorithms in runtime by 100× to 6000×, demonstrating its superior scalability and efficiency in data-plane verification of hyper-scale DCNs.

Network configuration verifiers can proactively reason about a network's correctness to prevent network outages. However, even recent efforts have proposed algorithms to "scale up" the verification to several thousand switches, these algorithms still cannot be used for networks with more than 10K switches or 1000M routes, which is common for large service providers. In this paper, instead of further scaling up the verification limited to a single server, we study how to "scale out" the verification using the resources of multiple servers. To achieve this, we propose S2, a distributed verifier for network configurations. S2 partitions the network model and distributes the verification tasks, i.e., control plane simulation and data plane verification, to run on multiple servers in parallel. Additionally, S2 uses prefix sharding during control plane simulation to further reduce the memory footprint on each server. We implement a prototype of S2 based on Batfish, the state-of-the-art network verifier. Based on real datacenter topologies of a large service provider and synthetic FatTree topologies, we show that S2 can verify networks with 10K routers and 1000M routes within 2 hours.

The data plane verification of networks in hyperscale environments is challenging due to the complexity and size of modern networks. In this paper, we introduce Medusa, a novel verifier that efficiently analyzes large data plane models using parallel processing on multi-core CPUs. First, we propose a new data structure called RANGESET, which overcomes the parallelism limitations of existing popular data structures such as Binary Decision Diagrams (BDD) used in data plane verifiers. Next, we leverage multi-core processing by dividing the network into distinct groups and assigning each group to a separate thread for computation. The results are then integrated for comprehensive verification. By optimizing the use of multi-core systems, we enhance computational efficiency and accelerate the verification process. Experimental results demonstrate that Medusa outperforms existing tools in terms of speed and memory. For instance, in a network with O(10K) devices and O(1M) forwarding rules, Medusa can detect loops in approximately 5 seconds, outperforming other Data Plane Verifiers (DPVs) where some cannot model and analyze the network. Moreover, in networks that we could compare with other state-of-the-art DPVs, Medusa provides a substantial improvement, with speedups up to 600X, 4000X, and 800X compared to alternatives like Flash, APKeep, and Tulkun, respectively.

Networks are error-prone due to misconfigurations, and it is hard to identify the root causes in the configuration and find a repair due to the size and complexity of networks running distributed routing protocols. Thus, we advocate Automatic Configuration Repair (ACR) to reduce the manual effort. Specifically, we draw some insights from the field of Automatic Software Repair (ASR), crystallize some lessons learned from the real-world repair experience of a large service provider, and propose some directions to realize ACR. Inspired by the generate-and-validate approach from ASR, we propose localize-fix-validate as a possible approach to realize ACR.

Software Defined Networking (SDN) has been proposed as a flexible solution for the next generation Internet provision. OpenFlow is a pioneering protocol for SDN which enables a hardware data plane to be managed by a software-based controller in a standard way. In this paper, we present a hardware-software co-design approach of an OpenFlow switch using a state-of-the-art heterogeneous system-on-chip (SoC) platform. Specifically, we implement the OpenFlow switch on a Xilinx Zynq ZC706 board. The Xilinx Zynq SoC family provides a tight coupling of field programmable gate array (FPGA) fabric and ARM processor cores, making it an attractive on-chip implementation platform for SDN switches. High-performance, yet highly-programmable, data plane processing can reside in programmable logic, while complex control software can reside in ARM processor. Our proposed architecture involves a methodology that scales across: (a) a range of possible packet throughput rates and (b) a range of possible flow table sizes. Post-place-and-route results show that our design targeted at Xilinx Zynq can achieve a total 88 Gbps throughput for a 1K flow table which supports dynamic and hitless updates. Correct operation has been demonstrated using a ZC706 board.

Multituple packet classification is one of the key technologies, and often the performance bottleneck in modern network devices. Devices such as firewalls demand fast packet classification on very complicated rule sets of large size, which is still challenging today. This paper proposes a practical packet classification algorithm named dynamic discrete bit selection (D2BS), which achieves high classification speed while requiring low storage. D2BS employs dynamic heuristic schemes at bit level, to explore the inherent characteristics of the rule sets. D2BS has been implemented on various platforms including Intel-architecture, multicore network processor, and FPGA, and is compared with the state-of-the-art solutions. Experimental results on real-life rule sets show that the memory storage required by D2BS is at least one to two orders of magnitude lower than that of the existing work, while the speed is much higher. With 64-byte Ethernet packet and 10K size ACL rule set, D2BS achieves a throughput over 10 Gbps on Cavium OCTEON CN5860 multicore network processor and over 135 Gbps on Xilinx Virtex-5 FPGA, which outperforms the existing work under the same test environment. All results promise that D2BS is a highly practical solution to satisfy vigorous requirements.

Packet classification is widely used as a core function for various applications in network infrastructure. With increasing demands in throughput, performing wire-speed packet classification has become challenging. Also the performance of today's packet classification solutions depends on the characteristics of rulesets. In this work, we propose a novel modular Bit-Vector (BV) based architecture to perform high-speed packet classification on Field Programmable Gate Array (FPGA). We introduce an algorithm named StrideBV and modularize the BV architecture to achieve better scalability than traditional BV methods. Further, we incorporate range search in our architecture to eliminate ruleset expansion caused by range-to-prefix conversion. The post place-and-route results of our implementation on a state-of-the-art FPGA show that the proposed architecture is able to operate at 100+ Gbps for minimum size packets while supporting large rulesets up to 28 K rules using only the on-chip memory resources. Our solution is ruleset-feature independent , i.e. the above performance can be guaranteed for any ruleset regardless the composition of the ruleset.

Ternary Content Addressable Memory (TCAM) is widely used in network infrastructure for various search functions. There has been a growing interest in implementing TCAM using reconfigurable hardware such as Field Programmable Gate Array (FPGA). Most of existing FPGA-based TCAM designs are based on brute-force implementations, which result in inefficient on-chip resource usage. As a result, existing designs support only a small TCAM size even with large FPGA devices. They also suffer from significant throughput degradation in implementing a large TCAM, mainly caused by deep priority encoding. This paper presents a scalable random access memory (RAM)-based TCAM architecture aiming for efficient implementation on state-of-the-art FPGAs. We give a formal study on RAM-based TCAM to unveil the ideas and the algorithms behind it. To conquer the timing challenge, we propose a modular architecture consisting of arrays of small-size RAM-based TCAM units. After decoupling the update logic from each unit, the modular architecture allows us to share each update engine among multiple units. This leads to resource saving. The capability of explicit range matching is also offered to avoid range-to-ternary conversion for search functions that require range matching. Implementation on a Xilinx Virtex 7 FPGA shows that our design can support a large TCAM of up to 2.4 Mbits while sustaining high throughput of 150 million packets per second. The resource usage scales linearly with the TCAM size. The architecture is configurable, allowing various performance trade-offs to be exploited. To the best of our knowledge, this is the first FPGA design that implements a TCAM larger than 1 Mbits.

Power consumption has become a limiting factor in designing next generation network routers. Recent observation shows that IP lookup engines dominate the power consumption of core routers. Previous work on reducing power consumption of routers mainly focused on network- and system-level optimizations. This paper represents the first thorough study on the data structure optimization for lowering the power consumption in static random access memory (SRAM)-based IP lookup engines. Three different SRAM-based IP lookup architectures are discussed: nonpipelined, simple pipelined, and memory-balanced pipelined architectures. For each architecture, we formulate the problem of power minimization by revisiting the time-space tradeoff in multibit tries. Two distinct multibit trie algorithms are investigated: the expanded trie and the tree bitmap trie, which are widely used in SRAM-based IP lookup solutions. A theoretical framework is proposed to determine the optimal strides for building a multibit trie so that the worst-case power consumption of the IP lookup architecture is minimized. Experiments using real-life routing tables including both IPv4 and IPv6 data sets demonstrate that careful selection of strides in building the multibit tries can reduce the power consumption dramatically. We believe our methodology can be applied to other variants of multibit tries and can help in designing more power-efficient SRAM-based IP lookup architectures.

Multi-field packet classification has evolved from traditional fixed 5-tuple matching to flexible matching with arbitrary combination of numerous packet header fields. For example, the recently proposed OpenFlow switching requires classifying each packet using up to 12-tuple packet header fields. It has become a great challenge to develop scalable solutions for next-generation packet classification that support higher throughput, larger rule sets and more packet header fields. This paper exploits the abundant parallelism and other desirable features provided by current field-programmable gate arrays (FPGAs), and proposes a decision-tree-based, 2-D multi-pipeline architecture for next-generation packet classification. We revisit the techniques for traditional 5-tuple packet classification and propose several optimization techniques for the state-of-the-art decision-tree-based algorithm. Given a set of 12-tuple rules, we develop a framework to partition the rule set into multiple subsets each of which is built into an optimized decision tree. A tree-to-pipeline mapping scheme is carefully designed to maximize the memory utilization while sustaining high throughput. The implementation results show that our architecture can store either 10K real-life 5-tuple rules or 1K synthetic 12-tuple rules in on-chip memory of a single state-of-the-art FPGA, and sustain 80 and 40 Gbps throughput for minimum size (40 bytes) packets, respectively.

Memory efficiency with compact data structures for Internet Protocol (IP) lookup has recently regained much interest in the research community. In this paper, we revisit the classic trie-based approach for solving the longest prefix matching (LPM) problem used in IP lookup. In particular, we target our solutions for a class of large and sparsely-distributed routing tables, such as those potentially arising in the next generation IPv6 routing protocol. Due to longer prefix and much larger address space, straight-forward implementation of trie based LPM can significantly increase the number of nodes and/or memory required for IP lookup. Additionally, due to the available on-chip memory and the number of I/O pins of in the state-of-the art Field Programmable Gate Arrays (FPGAs), existing designs cannot support large IPv6 routing tables consisting of over 300K prefixes. We propose two algorithms to compress the uni-bit-trie representation of a given routing table: (1) single-prefix distance bounded path compression and (2) multiple-prefix distance bounded path compression. These algorithms determine the optimal maximum slap distance at each node of the trie to minimize the total memory requirement. Our algorithms demonstrate substantial reduction in the memory footprint compared with the uni-bit-trie algorithm (1.86× for IPv4 and 6.16× for IPv6), and with the original path compression algorithm (1.77× for IPv4 and 1.53× for IPv6). Furthermore, implementation on a state of-the-art FPGA shows that our algorithms achieve 466 million lookups per second and are well suited for 100Gbps lookup. The implementation also scales to support larger routing tables and longer prefix length when we go from IPv4 to IPv6.

Network virtualization has become a powerful scheme to make efficient use of networking hardware. It allows multiple virtual networks to co-exist on the same physical networking substrate. This requires the hardware router to maintain multiple lookup tables. Hence, ultimately the hardware router should be capable of handling packets from different virtual networks. In this paper, we introduce a memory-efficient solution for router virtualization named, Multiroot. We propose this potential scheme for Provider Edge (PE) router virtualization after examining the address space requirement of such networks. Multiroot is a novel merging technique to consolidate all the routing tables to a single merged table. The shared data structure used in our algorithm results in a significant memory usage reduction in the lookup data structure while guaranteeing traffic isolation which is critical in a virtualized environment. This improvement in memory usage results in a very scalable solution for router virtualization in terms of resource usage of the hardware router. Multiroot uses trie data structure and can be implemented on a hardware or a software platform. Experiments show that our solution can achieve up to 5 fold memory usage reduction compared to state-of-the-art techniques present in literature.

Modern networks are increasingly becoming content aware to improve data delivery and security via content-based network processing. Content-aware processing at the front end of distributed network systems, such as application identification for datacenter load-balancers and deep packet inspection for security gateways, is more challenging due to the wire-speed and low-latency requirement. Existing work focuses on algorithm-level solutions while lacking system-level design to meet the critical requirement for front-end content processing. In this paper, we propose a system-level solution named FEACAN for front-end acceleration of content-aware network processing. FEACAN employs a software-hardware co-design supporting both signature matching and regular expression matching for content-aware network processing. A two-dimensional DFA compression algorithm is designed to reduce the memory usage and a hardware lookup engine is proposed for high-performance lookup. Experimental results show that FEACAN achieves better performance than existing work in terms of processing speed, resource utilization, and update time.

Real-time classification of Internet traffic according to application types is vital for network management and surveillance. Identifying emerging applications based on well-known port numbers is no longer reliable. While deep packet inspection (DPI) solutions can be accurate, they require constant updates of signatures and become infeasible for encrypted payload especially in multimedia applications (e.g. Skype). Statistical approaches based on machine learning have thus been considered more promising and robust to encryption, privacy, protocol obfuscation, etc. However, the computation complexity of traffic classification using those statistical solutions is high, which prevents them being deployed in systems that need to manage Internet traffic in real time. This paper proposes a FPGA-based parallel architecture to accelerate the statistical identification of multimedia applications while maintaining high classification accuracy. Specifically, we base our design on the k-Nearest Neighbors (k-NN) algorithm which has been shown to be one of the most accurate machine learning algorithms for Internet traffic classification. To enable high-rate data streaming for real-time classification, we adopt the locality sensitive hashing (LSH) for approximate k-NN. The LSH scheme is carefully designed to achieve high accuracy while being efficient for implementation on FPGA. Processing components in the architecture are optimized to realize high throughput. Extensive experiments and FPGA implementation results show that our design can achieve high accuracy above 99% for classifying three main categories of multimedia applications from Internet traffic while sustaining 80 Gbps throughput for minimum size (40 bytes) packets.

Next generation Internet requires processing rich and flexible flow information in the network infrastructure. Rapid growth in network traffic results in major challenge to support flexible flow matching at line rate. Most of the existing work focuses on functionality rather than performance, and simply adopts either power-hungry TCAM or performance-in deterministic hashing. This paper exploits the abundant parallelism and other desirable features provided by state-of-the-art FPGAs, and proposes a parallel architecture, named decision forest, for high-performance flexible flow matching. We develop a framework to partition a given table of flexible flow rules into multiple subsets each of which is built into a depth-bounded decision tree. The partitioning scheme is carefully designed to reduce rule duplication during the construction of the decision trees. Thus the overall memory requirement is significantly reduced. After such partitioning, the number of header fields used to build the decision tree for each rule subset is small. This leads to reduction in logic resource requirement. Exploiting the dual-port RAMs available in current FPGAs, we map each decision tree onto a linear pipeline to achieve high throughput. Our extensive experiments and FPGA implementation demonstrate the effectiveness of our scheme. Our design supports 1K flexible flow rules while sustaining 40 Gbps throughput for matching minimum size (40 bytes) packets. To the best of our knowledge, this is the first FPGA design for flexible flow matching to achieve over 10 Gbps.

Multi-dimensional packet classification is a key task in network applications, such as firewalls, intrusion prevention and traffic management systems. With the rapid growth of network bandwidth, wire speed multi-dimensional packet classification has become a major challenge for next-generation network processing devices. In this paper, we present a FPGA-based architecture targeting 100 Gbps packet classification. Our solution is based on HyperSplit, a memory-efficient tree search algorithm. First, we present an efficient pipeline architecture for mapping HyperSplit tree. Special logic is designed to support two packets to be processed every clock cycle. Second, a node-merging algorithm is proposed to reduce the number of pipeline stages without significantly increasing the memory requirement. Third, a leaf-pushing algorithm is designed to control the memory usage and to support on-the-fly rule update. The implementation results show that our architecture can achieve more than 100 Gbps throughput for the 64-byte minimum Ethernet packets. With a single Virtex-6 chip, our approach can handle over 50K rules. Compared with the state-of-the-art multi-core network processor based solutions, our FPGA design offers at least a 10x improvement in throughput performance.

Breadth-first Search (BFS) is a fundamental graph problem. Due to the irregular nature of memory accesses to graph data structures, parallelization of BFS on cache-based systems leads to poor performance. Many issues, such as memory access latency, cache coherence policy, and inter-process synchronization, affect the throughput performance of BFS on such systems. In our proposed message-passing multi-softcore architecture, parallelization is achieved by exchanging information among autonomous softcores on FPGA. Several optimizations are performed to reduce the traffic on the interconnect and to enable designs with high clock rates. Implementations on a state of the art FPGA achieve clock rates in excess of 100 MHz. The sustained performance of our system ranges from 160 to 795 Million Edges Per Second on a DDR3 DRAM. This result approaches the upperbound set by the DRAM bandwidth, and it rivals the best performance from implementations on various multi-core computing platforms.

Power consumption is becoming a limiting factor in next generation network routers. Recent observation shows that IP lookup engines dominate the power consumption of routers. Previous work on reducing power consumption of routers mainly focused on network-, system- and hardware-level optimizations. This paper represents the first attempt on the data structure optimization for power-efficient trie-based IP lookup engines. Both non-pipelined and pipelined static random access memory (SRAM) -based architectures are studied. Given the architecture, we formulate the problem by revisiting the time-space trade-off of multi-bit tries. A dynamic programming framework is then proposed to determine the optimal strides for building tree-bitmap tries so that the worst-case power consumption of the IP lookup engine is minimized. Experiments using real-life routing tables demonstrate that careful design of the data structure can reduce the power consumption dramatically. We hope our initial work can motivate the research community to expand their scope beyond the current efforts on either the hardware- or the system- and network- levels for power-efficient Internet infrastructure.

The ossification of Internet infrastructure and protocols have hindered the advancement of itself. GENI, AKARI and several other similar initiatives are pushing forward to overcome this hindrance. They facilitate researchers with networking platforms dedicated for innovative networking experiments. In these virtualized platforms, researchers can define their own forwarding schemes which can be radically different from the existing solutions. However, neither researchers nor the vendors are endowed with benchmarks to evaluate their new schemes. In this paper we introduce a Flexible Rule Generator, FRuG, an entirely user controlled benchmarking tool for evaluating future packet forwarding algorithms. With FRuG, rule generation does not need to be restricted to a fixed number of fields anymore, which makes it highly generic. It allows the user to select the protocol fields and the distribution of each field, which can either be defined by the user or configured to follow the distribution of an input seed file. The user has the complete control over the structure and the size of the rule table which makes it a powerful benchmark to assess various packet forwarding algorithms and for different types of routers (ex. edge routers, core routers, etc.). FRuG consists of an IPv4 prefix analyzer and generator, MAC address analyzer and generator, and a generic rule generator. We believe that FRuG will be a very useful tool to the networking research community with the paradigm shifts in networking like network virtualization, which takes packet forwarding to a completely new level. FRuG is an opensource tool freely available at http://sites.google.com/site/thilangane/research.

Multi-pattern string matching remains a major performance bottleneck in network intrusion detection and anti-virus systems for high-speed deep packet inspection (DPI). Although Aho-Corasick deterministic finite automaton (AC-DFA) based solutions produce deterministic throughput and are widely used in today's DPI systems such as Snort [1] and ClamAV [2], the high memory requirement of AC-DFA (due to the large number of state transitions in AC-DFA) inhibits efficient hardware implementation to achieve high performance. Some recent work [3], [4] has shown that the AC-DFA can be reduced to a character trie that contains only the forward transitions by incorporating pipelined processing. But they have limitations in either handling long patterns or extensions to support multi-character input per clock cycle to achieve high throughput. This paper generalizes the problem and proves formally that a linear pipeline with H stages can remove all cross transitions to the top H levels of a AC-DFA. A novel and scalable pipeline architecture for memory-efficient multi-pattern string matching is then presented. The architecture can be easily extended to support multi-character input per clock cycle by mapping a compressed AC-DFA [5] onto multiple pipelines. Simulation using Snort and ClamAV pattern sets shows that a 8-stage pipeline can remove more than 99% of the transitions in the original AC-DFA. The implementation on a state-of-the-art field programmable gate array (FPGA) shows that our architecture can store on a single FPGA device the full set of string patterns from the latest Snort rule set. Our FPGA implementation sustains 10+ Gbps throughput, while consuming a small amount of on-chip logic resources. Also desirable scalability is achieved: the increase in resource requirement of our solution is sub-linear with the throughput improvement.

Multi-field packet classification is a critical function that enables network routers to support a variety of applications such as firewall processing, quality of service differentiation, traffic billing, and other value added services. Explosive growth of Internet traffic requires the future packet classifiers be implemented in hardware. However, most of the existing packet classification algorithms need large amount of memory, which inhibits efficient hardware implementations. This paper exploits the modern FPGA technology and presents a partitioning-based parallel architecture for scalable and high-speed packet classification. We propose a coarse-grained independent sets algorithm and then combine it seamlessly with the cross-producting scheme. After partitioning the original rule set into several coarse-grained independent sets and applying the cross-producting scheme for the remaining rules, the memory requirement is dramatically reduced. Our FPGA implementation results show that our architecture can store 10 K real-life rules in a single state-of-the-art FPGA while consuming a small amount of on-chip resources. Post place and route results show that the design sustains 90 Gbps throughput for minimum size (40 bytes) packets, which is more than twice the current backbone network link rate.

Multi-field packet classification is a key enabling function of a variety of network applications, such as firewall processing, Quality of Service differentiation, traffic billing, and other value added services. Although a plethora of research has been done in this area, wire-speed packet classification while supporting large rule sets remains difficult. This paper exploits the features provided by current FPGAs and proposes a decision-tree-based, two-dimensional dual-pipeline architecture for multi-field packet classification. To fit the current largest rule set in the on-chip memory of the FPGA device, we propose several optimization techniques for the state-of-the-art decision-tree-based algorithm, so that the memory requirement is almost linear with the number of rules. Specialized logic is developed to support varying number of branches at each decision tree node. A tree-to-pipeline mapping scheme is carefully designed to maximize the memory utilization. Since our architecture is linear and memory-based, on-the-fly update without disturbing the ongoing operations is feasible. The implementation results show that our architecture can store 10K real-life rules in on-chip memory of a single Xilinx Virtex-5 FPGA, and sustain 80 Gbps (i.e. 2x OC-768 rate) throughput for minimum size (40 bytes) packets. To the best of our knowledge, this work is the first FPGA-based packet classification engine that achieves wire-speed throughput while supporting 10K unique rules.

Energy efficiency has become a critical concern in designing high speed packet classification engines for next generation routers. Although TCAM-based solutions can provide high throughput, they are not scalable with respect to power consumption. On the other hand, mapping decision-tree-based packet classification algorithms onto SRAM-based pipeline architectures becomes a promising alternative to TCAMs. However, existing SRAM-based algorithmic solutions need a variable number of accesses to large memories to classify a packet, and thus suffer from high energy dissipation in the worst case. This paper proposes a partitioning-based multi-pipeline architecture for energy-efficient packet classification. We optimize the HyperCuts algorithm, which is considered among the most scalable packet classification algorithms, and build a decision tree with a bounded height. Then we study two different schemes to partition the decision tree into several disjoint subtrees and map them onto multiple SRAM-based pipelines. Only one pipeline is active for classifying each packet, which takes a bounded number of accesses to small memories. Thus the energy dissipation is reduced. Simulation experiments using both real-life and synthetic traces show that the proposed architecture with 8 pipelines can store up to 10 K unique rules in 0.336 MB SRAM, sustains 1 Tbps throughput, and achieves 2.25-fold reduction in energy dissipation over the baseline pipeline architecture that is not partitioned.

Multi-field packet classification is a fundamental function that enables routers to support a variety of network services. Most of the existing multi-field packet classification algorithms can be divided into two classes: cutting-based and merging-based solutions. However, neither of them is scalable with respect to memory requirement for all rule sets with various characteristics. This paper makes several observations on real- life rule sets and proposes a novel hybrid scheme to leverage the desirable features of the two classes of algorithms. We propose a SRAM-based parallel multi-pipeline architecture to achieve high throughput. Several challenges in mapping the hybrid algorithm onto the architecture are addressed. Extensive simulations and FPGA implementation results show that the proposed scheme sustains 80 Gbps throughput for minimum size (40 bytes) packets while consuming a small amount of on-chip resources for large rule sets consisting of up to 10 K unique entries.

Power consumption has become a limiting factor in next-generation routers. IP forwarding engines dominate the overall power dissipation in a router. Although SRAM-based pipeline architectures have recently been developed as a promising alternative to power-hungry TCAM-based solutions for high-throughput IP forwarding, it remains a challenge to achieve low power. This paper proposes several novel architecture-specific techniques to reduce the dynamic power consumption in SRAM-based pipelined IP forwarding engines. First, the pipeline architecture itself is built as an inherent cache, exploiting the data locality in Internet traffic. The number of memory accesses which contribute to the majority of power consumption, is thus reduced. No external cache is needed. Second, instead of using a global clock, different pipeline stages are driven by separate clocks. The local clocking scheme is carefully designed to exploit the traffic rate variation and improve the caching performance. Third, a fine-grained memory enabling scheme is developed to eliminate unnecessary memory accesses, while preserving the packet order. Simulation experiments using real-life traces show that our solutions can achieve up to 15-fold reduction in dynamic power dissipation, over the baseline pipeline architecture that does not employ the proposed schemes. FPGA implementation results show that our design sustains 40 Gbps throughput for minimum size (40 bytes) packets while consuming a small amount of logic resources.

Vehicular ad hoc network (VANET) is a special class of wireless mobile communication network. For vehicle-to-vehicle (V2V) communication, suitable routing protocols are needed. A routing metric combining hop counts and retransmission counts at MAC layer is proposed with consideration of link quality and delay reduction. Based on the new routing metric, a cross-layer ad hoc on-demand multipath distance vector with retransmission counts metric (R-AOMDV) routing protocol is designed to make use of advantages of multi-path routing protocol, such as decrease of route discovery frequency. Compared with AOMDV with minimum hop-count metric, simulation results show that R-AOMDV achieves better performance with Pareto On/Off distribution traffic model in urban VANET, no matter in sparse or dense scenarios.

Multi-match packet classification is a critical function in network intrusion detection systems (NIDS), where all matching rules for a packet need to be reported. Most of the previous work is based on ternary content addressable memories (TCAMs) which are expensive and are not scalable with respect to clock rate, power consumption, and circuit area. This paper studies the characteristics of real-life Snort NIDS rule sets, and proposes a novel SRAM-based architecture. The proposed architecture is called field-split parallel bit vector (FSBV) where some header fields of a packet are further split into bit-level subfields. Unlike previous multi-match packet classification algorithms which suffer from memory explosion, the memory requirement of FSBV is linear in the number of rules. FPGA technology is exploited to provide high throughput and to support dynamic updates. Implementation results show that our architecture can store on a single Xilinx Virtex-5 FPGA the full set of packet header rules extracted from the latest Snort NIDS and sustains 100 Gbps throughput for minimum size (40 bytes) packets. The design achieves 1.25× improvement in throughput while the power consumption is approximately one fourth that of the state-of-the-art solutions.

In this paper we present a novel architecture for high-speed and high-capacity regular expression matching (REM) on FPGA. The proposed REM architecture, based on nondeterministic finite automaton (RE-NFA), efficiently constructs regular expression matching engines (REME) of arbitrary regular patterns and character classes in a uniform structure, utilizing both logic slices and block memory (BRAM) available on modern FPGA devices. The resulting circuits take advantage of synthesis and routing optimizations to achieve high operating speed and area efficiency. The uniform structure of our RE-NFA design can be stacked in a simple way to produce multi-character input circuits to scale up throughput further. An n-state m-character input REME takes only O (n X log2 m) time to construct and occupies no more than O (n X m) logic units. The REMEs can be staged and pipelined in large numbers to achieve high parallelism without sacrificing clock frequency.

Internet Protocol (IP) lookup in routers can be implemented by some form of tree traversal. Pipelining can dramatically improve the search throughput. However, it results in unbalanced memory allocation over the pipeline stages. This has been identified as a major challenge for pipelined solutions. In this paper, an IP lookup rate of 325 MLPS (millions lookups per second) is achieved using a novel SRAM-based bidirectional optimized linear pipeline architecture on Field Programmable Gate Array, named BiOLP, for tree-based search engines in IP routers. BiOLP can also achieve a perfectly balanced memory distribution over the pipeline stages. Moreover, by employing caching to exploit the Internet traffic locality, BiOLP can achieve a high throughput of up to 1.3 GLPS (billion lookups per second). It also maintains packet input order, and supports route updates without blocking subsequent incoming packets.

Most high-speed Internet Protocol (IP) lookup implementations use tree traversal and pipelining. However, this approach results in inefficient memory utilization. Due to available on-chip memory and pin limitations of FPGAs, state-of-the-art designs on FPGAs cannot support large routing tables arising in backbone routers. Therefore, ternary content addressable memory (TCAM) is widely used. We propose a novel SRAM-based linear pipeline architecture, named DuPI. Using a single Virtex-4, DuPI can support a routing table of up to 228 K prefixes, which is 3times the state-of-the-art. Our architecture can also be easily partitioned, so as to use external SRAM to handle even larger routing tables (up to 2 M prefixes), while maintaining a 324 MLPS throughput. The use of SRAM (instead of TCAM) leads to orders of magnitude of reduction in power dissipation. Employing caching to exploit Internet traffic locality, we can achieve a throughput of 1.3 GLPS (billion lookups per second). Our design also maintains packet input order, and supports in-place non-blocking route updates.

Ternary Content Addressable Memories (TCAMs) have been widely adopted for IP lookup engines in today's routers. However, due to the massive parallelism inherent in their architectures, TCAMs do not scale well in terms of power consumption. On the other hand, SRAM-based pipelined algorithmic solutions become attractive alternatives. This paper proposes a partitioning-based multi-way linear pipeline architecture for power-efficient trie-based IP lookup. We develop a hybrid partitioning scheme to map a routing table onto multiple linear pipelines, ensuring each pipeline uses equal amounts of memory. Within each pipeline, a memory-efficient fine-grained node-to-stage mapping scheme is employed to achieve evenly distributed memory across the stages. Simulation experiments using real-life traces show that our 8-way architecture, storing a backbone routing table with over 200 K prefixes, achieves a 27-fold reduction in power consumption over state-of-the-art TCAM-based solutions, while sustaining a throughput of 590 Gbps for minimum size (40 bytes) packets.

Continuous growth in network link rates poses a strong demand on high speed IP lookup engines. While Ternary Content Addressable Memory (TCAM) based solutions serve most of today's high-end routers, they do not scale well for the next-generation. On the other hand, pipelined SRAM- based algorithmic solutions become attractive. Intuitively multiple pipelines can be utilized in parallel to have a multiplicative effect on the throughput. However, several challenges must be addressed for such solutions to realize high throughput. First, the memory distribution across different stages of each pipeline as well as across different pipelines must be balanced. Second, the traffic on various pipelines should be balanced. In this paper, we propose a parallel SRAM-based multi- pipeline architecture for terabit IP lookup. To balance the memory requirement over the stages, a two-level mapping scheme is presented. By trie partitioning and subtrie-to-pipeline mapping, we ensure that each pipeline contains approximately equal number of trie nodes. Then, within each pipeline, a fine-grained node-to-stage mapping is used to achieve evenly distributed memory across the stages. To balance the traffic on different pipelines, both pipelined prefix caching and dynamic subtrie-to-pipeline remapping are employed. Simulation using real-life data shows that the proposed architecture with 8 pipelines can store a core routing table with over 200 K unique routing prefixes using 3.5 MB of memory. It achieves a throughput of up to 3.2 billion packets per second, i.e. 1 Tbps for minimum size (40 bytes) packets.

Power consumption has become a major concern in designing IP lookup engines for next generation routers. Although TCAMs dominate today's high-end routers, they are not scalable in terms of clock rate and power consumption. SRAM-based pipeline solutions are considered promising alternatives for high-speed IP lookup engines. However, existing SRAM-based pipeline architectures suffer from high power consumption in the worst cases, due to the large memory size and the long pipeline depth. This paper proposes a power-efficient SRAM-based pipelined IP lookup engine for future "green" routers. Both chip-level parallelism and clock gating techniques are employed to reduce the power consumption. With the aid of small TCAMs, a two-phase scheme is proposed to partition a routing trie into a number of height-bounded subtries, which are then mapped onto multiple pipelines. Each IP lookup is completed through a bounded number of accesses on small size memories. Simulation experiments using real-life traces show that our solution can store a backbone routing table with over 200 K prefixes in 4.25 MB memory, sustains a throughput of 400 Gbps, and achieves up to 7-fold and 3-fold reductions in power consumption over the state-of-the-art TCAM-based and SRAM-based solutions, respectively.

Pipelined SRAM-based algorithmic solutions have become competitive alternatives to TCAMs (ternary content addressable memories) for high throughput IP lookup. Multiple pipelines can be utilized in parallel to improve the throughput further. However, several challenges must be addressed to make such solutions feasible. First, the memory distribution over different pipelines as well as across different stages of each pipeline must be balanced. Second, the traffic among these pipelines should be balanced. Third, the intra-flow packet order should be preserved. In this paper, we propose a parallel SRAM-based multi-pipeline architecture for IP lookup. A two-level mapping scheme is developed to balance the memory requirement among the pipelines as well as across the stages in a pipeline. To balance the traffic, we propose a flow pre-caching scheme to exploit the inherent caching in the architecture. Our technique uses neither a large reorder buffer nor complex reorder logic. Instead, a payload exchange scheme exploiting the pipeline delay is used to maintain the intra-flow packet order. Extensive simulation using real-life traffic traces shows that the proposed architecture with 8 pipelines can achieve a throughput of up to 10 billion packets per second (GPPS) while preserving intra-flow packet order.

Link state routing (LSR) is widely adopted in wireless mesh networks (WMNs) while it's criticized for the high routing overhead. This work presents a hybrid mobility model for large-scale WMNs and develops a feedback-based distributed algorithm for each node to minimize the routing overhead by adaptively maximizing the control message broadcasting interval while satisfying its local mobility. This algorithm is integrated with other proposed schemes, into a routing protocol named THU-OLSR. Both theoretical analysis and simulation demonstrate that THU-OLSR effectively reduces the routing overhead and gains a better performance than other routing protocols in large-scale WMNs with hybrid mobility.

Routing in large-scale multi-radio wireless mesh networks (WMNs) is facing two challenges in achieving a high throughput. One is the long path between the source and the destination, and the other is the high routing overhead. We study the both aspects and develop our schemes accordingly. Firstly, a new routing metric for selecting multi-channel routes with maximum end-to-end capacity is presented. Secondly, a feedback based algorithm to maximize the control message broadcasting interval is proposed to minimize the routing overhead, offering more residual capacity for data traffic while keeping the routes reliable. Both the theoretic analysis and simulation experiments demonstrate the effectivity of our proposals.

In building a real-life mobile ad-hoc network (MANET), network emulation has been appraised as an efficient approach for testing the real implementations of routing algorithms and protocol stacks. Most existing MANET emulators can hardly support both real-time scene construction for proof-of-concept test and real-time traffic recording for performance evaluation simultaneously. They also lack the ability to emulate the multi-radio environment. This paper presents a flexible TCP/IP-based real-time MANET emulator that can be portably deployed to facilitate the development of real multi-radio MANET routing protocols. It friendly provides visual interaction of topology control and rich configuration of emulation conditions to enable a real-time and comprehensive examination of protocol implementations