Associative ternary cache for IP routing

Associative ternary cache for IP routing

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IEE Proceedings - Computers and Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

A study of a prefix routing cache for Internet IP routing is presented. An output port assignment requires one cache memory access when the assignment is found in cache. The cache array is divided into sets that are of variable size; all entries within a set have the same prefix size. The cache is based on a ternary content addressable memory that matches ones, zeroes and don't care values. Our study shows that an associative ternary cache provides an output port at the speed of one memory access with a very high hit rate. For an 8K entry cache the hit rate ranges from 97.62 to 99.67% on traces of 0.2 to 3.5 million addresses. A port error occurs when the port selected by the cache differs from the port that would have been selected from the routing table. A sampling technique is introduced that reduces the worst port error rate by an order of magnitude (from 0.52 to 0.05%).


    1. 1)
      • C. Partridge . A 50-Gb/s IP router. IEEE/ACM Trans. Netw. , 3
    2. 2)
      • Chiueh, T., Pradhan, P.: `Cache memory design for Internet processors', Presented at the 6th Symp. on High Performance Computer Architecture (HPCA-6), January 2000, Toulouse, France.
    3. 3)
      • W. Doeringer , G. Karjoth , M. Nassehi . Routing on longest-matching prefixes. IEEE/ACM Trans. Netw. , 1 , 86 - 97
    4. 4)
      • Liu, H.: `Routing Prefix Caching in Network Processor Design', Presented at the Int. Conf. on Computer Communications and Networks (ICCCN), Phoenix, AZ, 2001.
    5. 5)
      • Gupta, P., Lin, S., McKeown, N.: `Routing lookups in hardware at memory access speeds', Presented at IEEE InfoCom, April 1998, San Francisco, CA.
    6. 6)
      • Rekhter, Y., and Li, T.: ‘An architecture for IP address allocation with CIDR’, RFC 1528, September 1993.
    7. 7)
    8. 8)
      • J.G. Delgado-Frias , J. Nyathi . A high-performance encoder with priority lookahead. IEEE Trans. Circuits Syst., I, Fundam. Theory Appl. , 9 , 1390 - 1393
    9. 9)
      • Huan, N., Chen, W., Luo, J., Chen, J.: `Design of multi-field IPv6 packet classifiers using ternary CAMs', IEEE Global Telecommunications Conf. (GLOBECOM), 25–29 November 2001, 3, p. 1877–1881.
    10. 10)
      • Lines, V., Ahmed, A., Ma, P., Ma, S., McKenzie, R., Kim, H., Mar, C.: `66 MHz 2.3 M ternary dynamic content addressable memory', Proc. IEEE Int. Workshop on Memory Technology, Design and Testing, 7–8 August 2000, p. 101–105.
    11. 11)
    12. 12)
      • National Laboratory for Applied Network Research: ‘Passive measurement and analysis project of the National Laboratory for Applied Network Research at San Diego Super Computer Center’.
    13. 13)
      • Merit Networks Inc.: ‘Internet performance measurement and analysis (IPMA) project’. University of Michigan Department of Electrical Engineering and Computer Science and Merit Network.
    14. 14)
      • Partridge, C.: ‘Locality and route caches’. Position Statement for 1996 NSF Workshop on Internet Statistics Measurement and Analysis. Available at:

Related content

This is a required field
Please enter a valid email address