Using ternary and binary content addressable memory stages...

Details Using ternary and binary content addressable memory stages... Using ternary and binary content addressable memory stages...

2005-12-28

2009-10-13

Pham, Chi H (Department: 2416)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395320, C707S793000, C711S216000

Reexamination Certificate

active

07602787

ABSTRACT:
Methods and apparatus are disclosed herein for classifying packets using ternary and binary content-addressable memory stages to classify packets. One such system uses a stage of one or more TCAMS followed by a second stage one or more CAMS (or alternatively some other binary associative memories such as hash tables or TRIEs) to classify a packet. One exemplary system includes TCAMs for handling input and output classification and a forwarding CAM to classify packets for Internet Protocol (IP) forwarding decisions on a flow label. This input and output classification may include, but is not limited to routing, access control lists (ACLs), quality of service (QoS), network address translation (NAT), encryption, etc. These IP forwarding decisions may include, but are not limited to IP source and destination addresses, protocol type, flags and layer 4 source and destination ports, a virtual local area network (VLAN) id and/or other fields.

REFERENCES:
patent: 3648254 (1972-03-01), Beausoleil
patent: 4296475 (1981-10-01), Nederlof et al.
patent: 4791606 (1988-12-01), Threewitt et al.
patent: 4996666 (1991-02-01), Duluk, Jr.
patent: 5088032 (1992-02-01), Bosack
patent: 5319763 (1994-06-01), Ho et al.
patent: 5383146 (1995-01-01), Threewitt
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5440715 (1995-08-01), Wyland
patent: 5450351 (1995-09-01), Heddes
patent: 5481540 (1996-01-01), Huang
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5515370 (1996-05-01), Rau
patent: 5740171 (1998-04-01), Mazzola et al.
patent: 5841874 (1998-11-01), Kempke et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5898689 (1999-04-01), Kumar et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5930359 (1999-07-01), Kempke et al.
patent: 5956336 (1999-09-01), Loschke et al.
patent: 5978885 (1999-11-01), Clark, II
patent: 6000008 (1999-12-01), Simcoe
patent: 6041389 (2000-03-01), Rao
patent: 6047369 (2000-04-01), Colwell et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061368 (2000-05-01), Hitzelberger
patent: 6067574 (2000-05-01), Tzeng
patent: 6069573 (2000-05-01), Clark, II et al.
patent: 6081440 (2000-06-01), Washburn et al.
patent: 6091725 (2000-07-01), Cheriton et al.
patent: 6097724 (2000-08-01), Kartalopoulos
patent: 6134135 (2000-10-01), Andersson
patent: 6137707 (2000-10-01), Srinivasan et al.
patent: 6141738 (2000-10-01), Munter et al.
patent: 6148364 (2000-11-01), Srinivasan et al.
patent: 6154384 (2000-11-01), Nataraj et al.
patent: 6175513 (2001-01-01), Khanna
patent: 6181698 (2001-01-01), Hariguchi
patent: 6199140 (2001-03-01), Srinivasan et al.
patent: 6226710 (2001-05-01), Melchior
patent: 6236658 (2001-05-01), Essbaum et al.
patent: 6237061 (2001-05-01), Srinivasan et al.
patent: 6240003 (2001-05-01), McElroy
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6246601 (2001-06-01), Pereira
patent: 6247108 (2001-06-01), Long
patent: 6295576 (2001-09-01), Ogura et al.
patent: 6307855 (2001-10-01), Hariguchi
patent: 6374326 (2002-04-01), Kansal et al.
patent: 6377577 (2002-04-01), Bechtolsheim et al.
patent: 6389506 (2002-05-01), Ross et al.
patent: 6526474 (2003-02-01), Ross
patent: 6535951 (2003-03-01), Ross
patent: 6643260 (2003-11-01), Kloth et al.
patent: 6651096 (2003-11-01), Gai et al.
patent: 6658002 (2003-12-01), Ross et al.
patent: 6658458 (2003-12-01), Gai et al.
patent: 6658482 (2003-12-01), Chen et al.
patent: 6665297 (2003-12-01), Hariguchi et al.
patent: 6687144 (2004-02-01), Batson et al.
patent: 6715029 (2004-03-01), Trainin et al.
patent: 6732227 (2004-05-01), Baumann
patent: 6738862 (2004-05-01), Ross et al.
patent: 6792502 (2004-09-01), Pandya et al.
patent: 6862281 (2005-03-01), Chandrasekaran
patent: 6870812 (2005-03-01), Kloth et al.
patent: 6871262 (2005-03-01), Oren et al.
patent: 7065083 (2006-06-01), Oren et al.
McAuley, Anthony J. et al. “Fast Routing Table Lookup Using CAMs,” 1993, IEEE, 0743-166X/93, pp. 1382-1391.
Nilson, Stefan et al., “IP-Address Lookup Using LC-Tries,” Jun. 1999, IEEE, 0733-8713/99, vol. 17, pp. 1083-1092.
Huan Liu, “Reducing Routing Table Size Using Ternary-CAM,” Mar. 2001, IEEE, 7695-1357-3/01, pp. 69-73.
Jon P. Wade and Charles G. Sodini, “A Ternary Content Addressable Search Engine,” IEEE Journal of Solid-State Circuits, vol. 24, No. 4, Aug. 1989, pp. 1003-1013.
Teuvo Kohonen, Content-Addressable Memories, 1987, pp. 128-129 and 142-144, Springer-Verlang, New York.
Brian Dipert, ed., “Special-purpose SRAMs Smooth the Ride,” EDN, Jun. 24, 1999, pp. 93-104.
“Extending the LANCAM Comparand,” Application Brief AB-N3, Rev. 1.0a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Advantages of CAM in ASIC-Based Network Address Processing,” Application Brief AB-N11, Rev. 1.2a Draft, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 4 pages.
“Virtual Memory Applications of the MU9C1480A LANCAM,” Application Note AN-N3, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 12 pages.
“Using the MU9C1965A LANCAM MP for Data Wider than 128 Bits,” Application Note AN-N19, Rev. 1a, Music Semiconductors, Milpitas, CA, Sep. 30, 1998, 16 pages.
“Fast IPv4 and IPv4 CIDR Address Translation and Filtering Using the MUAC Routing CoProcessor (RCP),” Application Note AN-N25, Rev. 0a, Music Semiconductors, Milpitas, CA, Oct. 1, 1998, 16 pages.
“Using Music Devices and RCPs for IP Flow Recognition,” Application Note AN-N27, Rev. 0, Music Semiconductors, Milpitas, CA, Oct. 21, 1998, 20 pages.
“Wide Ternary Searches Using Music CAMs and RCPs,” Application Note AN-N31, Rev. 0, Music Semiconductors, Milpitas, CA, Apr. 13, 1999, 8 pages.

Affiliated with

Also associated with

Rating

Using ternary and binary content addressable memory stages... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Using ternary and binary content addressable memory stages..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using ternary and binary content addressable memory stages... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4114118