Speaker: Michael E. Kounavis
Title: Directions in Packet Classification for Network Processors
Network processors are characterized by limited memory access bandwidth and limited storage capacity. As a result, many packet classification algorithms fail to meet the forwarding latency and memory storage requirements associated with network processors.
To identify new directions in solving the packet classification problem we studied the structure and statistical properties of lists of rules used in routers. We discovered that packet classification rules satisfy properties reflecting standard network administration practices, which simplify the classification problem significantly. Specifically, we discovered that the number of intersections which source-destination IP prefix pairs form is significantly less than the theoretical upper bound. We also found that a small number of ranges associated with transport level fields are sufficient to characterize data bases of different sizes. In this talk we discuss how our observations can help with the design of new algorithms that potentially meet the network processor constraints.
This is joint work with Prof. Andrew T. Campbell, Alok Kumar (Intel), Prof. Harrick Vin (Univ. of Texas Austin) and Dr. Raj Yavatkar (Intel).