Name
Abstract | ||
|---|---|---|
We consider router tables comprised of n pairs of tuples of the form (r,a), where r is a range of destination addresses matched by the tuple. The set of ranges in the table is conflict free. We develop a data structure, which employs priority-search trees as well as red-black trees, to represent the router table. 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) each time. The insert and delete operations preserve the conflict-free property of the set of tuples. Our data structure represents the first O(log n) data structure for dynamic router tables with ranges. Experimental results are also presented. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/ISCC.2003.1214106 | Computers and Communication, 2003. |
Keywords | DocType | ISSN |
internet,packet switching,table lookup,telecommunication network routing,tree data structures,tree searching,conflict-free property,data structure,delete operations,destination addresses,dynamic router-tables,insert operations,lookup operation,most-specific range matching,packet routing,priority-search trees,range sets,ranges,red-black trees,tuples,update operations | Conference | 1530-1346 |
ISBN | Citations | PageRank |
0-7695-1961-X | 3 | 0.48 |
References | Authors | |
11 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haibin Lu | 1 | 170 | 11.90 |
| Sartaj Sahni | 2 | 6316 | 1764.85 |