Prefix and interval-partitioned dynamic IP router-tables
Two schemes-prefix partitioning and interval partitioning - are proposed to improve the performance of dynamic IP router-table designs. While prefix partitioning applies to all known dynamic router-table designs, interval partitioning applies to the alternative collection of binary search tree designs of Sahni and Kim [18]. Experiments using public-domain IPv4 router databases indicate that one of the proposed prefix partitioning schemes-TLDP-results in router tables that require less memory than when prefix partitioning is not used. Further significant reduction in the time to find the longest matching-prefix, insert a prefix, and delete a prefix is achieved.
prefix partitioning interval partitioning tables longest packet routing dynamic router prefix matching