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, Amerika Birleşik Devletleri, 1 - 03 Mayıs 2011, ss.77-80 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/fccm.2011.61
  • Basıldığı Şehir: Utah
  • Basıldığı Ülke: Amerika Birleşik Devletleri
  • Sayfa Sayıları: ss.77-80
  • Anahtar Kelimeler: IP lookup, packet forwarding, longest prefix match, binary search tree, search trie, Tree Bitmap
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.