Search

Cardinality estimation, also known as count-distinct, is the problem of finding the number of different elements in a set with repeated elements. Among the many approximate algorithms proposed for this task, HyperLogLog (HLL) has established itself as the state of the art due to its ability to accurately estimate cardinality over a large range of values using a small memory footprint. When elements arrive in a stream, as in the case of most networking applications, improved techniques are possible. We specifically propose a new algorithm that improves the accuracy of cardinality estimation by grouping counters, and by using their new organization to further track all updates within a given counter size range (compared with just the last update as in the standard HLL). Results show that when using the same number of counters, one configuration of the new scheme reduces the relative error by approximately 0.86x using the same amount of memory as the streaming HLL and another configuration achieves a similar accuracy reducing the memory needed by approximately 0.85x.

In the last decade, a number of frameworks started to appear that implement, directly in user-space with kernel-bypass mode, high-speed software data plane functionalities on commodity hardware. This may be the key to replace specific hardware-based middleboxes with custom pieces of software, as advocated by the recent Network Function Virtualization (NFV) paradigm. Vector Packet Processor (VPP) is one of such frameworks, representing an interesting point in the design space in that it offers: (i) in user-space networking, (ii) the flexibility of a modular router (Click and variants) with (iii) high-speed performance (several millions of packets per second on a single CPU core), achieved through techniques such as batch processing that have become commonplace in high-speed networking stacks (e.g. netmap or DPDK). Similarly to Click, VPP lets users arrange functions as a processing graph, providing a full-blown stack of network functions. However, unlike Click where the whole tree is traversed for each packet, in VPP each traversed node processes all packets in the batch (or vector) before moving to the next node. This design choice enables several code optimizations that greatly improve the achievable throughput. This paper introduces the main VPP concepts and architecture, and experimentally evaluates the impact of its design choices (such as batch packet processing) on its performance.

A recurring task in security monitoring consists in finding scan-type flows, namely flows which exhibit a large cardinality in terms of number of distinct source/destination addresses, or in most generality packet-level identifiers (e.g. ports, header fields, etc). But cardinality estimation requires to “remember” the identifiers seen in the past, and becomes quite challenging when the goal is to implement per-flow distinct count at wire speed, while maintaining high processing throughput and limited memory footprint. In this demo, we will show how to use HyperLogLog sketches to implement an efficient and innovative top-k cardinality estimation algorithm, called FlowFight. The algorithm has been tested and integrated in a full-fledged software router such as Vector Packet Processor.

Bloom filters and cuckoo filters are used in many applications to reduce the amount of memory needed to check if an element belongs to a set. The main drawback of these filters is that with low probability, a positive is returned for an element that is not in the set. Recently, the concept of Bloom filters with a false positive free zone has been introduced showing that false positives can be avoided when the universe from which elements are taken and the number of elements inserted in the filter are both small. Unfortunately, this limits the use of such false positive free Bloom filters in many practical applications. In this paper, a false positive free, i.e. perfect, cuckoo filter is presented and evaluated. The proposed design supports universe sizes of billions of elements and stores millions of elements, making it practical for a wide range of applications. The perfect cuckoo filter can be also used to perform mapping, further extending the range of scenarios in which can be used. The benefits of the proposed perfect cuckoo filter are illustrated with two case studies: IP address blacklisting and longest prefix match for IP forwarding.

Bloom filters are used to perform approximate membership checking in a wide range of applications in both computing and networking, but the recently introduced cuckoo filter is also gaining popularity. Therefore, it is of interest to compare both filters and provide insights into their features so that designers can make an informed decision when implementing approximate membership checking in a given application. This article first compares Bloom and cuckoo filters focusing on a packet classification application. The analysis identifies a shortcoming of cuckoo filters in terms of false positive rate when they do not operate close to full occupancy. Based on that observation, this article also proposes the use of a configurable bucket to improve the scaling of the false positive rate of the cuckoo filter with occupancy. Pedro Reviriego and David Larrabeiti would like to acknowledge the support of the ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Ministry of Science and Innovation and of the Madrid Community research project TAPIRCM grant no. P2018/TCS-4496. David Larrabeiti acknowledges the support of EU project PASSION, Grant Agreement 780326. Salvatore Pontarelli has been partly funded by the EU commission in the context of the 5G-PICTURE project, Grant Agreement 762057.

In-network computation based on programmable data plane hardware provides a tremendous opportunity to improve throughput, latency and reduce congestion in data center scenarios. However, a judicious use of these network devices must be done based on their limited resources and the specific features of the application to be offloaded. This paper promotes FlowBlaze, a stateful hardware programmable data plane, as a candidate for offloading online MapReduce tasks. Above all, tasks with strict time requirements can benefit from in-network computing since it can significantly lower their latency. Given that MapReduce is a generic programming paradigm, in this paper we first try to identify which subset of MapReduce operations can be transparently offloaded to a specific hardware architecture and which are the limitations of this offloading in terms of memory and computational resources. After, we show how the FlowBlaze architecture can match the partition/aggregation paradigm and we discuss a set of primitives exposed by the FlowBlaze abstraction to perform mapping and aggregation. Finally, we prove the feasibility of this approach applying it to a click-stream analysis use case.

We successfully carried out Europe's first 5G-ready railway trial in an operational environment by combining a passive wavelength-agnostic WDM for optical transport and 60 GHz millimeter-wave for wireless connectivity. The trial achieved multi-Gbit/s seamless connectivity from track-side access points to a fast-moving train.

In many applications, there is a need to estimate the frequency of elements. For example, in networking to know the number of packets of each flow. This poses a challenge as the number of flows and packets per second can be very large and therefore an exact count would require a large amount of fast memory. In those cases, an alternative is to use data structures, commonly referred to as sketches, that provide an estimate of the frequency of elements using a much smaller amount of memory. For example, the Count Min Sketch (CMS) hashes each element to a few counters and returns as estimate the minimum value among them. The CMS in general overestimates the frequency of an element as other elements may also map to the same counters and increment them. In this letter, fingerprint counting, a scheme to reduce the counter overestimation is presented and evaluated. The main idea is to add a fingerprint to the counters and use it to check if consecutive increments to a counter belong to the same element. When they do not, the counters can be incremented by half a packet instead of a full packet thus reducing the overestimation. The evaluation results show that the proposed scheme is able to reduce the overestimation and improve the CMS accuracy. In more detail, the overestimation is reduced by more than 20% in many of the configurations tested reaching values over 50% in some cases. A scheme to encode the fingerprints in the counters that practically eliminates the additional memory required for the fingerprints is also presented. Therefore, the improvement in the accuracy is achieved with a negligible impact on the size of the memory needed to implement the CMS.

Bloom filters are widely used in networking to accelerate checks and in particular to avoid accessing slow memories when a match will not be found. Unfortunately, filtering requires several on-chip memory bits per element and thus when the tables are large and the on-chip memory small is not applicable. In those cases, caching the most frequently accessed elements on-chip seems the only viable option. However, the key is typically formed by several packet header fields, which means that each cache entry consumes a significant amount of on-chip memory bits. In this paper, an efficient scheme to cache negatives, that is elements that will not find a match on the table is presented. In more detail, the proposed scheme enables the caching of negatives using less than 16 bits per entry regardless of the size of the key. This translates to a reduction of at least 6x in the size of the cache when used for example flow tracking.

In a network it is interesting to know the different number of flows that traverse a switch or link or the number of connections coming from a specific sub-network. This is generally known as cardinality estimation or count distinct. The HyperLogLog (HLL) algorithm is widely used to estimate cardinality with a small memory footprint and simple per packet operations. However, with current line rates approaching a Terabit per second and switches handling many Terabits per second, even implementing HLL is challenging. This is mostly due to a bottleneck in accessing the memory as a random position has to be accessed for each packet. In this letter, we present and evaluate Fast Update HLL (FU-HLL), a scheme that eliminates the need to access the memory for most packets. Results show that FU-HLL can indeed significantly reduce the number of memory accesses when the cardinality is much larger than the number of registers used in HLL as it is commonly the case in practical settings.

The increasing performance requirements of modern applications place a significant burden on software-based packet processing. Most of today's software input/output accelerations achieve high performance at the expense of reserving CPU resources dedicated to continuously poll the Network Interface Card. This is specifically the case with DPDK (Data Plane Development Kit), probably the most widely used framework for software-based packet processing today. The approach presented in this paper, descriptively called Metronome, has the dual goals of providing CPU utilization proportional to the load, and allowing flexible sharing of CPU resources between I/O tasks and applications. Metronome replaces DPDK's continuous polling with an intermittent sleep&wake mode, and revolves around a new multi-threaded operation, which improves service continuity. Since the proposed operation trades CPU usage with buffering delay, we propose an analytical model devised to dynamically adapt the sleep&wake parameters to the actual traffic load, meanwhile providing a target average latency. Our experimental results show a significant reduction of the CPU cycles, improvements in power usage, and robustness to CPU sharing even when challenged with CPU-intensive applications.

We introduce the adaptive cuckoo filter (ACF), a data structure for approximate set membership that extends cuckoo filters by reacting to false positives, removing them for future queries. As an example application, in packet processing queries may correspond to flow identifiers, so a search for an element is likely to be followed by repeated searches for that element. Removing false positives can therefore significantly lower the false-positive rate. The ACF, like the cuckoo filter, uses a cuckoo hash table to store fingerprints. We allow fingerprint entries to be changed in response to a false positive in a manner designed to minimize the effect on the performance of the filter. We show that the ACF is able to significantly reduce the false-positive rate by presenting both a theoretical model for the false-positive rate and simulations using both synthetic data sets and real packet traces.

An important function in modern routers and switches is to perform a lookup for a key. Hash-based methods, and in particular cuckoo hash tables, are popular for such lookup operations, but for large structures stored in off-chip memory, such methods have the downside that they may require more than one off-chip memory access to perform the key lookup. Although the number of off-chip memory accesses can be reduced using on-chip approximate membership structures such as Bloom filters, some lookups may still require more than one off-chip memory access. This can be problematic for some hardware implementations, as having only a single off-chip memory access enables a predictable processing of lookups and avoids the need to queue pending requests. We provide a data structure for hash-based lookups based on cuckoo hashing that uses only one off-chip memory access per lookup, by utilizing an on-chip pre-filter to determine which of multiple locations holds a key. We make particular use of the flexibility to move elements within a cuckoo hash table to ensure the pre-filter always gives the correct response. While this requires a slightly more complex insertion procedure and some additional memory accesses during insertions, it is suitable for most packet processing applications where key lookups are much more frequent than insertions. An important feature of our approach is its simplicity. Our approach is based on simple logic that can be easily implemented in hardware, and hardware implementations would benefit most from the single off-chip memory access per lookup.

A recurring task in security monitoring/anomaly detection applications consists in finding the so-called top “spreaders” (“scanners”), for instance hosts which connect to a large number of distinct destinations or hit different ports. Estimating the top k scanners, and their cardinality, using the least amount of memory meanwhile running at multi-Gbps speed, is a non trivial task, as it requires to “remember” the destinations or ports already contacted in the past by each specific host. This paper proposes and assesses an innovative design, called FlowFight. As the name implies, our approach revolves on the idea of deploying a relatively small number of per-flow HyperLogLog approximate counters — only slightly superior to the target k — and involve the potentially huge number of concurrent flows in a sort of dynamic randomized “competition” for entering such set. The algorithm has been tested and integrated in a full-fledged software router such as Vector Packet Processor. Using either synthetic or real traffic traces, we show that FlowFight is able to estimate the top- k cardinality flows with an accuracy of more than 95%, while retaining a processing throughput of around 8 Mpps on a single core. We further show that FlowFight achieves same accuracy of the state of the art competitor SpreadSketch using 10x times less memory with 1.2x times higher throughput.

In modern switches, a packet can go through a number of processing steps to determine, for example, if the packet has to be discarded due to security policies, if it needs to be marked for quality of service or to determine the next hop for the packet. Most of those steps can be modeled as a matching of some of the packet fields with a set of rules that are stored in the switch. This has been generalized with the adoption of Software Defined Networks, using for example, the Openflow protocol, on which the processing steps are programmable as table matching operations and defined dynamically by a controller. Implementing this flexible packet matching in a switch is challenging, as we need to support multiple matching tables, each having different key size, and the size of the tables should also be programmable. The main options to support multiple tables are to use different memories for each table or to have several tables share the same memories. In the first approach, each table would have to match the size and width of the memories to achieve an efficient memory usage. This is a severe limitation when flexible table size and entry width need to be supported. In the second approach, all the tables can dynamically share the memories, providing better flexibility. The problem is that the width of the memories needs to be dimensioned to support the largest entry size. This leads to significant memory waste for smaller entries. Hash based techniques like cuckoo hashing can be used to efficiently implement exact matching using standard SRAM memories, and are widely used in modern switches. However, current implementations only support entries of one size. This article presents the Single Double cuckoo hash, which can support elements of two sizes. Its main benefit is to improve memory utilization when multiple tables with entries of different sizes share the same memories. This is achieved at the cost of a small increase in circuit complexity.

The eight papers in this special section examine fault tolerance and defect analysis in VLSI and nanotechnology.

Fault-tolerant systems are usually implemented with triple modular redundancy (TMR)-based protection techniques which has a huge area and power overhead. Previous works have shown that this overhead can be improved by using reduced precision redundancy (RPR)-based approaches for intrinsically precision-tolerant applications like image and video processing. The error detection and steering logic required in the RPR schemes utilize subtraction and comparisons which are more complex hardware operations than TMR voting. This overhead is affordable for complex hardware structures, for example, finite impulse response filters, but for simple structures like adders, it can be significant. In this letter, it is shown that combining the traditional TMR voting with the RPR brings up considerable savings in area and power budget when applied to very-large-scale integration adder circuits.

Non-volatile emerging Multilevel Cell (MLC) memories (such as magneto electric, magnetic resistive, memristor-based and phase change memories) are attractive to increase density. A key advantage of these memories is that they can store several bits per cell by using different levels. This however reduces the margins against noise and other effects and can lead to larger error rates. Errors in MLC memories are usually limited to magnitude-2 levels, and thus corrupt one or two bits per cell when using a Gray mapping from levels to bits. This enables the use of codes that can correct those error patterns in a memory cell instead of codes that correct all possible patterns in the cell, thus reducing complexity and cost. In this paper, the case of a 64 data bit memory built using memory cells that can store four bits and suffer up to double bit errors per cell is considered. Several (72, 64) Spotty codes that can correct double bit errors in 4-bit cells are designed and evaluated. The new codes require fewer parity bits than existing Spotty codes or symbol-based codes such as Hong-Patel codes. Therefore, they reduce the size of the memory while having encoding and decoding complexity similar to existing alternative codes.

Offloading to the edge a subset of the cloud services requested by users is a very appealing solution to reduce the bandwidth pressure, minimize latency and improve the overall quality of experience of mobile users. Achieving this goal is technically challenging, since the network functionalities needed to manage this offloading are not trivial, and present significant requirements in terms of scalability and speed. We propose to realize these network functionalities directly in the dataplane, exploiting the characteristic of FlowBlaze, a novel stateful programmable dataplane. Furthermore, we show how the network functions for the traffic offload can be easily expressed using an ad-hoc domain specific language developed for the description of per-flow stateful network functions.

Ternary content addressable memories (TCAMs) are widely used in network devices to implement packet classification. They are used, for example, for packet forwarding, for security, and to implement software-defined networks (SDNs). TCAMs are commonly implemented as standalone devices or as an intellectual property block that is integrated on networking application-specific integrated circuits. On the other hand, field-programmable gate arrays (FPGAs) do not include TCAM blocks. However, the flexibility of FPGAs makes them attractive for SDN implementations, and most FPGA vendors provide development kits for SDN. Those need to support TCAM functionality and, therefore, there is a need to emulate TCAMs using the logic blocks available in the FPGA. In recent years, a number of schemes to emulate TCAMs on FPGAs have been proposed. Some of them take advantage of the large number of memory blocks available inside modern FPGAs to use them to implement TCAMs. A problem when using memories is that they can be affected by soft errors that corrupt the stored bits. The memories can be protected with a parity check to detect errors or with an error correction code to correct them, but this requires additional memory bits per word. In this brief, the protection of the memories used to emulate TCAMs is considered. In particular, it is shown that by exploiting the fact that only a subset of the possible memory contents are valid, most single-bit errors can be corrected when the memories are protected with a parity bit.

XTRA (XFSM for Transport) aims at providing a first attempt towards a “ code-once-port-everywhere ” platform-agnostic programming abstraction tailored to the deployment of transport layer functions. XTRA’s programming abstraction not only fits SW platforms, but is specifically designed to harness, with no re-coding effort, the offloading opportunities offered by CPU-less HW boards or smart NICs. We demonstrate the viability of XTRA with three completely different implementations of the underlying execution engine (HW proof-of-concept on a NetFPGA board, User-space SW over Linux’ Open Data Plane, and NS3 emulator). Flexibility is shown via a number of example applications, ranging from a variety of congestion control algorithms, to a middlebox-type TCP proxy functionality, up to a customized “Timer-Based” (TB) TCP which leverages the native reliance of XTRA on timers, so as to produce a loss recovery operation which, despite being formalized only via a handful of code lines, performs almost comparable with the highly optimized Linux and FreeBSD implementations.

Packet classification is an important part of many networking devices, such as routers and firewalls. Software-defined networking (SDN) heavily relies on online packet classification which must efficiently process two different streams: incoming packets to classify and rules to update. This rules out many offline packet classification algorithms that do not support fast updates. We propose a novel online classification algorithm, TupleMerge (TM), derived from tuple space search (TSS), the packet classifier used by Open vSwitch (OVS). TM improves upon TSS by combining hash tables which contain rules with similar characteristics. This greatly reduces classification time preserving similar performance in updates. We validate the effectiveness of TM using both simulation and deployment in a full-fledged software router, specifically within the vector packet processor (VPP). In our simulation results, which focus solely on the efficiency of the classification algorithm, we demonstrate that TM outperforms all other state of the art methods, including TSS, PartitionSort (PS), and SAX-PAC. For example, TM is 34% faster at classifying packets and 30% faster at updating rules than PS. We then experimentally evaluate TM deployed within the VPP framework comparing TM against linear search and TSS, and also against TSS within the OVS framework. This validation of deployed implementations is important as SDN frameworks have several optimizations such as caches that may minimize the influence of a classification algorithm. Our experimental results clearly validate the effectiveness of TM. VPP TM classifies packets nearly two orders of magnitude faster than VPP TSS and at least one order of magnitude faster than OVS TSS.

Cuckoo filters (CFs) are an alternative to Bloom filters (BFs) that supports deletions and can often be configured to have a lower false positive rate. A drawback of cuckoo filters is that the insertion process is complex and requires a large number of memory accesses when the filter operates at high occupancy. Therefore, insertion complexity may limit the applicability of cuckoo filters in many networking applications that require fast updates of the filter contents. In this letter, the cuckoo filter is extended to integrate a Bloom filter that is used to improve the performance of insertions. The proposed CFBF does not require additional memory accesses for lookup operations and preserves the support for deletion of the original cuckoo filter. The CFBF targets hardware implementations where the Bloom filter can be checked with negligible cost and where the memory width can also be adjusted to the bucket size. The evaluation results show that it can be used to reduce worst case insertion time by a factor of ten and achieve an average insertion time similar to that of a lookup. The CFBF can support bursts of hundreds of insertions for large filters and moderate false positive rates. Therefore, it can enable the use of hardware implemented cuckoo filters in applications that need to support bursts of insertions or to provide a low worst case insertion time.

This paper introduces CuCoTrack, a cuckoo hash based data structure designed to efficiently implement connection tracking. The proposed scheme exploits the fact that queries always match one existing connection to compress the 5-tuple that identifies the connection. This significantly reduces the amount of memory needed to store the connections and also the memory bandwidth needed for lookups. CuCoTrack uses a dynamic fingerprint to avoid collisions thus ensuring that queries are completed in at most two memory accesses and facilitating a hardware implementation. The proposed scheme has been analyzed theoretically and validated by simulation. The results show that using 16 bits for the fingerprint is enough to avoid collisions in practical configurations.

One drawback of Bloom filters is the inability to delete items due to hash collisions. Counting Bloom filters address this drawback using counters at the expense of increased filter size. Other alternatives like the Deletable Bloom Filter (DlBF) or the Ternary Bloom Filter (TBF) have been proposed to maintain a small filter size while supporting deletions of elements with some probability. These structures offer different trade-offs between deletability, false positive rate and filter size. In this paper, we propose a new filter called the D-FP (Deletable Fingerprint) Bloom filter that stores two-bit fingerprints, instead of a single bit or a counter, that can indicate whether the item can be deleted. By using the fingerprints, the D-FP Bloom filter provides lower false positive rates than the TBF at low filter occupancies and better deletability than the DlBF thus providing more options to desginers that want to trade-off both parameters. In addition to presenting the D-FP Bloom filter, this paper also presents an analysis of the effects of deletions on the performance of the DlBF and TBF. Finally, as a result of the simulations, we observe that the original analytical estimate for the deletable probability of DlBF tends to overestimate the probability.

By leveraging the uneven distribution of traffic among network flows, the authors improve the query throughput of Cuckoo hashing. They achieve this by placing the most frequently used items in the table that's accessed first during the Cuckoo query operation. Their scheme is named Cuckoo cache, as it's conceptually similar to a cache but implemented inside the Cuckoo hash with little additional cost. Cuckoo cache is evaluated using a traffic monitoring application fed with real traces. The results are compared with existing Cuckoo hashing implementations and show significant improvements.

Cuckoo hashing has proven to be an efficient option to implement exact matching in networking applications. It provides good memory utilization and deterministic worst case access time. The continuous increase in speed and complexity of networking devices creates a need for higher throughput exact matching in many applications. In this paper, a new Cuckoo hashing implementation named parallel d-pipeline is proposed to increase throughput. The scheme presented is targeted to implementations in which the tables are accessed in parallel. A parallel implementation increases the throughput and therefore is well suited to high speed applications. Parallel schemes are common for ASIC/FPGA implementations in which the tables are stored in several embedded memories. Using the proposed technique, the throughput can be significantly increased with gains that in practical scenarios can reach 60 percent compared to existing parallel implementations. The new scheme has been evaluated using a case study and detailed results for performance and implementation costs are reported.

In the last decade, a number of frameworks started to appear that implement, directly in userspace with kernel-bypass mode, high-speed software data plane functionalities on commodity hardware. Vector Packet Processor (VPP) is one of such frameworks, representing an interesting point in the design space in that it offers, in userspace networking, the flexibility of a modular router (Click and variants), with the benefits provided by techniques such as batch processing that have become commonplace in high-speed networking stacks (such as netmap or DPDK). Similarly to Click, VPP lets users arrange functions as a processing graph, providing a full-blown stack of network functions. However, unlike Click, where the whole tree is traversed for each packet, in VPP each traversed node processes all packets in the batch (called vector) before moving to the next node. This design choice enables several code optimizations that greatly improve the achievable processing throughput. This article introduces the main VPP concepts and architecture, and experimentally evaluates the impact of design choices (such as batch packet processing) on performance.

The challenge addressed in this paper consists in offloading packet-based pacing to a hardware Network Interface Card, while retaining the flexibility of software timers. In this direction, we propose, design, implement, and evaluate a hardware calendar, which can be programmed via a simple yet very flexible programming interface leveraging stateful (adaptive) per-packet timers. We show, for both specific examples (exponential, linearly increasing, etc) as well as for the general case, how to derive such a per-packet timer setting from a high-level desired rate envelope. Further, we describe and evaluate an FPGA implementation which relies on a novel insertion strategy for solving collisions in the calendar’s hash table.

5G networks are called to efficiently and flexibly support an ever growing variety of heterogeneous middlebox-type functions such as network address translation, tunneling, load balancing, traffic engineering, monitoring, intrusion detection, and so on. This flexibility, together with the increasing demands in terms of packet processing throughput, is extremely difficulty to achieve. One of the best candidates to provide such flexibility is a programmable dataplane based on a pipeline of match/action stages, similar to those proposed for Openflow. Designing an high speed programmable dataplane requires to have both flexible and efficient match tables and high speed programmable blocks for action execution. In particular, the most demanding actions, in terms of processing power, are those related to the manipulation of the data inside the packets, i.e. the set of operations (such as encapsulation or header manipulation) performed on packets after the forwarding decision. These encapsulation and header rewriting actions are key elements to put together heterogeneous networks and to enable flexible slicing, as envisioned by the forthcoming 5G network architecture. In the work presented in this paper we focused on the design of a Very Long Instruction Word (VLIW) processor, based on a custom instruction set, able to perform efficient packet processing operations granting multi-Gbps throughput. In particular, we provide details of the Packet Manipulator Processor (PMP) architecture and its I/O interfaces, which have been designed to accomplish packet manipulation tasks, we discuss the throughput analysis of three use cases (tunneling, NAT, and ARP reply generation) and present FPGA synthesis results.

As applications and user requirements are constantly evolving, there is a need to provide flexible networks that are able to process packets at high speed. One of the basic functions used for packet processing is matching a key formed by some fields of the incoming packet header against a set of stored rules. This is done for example to determine the next hop of a packet or to apply security checks on a firewall. In many cases, the stored rules have do not care bits as that enables a more flexible and compact representation of the rules. Therefore, the matching can be done in hardware using Ternary Content Addressable Memories (TCAMs). However, TCAMs pose several problems in many implementations. For example, for ASICs they require much more circuit area and power than standard SRAMs. On the other hand, designs based on programmable logic such as Field Programmable Gate Arrays (FPGAs) can only use the blocks provided by the FPGA that do not typically include TCAMs. In this last case, a TCAM can be emulated using the FPGA logic resources but with a large cost. To reduce the cost of implementing TCAMs, a number of algorithmic solutions have been proposed and are known as Algorithmic TCAMs or A-TCAMs. Most of those schemes target either software or ASIC implementations. In this paper we present Multiple Hash Matching Units (MHMU) an A-TCAM solution targeted towards FPGA implementations. The proposed scheme exploits the massive parallelism of FPGAs to implement many hash based matching units that use the embedded block RAM memories of the FPGA. The proposed MHMU scheme has been mapped to a Xilinx series 7 FPGA to check its efficiency in terms of resource usage and its scalability. To validate the effectiveness of MHMU, a simple configuration has been tested with Classbench generated sets of rules. The results show that the MHMU is able to consistently accommodate sets with several tens of thousands of rules with large keys.

In the last decade, a number of frameworks started to appear that implement, directly in user-space with kernel-bypass mode, high-speed software data plane functionalities on commodity hardware. Vector Packet Processor (VPP) is one of such frameworks, representing an interesting point in the design space in that it offers: (i) in user-space networking, (ii) the flexibility of a modular router (Click and variants) with (iii) the benefits brought by techniques such as batch processing that have become commonplace in lower-level building blocks of high-speed networking stacks (such as netmap or DPDK). Similarly to Click, VPP lets users arrange functions as a processing graph, providing a full-blown stack of network functions. However, unlike Click where the whole tree is traversed for each packet, in VPP each traversed node processes all packets in the batch before moving to the next node. This design choice enables several code optimizations that greatly improve the achievable processing throughput: the purpose of this demonstration is to introduce the main VPP concepts and architecture, as well as experimentally showing the impact of design choices- and especially of batch packet processing-, on the achievable packet forwarding performance.

To avoid data corruption, error correction codes (ECCs) are widely used to protect memories. ECCs introduce a delay penalty in accessing the data as encoding or decoding has to be performed. This limits the use of ECCs in high-speed memories. This has led to the use of simple codes such as single error correction double error detection (SEC-DED) codes. However, as technology scales multiple cell upsets (MCUs) become more common and limit the use of SEC-DED codes unless they are combined with interleaving. A similar issue occurs in some types of memories like DRAM that are typically grouped in modules composed of several devices. In those modules, the protection against a device failure rather than isolated bit errors is also desirable. In those cases, one option is to use more advanced ECCs that can correct multiple bit errors. The main challenge is that those codes should minimize the delay and area penalty. Among the codes that have been considered for memory protection are Reed-Solomon (RS) codes. These codes are based on non-binary symbols and therefore can correct multiple bit errors. In this paper, single symbol error correction codes based on Reed-Solomon codes that can be implemented with low delay are proposed and evaluated. The results show that they can be implemented with a substantially lower delay than traditional single error correction RS codes.

Recent trends in emerging nonvolatile memory systems necessitate efficient read/write (R/W) schemes. Efficient solutions with zero sneak path current, nondestructive R/W operations, minimum area and low power are some of the key requirements. Toward this end, we propose a novel crossbar memory scheme using a configuration row of cells for assisting R/W operations. The proposed write scheme minimizes the overall power consumption compared to the previously proposed write schemes and reduces the state drift problem. We also propose two read schemes, namely, assisted-restoring and self-resetting read. In assisted-restoring scheme, we use the configuration cells which are used in the write scheme, whereas we implement additional circuitry for self-reset which addresses the problem of destructive read. Moreover, by formulating an analytical model of R/W operation, we compare the various schemes. The overhead for the proposed assisted-restoring write/read scheme is an extra redundant row for the given crossbar array. For a typical array size of $200\times 200$ the area overhead is about $0.5\%$ , however, there is a 4X improvement in power consumption compared to the recently proposed write schemes. Quantitative analysis of the proposed scheme is analyzed by using simulation and analytical models.

Stateful programmable dataplanes are emerging as a disruptive technology and an enabler factor for network function virtualization in SDN environments. In this demo paper we show three real world use cases with stateful forwarding requirements to validate both the hardware and software implementations of the Open Packet Processor data plane.

Supporting the programming of stateful packet forwarding functions in hardware has recently attracted the interest of the research community. When designing such switching chips, the challenge is to guarantee the ability to program functions that can read and modify data plane's state, while keeping line rate performance and state consistency. Current state-of-the-art designs are based on a very conservative all-or-nothing model: programmability is limited only to those functions that are guaranteed to sustain line rate, with any traffic workload. In effect, this limits the maximum time to execute state update operations. In this paper, we explore possible options to relax these constraints by using simulations on real traffic traces. We then propose a model in which functions can be executed in a larger but bounded time, while preventing data hazards with memory locking. We present results showing that such flexibility can be supported with little or no throughput degradation., Comment: 6 pages

In this paper we show how to realize a per-flow QoS (Quality of Service) policy based on the token bucket algorithm using OPP (Open Packet Processor), a recently proposed stateful programmable dataplane. OPP is configured as a switch that enforce a token bucket policy independently on each flow processed by the switch controlling their bandwidth and burstiness. The paper shows the design of the token bucket algorithm using the extended finite state machine (EFSM) abstraction provided by OPP and discusses the details of the implementation carried out using a proof-of-concept FPGA prototype of the OPP pipeline.

This paper presents a method to implement complex tasks into stateful SDN programmable dataplanes. In particular, the presented method proposes to use the internal microcontroller typically used to configure the programmable dataplane also to perform some complex operations that do not require to be executed on each packet. These operations can be executed on a set of data gathered by the dataplane and processed in a time scale that is much higher than the time window of a packet, but is much less than time scale needed for an external SDN controller. Moreover, the use of the configuration microcontroller instead of an external SDN controller to avoid the exchange of data on the control links permits a fine grain tuning of the operations to perform from the timing point of view (precise timestamping, low latency etc.). A set of measurements showing the feasibility of the method are presented, and a simple use case is described to show the effectiveness of this method to enhance the capability of stateful programmable dataplanes.

Single error correction-double error detection- double adjacent error correction (SEC-DED-DAEC) codes have been proposed to protect SRAM devices from multiple cell upsets (MCUs). The correction of double adjacent errors ensures that the most common types of MCUs are corrected. At the same time, SEC-DED-DAEC codes require the same number of parity check bits as traditional SEC-DED codes. The main overhead associated with SEC-DED-DAEC codes is the increase in decoding complexity that can impact access time and circuit power and area. In this paper, a method to design SEC-DED-DAEC codes with optimized decoding is presented and evaluated. The proposed scheme starts by setting some constraints on the parity check matrix of the codes. Those constraints are then used to simplify the decoding. The proposed scheme has been implemented and evaluated for different word-lengths. The results show that, for data words of 32 bits, the scheme can be implemented with the same number of parity check bits as SEC-DED codes. For 16 and 64 bits words, an additional parity check bit is required, making the scheme less attractive. With the proposed method, the decoders can be optimized for area or speed. Both implementations are evaluated and compared with existing SEC-DED-DAEC decoders. The results show that the proposed decoders reduce significantly the circuit area, power, and delay. Index Terms—SEC-DAEC codes, Multiple Cell Upsets (MCUs), error correction codes, SRAM memories.

Invertible Bloom Lookup Tables (IBLTs) have been recently introduced as an extension of traditional Bloom filters. IBLTs store key-value pairs. Unlike traditional Bloom filters, IBLTs support both a lookup operation (given a key, return a value) and an operation that lists out all the key-value pairs stored. One issue with IBLTs is that there is a probability that a lookup operation will return "not found" for a key. In this paper, a technique to reduce this probability without affecting the storage requirement and only moderately increasing the search time is presented and evaluated. The results show that it can significantly reduce the probability of not returning a value that is actually stored in the IBLT. The overhead of the modified search procedure, compared to the standard IBLT search procedure, is small and has little impact on the average search time. An improved get operation for Invertible Bloom Lookup Table (IBTL) is presented.A further recursive variant is also presented.The improved get operation does not affect the storage requirement.Analytical estimations of the failure probability are presented.A set of experiment has been presented to validate the presented analysis.

Error correction codes (ECCs) are commonly used to protect memories against errors. Among ECCs, orthogonal latin squares (OLS) codes have gained renewed interest for memory protection due to their modularity and the simplicity of the decoding algorithm that enables low delay implementations. An important issue is that when ECCs are used, the encoder and decoder circuits can also suffer errors. In this brief, a concurrent error detection technique for OLS codes encoders and syndrome computation is proposed and evaluated. The proposed method uses the properties of OLS codes to efficiently implement a parity prediction scheme that detects all errors that affect a single circuit node.

Security of today's networks heavily rely on network intrusion detection systems (NIDSs). The ability to promptly update the supported rule sets and detect new emerging attacks makes field-programmable gate arrays (FPGAs) a very appealing technology. An important issue is how to scale FPGA-based NIDS implementations to ever faster network links. Whereas a trivial approach is to balance traffic over multiple, but functionally equivalent, hardware blocks, each implementing the whole rule set (several thousands rules), the obvious cons is the linear increase in the resource occupation. In this work, we promote a different, traffic-aware, modular approach in the design of FPGA-based NIDS. Instead of purely splitting traffic across equivalent modules, we classify and group homogeneous traffic, and dispatch it to differently capable hardware blocks, each supporting a (smaller) rule set tailored to the specific traffic category. We implement and validate our approach using the rule set of the well-known Snort NIDS, and we experimentally investigate the emerging trade-offs and advantages, showing resource savings up to 80 percent based on real-world traffic statistics gathered from an operator's backbone.

This brief presents a technique to efficiently correct single soft errors in serial shift registers. The proposed scheme uses two copies of the shift register. To achieve error correction, data are convolutionally encoded at the input of one of the copies and are decoded at its output. This processing ensures that in that copy, any error affecting a single bit will corrupt its output for multiple cycles. On the other hand, a single-bit error in the original copy will corrupt its output only for one cycle. Therefore, the error patterns can be used to identify the copy that has suffered the error and, consequently, to correct the error. The proposed technique has been implemented in a Hardware Description Language and implemented in a 45-nm library. A fault injection tool has been used to evaluate the effectiveness of the proposed scheme, showing that it can correct all single soft errors. The cost of the proposed approach in terms of circuit area has been compared with a traditional triple-modular redundancy implementation. The results show significant cost reductions, which approach a factor of 33% for large shift registers.

Error correction codes (ECCs) have been used for decades to protect memories from soft errors. Single error correction (SEC) codes that can correct 1-bit error per word are a common option for memory protection. In some cases, SEC codes are extended to also provide double error detection and are known as SEC-DED codes. As technology scales, soft errors on registers also became a concern and, therefore, SEC codes are used to protect registers. The use of an ECC impacts the circuit design in terms of both delay and area. Traditional SEC or SEC-DED codes developed for memories have focused on minimizing the number of redundant bits added by the code. This is important in a memory as those bits are added to each word in the memory. However, for registers used in circuits, minimizing the delay or area introduced by the ECC can be more important. In this paper, a method to construct low delay SEC or SEC-DED codes that correct errors only on the data bits is proposed. The method is evaluated for several data block sizes, showing that the new codes offer significant delay reductions when compared with traditional SEC or SEC-DED codes. The results for the area of the encoder and decoder also show substantial savings compared to existing codes.

Several network protocols require the ability to dynamically deploy, along a network path, stateful data, nicknamed “breadcrumbs”, used to forward packets on the reverse direction. This is the case of either classical reverse path forwarding schemes, as well as more recent information centric networking approaches. Perhaps surprisingly, this paper shows that such capability is already somewhat at reach in current OpenFlow switch architectures: its support requires only very marginal modification of the existing OpenFlow hardware. We support our claim with a concrete hardware proof-of-concept implementation, and we show, with the help of both traditional reverse path schemes and original approaches, how such functionality can be programmed via a platform-agnostic abstraction.

In many applications, there is a need to identify to which of a group of sets an element $x$ belongs, if any. For example, in a router, this functionality can be used to determine the next hop of an incoming packet. This problem is generally known as set separation and has been widely studied. Most existing solutions make use of hash-based algorithms, particularly when a small percentage of false positives is allowed. A known approach is to use a collection of Bloom filters in parallel. Such schemes can require several memory accesses, a significant limitation for some implementations. We propose an approach using Block Bloom Filters, where each element is first hashed to a single memory block that stores a small Bloom filter that tracks the element and the set or sets the element belongs to. In a naive solution, when an element $x$ in a set $S$ is stored, it necessarily increases the false positive probability for finding that $x$ is in another set $T$ . In this paper, we introduce our One Memory Access Set Separation (OMASS) scheme to avoid this problem. OMASS is designed so that for a given element $x$ , the corresponding Bloom filter bits for each set map to different positions in the memory word. This ensures that the false positive rates for the Bloom filters for element $x$ under other sets are not affected. In addition, OMASS requires fewer hash functions compared to the naive solution.

Bloom filters (BFs) are used in many applications for approximate check of set membership. Counting Bloom filters (CBFs) are an extension of BFs that enable the deletion of entries at the cost of additional storage requirements. Several alternatives to CBFs can be used to reduce the storage overhead. For example schemes based on d-left hashing or Cuckoo hashing have been proposed. Recently, also a new type of CBF, the Variable Increment Counting Bloom Filter (VI-CBF) has been introduced to improve performance. The VI-CBF uses different increments in the filter counters to reduce the false positive rate and therefore the storage requirements. In this paper, another mechanism to improve CBF performance: the Fingerprint Counting Bloom Filter (FP-CBF) is presented. The proposed scheme is based on the use of fingerprints on the filter entries to reduce the false positive rate. This results in a simpler implementation than VI-CBFs in terms of number of hash functions and arithmetic operations. The false positive rate of the proposed scheme has also been analyzed theoretically and by simulation and compared with the VI-CBF. The results show that the proposed scheme can achieve lower false positive rates than those of a simple VI-CBF implementation. When compared with a better and more complex VI-CBF implementation, the FP-CBF outperforms it when the number of bits per element is large while the VI-CBF is better for low number of bits per element. Fingerprints are used to improve the performance of Counting Bloom Filters.The implementation does not require arithmetic operations.The false positive rate is reduced compared to standard Counting Bloom Filters.

Cache memories are very relevant components in modern processors, and therefore, their protection against soft errors is important to ensure reliability. One important element in caches is the tag fields, which are critical to keep data integrity and achieve a high hit ratio. To protect them against soft errors, a parity bit or a single error correction (SEC) code is commonly used. In that case, on each cache access, the parity bit is checked or the SEC code decoded on each cache way to detect and correct errors. In this paper, FastTag, a novel approach to protect cache tags is presented and evaluated. The proposed scheme computes the parity or SEC bits on the incoming address and compares the result with the tag and parity bits stored in each cache way. This avoids parity recomputation or SEC decoding, thus reducing the circuit complexity. This is corroborated by the evaluation results that show how FastTag requires an area, delay, and power overhead much lower than the conventional techniques that are currently used.