A comparative review of scalable lookup algorithms for IPv6

IPv4 addresses have been exhausted, and the Internet is moving to IPv6. Many IP lookup algorithms have been proposed in the past. In this paper, we analyze their scalability and applicability to IPv6. In particular, we calculate the memory requirements of diverse lookup algorithms and compare them for different lookup table sizes, assuming the high lookup throughput of one lookup per memory access. The BPFL (Balanced Parallelized Frugal Lookup) algorithm requires the smallest external and internal memories for the examined IPv6 lookup tables. In BPFL, the lookup table is defined using the range selector, balanced trees, and bitmaps. Lookup algorithms based on hashing and TCAMs also use memory frugally.