On fast address-lookup algorithms

摘要

The growth of the Internet and its acceptance has sparkled keenninterest in the research community in respect to many apparent scalingnproblems for a large infrastructure based on IP technology. Anself-contained problem of considerable practical and theoreticalninterest is the longest-prefix lookup operation, perceived as one of thendecisive bottlenecks. Several novel approaches have been proposed tonspeed up this operation that promise to scale forwarding technology intongigabit speeds. This paper surveys these new lookup algorithms andnclassifies them based on applied techniques, accompanied by a set ofnpractical requirements that are critical to the design of high-speednrouting devices. We also propose several new algorithms to providenlookup capability at gigabit speeds. In particular, we show thentheoretical limitations of routing table size and show that one of ournnew algorithms is almost optimal, while requiring only a small number ofnmemory accesses to perform each address lookup