IP Routers use sophisticated forwarding table (FIB) lookup algorithms that minimize lookup time, storage, and update time. This paper presents SMALTA, a practical, near-optimal FIB aggregation scheme that shrinks forwarding table size without modifying routing semantics or the external behavior of routers, and without requiring changes to FIB lookup algorithms and associated hardware and software. On typical IP routers using the FIB lookup algorithm Tree Bitmap, SMALTA shrinks FIB storage by at least 50%, representing roughly four years of routing table growth at current rates. SMALTA also reduces average lookup time by 25% for a uniform traffic matrix. Besides the benefits this brings to future routers, SMALTA provides a critical easy-to-deploy one-time benefit to the installed base should IPv4 address depletion result in increased routing table growth rate. The effective cost of this improvement is a sub-second delay in inserting updates into the FIB once every few hours. We describe SMALTA, prove its correctness, measure its performance using data from a Tier-1 provider as well as Route-Views. We also describe an implementation in Quagga that demonstrates its ease of implementation.

Semantically equivalent IP prefix tables exhibit the same forwarding behavior and, thus, can be used in place of each other for the purpose of packet forwarding. Researchers, service providers, and equipment vendors often need to establish this semantic equivalence of prefix tables. Given the large number of IP addresses in use today, either (i) this task takes too long to complete on any available hardware, or (ii) one has to resort to approximation by looking up, in the two tables, only a sample of IP addresses from the entire IP space. We present TaCo (Table Comparison), an algorithm to determine whether or not two given IP prefix tables are semantically equivalent. TaCo is efficient yet accurate, as it guarantees the equivalence result over the entire IP space without explicitly performing a lookup on each IP address over this space. We show that the number of longest prefix matching lookups TaCo needs to perform is bounded by a number that is linear in the sum of the number of entries in the two tables. In practice, for the existing prefix tables in large service providers, the number of longest prefix matchings needed by TaCo does not exceed a few hundred thousand entries.