O(log n) dynamic router-tables for prefixes and ranges
Authors:
- Sartaj SahniSSSartaj Sahni
- 30 August 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 53 (10) , 1217-1230
Abstract
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 are also presented.Keywords
This publication has 29 references indexed in Scilit:
- Fast routing table lookup using CAMs2002
- Detecting and resolving packet filter conflicts2002
- Routing with a clueIEEE/ACM Transactions on Networking, 2001
- An evaluation of the key design criteria to achieve high update rates in packet classifiersIEEE Network, 2001
- Fast address lookup for Internet routers1998
- IP switching and gigabit routersIEEE Communications Magazine, 1997
- Trading packet headers for packet processingIEEE/ACM Transactions on Networking, 1996
- Routing on longest-matching prefixesIEEE/ACM Transactions on Networking, 1996
- Priority Search TreesSIAM Journal on Computing, 1985
- Data Structures and Algorithms 11984