Title
Enhanced Interval Trees for Dynamic IP Router-Tables
Abstract
We develop an enhanced interval tree data structure that is suitable for the representation of dynamic IP router tables. Several refinements of this enhanced structure are proposed for a variety of IP router tables. For example, the data structure called BOB (binary tree on binary tree) is developed for dynamic router tables in which the rule filters are nonintersecting ranges and in which ties are broken by selecting the highest-priority rule that matches a destination address. Prefix filters are a special case of nonintersecting ranges and the commonly used longest-prefix tie breaker is a special case of the highest-priority tie breaker. When an n-rule router table is represented using BOB, the highest-priority rule that matches a destination address may be found in O(\log ^2 n) time; a new rule may be inserted and an old one deleted in O(\log n) time. For general ranges, the data structure CBOB (compact BOB is proposed). For the case when all rule filters are prefixes, the data structure PBOB (prefix BOB) permits highest-priority matching as well as rule insertion and deletion in O(W) time, where W is the length of the longest prefix, each. When all rule filters are prefixes and longest-prefix matching is to be done, the data structure LMPBOB (longest matching-prefix BOB) permits longest-prefix matching in O(W) time; rule insertion and deletion each take O(\log n) time. On practical rule tables, BOB and PBOB perform each of the three dynamic-table operations in O(\log n) time and with O(\log n) cache misses. The number of cache misses incurred by LMPBOB is also O(\log n). Experimental results also are presented.
Year
DOI
Venue
2004
10.1109/TC.2004.116
IEEE Trans. Computers
Keywords
Field
DocType
special case,highest-priority rule,binary tree,dynamic ip router-tables,packet classification,enhanced interval trees,log n,highest-priority matching,compact bob,rule insertion,router tables,dynamic rule-tables,longest-prefix matching,new rule,rule filter,packet routing,destination address,rule insertion and deletion.,interval trees,practical rule table,packet switching,data structure,longest prefix matching,computational complexity,tree data structures
Data structure,Computer science,Cache,Tree (data structure),Parallel computing,Binary tree,Prefix,Longest prefix match,Router,Interval tree
Journal
Volume
Issue
ISSN
53
12
0018-9340
Citations 
PageRank 
References 
20
0.78
22
Authors
2
Name
Order
Citations
PageRank
Haibin Lu117011.90
Sartaj Sahni263161764.85