A parallel IP lookup algorithm for terabit router
Kai Zheng, Hongbin Lu, Bin Liu · 2004
IP address lookup is a key bottleneck for high performance routers because they need to find the longest matching prefix. With traditional memory organization, core routers can hardly improve their performance much with the restriction of memory accessing speed. By analyzing the statistical attribution of the IP prefixes, this paper presents a novel parallel IP lookup algorithm based on a new memory organization, which can achieve a much higher throughput rate while keeping the memory consumption unchanged. With current 5 ns SRAM, the proposed mechanism furnishes approximately 600 million routing lookups per second.