Prefix and Interval-Partitioned Dynamic IP Router-Tables

Abstract

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 [S. Sahni et al., (2004)]. 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.