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

Yang Y. E., Erdem O., Prasanna V. K.

IEEE 19th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Utah, United States Of America, 1 - 03 May 2011, pp.77-80, (Full Text) identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/fccm.2011.61
  • City: Utah
  • Country: United States Of America
  • Page Numbers: pp.77-80
  • Keywords: IP lookup, packet forwarding, longest prefix match, binary search tree, search trie, Tree Bitmap
  • Middle East Technical University Affiliated: Yes

Abstract

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 TreeBitmap 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 thoughput with 64-byte packets) against 9.5 million prefixes on state-of-the-art FPGA.