An evaluation of the key design criteria to achieve high update rates in packet classifiers

Abstract

The increased capacity of networks and nodes might enable us to keep pace with the growing traffic load, but the change of paradigm in IP networks towards a QoS-aware and multimedia-friendly infrastructure creates new bottlenecks in the communication path. An example of such a bottleneck is dynamic packet classification, which is fundamental to supporting any sort of QoS and value-added services. Typically, high update rates in packet classification designs have been sacrificed to achieve better search times or to reduce storage capacity requirements. By carefully analyzing current proposals, we unveil three previously neglected key design criteria for general classifiers to successfully achieve high update rates at wire speed: filter localization, nonstructural dependencies, and dynamic precomputation. We also analyze their impact in current algorithms.