Efficient Packet Classification Algorithm Based On The Aggregation Feature Of Rule

The rapid development of Cloud Computing and Big Data brings an increasing number of Internet applications,resulting in a substantial amplification of the data scale.The traditional best-effort network services simply can't meet the needs of customers.Packet Classification is a key functionality for next-generation Internet routers to provide various advanced services.So quickly classify packets for network development is of great significance.Currently,the researchers began to study the packet classification towards a broader scope.The clustering ideas can solve the problems that encountered in the field of packet classification.Packet classification based clustering algorithms typically introduced clustering analysis in the formal modeling of packet classification.Then,the aggregation feature of rule is used to design efficient and flexible packet classification structures,algorithms,and mechanisms for enhancing the overall performance of packet classification.In recent years,IPv4 address shortage,the future development of the Internet is inseparable from the IPv6 support.Therefore,the packet classification algorithm design of simple and support both IPv4 and IPv6 is a challenging task.In response to these problems,this paper do the following work:(1)The Efficient Total Prefix Length-Based Clustering Packet Classification Algorithm(TPLC)is proposed.By analyzing and using the aggregation features of real IPv4 rule,TPLC algorithm design an efficient hybrid hierarchical search structure.The first layer structure partitions the rules into different clusters according to the source/destination address total prefix length.Building a priority pruning binary tree according to these clusters and the rules that highest priority.Each cluster is a valid search tree node.There are a lot of blank node in the Area based Quad-Tree traditional algorithmic search architecture,memory space is a great waste.Building the Priority Area-based Quad-Tree(PAQT)in these clusters.The PAQT tree puts high priority rules into the lower level empty nodes.By this way,the TPLC algorithm greatly reduced the gap in the middle of the node and speeded up the search process.(2)An IPv6 packet classification algorithm based on the Priority Trie(Ptrie)is proposed.The research and analysis based on the real network IPv6 rule,this paper found that:1)there are only a few different values for the first 16 bits of the source/destination address prefix;2)most of the source/destination address prefixes begin with 0x2001,the prefixes begin with other values are very few;3)there is no prefix with prefix length less than 16.According to these characteristics,the algorithm begin reducing the dimension from 17 bits of the rule's source/destination address prefix by prefix bitwise XOR,finally get a recombination IP address prefix.Building the Priority Trie according to this recombination IP address prefix.The higher priority rule is placed ahead of the lower level in the empty node of the Trie.By this way,the Ptrie algorithm greatly save memory space and reduce the depth of the trie.