The Research Of Fast Packet Classification Algorithm

The Internet users are demanding more reliable, secure and diverse network services as the rapid development of network technology and online applications. The routers need to provide diverse services such as firewalls of packet filtering, traffic billing, differentiated services and QoS to satisfy different users. In order to avoid the bottleneck of high-speed network caused by routers, a fast and efficient packet classification algorithm is accepted as a key component of high-speed routers. This thesis presents an ameliorate algorithm together with the experimental result based on Binary Search on Levels(BSOL) packet classification algorithm and Independent Set (IS) packet classification algorithm.Binary Search on Levels (BSOL) algorithm, which supports range and prefix rules, is a time efficient packet classification algorithm and can extend to multi-dimension packet classification easily while its performance is affected badly when the load factor of hash table is large or hash collision occurs frequently since the key structure is a hash table created by Trie tree in every layer. This thesis presents a new algorithm by introducing the Bloom Filter searching operation before the hash calculation to solve the larger loader factor issue when only uses the hash table. The experimental result shows that when the hit ratio of packet is less than 90 percent and the loader factor is relatively-larger, the new algorithm provides a better performance.Independent Set (IS) algorithm which only processes the starting point of regular interval rather than the FIS algorithm processes both the start and end points, is a space efficient algorithm while the neglects of priority of rules during the construction of independent sets affects the performance during the linear matching of packet. An algorithm is proposed by introducing a priority-sorted mechanism to solve the linear matching issues since the first matching rule is the final rule after sorting rather than traverse the whole rule index table. The experimental result shows that the new algorithm is much time efficient than IS. A proposal of split rule to reduce space consumption is also provided in this thesis to solve the issue of frequent creating new independent set during dynamic updates in IS algorithm.