PAPER A Small and Fast IP Forwarding Table Using Hashing∗

SUMMARY Building next generation routers with the capability of for-warding multiple millions of packets per second is required for the increas-ing demand for high bandwidth on the Internet. Reducing the required memory size of the forwarding table is a possible solution since small for-warding table can be integrated into the application specific integrated cir-cuit (ASIC). In this paper a hash technique is developed to reduce the size of the IP forwarding table. The proposed data structure is a compressed 8-8-8-8 multibit trie that is based on hash tables of 4-bit addresses. Two optimization techniques are also proposed to further improve the perfor-mance of the proposed schemes. Our experimental results show that the proposed hashing-based schemes are better than the Small Forwarding Ta-ble scheme [6] both in memory size and lookup latency. key words: hash table, IP lookup, binary trie 1