Set-associative memory architecture for routing tables

Details Set-associative memory architecture for routing tables Set-associative memory architecture for routing tables

2004-11-08

2009-08-11

Ngo, Ricky (Department: 2416)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C711S128000

Reexamination Certificate

active

07573880

ABSTRACT:
A set-associative architecture (IPStash) restricts routing table prefixes to a limited number of lengths using a controlled, prefix-expansion technique. Since this inflates the routing tables, skewed associativity can be used to increase the effective capacity of IPStash. In addition, pruning of redundant entries can be applied to decrease the size of the expanded tables. Compared to previous proposals, IPStash does not require any complicated routing table transformations but, more importantly, it makes incremental updates to the routing tables effortless. IPStash is also easily expandable. IPStash is both fast and power-efficient compared to TCAMs. Specifically, IPStash devices built in the same technology as TCAMs can run at speeds in excess of 600 MHz, offer more than twice the search throughput (>200 Msps), and consume up to 35 % less power (for the same throughput) than the best commercially available TCAMs when tested with real routing tables and IP traffic.

REFERENCES:
patent: 6564211 (2003-05-01), Andreev et al.
patent: 2004/0100960 (2004-05-01), Mehta
Huan Liu, “Reducing Routing Table Size Using Ternary-CAM,” Hot Interconnects 9, 2001, Aug. 22-24, 2001, pp. 69-73.
A. Agarwal, M. Horowitz, J. Hennessy, “Cache Performance of Operating System and Multiprogramming Workloads,”ACM Transactions on Computer Systems, Nov. 1988.
A. Agarwal and S. D. Pudar, “Column-Associative Caches: A Technique for Reducing the Miss Rate of Direct-Mapped Caches,”ISCA-20, May 1993.
Norman P. Jouppi, “Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers,”ISCA-17, pp. 364-373, 1990.
B. Lampson, V. Srinivasan, G. Varghese, “OP Lookups using Multiway and Multicolumn Search,” Proceedings ofIEEE INFOCOM, vol. 3, pp. 1248-1256, Apr. 1998.
Huan Liu, “Routing Table Compaction In Ternary CAM,”IEEE Micro, 22(1) 58-64, Jan.-Feb. 2002.
Stefan Nilsson and Gunnar Karlsson, “IP-Address Lookup Using LC-Tries,”IEEE Journal of Selected Areas in Communications, vol. 17, No. 6, pp. 1083-1092, Jun. 1999.
André Seznec, “A case for two-way skewed-associative caches,” Proceedings of the 20thInternational Symposium on Computer Architecture, May 1993.
V. Srinivasan and G. Varghese, “Fast Address Lookups Usings Controlled Prefix Expansion,”ACM Transactions on Computer Systems, 17(1), pp. 1-40 Feb. 1999.

Affiliated with

Also associated with

Rating

Set-associative memory architecture for routing tables does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Set-associative memory architecture for routing tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set-associative memory architecture for routing tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4071806