The Experts below are selected from a list of 3852 Experts worldwide ranked by ideXlab platform
Pi-chung Wang - One of the best experts on this subject based on the ideXlab platform.
-
Efficient Packet Classification with a Hybrid Algorithm
IEICE Transactions on Information and Systems, 2020Co-Authors: Pi-chung WangAbstract:Packet Classification categorizes incoming Packets into multiple forwarding classes based on pre-defined filters. This categorization makes information accessible for quality of service or security handling in the network. In this paper, we propose a scheme which combines the Aggregate Bit Vector algorithm and the pruned Tuple Space Search algorithm to improve the performance of Packet Classification in terms of speed and storage. We also present the procedures of incremental update. Our scheme is evaluated with filter databases of varying sizes and characteristics. The experimental results demonstrate that our scheme is feasible and scalable
-
Packet Classification with Hierarchical Cross-Producting
IEICE Transactions on Information and Systems, 2020Co-Authors: Chia-tai Chan, Pi-chung WangAbstract:Packet Classification has become one of the most important application techniques in network security since the last decade. The technique involves a traffic descriptor or user-defined criteria to categorize Packets to a specific forwarding class which will be accessible for future security handling. To achieve fast Packet Classification, we propose a new scheme, Hierarchical Cross-Producting. This approach simplifies the Classification procedure and decreases the distinct combinations of fields by hierarchically decomposing the multi-dimensional space based on the concept of telescopic search. Analogous to the use of telescopes with different powers**, a multiple-step process is used to search for targets. In our scheme, the multi-dimensional space is endowed with a hierarchical property which self-divides into several smaller subspaces, whereas the procedure of Packet Classification is translated into recursive searching for matching subspaces. The required storage of our scheme could be significantly reduced since the distinct field specifications of subspaces is manageable. The performance are evaluated based on both real and synthetic filter databases. The experimental results demonstrate the effectiveness and scalability of the proposed scheme
-
Scalable Packet Classification for IPv6 by using limited TCAMs
Lecture Notes in Computer Science, 2020Co-Authors: Chia-tai Chan, Pi-chung Wang, Shuo-cheng Hu, Rong-chang ChenAbstract:It has been demonstrated that performing Packet Classification on a potentially large number of filters on key header fields is difficult and has poor worst-case performance. To achieve fast Packet Classification, hardware support is unavoidable. Ternary content-addressable memory (TCAM) has been widely used to perform fast Packet Classification due to its ability to solve the problem in O(1) time without considering the number of entries, mask continuity and their lengths. As compared to the software-based solutions, the TCAM can offer sustained throughput and simple system architecture. It is attractive for Packet Classification, especially for the ultimate IPV6-based networks. However, it also comes with several shortcomings, such as the limited number of entries, expansive cost and power consumption. Accordingly, we propose an efficient algorithm to reduce the required TCAM by encoding the address portion of the searchable entries. The new scheme could encrypt the 128-bit prefixes of the real-world IPv6 routing tables into 11 bits and still keeps the property of CIDR.
-
Scalable Multi-Match Packet Classification Using TCAM and SRAM
IEEE Transactions on Computers, 2016Co-Authors: Yu-chieh Cheng, Pi-chung WangAbstract:Packet Classification is an enabling technology for various network services. Fast single-match Packet Classification can be achieved by using ternary content addressable memory (TCAM) because of the superior speed performance. TCAM has some drawbacks including incapability to store arbitrary ranges, confined TCAM capacity and limited choices of entry lengths. Moreover, TCAM only reports the first matching entry to impose a limitation on supporting multi-match Packet Classification, which requires all matching rules. The existing algorithms deal with the issues of TCAM-based multi-match Packet Classification by burdening TCAM with extra entries and/or accesses. In this work, we offload the overhead of TCAM to static random access memory (SRAM) to achieve efficient multi-match Packet Classification. Our scheme synthesizes TCAM compatible entries by using binary decision trees and employs SRAM for further comparisons. Each synthesized entry can be stored in one TCAM entry to significantly reduce TCAM consumption and fulfill low power consumption. The experimental results show that our scheme can lower the demand of TCAM to improve both search latency and energy efficiency. The scalability of TCAM-based multi-match Packet Classification can thus be improved drastically.
-
TCAM-Based Multi-Match Packet Classification Using Multidimensional Rule Layering
IEEE ACM Transactions on Networking, 2016Co-Authors: Dao-yuan Chang, Pi-chung WangAbstract:Ternary content addressable memory (TCAM) has superior performance for single-match Packet Classification but not the case for multi-match Packet Classification. The limitation is caused by TCAM architecture that reports only the first matching rule. To cope with the limitation, previous algorithms use extra TCAM entries or accesses, or both, to fulfill multi-match Packet Classification. These algorithms also reorder rules; thus, a multi-match classifier based on these algorithms cannot maintain performance for single-match Packet Classification. In other words, all matching rules must be yielded to determine the highest priority matching rule. In this paper, we present a TCAM-based scheme for multi-match Packet Classification without single-match penalty. Our scheme partitions a rule set based on range layering, which can be applied to achieve range encoding. The rule partitioning generates rule subsets which satisfy that the rules in a subset are mutually disjoint. Each rule is then tagged a bitmap for subset identification to fulfill multi-match Packet Classification. Two approaches, loose coupling and tight coupling, are derived with different search procedures while incorporating range encoding. Both approaches can maintain original rule order, but with different performance tradeoff. We also present a refinement which uses all available TCAM entries to improve the performance of multi-match Packet Classification. The experimental results show that combining range encoding with multi-match Packet Classification has advantages of storage efficiency and speed superiority. The capability of supporting single-match Packet Classification also provides better flexibility of applying different Packet actions.
Laurent Mathy - One of the best experts on this subject based on the ideXlab platform.
-
ICNP - Meta-algorithms for Software-Based Packet Classification
2014 IEEE 22nd International Conference on Network Protocols, 2014Co-Authors: Peng He, Kavé Salamatian, Laurent MathyAbstract:We observe that a same rule set can induce very different memory requirement, as well as varying Classification performance, when using various well known decision tree based Packet Classification algorithms. Worse, two similar rule sets, in terms of types and number of rules, can give rise to widely differing performance behaviour for a same Classification algorithms. We identify the intrinsic characteristics of rule sets that yield such performance differences, allowing us to understand and predict the performance behaviour of a rule set for various modern Packet Classification algorithms. Indeed, from our observations, we are able to derive a memory consumption model and an offline algorithm capable of quickly identifying which Packet Classification is suited to a give rule set. By splitting a large rule set in several subsets and using different Packet Classification algorithms for different subsets, our Smart Split algorithm is shown to be capable of configuring a multi-component Packet Classification system that exhibits up to 11 times less memory consumption, as well as up to about 4× faster Classification speed, than the state-of-art work [20] for large rule sets. Our Auto PC framework obtains further performance gain by avoiding splitting large rule sets if the memory size of the built decision tree is shown by the memory consumption model to be small.
-
Meta-algorithms for Software-Based Packet Classification
2014 IEEE 22nd International Conference on Network Protocols, 2014Co-Authors: Peng He, Kavé Salamatian, Laurent MathyAbstract:We observe that a same rule set can induce very different memory requirement, as well as varying Classification performance, when using various well known decision tree based Packet Classification algorithms. Worse, two similar rule sets, in terms of types and number of rules, can give rise to widely differing performance behaviour for a same Classification algorithms. We identify the intrinsic characteristics of rule sets that yield such performance differences, allowing us to understand and predict the performance behaviour of a rule set for various modern Packet Classification algorithms. Indeed, from our observations, we are able to derive a memory consumption model and an offline algorithm capable of quickly identifying which Packet Classification is suited to a give rule set. By splitting a large rule set in several subsets and using different Packet Classification algorithms for different subsets, our Smart Split algorithm is shown to be capable of configuring a multi-component Packet Classification system that exhibits up to 11 times less memory consumption, as well as up to about 4× faster Classification speed, than the state-of-art work [20] for large rule sets. Our Auto PC framework obtains further performance gain by avoiding splitting large rule sets if the memory size of the built decision tree is shown by the memory consumption model to be small.
-
Toward predictable performance in decision tree based Packet Classification algorithms
2013 19th IEEE Workshop on Local & Metropolitan Area Networks (LANMAN), 2013Co-Authors: Peng He, Laurent Mathy, Hongtao Guan, Kavé SalamatianAbstract:Packet Classification has been studied extensively in the past decade. While many efficient algorithms have been proposed, the lack of deterministic performance has hindered the adoption and deployment of these algorithms: the expensive and power-hungry TCAM is still the de facto standard solution for Packet Classification. In this work, in contrast to proposing yet another new Packet Classification algorithm, we present the first steps to understand this unpredictability in performance for the existing algorithms. We focus on decision-tree based algorithms in this paper. In order to achieve the predictability, we firstly revisit the classical and many state-of-art Packet Classification algorithms. Through a detailed analysis, we conclude that two features of ruleset usually dominate the performance results: 1) the uniformity of the range distribution in different dimensions of the rules; 2) the existence and the number of “orthogonal structure” and wildcard rules in the ruleset. We conduct experiments to show the correctness of these observations, and discribe some potential applications for those results. Our work provides some insight to make the Packet Classification algorithms a credible alternative to the TCAM-only solutions.
Viktor K. Prasanna - One of the best experts on this subject based on the ideXlab platform.
-
Packet Classification Engine on FPGA
2020Co-Authors: Yun R. Qu, Viktor K. PrasannaAbstract:High-performance and dynamically updatable hardware architectures for multi-field Packet Classification have regained much interest in the research community. For example, software defined networking requires 15 fields of the Packets to be checked against a predefined rule set. Many algorithmic solutions for Packet Classification have been studied over the past decade. FPGA-based Packet Classification engines can achieve very high throughput; however, supporting dynamic updates is yet challenging. In this paper, we present a two-dimensional pipelined architecture for Packet Classification on FPGA; this architecture achieves high throughput while supporting dynamic updates. In this architecture, modular Processing Elements (PEs) are arranged in a two-dimensional array. Each PE accesses its designated memory locally, and supports prefix match and exact match efficiently. The entire array is both horizontally and vertically pipelined. We exploit striding, clustering, dual-port memory, and power gating techniques to further improve the performance of our architecture. The total memory is proportional to the rule set size. Our architecture sustains high clock rate even if we scale up (1) the length of each Packet header, or/and (2) the number of rules in the rule set. The performance of the entire architecture does not depend on rule set features such as the number of unique values in each field. The PEs are also self-reconfigurable; they support dynamic updates of the rule set during run-time with very little throughput degradation. Experimental results show that, for a 1 K 15-tuple rule set, a state-of-the-art FPGA can sustain a throughput of 650 Million Packets Per Second (MPPS) with 1 million updates/second. Compared to TCAM, our architecture demonstrates at least four-fold energy efficiency while achieving two-fold throughput. Index Terms—Packet Classification, field-programmable gate array (FPGA), two-dimensional pipeline, dynamic updates C
-
ASAP - Large-scale Packet Classification on FPGA
2015 IEEE 26th International Conference on Application-specific Systems Architectures and Processors (ASAP), 2015Co-Authors: Shijie Zhou, Yun R. Qu, Viktor K. PrasannaAbstract:Packet Classification is a key network function enabling a variety of network applications, such as network security, Quality of Service (QoS) routing, and other value-added services. Routers perform Packet Classification based on a predefined rule set. Packet Classification faces two challenges: (1) the data rate of the network traffic keeps increasing, and (2) the size of the rule sets are becoming very large. In this paper, we propose an FPGA-based Packet Classification engine for large rule sets. We present a decomposition-based approach, where each field of the Packet header is searched separately. Then we merge the partial search results from all the fields using a merging network. Experimental results show that our design can achieve a throughput of 147 Million Packets Per Second (MPPS), while supporting upto 256K rules on a state-of-the-art FPGA. Compared to the prior works on FPGA or multi-core processors, our design demonstrates significant performance improvements.
-
Scalable Many-Field Packet Classification on Multi-core Processors
2013 25th International Symposium on Computer Architecture and High Performance Computing, 2013Co-Authors: Yun Qu, Shijie Zhou, Viktor K. PrasannaAbstract:Packet Classification matches a Packet header against the predefined rules in a rule set, it is a kernel function that has been studied for decades. A recent trend in Packet Classification is to match a large number of Packet header fields. For example, the flow table lookup in Software Defined Networking (SDN) requires 15 fields of the Packet header to be examined. Another trend in Packet Classification is to use software-based solutions employing multi-core general purpose processors and virtual machines. Although Packet Classification has been widely studied, most existing solutions on multi-core systems target the classic 5-field Packet Classification, their performance cannot be easily scaled up for a larger number of Packet header fields. In this paper, we propose a decomposition-based Packet Classification approach, it supports large rule sets consisting of a large number of Packet header fields. We first use range-tree and hashing to search each field of the input Packet header individually in parallel. The partial results from all the fields are represented by bit vectors, they are merged in parallel to produce the final Packet header match. We also balance the search and merge latencies, and employ software pipelining to further enhance the overall performance. We implement our approach on state-of-the-art multi-core processors, we evaluate its performance with respect to throughput and latency for rule set size ranging from 1K to 32K. Experimental results show that, for a 32K rule set, our algorithms can achieve an average processing latency of 2000 ns per Packet and an overall throughput of 30 million Packets per second on a state-of-the-art 16-core platform.
-
scalable Packet Classification on fpga
IEEE Transactions on Very Large Scale Integration Systems, 2012Co-Authors: Weirong Jiang, Viktor K. PrasannaAbstract: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.
-
stridebv single chip 400g Packet Classification
High Performance Switching and Routing, 2012Co-Authors: Thilan Ganegedara, Viktor K. PrasannaAbstract:Hardware firewalls act as the first line of defense in protecting networks against attacks. Packets are organized into flows based on a set of Packet header fields and a predefined rule is applied on the Packets in each flow to filter malicious network traffic. This is realized using Packet Classification, which is implemented in secure networking environments where mere best-effort delivery of Packets is not adequate. Existing Packet Classification solutions are highly dependent on the properties (or features) of the ruleset. We present a bit vector based lookup scheme and a parallel hardware architecture that does not rely on ruleset features. A detailed performance analysis of the proposed scheme is given under different configurations. Post place-and-route results of our parallel pipelined architecture on a state-of-the-art Field Programmable Gate Array (FPGA) device shows that for real-life firewall rulesets, the proposed solution achieves 400G+ throughput. To the best of our knowledge, this is the first Packet Classification engine that achieves 400G+ rate on a single FPGA. Further, on the average we achieve 2.5× power efficiency compared with the state-of-the-art solutions.
Peng He - One of the best experts on this subject based on the ideXlab platform.
-
ICNP - Meta-algorithms for Software-Based Packet Classification
2014 IEEE 22nd International Conference on Network Protocols, 2014Co-Authors: Peng He, Kavé Salamatian, Laurent MathyAbstract:We observe that a same rule set can induce very different memory requirement, as well as varying Classification performance, when using various well known decision tree based Packet Classification algorithms. Worse, two similar rule sets, in terms of types and number of rules, can give rise to widely differing performance behaviour for a same Classification algorithms. We identify the intrinsic characteristics of rule sets that yield such performance differences, allowing us to understand and predict the performance behaviour of a rule set for various modern Packet Classification algorithms. Indeed, from our observations, we are able to derive a memory consumption model and an offline algorithm capable of quickly identifying which Packet Classification is suited to a give rule set. By splitting a large rule set in several subsets and using different Packet Classification algorithms for different subsets, our Smart Split algorithm is shown to be capable of configuring a multi-component Packet Classification system that exhibits up to 11 times less memory consumption, as well as up to about 4× faster Classification speed, than the state-of-art work [20] for large rule sets. Our Auto PC framework obtains further performance gain by avoiding splitting large rule sets if the memory size of the built decision tree is shown by the memory consumption model to be small.
-
Meta-algorithms for Software-Based Packet Classification
2014 IEEE 22nd International Conference on Network Protocols, 2014Co-Authors: Peng He, Kavé Salamatian, Laurent MathyAbstract:We observe that a same rule set can induce very different memory requirement, as well as varying Classification performance, when using various well known decision tree based Packet Classification algorithms. Worse, two similar rule sets, in terms of types and number of rules, can give rise to widely differing performance behaviour for a same Classification algorithms. We identify the intrinsic characteristics of rule sets that yield such performance differences, allowing us to understand and predict the performance behaviour of a rule set for various modern Packet Classification algorithms. Indeed, from our observations, we are able to derive a memory consumption model and an offline algorithm capable of quickly identifying which Packet Classification is suited to a give rule set. By splitting a large rule set in several subsets and using different Packet Classification algorithms for different subsets, our Smart Split algorithm is shown to be capable of configuring a multi-component Packet Classification system that exhibits up to 11 times less memory consumption, as well as up to about 4× faster Classification speed, than the state-of-art work [20] for large rule sets. Our Auto PC framework obtains further performance gain by avoiding splitting large rule sets if the memory size of the built decision tree is shown by the memory consumption model to be small.
-
Toward predictable performance in decision tree based Packet Classification algorithms
2013 19th IEEE Workshop on Local & Metropolitan Area Networks (LANMAN), 2013Co-Authors: Peng He, Laurent Mathy, Hongtao Guan, Kavé SalamatianAbstract:Packet Classification has been studied extensively in the past decade. While many efficient algorithms have been proposed, the lack of deterministic performance has hindered the adoption and deployment of these algorithms: the expensive and power-hungry TCAM is still the de facto standard solution for Packet Classification. In this work, in contrast to proposing yet another new Packet Classification algorithm, we present the first steps to understand this unpredictability in performance for the existing algorithms. We focus on decision-tree based algorithms in this paper. In order to achieve the predictability, we firstly revisit the classical and many state-of-art Packet Classification algorithms. Through a detailed analysis, we conclude that two features of ruleset usually dominate the performance results: 1) the uniformity of the range distribution in different dimensions of the rules; 2) the existence and the number of “orthogonal structure” and wildcard rules in the ruleset. We conduct experiments to show the correctness of these observations, and discribe some potential applications for those results. Our work provides some insight to make the Packet Classification algorithms a credible alternative to the TCAM-only solutions.
Kavé Salamatian - One of the best experts on this subject based on the ideXlab platform.
-
ICNP - Meta-algorithms for Software-Based Packet Classification
2014 IEEE 22nd International Conference on Network Protocols, 2014Co-Authors: Peng He, Kavé Salamatian, Laurent MathyAbstract:We observe that a same rule set can induce very different memory requirement, as well as varying Classification performance, when using various well known decision tree based Packet Classification algorithms. Worse, two similar rule sets, in terms of types and number of rules, can give rise to widely differing performance behaviour for a same Classification algorithms. We identify the intrinsic characteristics of rule sets that yield such performance differences, allowing us to understand and predict the performance behaviour of a rule set for various modern Packet Classification algorithms. Indeed, from our observations, we are able to derive a memory consumption model and an offline algorithm capable of quickly identifying which Packet Classification is suited to a give rule set. By splitting a large rule set in several subsets and using different Packet Classification algorithms for different subsets, our Smart Split algorithm is shown to be capable of configuring a multi-component Packet Classification system that exhibits up to 11 times less memory consumption, as well as up to about 4× faster Classification speed, than the state-of-art work [20] for large rule sets. Our Auto PC framework obtains further performance gain by avoiding splitting large rule sets if the memory size of the built decision tree is shown by the memory consumption model to be small.
-
Meta-algorithms for Software-Based Packet Classification
2014 IEEE 22nd International Conference on Network Protocols, 2014Co-Authors: Peng He, Kavé Salamatian, Laurent MathyAbstract:We observe that a same rule set can induce very different memory requirement, as well as varying Classification performance, when using various well known decision tree based Packet Classification algorithms. Worse, two similar rule sets, in terms of types and number of rules, can give rise to widely differing performance behaviour for a same Classification algorithms. We identify the intrinsic characteristics of rule sets that yield such performance differences, allowing us to understand and predict the performance behaviour of a rule set for various modern Packet Classification algorithms. Indeed, from our observations, we are able to derive a memory consumption model and an offline algorithm capable of quickly identifying which Packet Classification is suited to a give rule set. By splitting a large rule set in several subsets and using different Packet Classification algorithms for different subsets, our Smart Split algorithm is shown to be capable of configuring a multi-component Packet Classification system that exhibits up to 11 times less memory consumption, as well as up to about 4× faster Classification speed, than the state-of-art work [20] for large rule sets. Our Auto PC framework obtains further performance gain by avoiding splitting large rule sets if the memory size of the built decision tree is shown by the memory consumption model to be small.
-
Toward predictable performance in decision tree based Packet Classification algorithms
2013 19th IEEE Workshop on Local & Metropolitan Area Networks (LANMAN), 2013Co-Authors: Peng He, Laurent Mathy, Hongtao Guan, Kavé SalamatianAbstract:Packet Classification has been studied extensively in the past decade. While many efficient algorithms have been proposed, the lack of deterministic performance has hindered the adoption and deployment of these algorithms: the expensive and power-hungry TCAM is still the de facto standard solution for Packet Classification. In this work, in contrast to proposing yet another new Packet Classification algorithm, we present the first steps to understand this unpredictability in performance for the existing algorithms. We focus on decision-tree based algorithms in this paper. In order to achieve the predictability, we firstly revisit the classical and many state-of-art Packet Classification algorithms. Through a detailed analysis, we conclude that two features of ruleset usually dominate the performance results: 1) the uniformity of the range distribution in different dimensions of the rules; 2) the existence and the number of “orthogonal structure” and wildcard rules in the ruleset. We conduct experiments to show the correctness of these observations, and discribe some potential applications for those results. Our work provides some insight to make the Packet Classification algorithms a credible alternative to the TCAM-only solutions.
