Search

To support fast rule updates in SDN, the Open vSwitch implements Priority Sorting Tuple Space Search (PSTSS) for its packet classifications. Although it has good performance on rule updates, it has a performance concern on table lookups. In contrast, decision tree methods are being actively investigated for high throughput, but they are not able to support fast updates because of rule replications. CutSplit, the state-of-the-art decision tree scheme, provides a novel rule update mechanism by avoiding tree reconstructions. However, its average update time is still two orders of magnitude larger than PSTSS. Meanwhile, existing decision trees are not only unbalanced but also depth unbounded, making them difficult to be optimized on FPGA. In this paper, we present a new decision tree scheme called TabTree, which achieves high performance on both lookups and updates. By mapping rules into tree nodes dynamically, a very limited number of balanced trees with bounded depths can be generated without the trouble of rule replications. Experimental results show that, TabTree has comparable update performance to PSTSS, but it outperforms PSTSS significantly in terms of number of memory accesses for packet classification. Additionally, TabTree is more practical for implementations on FPGA.

Packet classification is a very important component for today's network architecture. It can help or provide packet forwarding and other network functions. With the development of Internet and the emergence of software-defined networking (SDN), the methods designed for the traditional 5-dimensional rule set is not sufficient to process the current rule set that contains rules of 12 or more dimensions. The main problem is to process the rule sets of 12 or more dimensions in high throughput. To achieve high throughput, we study the implementations on GPU where some use a single hash table and others use Binary Range Tree to process the searching. In 12-dimensional rule sets defined by OpenFlow 1.0, 8 fields are in the format of exact value or wildcard, and so using the single hash table or binary range tree is not efficient. Another problem to implement packet classification on GPU is that we must transfer the input data and results via the PCI-E bus that will incur long bus latency. In this paper, we propose a modified hash table to process the fields that contain only exact value or wildcard, and use the compressing method to reduce memory consumption. On the other hand, we implement the proposed method on APU that uses Heterogeneous System Architecture to skip the bus latency. According to the experimental results on AMD A10–7850 APU, our method can achieve the throughput of 1814 MPPS, and can support the rule sets of more than 12K 12-dimensional rules. The achieved throughput is 10 times of the methods on legacy GPU.

The future of fast Internet needs powerful routers to support abundant network functionalities, such as firewall, QoS, and virtual private networks, by classifying the packets into different categories based on a set of predefined rules, so-called multi-field packet classification. Traditional packet classification that considers only 5-tuple fields is not sufficient for today’s complicated network requirements. OpenFlow switch was born to take care of these complex requirements using a rule set with the rich definition as the software–hardware interface. This paper considers OpenFlow1.0, consisting of 12-tuple header fields. We propose two schemes to process the range fields. The first scheme has the same characteristic as StrideBV [15] using specially designed codes to store the pre-computed results in memory. The second scheme uses a simple sub-range comparison method to find the matching result in a sequential fashion. To show the performance and compare with other proposed schemes, we implement the proposed schemes on Xilinx Virtex-6 XC6VLX760 FPGA device. Experimental results show that our designs can handle 5 K more OpenFlow rules on Virtex-6 XC6VLX760. To the best of our knowledge, our proposed scheme is the first range supported method that can sustain the throughputs of more than 380 MHz.

Software-Defined Networking (SDN) attracts the attention of many researchers in the academic and industry. OpenFlow protocol is a solution of SDN. In OpenFlow version 1.3, there are 40 match fields. This makes the design of switch more complicated. Casado et al. describe a new network architecture, called fabric network [2]. They separate the network elements into edge switches and core switches. Edge switches tag a label onto packet header, and core switches use this label to perform lookup. In this paper, we propose a scheme called Path_label switching. In this scheme, core switch only uses one field to perform lookup. In order to reduce the number of rules in edge switches, we encode the output port number of the last hop into MPLS field. We also propose a scheme to minimize the number of rules in fat-tree topology. In our scheme, the number of rules in core and aggregation switches is the same as the number of ports. We use Mininet to construct the experiments. We will show that our proposed scheme needs much less number of rules than other methods in leaf-spine and fat-tree topologies.