A dynamic indirect IP lookup based on prefix relationships

Internet is growing very rapidly in both the size and the traffic. Routers with efficient IP lookup schemes are needed to handle the amount of traffic. The IP lookup scheme is a key issue in design of IP routers, which searches the next hop of each incoming packet with a longest prefix matching in routing table. This operation is complex and is a major bottleneck in a high performance router. In this paper, we propose a fast and updateable scheme for dynamic routing tables that can dynamically insert and delete prefixes. We adopt a compressed bitmap data structure for IP lookup and develop a prefix parent relationship data structure for dynamically update prefixes. The simulation reveals that our scheme has high performance in IP lookup, even using real IPv4 routing tables with large entries.