Parallel IP Address Lookup using Hashing with Multiple SRAMs

One of the important design issues for IP routers responsible for packet forwarding in computer networks is the route-lookup mechanism. For each incoming packet, IP routing requires that a router performs a longest-prefix-match address lookup in order to determine the next hop that the incoming packet should be forwarded to. In this paper, we present a new scheme which applies the hashing function for IP address lookup. In the proposed scheme, the forwarding table is composed of multiple SRAMs, and each SRAM represents an address lookup table in each prefix. Hashing function is applied in order to find out the matching entries from the address lookup tables in parallel, and the entry with the longest prefix match among them is selected. Simulation using the MAE-WEST router example shows that a large routing table with 37000 entries can be compacted to a forwarding table of 300 Kbytes in the proposed scheme. It is also shown that the proposed scheme achieves one route lookup every 1.93 memory accesses in average.