Network processor memory hierarchy designs for IP packet classification

The use of Application Specific Integrated Circuits (ASICs) for processing Internet Protocol (IP) packets is becoming infeasible due to increasing network wire transmission speeds, coupled with frequent improvements to existing algorithms. Development time and cost to fabricate a new generation of ASICs to implement newly developed algorithms is increasing. The age of programmable network processors (NPs) has arrived, since their flexibility allows reuse and thus amortizes their development cost over successive generations of network applications.; The flexibility of network processors comes at a price; there is a trade-off in performance compared to ASICs. One major factor is the performance of the memory subsystem. This dissertation discusses the design of memory hierarchies for network processors to achieve high performance in IP packet forwarding and classification. We demonstrate how caching can be used to improve the performance of a trie-based IP forwarding algorithm. We develop a new packet classification algorithm based on partitioning classification rules into separate categories. Packets are classified independently using each rule category and then results are combined. The advantage is two-fold: parallel computation and reduced memory requirements per rule category. The algorithm is thus well-suited for implementation on multiple NPs which have limited memory. We justify our approach through trace-driven simulation.