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%).
References
-
-
1)
-
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’. http://pma.nlanr.net/PMA.
-
2)
-
Partridge, C.: ‘Locality and route caches’. Position Statement for 1996 NSF Workshop on Internet Statistics Measurement and Analysis. Available at: http://www.caida.org/outreach/isma.
-
3)
-
H. Liu
.
Routing table compaction in ternary CAM.
IEEE Micro
,
1 ,
58 -
64
-
4)
-
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.
-
5)
-
D.H. Summerville ,
J.G. Delgado-Frias ,
S. Vassiliadis
.
A Flexible bit-associative router for interconnection networks.
IEEE Trans. Parallel Distrib. Syst.
,
5 ,
477 -
485
-
6)
-
Merit Networks Inc.: ‘Internet performance measurement and analysis (IPMA) project’. University of Michigan Department of Electrical Engineering and Computer Science and Merit Network. http://www.merit.edu/ipma.
-
7)
-
W. Doeringer ,
G. Karjoth ,
M. Nassehi
.
Routing on longest-matching prefixes.
IEEE/ACM Trans. Netw.
,
1 ,
86 -
97
-
8)
-
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.
-
9)
-
J.G. Delgado-Frias ,
J. Nyathi
.
A high-performance encoder with priority lookahead.
IEEE Trans. Circuits Syst., I, Fundam. Theory Appl.
,
9 ,
1390 -
1393
-
10)
-
Liu, H.: `Routing Prefix Caching in Network Processor Design', Presented at the Int. Conf. on Computer Communications and Networks (ICCCN), Phoenix, AZ, 2001.
-
11)
-
Gupta, P., Lin, S., McKeown, N.: `Routing lookups in hardware at memory access speeds', Presented at IEEE InfoCom, April 1998, San Francisco, CA.
-
12)
-
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.
-
13)
-
C. Partridge
.
A 50-Gb/s IP router.
IEEE/ACM Trans. Netw.
,
3
-
14)
-
Rekhter, Y., and Li, T.: ‘An architecture for IP address allocation with CIDR’, RFC 1528, September 1993.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cdt_20041014
Related content
content/journals/10.1049/ip-cdt_20041014
pub_keyword,iet_inspecKeyword,pub_concept
6
6