Scalable IPv6 Lookup/Update Design for High-Throughput Routers

Abstract

Achieving scalable performance in the IPv6 address lookup and update poses a challenge to the design of existing routers. To concurrently match address prefixes with different route entries, we propose a parallel memory lookup scheme which uses three-level tables to cover various lengths of prefix distributions for the long IP address. The scheme employs a parallel CRC address compression hardware to reduce the lookup table sizes. The multi-cycle implementation of the design has achieved an average of 1.6 memory accesses per lookup request. The pipeline version features a five-stage pipeline design with a mechanism to reduce pipeline stalls due to updates. Performance simulation reveals that the number of address queue entries significantly influences the lookup throughput when frequent table updates occur. The proposed single pipeline module with an eight-entry queue stage has achieved a maximum rate of 100×10^6 lookups per second. With the four-pipeline configuration, the throughput is increased by a factor of 2.5 for sparse updates and up to 2.3 when the update rate increases to 20 percents of the lookup's. This paper has demonstrated a viable IPv6 lookup design that is scalable for high-throughput routers.