An Incremental Update Algorithm of High Performance Packet Classification

Packet classification is one of the core issues in wire speed packet input processing research The key problem of packet classification is to find a dynamic algorithm with worst case performance for 1000000 rules Grid of tries algorithm is one of the packet classification algorithm with worst case performance, and can scale to 1000000 rules But the weaknesses of the grid of tries are static and 2 dimension algorithm In this paper, an incremental update algorithm for grid of tries, is proposed Thus grid of tries becomes a dynamic algorithm, and the synthetic performance of grid of tries is improved