High speed IP address lookup architecture using hashing

摘要

One of the most important design issues for IP routers responsible for datagram forwarding in computer networks is the route-lookup mechanism. In this letter, we explore a practical IP address lookup scheme which converts the longest prefix matching problem into the exact matching problem. In the proposed architecture, the forwarding table is composed of multiple SRAM, 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 the MAE-WEST router shows that a large routing table with 37000 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.