Modern network devices need to perform deep packet inspection at high speed for security and application- specific services. For this purpose, regular expressions are used, due to their high expressive power, and Deterministic Finite Automata (DFAs) are adopted to match them. Many works have been proposed to improve DFAs, especially in terms of memory consumption and speed. Instead, we address another issue: the scalability of DFAs to parallel systems and their buffer requirements. To our knowledge, a single attempt to parallelize DFA walk on regular multicore systems (which ex- ploits speculation with limited efficiency) has been proposed in literature. We propose a solution in which a number of processing units are committed to walk in parallel a DFA for the same packet; at this aim, sampling techniques on both text and regular expressions are adopted. This scheme is the first in literature that proposes effective parallelization of DFA walk, hence allowing for packet processing time reduction and less memory for reordering buffers. The result is that speed scales as the number of processing units.

Deep packet inspection is a fundamental task to improve network security and provide application-specific services. State-of-the-art systems adopt regular expressions due to their high expressive power. They are typically matched through deterministic finite automata (DFAs), but large rule sets need a memory amount that turns out to be too large for practical implementation. Many recent works have proposed improvements to address this issue, but they increase the number of transitions (and then of memory accesses) per character. This paper presents a new representation for DFAs, orthogonal to most of the previous solutions, called delta finite automata ($\delta$FA), which considerably reduces states and transitions while preserving a transition per character only, thus allowing fast matching. A further optimization exploits$N$th order relationships within the DFA by adopting the concept of “temporary transitions.”

Because of the rapid growth of both traffic and links capacity, the time budget to perform IP address lookup on a packet continues to decrease and lookup tables of routers unceasingly grow. Therefore, new lookup algorithms and new hardware platform are required to perform fast IP lookup. This paper presents a new scheme on top of the NetFPGA board which takes advantage of parallel queries made on perfect hash functions. Such functions are built by using a very compact and fast data structure called Blooming Trees, thus allowing the vast majority of memory accesses to involve small and fast on-chip memories only.

A Bloom Filter is an efficient randomized data structure for membership queries on a set with a certain known false positive probability. Bloom Filters (BFs) are very attractive for their limited memory requirements and their easy construction which make them a popular choice for many tasks in network devices. However, in a number of network applications, more than simple probabilistic membership queries is required, and BFs can be adopted as a coarse filtering stage, leaving the ultimate filtering and classification process to other techniques, such as hash tables or tree-like structures. In this paper we propose a scheme to extend BFs with "indexing" features so that when an element x is queried, an univocal index of that element is returned, which in turn can be used as an address for a table, just as a perfect hashing scheme. This extension, called indexed Bloom Filter (iBF), comes at the cost of a small increment of false positive probability and simply fits in existing BF-based applications.

Modern network devices need to perform deep packet inspection at high speed for security and application-specific services. Instead of standard strings to represent the dataset to be matched, state-of-the-art systems adopt regular expressions, due to their high expressive power. The current trend is to use Deterministic Finite Automata (DFAs) to match regular expressions. However, while the problem of the large memory consumption of DFAs has been solved in many different ways, only a few works have focused on increasing the lookup speed. This paper introduces a novel yet simple idea to accelerate DFAs for security applications: payload sampling. Our approach allows to skip a large portion of the text, thus processing less bytes. The price to pay is a slight number of false alarms which require a confirmation stage. Therefore, we propose a double-stage matching scheme providing two new different automata. Results show a significant speed-up in regular traffic processing, thus confirming the effectiveness of the approach.

Bloom Filters are efficient randomized data structures for membership queries on a set with a certain known false positive probability. Counting Bloom Filters (CBFs) allow the same operation on dynamic sets that can be updated via insertions and deletions with larger memory requirements. This paper first presents a simple tight upper bound for counters overflow probability in CBFs, which is adopted in the design of more efficient CBFs. On the basis of such theoretical achievements, we introduce the idea of a hierarchical structure as well as the use of Huffman code to improve standard CBFs in terms of fast access and limited memory consumption (up to 50% of memory saving). The target could be the implementation of the compressed data structures in the small (but fast) local memory or “on-chip SRAM” of devices such as network processors. As an application of our algorithms, an anti-evasion system is finally proposed.

IP address lookup is a fundamental task for Internet routers, due to the rapid growth of both traffic and links capacity. Many algorithms have been proposed to improve lookup performance in terms of memory consumption, search speed and update complexity. Due to the presence of wildcards and netmasks, such algorithms adopt several techniques to deal with longest prefix matching. However, the analysis of lookup tables reveals that the first 16 bits of forwarding rules are almost always specified. Therefore, more powerful exact-matching schemes can be applied to the first half of addresses. This paper presents a routing lookup accelerator (RLA) which allows the lookup of the first 16 bits to be sped up. The target is an efficient scheme to be implemented in small and fast memories of recent hardware platforms. Specifically, since in several forwarding tables the distribution of the first 16 bits is characterized by empty gaps as well as pronounced peaks, we propose to divide the address space in different ranges and to encode each address only as a difference with respect to a given address chosen as reference for that range. Then, a hybrid direct-addressing / multibit trie scheme is used for each range. As RLA is orthogonal to all other schemes, any other lookup algorithm can be used to perform longest prefix matching on the remaining bits.

Characterizing delay distribution over the links of a network provides a remarkable amount of information which can be useful for troubleshooting, traffic engineering, adaptive multimedia flow coding, overlay network design, etc. Since querying each and every node of a path in order to retrieve this kind of information can be unfeasible or just too resource demanding, the recent research trend is to infer the internal state of a network by means of end-to-end measurements. Many algorithms in literature require active measurements and are based on a single-sender multiple-receivers scheme, thus relying on the cooperation of a possibly wide number of nodes, which is a quite strong assumption. Moreover, many previous works adopt Expectation-Maximization algorithms to cope with large and under-determined equation systems, thus increasing the uncertainty of the final delay estimation. This paper, instead, proposes a technique to infer the cumulants of the delay distribution over each link of a given network path, based on two-points measurements only. The cumulants, in turn, can be used to approximate the distribution function through the Edgeworth series. The results of our approach are assessed through a wide series of model-based and ns2 based simulations and show fairly good performance under different network load conditions.

Network Topology Discovery is crucial to a number of network management tasks. Traditional topology discovery techniques require internal nodes to take actions on measurement packets, which makes them unpractical in many cases. For these reasons, tomographic techniques have been introduced, which allow for the reconstruction of network topologies with no need for cooperation from internal routers. The usual approach to tomographic topology discovery is based on clustering nodes into tree structures according to soft similarity metrics. We recently proposed a novel technique based on decision theoretic considerations that help the topology reconstruction by limiting the set of hypotheses to a finite and well-defined set, thus determining hard metrics. In the scheme, probe traffic is sent to all couples of end-nodes and a metric is assigned to each measurement. In this paper, we extend the technique by ordering the topology reconstruction procedure according to metrics reliability defined in terms of their variances. The algorithms presented in the paper are validated through extensive simulations in several network scenarios. The results show that such a methodology allows to retrieve a complete picture of the network that includes the detection of all the internal nodes along with the values of capacities of the interconnecting links.

Deep packet inspection is required in an increasing number of network devices, in order to improve network security and provide application-specific services. Instead of standard strings to represent the data set to be matched, state-of-the-art systems adopt regular expressions, due to their high expressive power and flexibility. Typically regular expressions are matched through deterministic finite automata (DFAs), but large rule sets need a memory amount which turns out to be too large for practical implementation. Many recent works have proposed improvements to address this issue, but they increase the number of transitions (and then of memory accesses) per character. In a previous work, we have presented a smart representation for DFA which, while preserving fast matching (i.e., a transition per character only), considerably reduces states and transitions. In this paper we introduce a novel optimized automaton, which exploits second order relationships within the DFA and is based on the key concept of "temporary transitions". Results for real data sets show that it allows for a further memory saving.

Tomographic techniques allow the reconstruction of network topologies with no need for cooperation from internal routers. However, most of such mechanisms adopt a method of node clustering producing trees that reveal only a partial structure of the network. Therefore, we have proposed a novel approach to topology discovery based on packet sandwich probes and decision theory allowing to retrieve a complete picture of the network, which includes the detection of all the internal nodes along with the values of capacities of the interconnecting links. Such an approach, as well as all the standard techniques of topology discovery, reconstructs the spanning tree of the probe sender only. Hence, in this paper a specific technique is presented for merging the spanning trees associated to all different roots, in order to provide a complete representation of the network. Such a method does not require further probing traffic and is specifically designed to merge topology reconstructions where all the nodes of the network (not only the branching nodes) are revealed, along with link capacities. Our algorithm performs quite well on a wide set of both synthetic and realistic topologies, and in many cases provides a picture of the network which is exactly equivalent to the original one.

Performing deep packet inspection at high speed is a fundamental task for network security and application-specific services. In state-of-the-art systems, sets of signatures to be searched are described by regular expressions, and finite automata (FAs) are employed for the search. In particular, deterministic FAs (DFAs) need a large amount of memory to represent current sets, therefore the target of many works has been the reduction of memory footprint of DFAs. This paper, instead, focuses on speed multiplication by enlarging the amount of bytes observed in the text (i.e., searching for k-bytes per state-traversal). For this purpose, an interesting yet simple inverse homomorphism is employed to reduce the amount of transitions in the modified DFA. The algorithm results to be remarkably faster than standard DFAs, and provides also a good compression scheme that is orthogonal to other schemes.

Evaluating the performance of high-speed networks is a critical task due to the lack of reliable tools to generate traffic workloads at high rates. The current open-source software tools are not suitable to deal with high-speed networks as they present poor performance in terms of generated frames per second and scarce timing/rate accuracy in traffic generation. These issues are due to the intrinsic limitations of the PC architecture, for which these tools are designed. This paper proposes a different approach based on the Intel Network Processor IXP2400. The design aims to maintain the high flexibility of PC solutions while outperforming them in terms of throughput and packet rate. This is obtained by combining a general-purpose PC with the processing units of a network processor.

Hash tables are used in many networking applications, such as lookup and packet classification. But the issue of collisions resolution makes their use slow and not suitable for fast operations. Therefore, perfect hash functions have been introduced to make the hashing mechanism more efficient. In particular, a minimal perfect hash function is a function that maps a set of n keys into a set of n integer numbers without collisions. In literature, there are many schemes to construct a minimal perfect hash function, either based on mathematical properties of polynomials or on graph theory. This paper proposes a new scheme which shows remarkable results in terms of space consumption and processing speed. It is based on an alternative to Bloom Filters and requires about 4 bits per key and 12.8 seconds to construct a MPHF with 3.8times109elements.

A Bloom filter is an efficient randomized data structure for membership queries on a set with a certain known false positive probability. A counting Bloom filter (CBF) allows the same operations on dynamical sets that can be updated via insertions and deletions with larger memory requirements. This paper presents a novel hierarchical data structure, called Blooming tree, that replicates the functionalities of a CBF with lower memory consumption and tunable false positive probability. The hierarchical multi-layer design of Blooming trees allows for distributing the structure in different memory levels, thus exploiting small but fast on-chip memories for most frequently accessed substructures. The proposed algorithm is compared to previous existing schemes on a target platform: Intel IXP2XXX Network Processors (NPs).

Bloom filters are efficient randomized data structures for membership queries on a set with a certain known false positive probability. Counting bloom filters (CBFs) allow the same operation on dynamic sets that can be updated via insertions and deletions with larger memory requirements. This paper first presents a new upper bound for counters overflow probability in CBFs. This bound is much tighter than that usually adopted in literature and it allows for designing more efficient CBFs. Three novel data structures are proposed, which introduce the idea of a hierarchical structure as well as the use of Huffman code. Our algorithms improve standard CBFs in terms of fast access and limited memory consumption (up to 50% of memory saving): the target could be the implementation of the compressed data structures in the small (but fast) local memory or "on-chip SRAM" of devices such as network processors .

The growth of the Internet in the last years has been pushed by increasing requirements in terms of capacity, security and reliability. Moreover, improvements in multimedia applications need mechanisms and architectures to accomplish quality of service (QoS) and differentiated services. Technology development has shown that the evolution of processing power cannot cope with the link capacity growth. Therefore a link capacity scheduler is no longer sufficient to assure efficient service differentiation to end-users, but a proper computing power allocation for packet processing must be adopted. In this paper a processing scheduling scheme for IntelregIXP2XXX Network Processors is proposed. A model of the architecture is defined and an ad-hoc simulator is developed to help the comprehension of the system and the re-design of the application. Finally experimental results show the performance of the proposed algorithm.

Nowadays packet classification is a fundamental task for network devices such as edge routers, firewalls and intrusion detection systems. Determining which flow packets belong to is important for many applications, and it is necessary, for example, to provide differentiated services, to detect anomalous traffic and to sort attack patterns. Therefore packet classification is becoming more and more complex, with more flexibility and higher performance requirements. Network Processors (NPs) are emerging as very promising platforms due to their capability to combine the flexibility of general-purpose processors with high performance of hardware-based solutions. In this paper we illustrate the design of a multidimensional packet classifier realized on the Radisys® ENP-2611 board equipped with Intel® IXP2400 Network Processor. The first goal of this study is the selection of the most suitable classification algorithm to be integrated into the embedded system. Our investigation is then directed to adjustments and refinements of the selected algorithm (namely the multidimensional multibit trie algorithm) to capitalize the peculiar functional properties and capabilities of our network processor.

In a multi-service IP network, it is a key challenge to provide quality of service (QoS) to end-user applications while effectively using network resources. The DiffServ architecture has emerged as a scalable solution to provide a network with multiple service classes. The multiprotocol label switching (MPLS) traffic engineering (TE), instead, enables resource reservation, fault-tolerance and optimization of transmission resources. MPLS DiffServ-aware TE combines the advantages of these solutions and allows network operators to provide services that require strict QoS performance guarantees. The choice of the signalling protocol to exchange DiffServ, MPLS and TE-related information is a key point in this scenario. Different solutions have been proposed, such as RSVP-TE and CR-LDP. Since the first one seems to be the most attractive for router manufacturers, in this paper, the design and the development of a new software module to simulate the RSVP-TE protocol in the Network Simulator 2 (NS2) is presented. This module could be useful to speed-up the design, development and deployment of DiffServ-aware MPLS networks