IP routing table compression using ESPRESSO-MV
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
In an attempt to slow the exhaustion of Internet Protocol (IP) address space, Class-less Inter-Domain Routing (CIDR) was adopted. However, the decision to utiulize CIDR also increases the size of the routing table, since it allows an arbitrary partitioning of the routing space. In this paper, we propose a scheme to reduce the size of routing table in the CIDR context. Our approach utilizes a well-known and highly efficient technique to perform multi-valued logic minimization. This technique, implemented using Espresso-MV, is extensively used in multi-valued VLSI logic function optimization. Our approach for IP routing table compression leverages the full flexibility and power of Espresso-MV. By considering the IP routing table as an incompletely specified multi-valued function, we demonstrate that our technique can achieve average 77% reduction in the size of IP routing tables. Our algorithm requires exactly one espresso run, as opposed to O(MN) runs for an existing algorithm, where M is the number of unique masks and N is the number of interfaces in the routing table. 2003 IEEE.
