Content addressable memory-based circuits for Internet protocol routers: A cache and a lookup table

Packet forwarding is a fundamental task for an Internet router. A routing lookup table (LUT) is used to decide where to forward a packet at each router. The routing lookup is a rather complicated and slow process and the lookup delay is a bottleneck in high throughput routers. An effective strategy to speed up routing lookup is to use a cache to store recent routing results for reuse. This thesis proposes an efficient forwarding mechanism with a hardware-based LUT and a Multizone Pipelined Cache.; The LUT is implemented with a pipelined TCAM (Ternary Content Addressable Memory). Our TCAM employs a novel Hardware-based Longest Prefix Matching (HLPM) to completely eliminate table management requirements and to reduce the power consumption for short matching prefixes. The cache is a multizone non-blocking pipelined cache for IP routing lookup that achieves lower miss rates compared to previously reported IP caches and reduces the effective miss penalty by using a very small non-blocking buffer. The simulation results of our forwarding mechanism, based on real traffic, demonstrate the efficiency of the design.