Source: http://www.google.com/patents/US7502374?dq=7222078
Timestamp: 2017-04-24 10:51:45
Document Index: 737221326

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

Patent US7502374 - System for deriving hash values for packets in a packet processing system - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA system for deriving hash values for packets in a packet processing system is described. In this system, hash derivation logic is configured to derive a hash value for the packet responsive to a key that drives processing of the packet. The hash value is useful for supporting additional processing of...http://www.google.com/patents/US7502374?utm_source=gb-gplus-sharePatent US7502374 - System for deriving hash values for packets in a packet processing systemAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7502374 B1Publication typeGrantApplication numberUS 10/834,566Publication dateMar 10, 2009Filing dateApr 28, 2004Priority dateMar 30, 2004Fee statusPaidAlso published asUS7522516, US7554978, US7580350, US7606263, US7646770, US7936687, US8085779, US20100054256Publication number10834566, 834566, US 7502374 B1, US 7502374B1, US-B1-7502374, US7502374 B1, US7502374B1InventorsDavid K. Parker, Michael K. YipOriginal AssigneeExtreme Networks, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (40), Non-Patent Citations (6), Referenced by (11), Classifications (13), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetSystem for deriving hash values for packets in a packet processing system
US 7502374 B1Abstract
Extreme Dkt.
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 COoS priority. EMS/EMM PRI—current Egress Mark Select/Mask priority. SAMPLE 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 copending U.S. patent application Ser. No. 10/834,573, filed Apr. 28, 2004.
fetch SCT entry based on current SCT index value. form CAM key (using data path logic 1808). execute CAM search. select active Exception Handler, as described in U.S. patent application Ser. No. 10/835,252, filed Apr. 28, 2004. execute QoS mapping operations, using PST, VST and QoS Map tables as described in U.S. patent application Ser. No. 10/835,532, filed Apr. 28, 2004. execute VPST access, as described in U.S. patent application Ser. No. 10/835,271, filed Apr. 28, 2004. if CAM hit, fetch corresponding ARAM entry. selectively update process and statistics data based on SCT and/or ARAM entry data (as well as QoS mapping operations, VPST access, and exception handling operations). unload operation if last cycle of processing for packet. In one example, CAM 1810 is organized so that higher priority entries precede lower priority entries. If there are multiple matches or hits with the CAM key, the first such match or hit is selected, consistent with the higher priority of this entry compared to the other entries.
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—Context 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 in U.S. patent application Ser. No. 10/835,271, filed Apr. 28, 2004; U.S. patent application Ser. No. 10/834,576, filed Apr. 28, 2004.
PTI—the possible sources of the next PTI field include an ARAM entry, if any, corresponding to a CAM hit, and one or more of the Exception Handlers. If there is a tie, the first value is used. The ARAM-supplied PTI value has a priority determined by the current SCT entry, and the priority of any Exception Handler value is supplied by the Exception Handler. The next PTI is taken to be the PTI value from any of these sources that has the highest priority that exceeds the current priority. If there is no CAM hit, a default PTI value is obtained from one or more of the Exception Handlers. This default value only supplants the current PTI if its priority exceeds that of the current PTI. IQoS—the possible sources of the next IQoS field include any of 0.1 p, MPLS, or ToS QoS mapping (if enabled by the current SCT entry), the PST (or VST), and the current ARAM entry (assuming a CAM hit). The SCT supplies the priority associated with the ARAM-supplied IQoS. A 4-bit PST (or VST) resident field is used to select a QoS Priority control structure from 16 possible structures. This structure indicates the priority for the PST, VST, 0.1 p, MPSL, and ToS IQoS values. The next IQoS value is taken to be the IQoS value from any of these sources that has the highest priority that exceeds the current priority. If there is a tie, the first value is used. In the case of MPLS parallel label processing, as described in U.S. patent application Ser. No. 10/835,271, filed Apr. 28, 2004, parallel IQoS mappings are performed for each of the MPLS labels, and an ARAM supplied field (the MPLS field) is used to select the next IQoS value from these parallel operations. EQoS—EQoS updating is performed the same way as IQoS, but using an independent set of resources. In one mode of operation, the least significant bits of the EQoS value encodes the following egress side decisions: None. Pre-emptive Kill. Normal Kill. Thermonuclear Kill. Egress Mirror Copy. Pre-emptive Intercept (to CPU or host). Normal Intercept (to CPU). CQoS—CQoS updating is performed the same way as IQoS, but using an independent set of resources. The assertion of a CQoS valid flag for any resource that wins the priority context causes a copy of the packet to be sent to the CPU regardless of the setting of any CPU_Copy or CPU_Alert flags. EMS/EMM—EMS/EMM updating is performed the same way as IQoS, but using an independent set of resources. TXMI—assuming a CAM hit, the SCT-supplied priority of the ARAM-supplied TXMI value is compared with the current priority, and if it exceeds the current priority, the ARAM-supplied TXMI value becomes the next TXMI value. LAI—the next LAI may be supplied by two possible methods. First, if the ARAM-supplied LAI VALID field is asserted, the next LAI value is taken to be the value of the ARAM-supplied LAI field. Second, the next LAI value may be accumulated over one or more of the processing cycles using a hash-based lookup scheme as described herein. The process of updating values in the STATS SET portion of the process data, and the process of updating the statistics data structures as maintained in the Statistics RAM 146 at the end of a processing cycle is described in U.S. patent application Ser. No. 10/834,573, filed Apr. 28, 2004.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5282270 *Jun 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 supportUS6173333Jul 17, 1998Jan 9, 2001Interprophet CorporationTCP/IP network accelerator system and method which identifies classes of packet traffic for predictable protocolsUS6275861 *Sep 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 processorUS6553002Aug 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 instructionsUS6765881 *Dec 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 servicesUS6871262 *Feb 14, 2002Mar 22, 2005Cisco Technology, Inc.Method and apparatus for matching a string with multiple lookups using a single associative memoryUS6882642Oct 14, 1999Apr 19, 2005Nokia, Inc.Method and apparatus for input rate regulation associated with a packet processing pipelineUS6888797 *Mar 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 gatewayUS6980552Aug 15, 2002Dec 27, 2005Cisco Technology, Inc.Pipelined packet switching and queuing architectureUS7079407Oct 18, 2002Jul 18, 2006Netlogic Microsystems, Inc.Content addressable memory (CAM) device including match line sensingUS7152191Oct 23, 2003Dec 19, 2006Hewlett-Packard Development Company, L.P.Fault containment and error recovery in a scalable multiprocessorUS7190696 *Mar 5, 2002Mar 13, 2007Force10 Networks, Inc.System and method for distributing packets among a plurality of paths to a destinationUS7248584 *Aug 7, 2002Jul 24, 2007Intel CorporationNetwork packet processingUS7248585 *Oct 16, 2002Jul 24, 2007Sun Microsystems, Inc.Method and apparatus for a packet classifierUS7274693Dec 23, 2002Sep 25, 2007Cisco Technology, Inc.Search engine for forwarding table content addressable memoryUS7292591 *Mar 30, 2004Nov 6, 2007Extreme Networks, Inc.Packet processing system architecture and methodUS7304996 *Mar 30, 2004Dec 4, 2007Extreme Networks, Inc.System and method for assembling a data packetUS7385984 *Mar 30, 2004Jun 10, 2008Extreme Networks, Inc.Packet processing system architecture and methodUS20010025315Jan 10, 2001Sep 27, 2001Jolitz Lynne G.Term addressable memory of an accelerator system and methodUS20020191605Feb 28, 2002Dec 19, 2002Lunteren Jan VanPacket classificationUS20030069973 *Jul 8, 2002Apr 10, 2003Elango GanesanContent service aggregation system control architectureUS20030193949Feb 26, 2003Oct 16, 2003Yuji KojimaPacket processing deviceUS20040003110Jun 27, 2002Jan 1, 2004International Business Machines CorporationMethod and apparatus for implementing frame header alterationsUS20040100956 *Nov 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 forwardingUS20050226242 *Apr 28, 2004Oct 13, 2005Parker David KPipelined packet processorUS20080049774 *Oct 25, 2007Feb 28, 2008Swenson Erik RSystem and method for assembling a data packetWO2003081857A1Mar 4, 2003Oct 2, 2003Intel CorporationVlan 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 dateApplicantTitleUS7554978 *Apr 28, 2004Jun 30, 2009Extreme Networks, Inc.System for accessing content-addressable memory in packet processorUS7889750 *Dec 30, 2005Feb 15, 2011Extreme Networks, Inc.Method of extending default fixed number of processing cycles in pipelined packet processor architectureUS8085779Nov 5, 2009Dec 27, 2011Extreme Networks, Inc.Systems for supporting packet processing operationsUS8139583 *Sep 30, 2008Mar 20, 2012Extreme Networks, Inc.Command selection in a packet forwarding deviceUS8605732Feb 15, 2011Dec 10, 2013Extreme Networks, Inc.Method of providing virtual router functionalityUS9014219Jan 14, 2013Apr 21, 2015International Business Machines CorporationLink aggregation (LAG) information exchange protocolUS9172557Aug 17, 2012Oct 27, 2015International Business Machines CorporationLoad balancing overlay network traffic using a teamed set of network interface cardsUS20060156129 *Nov 15, 2005Jul 13, 2006International Business Machines CorporationSystem for maintaining dataUS20080069114 *Aug 13, 2007Mar 20, 2008Fujitsu LimitedCommunication device and methodUS20090201959 *Feb 7, 2008Aug 13, 2009Board Of Regents, The University Of Texas SystemWavelength and Intensity Monitoring of Optical CavityUS20100054256 *Nov 5, 2009Mar 4, 2010Parker David KSystems for supporting packet processing operations* Cited by examinerClassifications U.S. Classification370/395.32, 370/401, 370/235, 370/394, 370/392, 709/236, 370/252, 709/238International ClassificationH04L12/56Cooperative ClassificationH04L45/745, H04L12/56European ClassificationH04L45/745, H04L12/56Legal EventsDateCodeEventDescriptionNov 8, 2004ASAssignmentOwner name: EXTREME NETWORKS, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:PARKER, DAVID K.;YIP, MICHAEL K.;REEL/FRAME:015353/0499;SIGNING DATES FROM 20040810 TO 20041008Sep 10, 2012FPAYFee paymentYear of fee payment: 4Jul 27, 2015ASAssignmentOwner name: SILICON VALLEY BANK, CALIFORNIAFree format text: SECURITY AGREEMENT;ASSIGNOR:EXTREME NETWORKS, INC.;REEL/FRAME:036189/0284Effective date: 20150724Sep 12, 2016FPAYFee paymentYear of fee payment: 8Oct 31, 2016ASAssignmentOwner name: SILICON VALLEY BANK, CALIFORNIAFree format text: AMENDED AND RESTATED PATENT AND TRADEMARK SECURITY AGREEMENT;ASSIGNOR:EXTREME NETWORKS, INC.;REEL/FRAME:040521/0762Effective date: 20161028RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services