by Zhen Liu, Alan Kennedy, Olga Ormond and Xiaojun Wang
Building high-performance and power-efficient packet classifiers is important for the success of next-generation networking devices. The Network Processing Group, part of the Network Innovations Centre (NIC) in the Research Institute for Networks and Communications Engineering (RINCE) at Dublin City University (DCU), is devoted to research in this area.
Packet classification involves matching several fields extracted from a packet header to a set of pre-defined rules in order to determine the follow-up action to be performed on the packet by networking devices. As one of the key functions of a router/switch, packet classification is widely used in applications such as policy-based routing, Quality of Service (QoS), Virtual Private Networks (VPN), network security (eg firewalls and intrusion detection) and sophisticated traffic billing. Transmission line speeds keep increasing. For example, the state-of-art line rate of OC-768 (40 Gbps), used in optical fibre backbone networks, demands a worst-case processing speed of 125 million packets per second. In addition to meeting the ever-increasing line rates, growing attention has been paid to reducing power consumption in the design of next-generation networking devices, since it is desirable for the packet classifier to consume as little energy as possible.
The most commonly used header fields in packet classification form a 5-tuple, which includes source IP address and destination IP address for prefix matching, source port and destination port for range matching, and protocol number for exact or wildcard matching. The typical size of a rule-set ranges from hundreds to millions of rules, depending on the application and location of the router/switch. Due to the complexity of packet classification, Ternary Content Addressable Memory (TCAM) is frequently used, which can guarantee millions of searches per second by examining all rules simultaneously. However, the high power consumption caused by the parallel comparison in TCAM makes it less likely to be incorporated in the design of future power-efficient networking equipment.
Our project aims to design a packet classifier that meets the challenges of both high speed and low power consumption. In order to achieve this goal, we choose to implement in hardware a packet classification algorithm (HyperCuts) based on a decision tree, meaning TCAM can be replaced with energy-efficient memory devices such as SRAM or DRAM. This type of algorithm recursively cuts the hyperspace represented by the rule-set into smaller hyper-boxes called Regions along some selected dimensions, forming a decision tree, until the number of rules contained in the resulting hyper-boxes is smaller than a predefined threshold. When a packet is received, the classifier traverses down the decision tree, based on the value of header fields, until a leaf node is found and searched for the matching rules. The structure and parameters of the packet classifier are carefully selected to make sure that only a small number of memory accesses are needed in order to guarantee the throughput.
Figure 1: Architecture of the decision-tree-based packet classifier.
The major parts of the packet classifier are the Tree Traverser and Leaf Searcher (see Figure 1). Each internal node contains the cutting scheme to be performed on the hyperspace represented by this node, and the starting address of each child node. Other information, such as whether the child node is a non-empty leaf, is also coded. In each leaf node, rules are stored in the order of priority, along with their IDs. When the cutting scheme is fetched and interpreted, the Region corresponding to the header fields is selected, ie the starting address of this child node will be read out from memory and used for the next round of tree traversing. If a non-empty leaf is encountered, the control is passed to Leaf Searcher. The rules are compared against packet header fields one by one, until either a matching rule is found or all of the rules have been examined.
The power consumption of the packet classifier can be further reduced by exploiting the common fluctuations in network traffic. For example, traffic volume during the night might be less than one third of the peak day rate. This phenomenon implies that the packet classifier need not always run at its highest possible clock speed. When the packet arrival rate is low, the packet classifier can reduce its working frequency to an appropriate level in order to save energy. In our project, we use a header buffer to monitor changes in network traffic, with the number of outstanding packet headers waiting for classification working as an indicator of the frequency required for the packet classifier.
Our packet classifier can be easily implemented in hardware (FPGA or ASIC), working as an individual component on a line card or integrated into a network processor. The experiments performed on sample implementations in Altera FPGA and ASIC show that our packet classifier can achieve packet classification throughput of up to OC-768 line rate with significantly lower power consumption than TCAM implementations.
Link:
http://wiki.eeng.dcu.ie/nic/278-EE.html
Please contact:
Olga Ormond
Network Innovations Centre, RINCE
Dublin City University, Ireland
Tel: +353 1 700 5444
E-mail:
Xiaojun Wang
Network Innovations Centre, RINCE
Dublin City University, Ireland
Tel: +353 1 700 5808
E-mail:
