A B-tree dynamic router-table design

摘要: We propose B-tree data structures for dynamic router-tables the cases when filters are prefixes as well they nonintersecting ranges. A crucial difference between our structure prefix and MRT (multiway range trees) is that, in structure, each stored O(1) nodes per level, whereas, MRT, O(m) level (m order of B-tree). As a result this difference, measured average insert delete times using about 30 percent less than used. Further, an update operation will, worst case, make 2.5 many cache misses made The asymptotic complexity to find longest matching same time also nearly both structures. Both take O(n) memory. However, more memory efficient by constant factor. For case ranges, requires O(n log/sub m/n) O(log/sub accessed during (finding highest-priority range, range).