In an attempt to slow the exhaustion of the Internet Protocol (IP) address space,
Class-less Inter-Domain Routing (CIDR) was proposed and 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. We propose a scheme to reduce the
size of routing table in the CIDR context. Our approach utilizes a well-known and
highly efficient heuristic to perform 2-level logic minimization in order to compress
the routing table. By considering the IP routing table as a set of completely specified
logic functions, we demonstrate that our technique can achieve about 25% reduction
in the size of IP routing tables, while ensuring that our approach can handle routing
table updates in real-time. The resulting routing table can be used with existing
routers without needing any change in architecture. However, by realizing the IP
routing table as proposed in this thesis, the implementation requires less complex
hardware than Ternary CAM (TCAM) which are traditionally used to implement IP
routing tables. The proposed architecture also reduces lookup latency by about 46%,
hardware area by 9% and power consumed by 15% in contrast to a TCAM based
implementation.
Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2009-12-7597 |
Date | 2009 December 1900 |
Creators | Bollapalli, Kalyana Chakravarthy |
Contributors | Khatri, Sunil P. |
Source Sets | Texas A and M University |
Language | en_US |
Detected Language | English |
Type | Book, Thesis, Electronic Thesis, text |
Format | application/pdf |
Page generated in 0.0259 seconds