IF-address lookup using LC-tries

There has recently been a notable interest in the organization of routing i nformation to enable fast lookup of LP addresses. The interest is primarily motivated by the goal of building multigigabit routers for the Internet, w ithout having to rely on multilayer switching techniques. We address this p roblem by using an LC-trie, a trie structure with combined path and level c ompression. This data structure enables us to build efficient, compact, and easily searchable implementations of an LP-routing table, The structure ca n store both unicast and multicast addresses with the same average search t imes. The search depth increases as Theta(log log n) with the number of ent ries in the table for a large class of distributions, and it is independent of the length of the addresses. A node in the trie can be coded with four bytes. Only the size of the base vector, which contains the search strings, grows linearly with the length of the addresses when extended from 4 to 16 bytes, as mandated by the shift from IP version 4 to IP version 6, We pres ent the basic structure as well as an adaptive version that roughly doubles the number of lookups/s, More general classifications of packets that are needed for link sharing, quality-of-service provisioning, and multicast and multipath routing are also discussed. Our experimental results compare fav orably with those reported previously in the research literature.