Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2006-02-21
2006-02-21
Nguyen, Brian (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C709S238000, C711S108000
Reexamination Certificate
active
07002965
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: 6389506 (2002-05-01), Ross et al.
patent: 6526474 (2003-02-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: 6862281 (2005-03-01), Chandrasekaran
patent: 6871262 (2005-03-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-8716/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.
Cisco Technology Inc.
Nguyen Brian
Phan Tri H.
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for using ternary and binary... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for using ternary and binary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for using ternary and binary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3663383