ABSTRACT
The primary prefix partitioning scheme was proposed by B. Lampson et al. The scheme is not suitable for dynamic routing tables. Haibin Lu et al. proposed a prefix partitioning scheme and interval partitioning to improve the performance of dynamic routing table designs. The interval-partitioning scheme is an alternative to the one-level dynamic partitioning and two-level dynamic partitioning schemes that may be applied to interval-based structures such as the alternative collection of binary search tree. N.-F. Tzeng proposed a partitioning scheme to fragment the routing table into N sub-tables, one for each line card, so that the number of entries in each sub-table drops as the router grows, and the table lookup is accelerated. Partitioning is done using appropriately chosen bits in internet protocol prefixes, and a subset of routing table prefixes is referred to as an ROT-partitioning. Using ROT-partition scheme, the routing table is partitioned into sub-tables in accordance with the number of line cards in the router.
