Cache Architecture for High-Speed Multidimensional Packet Processing

In this paper, we implement a multi-dimensional packet classification that is based on the hierarchical binary prefix search. We first implement the multi-dimensional binary prefix search packet classification on Intel IXP2400 Network Processor that does not have hardware supported cache. To further improve the performance of our proposed search, we develop a software-based cache scheme. We introduce the idea of "partial hit" in which the packet header not only matches the first dimension of the cache entry but not the first two dimensions. With the specially processing to the case "partial hit", our cache has contribution to the overall performance even when the cache is not hit.