High Speed IP Address Lookup Architecture Using Hashing

Hyesook Lim, Ji Hyun Seo, Yeo Jin Jung

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

One of the most important design issues for IP routers responsible for datagram forwarding in computer networks is route-lookup mechanism. In this letter, we explored a practical IP address lookup scheme which converts longest prefix matching problem into the exact matching problem. In the proposed architecture, the forwarding table is composed of multiple SRAMs, and each SRAM represents an address lookup table in a single prefix. Hashing functions are applied to each address lookup table in order to find out matching entries in parallel, and the entry matched with the longest prefix among them is selected. Simulation using data from MAE-WEST router shows that a large routing table with 37 000 entries is compacted to a forwarding table of 189 kbytes in the proposed scheme and achieves one route lookup every two memory accesses in average.

Original languageEnglish
Pages (from-to)502-504
Number of pages3
JournalIEEE Communications Letters
Volume7
Issue number10
DOIs
StatePublished - Oct 2003

Keywords

  • Address lookup
  • Best matching prefix
  • Longest prefix matching
  • Parallel hashing

Fingerprint

Dive into the research topics of 'High Speed IP Address Lookup Architecture Using Hashing'. Together they form a unique fingerprint.

Cite this