A small and fast IP forwarding table using hashing

Building next generation routers with the capability of for-warding multiple millions of packets per second is required for the increasing 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 circuit (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 performance of the proposed schemes. Our experimental results show that the proposed hashing-based schemes are better than the Small Forwarding Table scheme [6] both in memory size and lookup latency.