Source: http://www.google.com/patents/US7554978?dq=6125447
Timestamp: 2015-05-25 00:41:07
Document Index: 436801315

Matched Legal Cases: ['art. 2', 'art. 3', 'art. 4', 'art. 5', 'art. 6', 'art. 7']

Patent US7554978 - System for accessing content-addressable memory in packet processor - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA system for accessing a content-addressable memory in a packet processing system is described. A register holds a data element having a key field. Logic derives a value of the key responsive to 1) packet processing state data relating to one or more packets undergoing processing by the packet processing...http://www.google.com/patents/US7554978?utm_source=gb-gplus-sharePatent US7554978 - System for accessing content-addressable memory in packet processorAdvanced Patent SearchPublication numberUS7554978 B1Publication typeGrantApplication numberUS 10/834,576Publication dateJun 30, 2009Filing dateApr 28, 2004Priority dateMar 30, 2004Fee statusPaidAlso published asUS7502374, US7522516, US7580350, US7606263, US7646770, US7936687, US8085779, US20100054256Publication number10834576, 834576, US 7554978 B1, US 7554978B1, US-B1-7554978, US7554978 B1, US7554978B1InventorsDavid K. ParkerOriginal AssigneeExtreme Networks, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (51), Non-Patent Citations (6), Referenced by (13), Classifications (19), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetSystem for accessing content-addressable memory in packet processor
US 7554978 B1Abstract
A system for accessing a content-addressable memory in a packet processing system is described. A register holds a data element having a key field. Logic derives a value of the key responsive to 1) packet processing state data relating to one or more packets undergoing processing by the packet processing system, and 2) the value of this key field. The derived value of the key is presented to the memory. In response, the memory searches for an entry associated with the presented key value. If found, the content value associated with the entry is output. If not found, a signal indicative of a miss condition is output.
This invention relates to the field of packet processing, and more specifically, to accessing a content-addressable memory in packet processing system.
In a first aspect, the invention provides a system for accessing a content-addressable memory in a packet processing system. The memory has a plurality of locations, each associated with a value of a key and a content value.
FIG. 2 illustrates the format of classification data 200 for a packet as produced by one embodiment of packet classification system 102. The classification data 200 in this embodiment has first and second portions, identified respectively with numerals 202 and 204. The first portion 202 is a 64 bit Address Filtering Header (AFH) which is pre-pended to the packet. The second portion 204 is a 20 bit grouping of flags that are encoded as control bits maintained by the system ˜100.
BUSY—a bit that, if asserted, indicates the pipeline slot is processing a packet. CPU—a bit that, if asserted, indicates the pipeline slot is processing a CPU or host access. FIRST—a bit that, if asserted, indicates the current cycle is the first processing cycle for the packet. DONE PEND—a bit that, if asserted, indicates that the packet has undergone all required cycles of processing and that an AFH assignment to the packet is pending. PTR—a pointer or reference handle to the packet in a receive FIFO. LEN—packet length up to 128 bytes total IF TYPE—ingress interface type; 0=Ethernet, 1=POS. IF PST ACTIVE—an indicator of whether the Port State Table is active during this processor cycle. PORT—the ingress port of the packet being processed. VLAN—the working VLAN for the current processing cycle. C1—the C1 context pointer for the current processing cycle. C2—the C2 context pointer for the current processing cycle. C3—the C3 context pointer for the current processing cycle. C4—the C4 context pointer for the current processing cycle. C5—the C5 context pointer for the current processing cycle. C6—the C6 context pointer for the current processing cycle. LKUP COUNT—a count of the number of cycles of processing undertaken to date for the packet. SCT—the SCT index for the current processing cycle. PAGE SEL—the page selector for the current processing cycle. VLAN SEL—the VLAN selector for the current processing cycle. L3 SEL—the L3 Header selector for the current processing cycle.
DEBUG ACTIVE—a flag that, if asserted, indicates that a Debug Process is active. DEBUG LAST SLOT—an indicator to the Debug Process that the current slot is the last slot in the pipeline. DEBUG LAST LKUP—an indicator to the Debug Process that the current processing cycle is the last processing cycle in the pipeline. DEBUG VALID—Debug Valid bits to control debug triggering. The functions of the bits and fields illustrated in FIG. 23 are as follows: PTI—see discussion of FIG. 2. TXMI—see discussion of FIG. 2. EQoS—see discussion of FIG. 2. IQoS—see discussion of FIG. 2. CQoS—see discussion of FIG. 2. CPU Copy—see discussion of FIG. 2. In one implementation, set when a QoS source returns a valid CPU QoS value. EMRK SEL—see discussion of FIG. 2. PERR KILL—see discussion of FIG. 2. LAI—see discussion of FIG. 2. LAI KEEP—an indicator whether the LAI was supplied by ARAM. EMIRROR—see discussion of FIG. 2. In one implementation, this flag is set if the ARAM EMirror flag is set or if an Egress QoS is returned with a special Mirror Copy encode value. IMIRROR—see discussion of FIG. 2. In one implementation, this flag is set if either the ARAM IMirror or VPST Mirror flags are set. ROUTE—see discussion of FIG. 2. In one implementation, this flag is set when any SCT entry in the lookup sequence for the packet requests that it be set. LEARN—see discussion of FIG. 2. In one implementation, this flag may be set when an SCT-enabled comparison indicates that the ingress port does not equal the least significant bits of the PTI obtained from a matching CAM entry, or that the CAM search did not result in a match (also subject to VPST.Learn enable control). REDIRECT—see discussion of FIG. 2. In one implementation, this flag is set when an SCT-enabled comparison determines that the ingress and egress (ARAM-supplied) VLANs are equal. JUMBO—see discussion of FIG. 2. In one implementation, this flag is set when any SCT entry in the lookup sequence for the packet requests that it be set. DON'T FRAG—see discussion of FIG. 2. In one implementation, this flag is always set for IPv6 processing, and set for IPv4 processing if the Don't Fragment bit in the IPv4 header is set. In one example, unlike the other flags in this table, which are all persistent, i.e. once set, remain set, this flag is pseudo-persistent, i.e., once set, normally remains set, but may be overwritten in limited circumstances. For example, the bit may be initially set based on the processing of an outer IP header, but then is updated (through a SCT request) based on the processing of an inner UDP header. RED—see discussion of FIG. 2. In one implementation, this flag is set when a QoS source returns this flag set. IF TYPE—see discussion of FIG. 2. PTI PRI—current PTI priority. TXMI PRI—current TXMI priority. EQoS PRI—current EQoS priority. IQoS PRI—current IQoS priority. CQoS PRI—current CQoS priority. EMS/EMM PRI—current Egress Mark Select/Mask priority. SSAMPLE BIN—Statistical Sample bin. SAMPLE ARAM—indicator that Statistical Sample bin is supplied by ARAM. The functions of the bits and fields illustrated in FIG. 24 are explained in co-pending U.S. patent application Ser. No. 10/834,573.
NEXT SCT HIT—the index of the next SCT command assuming a CAM hit during this processing cycle. NEXT SCT MISS—the index of the next SCT command assuming a CAM miss during this processing cycle. PTI PRIORITY—the priority of the PTI during this processing cycle TXMI PRIORITY—the priority of the TXMI during this processing cycle. EQoS PRIORITY—the priority of the ARAM-supplied EQoS field during this processing cycle. IQoS PRIORITY—the priority of the ARAM-supplied IQoS field during this processing cycle. CQoS PRIORITY—the priority of the ARAM-supplied CQoS field during this processing cycle. LEARN OP—enable Learn processing operation ROUTE OP—set the Unicast Route flag during the current processing cycle. DON'T FRAG OP—enable Don't Frag processing operation during the current processing cycle. JUMBO OP—enable a Jumbo processing operation during the current processing cycle. CAM KEY SEL NIBBLE 0-17—Eighteen CAM Key Selection Fields, discussed below. In one implementation, the CAM key used to search through CAM 1810 during a processing cycle is derived by the data path logic 1808 of FIG. 18 from the process and packet data for that processing cycle, as well as the current SCT entry. In FIG. 18, the packet and process data is provided to the data path logic 1808 over one or more signal lines 1814, and selection data, used to narrow the combined 256 bytes of data represented by this process and packet data down to the desired size of the CAM key, is provided to the data path logic 1808 from the current SCT entry over one or more signal lines 1816.
NIBBLE SELECT—selects one of the two nibbles in the selected byte. BYTE SELECT —selects one of 128 bytes in the selected data structure (either process or packet data). PROCESS PACKET DATA SELECT —selects either the process or packet data structures. CONTEXT SELECT—must be 0 if the process data structure is selected; otherwise, selects one of seven packet contexts as follows: 0—Context 0—beginning of packet. 1—Context 1—MAC Header Start. 2—Context 2—Encapsulation/EtherType Start. 3—Context 3—MPLS Start. 4—Context 4—L3 Outer Start. 5—Context 5—L3 Inner Start. 6—Contect 6—L4 Start. 7—Reserved. In a second example, a 144 bit CAM key is formed using the structure of FIG. 29 from two successive retrievals of SCT entries over two successive half cycles. The selection fields from the two successive SCT entries are successively input to the multiplexors of FIG. 29 with the same process and packet data as inputs. Through this process, two 72 data structures are formed that are concatenated to form the 144 bit CAM key. Other examples are possible, so nothing in this or the previous example should be taken as limiting. FIG. 31 illustrates several possible examples of 72 bit keys.
PTI—see discussion of FIG. 2. TXMI—see discussion of FIG. 2. EQoS—see discussion of FIG. 2. IQoS—see discussion of FIG. 2. CQoS—see discussion of FIG. 2. PTI VALID —indicates whether ARAM-supplied PTI field is valid. TXMI VALID—indicates whether ARAM-supplied TXMI field is valid. EQoS VALID —indicates whether ARAM-supplied EQoS field is valid. IQoS VALID —indicates whether ARAM-supplied IQoS field is valid. CQoS VALID —indicates whether ARAM-supplied CQoS field is valid. RED—if asserted, sets the AFH RED flag. Next SCT—the next SCT address or index (depending on state of NEXT SCT VALID flag) NEXT SCT VALID—a flag that, if asserted, indicates the Next SCT field is valid. VLAN ID —replaces the working VLAN for the packet if REPLACE VLAN flag asserted (see below). CONT UPDATE—a 4 bit field that, if non-zero, selects one of 15 context update registers for updating the packet context for the current processing cycle. EMIRROR—when asserted, selects egress mirroring. IMIRROR—when asserted, selects ingress mirroring. REPLACE VLAN—when asserted, specifies that the VLAN represented by the VLAN ID field becomes the next working VLAN for the packet. In one embodiment, the current SCT and/or ARAM entries yield data that is used to selectively update the state data for the slot. Other resources may be accessed as well for the purpose of retrieving data for use in updating the current state data as described herein and in U.S. patent application Ser. No. 10/835,271.
In one configuration, the related state data for a packet is control data, such as pipeline management data, or packet process state data. In one example, the control data is static packet information. In another example, the related state data is packet classification/forwarding information, such as priority-based packet classification/forwarding information or non-priority-based packet classification/forwarding information. The related state data may also comprise one or more “sticky” flags relating to the packet, or statistical information relating to the packet, including statistical information relating to each of a plurality of processing cycles performed on the corresponding packet data.
FIG. 39 illustrates an embodiment 3900 of a system for accessing a content-addressable memory 3902 in a packet processing system. The memory 3902 has a plurality of locations, each associated with a value of a key and a content value. A register 3904 is configured to hold a data element having a key field 3906, the key field having a value. Logic 3908 is configured to derive a value of the key responsive to 1) packet processing state data relating to one or more packets, provided to the logic 3908 over one or more signal lines 3910, and 2) the value of the key field of the data element, provided to the logic 3908 over one or more signal lines 3912. The logic 3908 is further configured to present the derived value to the memory 3902 over one or more signal lines 3914.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4025901 *Jun 19, 1975May 24, 1977Honeywell Information Systems, Inc.Database instruction find ownerUS4042912 *Jun 19, 1975Aug 16, 1977Honeywell Information Systems Inc.Database set condition test instructionUS5282270Jun 6, 1990Jan 25, 1994Apple Computer, Inc.Network device location using multicastUS6034957Feb 24, 1998Mar 7, 2000Extreme Networks, Inc.Sliced comparison engine architecture and method for a LAN switchUS6172980Sep 11, 1997Jan 9, 20013Com CorporationMultiple protocol supportUS6173333 *Jul 17, 1998Jan 9, 2001Interprophet CorporationTCP/IP network accelerator system and method which identifies classes of packet traffic for predictable protocolsUS6275861Sep 15, 1997Aug 14, 2001Pmc-Sierra, Inc.Method and apparatus to identify flows in data systemsUS6295299Jan 30, 1998Sep 25, 2001Extreme Networks, Inc.Data path architecture for a LAN switchUS6381242Aug 29, 2000Apr 30, 2002Netrake CorporationContent processorUS6466983 *Sep 30, 1999Oct 15, 2002Steven Paul StrazzaSystems and methods for controlling access to data maintained in a repositoryUS6502185 *Jan 3, 2000Dec 31, 2002Advanced Micro Devices, Inc.Pipeline elements which verify predecode informationUS6553002Aug 29, 1997Apr 22, 2003Ascend Communications, Inc.Apparatus and method for routing data packets through a communications networkUS6570877 *Apr 7, 1999May 27, 2003Cisco Technology, Inc.Search engine for forwarding table content addressable memoryUS6738892Oct 20, 1999May 18, 2004Transmeta CorporationUse of enable bits to control execution of selected instructionsUS6765881Dec 6, 2000Jul 20, 2004Covad Communications Group, Inc.Virtual L2TP/VPN tunnel network and spanning tree-based method for discovery of L2TP/VPN tunnels and other layer-2 servicesUS6871262Feb 14, 2002Mar 22, 2005Cisco Technology, Inc.Method and apparatus for matching a string with multiple lookups using a single associative memoryUS6882642 *Oct 14, 1999Apr 19, 2005Nokia, Inc.Method and apparatus for input rate regulation associated with a packet processing pipelineUS6888797Mar 25, 2000May 3, 2005Lucent Technologies Inc.Hashing-based network load balancingUS6914905Jun 16, 2000Jul 5, 2005Extreme Networks, Inc.Method and system for VLAN aggregationUS6917617Dec 16, 1998Jul 12, 2005Cisco Technology, Inc.Use of precedence bits for quality of serviceUS6957258Apr 11, 2001Oct 18, 2005Netrake CorporationPolicy gatewayUS6980552 *Aug 15, 2002Dec 27, 2005Cisco Technology, Inc.Pipelined packet switching and queuing architectureUS7007151 *Oct 4, 2000Feb 28, 2006Nortel Networks LimitedSystem, device, and method for controlling access to a memoryUS7079407Oct 18, 2002Jul 18, 2006Netlogic Microsystems, Inc.Content addressable memory (CAM) device including match line sensingUS7120733 *Nov 14, 2003Oct 10, 2006Integrated Device Technology, Inc.CAM-based search engines having per entry age reporting capabilityUS7149216 *Sep 5, 2000Dec 12, 2006Cisco Technology, Inc.M-trie based packet processingUS7152191 *Oct 23, 2003Dec 19, 2006Hewlett-Packard Development Company, L.P.Fault containment and error recovery in a scalable multiprocessorUS7177276 *Aug 15, 2002Feb 13, 2007Cisco Technology, Inc.Pipelined packet switching and queuing architectureUS7190696Mar 5, 2002Mar 13, 2007Force10 Networks, Inc.System and method for distributing packets among a plurality of paths to a destinationUS7248584Aug 7, 2002Jul 24, 2007Intel CorporationNetwork packet processingUS7248585Oct 16, 2002Jul 24, 2007Sun Microsystems, Inc.Method and apparatus for a packet classifierUS7274693 *Dec 23, 2002Sep 25, 2007Cisco Technology, Inc.Search engine for forwarding table content addressable memoryUS7463628 *Mar 30, 2004Dec 9, 2008Extreme Networks, Inc.Packet data modification processor command instruction setUS7502374 *Apr 28, 2004Mar 10, 2009Extreme Networks, Inc.System for deriving hash values for packets in a packet processing systemUS7522516 *Apr 28, 2004Apr 21, 2009Extreme Networks, Inc.Exception handling system for packet processing systemUS20010025315 *Jan 10, 2001Sep 27, 2001Jolitz Lynne G.Term addressable memory of an accelerator system and methodUS20020109615 *Feb 13, 2001Aug 15, 2002Mosaid Technologies, Inc.Method and apparatus for adaptive data compressionUS20020191605 *Feb 28, 2002Dec 19, 2002Lunteren Jan VanPacket classificationUS20030069973Jul 8, 2002Apr 10, 2003Elango GanesanContent service aggregation system control architectureUS20030193949Feb 26, 2003Oct 16, 2003Yuji KojimaPacket processing deviceUS20030196081 *Apr 11, 2002Oct 16, 2003Raymond SavardaMethods, systems, and computer program products for processing a packet-object using multiple pipelined processing modulesUS20040003110Jun 27, 2002Jan 1, 2004International Business Machines CorporationMethod and apparatus for implementing frame header alterationsUS20040100956Nov 20, 2003May 27, 2004Akira WatanabePacket search device, packet processing search method used for the same, and program for the sameUS20040205753Aug 18, 2003Oct 14, 2004Globespan Virata Inc.Timing ring mechanismUS20040246981Jan 28, 2004Dec 9, 2004Zhiqun HeSystem and method of accessing and transmitting different data frames in a digital transmission networkUS20050074009Oct 1, 2004Apr 7, 2005Tatsuo KanetakePacket transfer unitUS20050198362Dec 31, 2003Sep 8, 2005Navada Muraleedhara H.Exception packet forwardingUS20050220094 *Mar 30, 2004Oct 6, 2005Parker David KPacket data modification processor command instruction setUS20050226242 *Apr 28, 2004Oct 13, 2005Parker David KPipelined packet processorUS20070153808 *Dec 30, 2005Jul 5, 2007Parker David KMethod of providing virtual router functionalityWO2003081857A1Mar 4, 2003Oct 2, 2003Intel CorpVlan table management for memory efficient lookups and inserts in hardware-based packet switches* Cited by examinerNon-Patent CitationsReference1Netlogic Microsystems, Product Brief NSE5000GLQ, Copyright 2004, available at: http://www.netlogicmicro.com/datasheets/nse5000glq.html.2Network Working Group, RFC 1071-Computing the Internet Checksum, Sep. 1988, available at: http://www.faqs.org/rfcs/rfc1071.html.3Network Working Group, RFC 1141-Incremental Updating of the Internet Checksum, Jan. 1990, available at: http://www.faqs.org/rfcs/rfc1141.html.4Network Working Group, RFC 1624-Computation of the Internet Checksum via Incremental Update, May 1994, available at: http://www.faqs.org/rfcs/rfc1624.html.5Van Ess, D., A Circular FIFO, PSoC Style, Cypress Microsystems, Application Note AN2036, Rev. B, pp. 1-5, Jun. 21, 2002.6Zhang, Z., Recovery of Memory and Process in DSM Systems: HA Issue #1, Hewlett-Packard Co. HPL-2001-76, Mar. 30, 2001.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7715437 *Sep 26, 2002May 11, 2010Broadcom CorporationHighly integrated media access controlUS7835398Aug 17, 2007Nov 16, 2010Broadcom CorporationHighly integrated media access controlUS7991010Apr 20, 2010Aug 2, 2011Broadcom CorporationHighly integrated media access controlUS8085779Nov 5, 2009Dec 27, 2011Extreme Networks, Inc.Systems for supporting packet processing operationsUS8225026 *Aug 5, 2010Jul 17, 2012Hangzhou H3C Technologies Co., Ltd.Data packet access control apparatus and method thereofUS8239914Jul 22, 2005Aug 7, 2012Broadcom CorporationHighly integrated single chip set-top boxUS8494002Jul 19, 2011Jul 23, 2013Broadcom CorporationHighly integrated media access controlUS8578434May 20, 2005Nov 5, 2013Broadcom CorporationIntegrated cable modemUS8614967 *Dec 24, 2009Dec 24, 2013Panasonic CorporationTerminal devices and packet transmitting methodUS8732788May 20, 2005May 20, 2014Broadcom CorporationIntegrated set-top boxUS8934503Jun 14, 2013Jan 13, 2015Broadcom CorporationHighly integrated media access controlUS20110040923 *Aug 5, 2010Feb 17, 2011Hangzhou H3C Technologies Co., Ltd.Data packet access control apparatus and method thereofUS20110305169 *Dec 24, 2009Dec 15, 2011Panasonic CorporationTerminal devices and packet transmitting method* Cited by examinerClassifications U.S. Classification370/389, 709/224, 709/223, 370/412, 711/122, 709/231, 370/429, 709/249, 370/469, 711/108, 370/256, 370/392International ClassificationH04L12/56, G06F13/16, G06F12/00Cooperative ClassificationH04L45/745, H04L12/56European ClassificationH04L45/745, H04L12/56Legal EventsDateCodeEventDescriptionDec 31, 2012FPAYFee paymentYear of fee payment: 4Aug 31, 2004ASAssignmentOwner name: EXTREME NETWORKS, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:PARKER, DAVID K.;REEL/FRAME:015097/0739Effective date: 20040810RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services