High Performance IP Lookup on FPGA with Combined Length-Infix Pipelined Search

We propose a combined length-infix pipelined search (CLIPS) architecture for high-performance IP lookup on FPGA. By performing binary search in prefix length, CLIPS can find the longest prefix match in (log L-c) phases, where L is the IP address length (32 for IPv4) and c>;0 is a small design constant (c=2 in our prototype design). Each CLIPS phase matches one or more input infixes of the same length against a regular data structure. Various CLIPS phases can be optimized individually: (1) 16 bits of the IP address are used to direct-access a 288-kbit on-chip BRAM in phase 1, (2) 8 additional bits of the IP address are used to search a 1.5-million-entry pipelined dynamic search forest for a match in phase 2, (3) 1 to 8 additional bits of the IP address are used by a 2-stage Tree Bitmap for storing another 1 to 8 million routing prefixes in the tail phase. Post place-and-route results show that our CLIPS prototype, utilizing 28 Mbits on-chip BRAM and 4 external SRAM channels, sustains 312 MPPS IPv4 lookup (or 160 Gbps routing though put with 64-byte packets) against 9.5 million prefixes on state-of-the-art FPGA.