High Speed Packet Classification Algorithms for Next Generation Network Services

Abstract

The routing and flow classification of IP packets is a vital component in operation newlineof Internet. The divergence and development of the Internet enforces increasing newlineexpectations from the network resources. Packet classification at link rates is vital newlinefor variety of upcoming value added next generation network services like security, newlineVoice-over Internet Protocol (VoIP), Video on Demand (VoD) and Quality of Service newline(QoS). QoS enabled routers, firewalls, network intrusion detection systems, differentiated newlineservices edge routers, etc. need to implement packet classification to find out to newlinewhich flow packet belongs to or which action is to be taken on it. Although variety newlineof hardware designs and software solutions are presented by the research community, newlinethe design and development of efficient packet classification system remains newlinea challenging problem. The factors which contribute to the difficulty are diversity newlineof rule specifications, scale of rule sets, variety of services offered, and throughput newlinerequirements of the high-speed networks. newlineThe research work presented in this thesis addresses solution to some of these newlineproblems which become a bottleneck with increasing link rates. The contributions newlineof this work include Fast Parallel Packet Classification (FPPC) algorithm, a new newlineparallel approach to packet classification to achieve high speed. Top-N selection newlinealgorithm is used to select non-overlapping active rules from the classifier according newlineto hit rate. By using these selected rules a classification data structure is constructed. newlineDisjoint grouping clustering algorithm and a new data structure are also proposed newlinewhich avoids backtracking. Hierarchical search results are passed on to the Bloom newlinefilters for final classification in place of traditional linear search. This results in newlineincreased throughput with slight decrease in memory efficiency. newlineHyper space Point Location (HPL) algorithm is a second contribution which is newlineinspired by recursive flow classification algorithm (RFCA) used for fast multidimensional packet classific