Merge FSM Based Low Power Packet Classification

Abstract

Packet classification is a vital and complicated task as the processing of packets should be done at a specified line speed. In order to classify a packet as belonging to a particular flow or set of flows, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. Packet classification is used by networking equipment to sort packets into flows by comparing their headers to a list of rules. A flow is used to decide a packet’s priority and the manner in which it is processed. Packet classification is a difficult task due to the fact that all packets must be processed at wire speed and rulesets can contain tens of thousands of rules. Also the performance of today's packet classification solutions depends on the characteristics of rulesets. The range-based packet classification function maps input packets to the highest-priority matching rule in a given rule set specified by ranges. In this project, a Merge FSM model based Classifier is proposed to reduce its complexity and time consumption. The contributions of this work towards the area of packet classification are hardware accelerators that allow packet classification to be implemented at core network line speeds when classifying packets using rulesets containing tens of thousands of rules. A new pre-cutting process has been implemented to reduce the memory size to fit in an FPGA. This classifier can classify packets with high speed and with a power consumption factor of less than 3W. The proposed algorithm also removes the need for floating point division to be performed when classifying a packet, allowing higher clock speeds and thus obtaining higher throughputs.