Two versions of the Internet (IP) router-table problem are considered. In the first, the router table consists of n pairs of tuples of the form (p, a), where p is an address prefix and a is the next-hop information. In this version of the router-table problem, we are to perform the following operations: insert a new tuple, delete an existing tuple, and find the tuple with longest matching-prefix for a given destination address. We show that each of these three operations may be performed in O(log n) time in the worst case using a priority-search tree. In the second version of the router-table problem considered by us, each tuple in the table has the form (r, a), where r is a range of destination addresses matched by the tuple. The set of tuples in the table is conflict free. For this version of the router-table problem, we develop a data structure that employs priority-search trees as well as red-black trees. This data structure permits us to perform each of the operations insert, delete, and find the tuple with most-specific matching-range for a given destination address in O(log n) time each in the worst case. The insert and delete operations preserve the conflict-free property of the set of tuples. Experimental results also are presented.
Lu and Sahni REF use priority search trees to arrive at an Oðlog nÞ data structure for dynamic prefix-tables.
o(log n) dynamic router-tables for prefixes and ranges
IEEE Transactions on Computers
Computer Science