Research And Application Of Efficient Packet Classification Algorithm Based On Clustering

In recent years,the development of network technology has spawned many new emerging network applications,but the existing network cannot support these new applications commendably.A good performance packet classification algorithm not only plays a crucial role for enhancing network properties.Meanwhile,due to the existing network exposed more and more shortcomings,increasingly sophisticated functionality is added to the router's architecture,which greatly affected its performance improvement.Therefore,OpenFlow emerged and became one of the powerful enabler of this network innovative idea.While due to its flexibility and scalability,the requirements of packet classification in OpenFlow network are higher and more complex,but there is little existing solution specifically for OpenFlow packet classification in existing researches,which result in some limitations in performance.Therefore the design of a classification schema for OpenFlow packages becomes imperative.In response to these problems,the article mainly does the following work:(1)Proposed a novel efficient hierarchy Trie structure based on the no prefix relationship according to data mining.The structure can eliminate the hierarchical Trie backtracking based on the relationship between the different prefixes clustering way.Firstly,according to the relationship between them,the prefix is divided into different clusters,and use these clusters to build hierarchical Tries,the nodes in a single hierarchical Trie does not exist prefix relationship,thus eliminating the backtracking.And in virtue of the node path compressing strategy,which improved the memory performance to a large extent.(2)For the OpenFlow ultra five-tuple packet classification,this paper presents an alternative clustering approach,which is a design schema based on the prefix length clustering,the schema based on the prefix length for different prefix cluster,the prefixes in each cluster have the same prefix length.And then selectively merge these clusters.The principle of selection for the merging clusters not only meeting the requirements of the numbers of elements of the clusters,the requirement of no prefix relationship in each clusters is also needed.Finally,constructing the hierarchical Trie Tree based on the clusters.(3)For 12-tuple classification,the article designed a classification architecture that uses filtering solution to match the fields of 12-tuple group successively.According to the OpenFlow header parsing process,all the fields are divided into five search engines,while OpenFlow parse path shows that the IP search engines displays the important proportion,so firstly the IP search engine will pre-filter most of the rule,and then further find within the few rules left with the other search engines to get the final match rule,which largely increased the efficient of the 12-tuple packet classification.