Modern network devices need to perform deep packet inspection at high speed for security and application-specific services. Finite Automata (FAs) are used to implement regular expressions matching, but they require a large amount of memory. Many recent works have proposed improvements to address this issue. This paper presents a new representation for deterministic finite automata (orthogonal to previous solutions), called Delta Finite Automata (δFA), which considerably reduces states and transitions and requires a transition per character only, thus allowing fast matching. Moreover, a new state encoding scheme is proposed and the comprehensive algorithm is tested for use in the packet classification area.
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 ( δFA), which considerably reduces states and transitions while preserving a transition per character only, thus allowing fast matching. A further optimization exploits Nth order relationships within the DFA by adopting the concept of “temporary transitions”.
1 January 2018 in Wireless Communications and Mobile Computing
The fifth generation (5G) of cellular networks promises to be a major step in the evolution of wireless technology. 5G is planned to be used in a very broad set of application scenarios. These scenarios have strict heterogeneous requirements that will be accomplished by enhancements on the radio access network and a collection of innovative wireless technologies. Softwarization technologies, such as Software‐Defined Networking (SDN) and Network Function Virtualization (NFV), will play a key role in integrating these different technologies. Network slicing emerges as a cost‐efficient solution for the implementation of the diverse 5G requirements and verticals. The 5G radio access and core networks will be based on a SDN/NFV infrastructure, which will be able to orchestrate the resources and control the network in order to efficiently and flexibly and with scalability provide network services. In this paper, we present the up‐to‐date status of the software‐defined 5G radio access and core networks and a broad range of future research challenges on the orchestration and control aspects.
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.