Optimizing packet lookup in time and space on FPGA

The evolution of the Internet has transformed the simplistic Ethernet/IP based packet forwarding into a complex collection of lookup schemes. Depending on the location of the networking equipment (core, provider/customer edge, etc.,) a router/switch may potentially have to support several such complex lookup schemes. However, the hardware resources allocated to perform such operations are limited, especially in single chip implementations. In this paper, we propose techniques to map such complex lookup schemes on to hardware platforms under a limited resource budget and produce a design for a pipelined packet lookup architecture. An Integer Linear Programming (ILP) based technique is introduced to optimally allocate the limited hardware resources for a single lookup scheme. We extend our solution to multiple lookup schemes by proposing techniques to improve resource sharing, which results in a resource planning tool. Field Programmable Gate Array (FPGA) - a natural choice for high-speed packet processing applications - is used as the target platform. By using the proposed techniques, we show that up to 4 complex lookup schemes can be hosted on a single FPGA consuming only 20 Mbit on-chip memory and 750 pins for external memory communication.