Range Encoding and Hash table based Packet Classification for Global View Networking

Abstract

Packet classification is an important functionality of the Internet router for many network applications such as Quality of Service (QoS) firewall traffic control or analysis With the development of Internet and the mergence of software-defined networking (SDN) packet classification for global view networking is no longer just used to search for the action taken at a single router The global view of networks requires to identify the network-wide behaviors of packets which is defined as the combination of output actions As the search becomes more complex traditional packet classification methods are not efficient to be employed in today’s network architecture In this thesis we propose a 2-layer packet classification scheme named Range Encoding Hash Table (REHT) REHT can search for the network-wide behaviors of packets efficiently In layer 1 we encode the field values of the input header separately In layer 2 hash tables are used for the encoded values to achieve high classification speed Some header fields may be wildcard or a large range value in the multidimensional rule table These rules lead to a memory explosion problem in the hash table In response to this problem we define the wildcard standards for each header fields and reduce the memory usage by the proposed grouping optimizations Since we use hashing method to store and search rules we can solve the problem that cross-product may encounter and also reach very fast classification speed Experiments with real network datasets show that compared with another two methods for network-wide behaviors our proposed schemes have better performance in both memory consumption and classification speed

Date of Award	2017 Aug 29
Original language	English
Supervisor	Yeim-Kuan Chang (Supervisor)