부산대학교 도서관

The increase in routing table sizes, number of updates, traffic, speed of links and migration to IPv6 have made IP address lookup, based on longest prefix matching, a major bottleneck for high performance routers. We evaluate and compare several schemes based on complexity analysis and simulation results. We present a trie based scheme, which we call linked list cascade addressable trie (LLCAT), which is easy to be implemented in hardware and allows routing table update operations to be performed incrementally requiring very few memory operations guaranteed for worst case to satisfy requirements of dynamic routing tables in high speed routers. We also consider compression schemes to be applied to our algorithm to improve memory consumption and search time.