Multi-layered Binary Prefix Search for Packet Classification

Abstract

Packet classification is a key functionality of the Internet routers for many network applications such as Quality of Service (QoS) security monitoring analysis and network intrusion detection (NIDS) The existing well-known decision-tree-based schemes like HiCuts HyperCuts and EffiCuts suffer from a memory explosion problem caused by rule duplication and the number of memory accesses are inseparable with the height of decision tree they built In this thesis we propose a scheme called binary search on buckets (BSOB) for multi-dimensional packet classification problem BSOB performs binary searches on the ID (prefix) of ordered leaf nodes in the decision tree We give a pointer to tree node pointing to its corresponding ancestor node based on their prefix When searching to a certain node the fast link can be utilized to directly access to its ancestor node that is related to the certain node Hence BSOB can improves the existing well-known decision-tree-based schemes that need to traverse the decision tree from the root node to some leaf nodes In order to solve the memory explosion problem caused by decision-tree-based scheme we divide the original rule table into multiple groups and construct the BSOB structure to each group Moreover we use node retain technique which retains the rule that causes duplication in internal node Hence the rule duplication problem can be reduced For 12 types classifiers with 100 000 rules generated by ClassBench our experimental results implemented on a PC software environment show that BSOB uses 2 5-2 8 MB memory and needs 8-15 memory accesses in average case and 21-51 memory accesses in worst case that is much better than the existing well-known decision-tree based schemes We also show the update results of BSOB Insert operation is about 1-3 times higher than search and the delete operation is close to the search speed Because of the advantage of less memory usage and high classification speed BSOB is able to address the packet classification problems in SDN environment that has more header fields and large rule sizes

Date of Award	2016 Aug 16
Original language	English
Supervisor	Yeim-Kuan Chang (Supervisor)