Design Issues in Network Processor Cache

Faculty: Tzi-cker Chiueh

Member(s): Prashant Pradhan , Kartik Gopalan

Project Description

The exponential growth in Internet traffic has motivated the development of a new breed of microprocessors called Network Processors, which are designed to address the performance problem resulting from exploding Internet traffic. A central design issue in network processor architecture is to perform packet classification at wire speed. Routing table lookup is a special instance of packet classification based solely on a packet's destination address. More concretely, the routing table lookup problem is to find the longest prefix match to a given packet's destination address from a table of prefix/mask pairs.

The current development efforts on network processors concentrate almost exclusively on streamlining their data-paths to speed up network packet processing. In particular, efforts are focussed on designing compact routing table representations and implementing the route lookup algorithms in hardware. Rather than blindly pushing the performance of packet processing hardware, an alternative approach is to avoid repeated computation by applying the time-tested architectural idea of caching to network packet processing. The caching technique memoizes the route lookup process, i.e., the cache remembers the results of previous route lookups for subsequent reuse. Because the data streams presented to network processors and general-purpose CPUs exhibit different characteristics, detailed cache design tradeoffs for the two also differ considerably.

Our research focuses on cache memory design specifically for network processors. Our results demonstrate that the incorporation of hardware caches into network processors, when combined with efficient caching algorithms, can significantly improve the overall packet forwarding performance. A major concern with the application of caching to the routing table lookup problem is the lack of sufficient locality in packet address streams when compared to instruction/data address streams in program execution, especially at the backbone routers. We argue that there exists sufficient locality in packet address streams at the granularity of address ranges, as opposed to individual addresses, to justify the use of caching in network processors.

We have proposed a series of novel network processor cache designs that aggresively exploit caching at the granularity of address ranges. These designs tackle the following three basic issues.

• Reducing capacity misses by minimizing the number of address ranges that need to be cached. We propose Host Address Range Cache (HARC) and Intelligent Host Address Range Cache (IHARC) that can improve the routing table lookup times over generic host address caching by a factor of five.



• Reducing conflict misses by balancing the number of address ranges across different cache sets. We propose two techniques that improve the basic IHARC design. The first reduces the deviation in number of address ranges mapped to each cache set and the second assigns variable number of cache sets to different IP address partitions.



• Maintaining cache consistency during frequent routing table updates. We propose a Selective Cache Invalidation technique that significantly minimizes the penalty of maintaining cache consistency in face of frequent routing table updates.

Currently we are extending the cache design to efficiently handle IPv6 addresses and multi-field classification.

  
Publications

• Tzi-cker Chiueh and Prashant Pradhan, High Performance IP Routing Table Lookup using CPU Caching In Proc. of IEEE INFOCOMM'99, New York, NY, March 1999, [ps]



• Tzi-cker Chiueh and Prashant Pradhan, Cache Memory Design for Network Processors, In Proc. of 6th Intl. Symp. on High Performance Computer Architecture, Tolouse, France, January 2000. [ps]



• Kartik Gopalan and Tzi-cker Chiueh, Improving Route Lookup Performance Using Network Processor Cache, In Proc. of SC2002 High Performance Networking and Computing, Baltimore, MD, November 2002, [ps] [extended]