Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1999-01-01

Filename

WUCS-99-28.PDF

DOI:

10.7936/K7TX3CMR

Technical Report Number

WUCS-99-28

Abstract

Internet routers forward packets based on the destination address of a packet. A packet's address is matched against the destination prefixes stored in the router's forwarding table, and the packet is sent to the output interface determined by the longest matching prefix. While some existing schemes work well for IPv4 addresses, we believe that none of the current schemes scales well to IPv6, especially when fast updates are required. As the Internet evolves into a global communication medium, requiring multiple addresses per user, the switch to longer addresses (e.g. IPv6) seems inevitable despite temporary measures such as network addres translation (NAT) boxes. Since IPv6 uses 128 bit addresses, schemes whose lookup time groqws with address length (such as patricia or multi-bit tries) become less attractive. Because of backbone protocol instabilities, it is also important that lookup schemes be able to accomodate fast updates. In this paper, we introduce a new IP lookup scheme with worst-case search and update time of O(log n), where n is the number of prefixes in the forwarding table. Our scheme is based on a new data structure, a multiway range tree, which achieves the optimal lookup time of binary search, but can also be updated in logarithmic time when a prefix is added or deleted; by contrast, plain binary search relies on precomputation, and a single update can require O(n) time. Our performance analysis shows that, even for IPv4, multiway range trees are competitive with the best lookup schemes currently known. In fact, among existing schemes, only multibit tries have update performance comparable to our scheme. However, when considering IPv6 or any future routing protocol that uses longer addresses, our scheme outperforms all existing schemes, including multibit tries.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7TX3CMR

Download

Share

COinS