Practical & Real Time IP Routing Table Compression

In an attempt to slow the exhaustion of the Internet Protocol (IP) address space, Class-less Inter-Domain Routing (CIDR) was adopted. However, the decision to utilize CIDR also increases the size of the routing table, since it allows an arbitrary partitioning of the routing space. A scheme to reduce the size of routing table in the CIDR context is detailed. A well-known and highly ecient heuristic to perform 2-level logic minimization is extended to compress the routing table. IP routing table represented as a set of completely specied logic functions can be compressed to about 25% in size, while ensuring that routing table updates are handled in real-time. The resulting routing table can be used with existing routers without needing any change in architecture. By compressing the IP routing table as proposed, less complex hardware than Ternary CAM (TCAM) can be used to achieve exact functionality. This approach also reduces lookup latency by about 46%, hardware area by 9% and power consumed by 15% in contrast to a traditional TCAM based implementation.