Low-Power, Fast and Dense Longest Prefix-Match Content Addressable Memory for IP Routers

Description

The exponential growth of the Internet over the last few decades provides testament to the extreme success of the internet protocol (IP), the primary protocol responsible for delivering data packets between hosts across the heavily trafficked internet. Notwithstanding this success, IP address space is rapidly running out. Consequently, the more complex 128-bit IPv6 will soon replace the nearly exhausted 32-bit range of the existing IPv4.

IP routers are the devices responsible for physically employing the IP to forward packets toward their final destination. In order for an IP router to perform this function, the router must conduct an address search, then buffer, schedule, and transmit packets to the next hop address through the appropriate port. Meanwhile, to perform the address search function, an IP router implements an associate matching process to identify the longest matching address prefix in its router forwarding table. Because associative processes are complex, the address search constitutes a key power and speed bottleneck in the IP.

Researchers at Arizona State University have developed a novel circuit that addresses the power and speed bottleneck in the IP by improving the router search function. Specifically, the invention replaces the conventional ternary content-addressable memory (CAM) that performs the address search function with a more sophisticated CAM that discretely determines the longest prefix match to the stored address and outputs the match as a two-part thermometer code. As a result, one entry replaces an average of 22 TCAM entries; consequently, these novel CAMs are an order of magnitude smaller than equivalent TCAMs and dissipate over 90% less dynamic power. Furthermore, because the design automatically produces an encoded prefix match length limited by the prefix mask, there is no need to sort the order of the entries. Meanwhile, work to refine the design and apply it to IPv6 is ongoing.

Potential Applications

  • Electronics
  • Networks & Communication

Benefits and Advantages

  • Improves Address Search Speed for IP Routing ? replaces an average of 22 conventional TCAM entries with only one; simulations operate above 1 GHz
  • Reduces the Physical Size of the IP CAM Circuit ? proposed IP CAMs are an order of magnitude smaller in area than conventional CAMs
  • Reduces Dynamic Power Dissipation ? dissipates over 90% less dynamic power in comparison to conventional CAMs; circuit design density is an order of magnitude better than convention designs

Case ID:
M09-103P
Published:
01-25-2011
Last Updated:
12-05-2018

Patent Information

App Type:
Nationalized PCT
Serial No.:
13/321,309
Patent No.:
8,717,793
File Date:
06-16-2010
Issue Date:
05-06-2014
Expire Date:
01-30-2031

For More Information, Contact