A B-tree dynamic router-table design

摘要

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