Source: http://www.google.com/patents/US7502374?dq=7,181,560
Timestamp: 2017-09-22 21:14:00
Document Index: 220046889

Matched Legal Cases: ['art.\n2', 'art.\n3', 'art.\n4', 'art.\n5', 'art.\n6', 'art.\n7']

Patent US7502374 - System for deriving hash values for packets in a packet processing system - Google Patents
A 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 system
Publication number US7502374 B1
Application number US 10/834,566
Also published as US7522516, US7554978, US7580350, US7606263, US7646770, US7936687, US8085779, US20100054256
Publication number 10834566, 834566, US 7502374 B1, US 7502374B1, US-B1-7502374, US7502374 B1, US7502374B1
Inventors David K. Parker, Michael K. Yip
Original Assignee Extreme Networks, Inc.
Patent Citations (40), Non-Patent Citations (6), Referenced by (13), Classifications (13), Legal Events (6)
System for deriving hash values for packets in a packet processing system
US 7502374 B1
A 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 the packet, such as link aggregation and equal cost multi-path.
1. A system for deriving hash values for packets in a packet processing system comprising:
key derivation logic, coupled to receive a sequence of commands related to content addressable memory selection from a sequence control table and coupled to receive packet processing data, comprising either or both a packet undergoing processing by packet processing logic or state data generated by the packet processing logic during processing of the packet, the key derivation logic generating a key, from a portion of the packet processing data as selected by a command from the sequence control table, for driving each of a plurality of processing cycles by the packet processing logic in processing the packet;
hash derivation logic, coupled to receive the keys from the key derivation logic and coupled to receive mask data from the sequence control table, the hash derivation logic providing hash information for each of the plurality of processing cycles that is useful for supporting a link aggregation function for the packet, the hash information for a processing cycle derived by masking the key for that processing cycle using mask data from the sequence control table;
resolution logic, coupled to receive the hash information from the hash derivation logic for each of the plurality of processing cycles and coupled to receive one or more commands related to the link aggregation function from the sequence control table, the resolution logic resolving the hash information received from the hash derivation logic over the plurality of processing cycles using the one or more commands from the sequence control table to derive a hash value for the packet; and
link aggregation logic coupled to the resolution logic for receiving the hash value and supporting the link aggregation function for the packet by allocating to the packet a physical link from a plurality of physical links, comprising a logical link, based on the hash value of the packet.
2. The system of claim 1 further comprising equal cost multi-path logic for supporting an equal cost multi-path function by modifying, responsive to the hash value for the packet, an egress port identifier for the packet derived by the packet processing logic.
3. The system of claim 1 further comprising equal cost multi-path logic for supporting an equal cost multi-path function by modifying an identifier of a packet processing sequence assigned to the packet by the packet processing logic, the processing sequence specifying one or more packet processing operations to be performed on the packet prior to egress thereof by the packet processing system.
4. The system of claim 1 wherein the resolution logic is configured to resolve the hash values for the plurality of processing cycles by substituting the hash value derived during a processing cycle for the hash value derived during a preceding processing cycle.
5. The system of claim 1 wherein the resolution logic is configured to resolve the hash values for the plurality of processing cycles by logically combining these hash values into a hash value for the packet.
6. A method of deriving hash values for packets in a packet processing system comprising the steps of:
generating a key for each of a plurality of processing cycles undertaken by packet processing logic in processing a packet, by utilizing key derivation logic, wherein said key derivation logic is coupled to receive a sequence of commands related to content addressable memory selection from a sequence control table and coupled to receive packet processing data comprising either or both the packet undergoing processing by the packet processing logic or state data generated by the packet processing logic in processing the packet, the key for a processing cycle generated by selecting a portion of the packet processing data in effect during that processing cycle using a command from the sequence control table;
deriving hash information for each of the plurality of processing cycles useful for supporting a link aggregation function for the packet by utilizing hash derivation logic, wherein the hash derivation logic is coupled to receive the keys from the key derivation logic and coupled to receive a sequence of commands related to mask data from the sequence control table, and derive the hash information for a processing cycle by masking the key for that processing cycle using mask data from the sequence control table;
providing a hash value for the packet by utilizing resolution logic, wherein the resolution logic is configured to resolve the hash information received from the hash derivation logic for each of the plurality of processing cycles using one or more commands related to the link aggregation function received from the sequence control table; and
supporting the link aggregation function by allocating, utilizing link aggregation logic, to the packet one of a plurality of physical links, comprising a logical link, based on the hash value.
7. The method of claim 6 further comprising supporting an equal cost multi-path function by modifying, responsive to the hash value for the packet, an egress port identifier for the packet derived during or responsive to the processing step.
8. The method of claim 6 further comprising supporting an equal cost multi-path function by modifying an identifier of a packet processing sequence assigned to the packet during or responsive to the processing step, the processing sequence specifying one or more packet processing operations to be performed on the packet prior to egress thereof by the packet processing system.
9. The method of claim 6 further comprising resolving the hash values for the plurality of processing cycles by substituting the hash value derived during a processing cycle for the hash value derived during a preceding processing cycle.
10. The method of claim 6 further comprising resolving the hash values for the plurality of processing cycles by logically combining these hash values into a hash value for the packet.
11. A system for deriving hash values for packets in a packet processing system comprising:
key derivation logic, coupled to receive a sequence of commands related to content addressable memory selection from a sequence control table and coupled to receive packet processing data comprising either or both a packet undergoing processing by packet processing logic or state data generated by the packet processing logic in processing the packet, the key derivation logic generating a key, by selecting a portion of the packet processing data using a command from the sequence control table, for driving each of a plurality of processing cycles undertaken by the packet processing logic in processing the packet;
hash derivation logic, coupled to receive the keys from the key derivation logic and coupled to receive a sequence of commands related to mask data from a sequence control table, the hash derivation logic providing hash information for each of the plurality of processing cycles that is useful for supporting a link aggregation function for the packet, the hash information for a processing cycle derived by masking the key for that processing cycle using mask data from the sequence control table;
resolution logic, coupled to receive the hash information provided from the hash derivation logic for each of the plurality of processing cycles and coupled to receive one or more commands related to the link aggregation function from the sequence control table, the resolution logic configured to resolve the hash information provided by the hash derivation logic for each of the plurality of processing cycles using the one or more commands related to the link aggregation function obtained from the sequence control table to derive a hash value for the packet; and
link aggregation logic for supporting a link aggregation function for the packet by allocating to the packet a physical link from a plurality of physical links comprising a logical link;
wherein the state data comprises any one or more of control, address, filter, header and statistical information for the packet.
12. The system of claim 1 wherein the state data comprises any one or more of control, address, filter, header, and statistical information for the packet.
13. The method of claim 6 wherein the state data comprises any one or more of control, address, filter, header, and statistical information for the packet.
This invention relates to the field of packet processing, and more specifically, to deriving hash values for packets in a packet processing system, the hash values useful for supporting various operations such as link aggregation and equal cost multi-path operations.
Current packet processing systems are under increasing pressure to handle higher and higher data throughputs of, e.g., 10 GB/s or more, and more complex and diverse data packet formats, e.g., embedded packet formats. However, these systems are subject to various bottlenecks and constraints that limit the data throughput that is achievable and the packet formats that can be handled. Hence, there is a need for a packet processing system that overcomes the problems of the prior art.
A system is described for deriving hash values for packets in a packet processing system. In this system, key derivation logic is configured to derive a key from packet processing state data relating to a packet. This key is configured to drive processing of the packet by packet processing logic, which processes the packet responsive to the key. Hash derivation logic is configured to derive a hash value for the packet responsive to the key. This hash value is useful for supporting additional processing of the packet, such as link aggregation and equal cost multi-path functions.
FIG. 13 is a flowchart of an embodiment of a method of maintaining packet statistics that involves allocating a packet size determiner to a packet from a pool of packet size determiners.
FIG. 39 is a block diagram of one embodiment of a system for deriving hash values for packets in a packet processing system.
FIG. 40 illustrates one implementation of the hash derivation logic in the system of FIG. 39.
FIG. 41 illustrates an example of the link aggregation function.
FIG. 42 illustrates an example of the equal cost multi-path function.
FIG. 43 is a flowchart illustrating one embodiment of a method of deriving hash values for packets in a packet processing system.
The following applications are commonly owned by the assignee hereof, and are each incorporated by reference herein as though set forth in full:
Howrey Extreme Dkt.
Dkt. No. No. Title Filing date
10/814,725 P111 PACKET Mar. 30,
PROCESSiNG 2004
10/814,552 P153 PACKET Mar. 30,
10/814,556 P122 PACKET DATA Mar. 30,
MODIFICATION 2004
10/814,728 P124 SYSTEM AND Mar. 30,
METHOD FOR 2004
10/814,545 P126 METHOD AND Mar. 30,
SYSTEM FOR 2004
10/814,729 P127 SYSTEM AND Mar. 30,
10/813,731 P128 SYSTEM AND Mar. 30,
10/814,727 P125 PACKET DATA Mar. 30,
10/814,774 P123 DATA STRUCTURES Mar. 30,
FOR SUPPORTING 2004
10/835,532 P144 SYSTEM FOR Concurrently
DERIVING PACKET herewith
10/835,272 P145 PACKET PARSER Concurrently
10/835,598 P146 PIPELINED PACKET Concurrently
PROCESSOR herewith
10/835,271 P148 SYSTEMS FOR Concurrently
SUPPORTING herewith
10/834,576 P149 SYSTEM FOR Concurrently
ACCESSING herewith
10/834,573 P150 SYSTEM FOR Concurrently
STATISTICS herewith
10/835,252 P151 EXCEPTION Concurrently
HANDLING SYSTEM herewith
The term “register” refers to any physical medium for holding a data element, including, but not limited to, a buffer, FIFO, or the like.
The term “packet processing state data” in relation to a packet refers to data representative of at least a portion of the packet, data representative of at least a portion of the state of processing of the packet, or both.
A. Overall Packet Processing System
In one embodiment, packet post-processor 136 comprises Egress Access Control List (ACL) logic 136 a and Packet Marking logic 136 b. The Egress ACL logic 136 a is configured to arrive at an ACL decision with respect to a packet. In one implementation, four ACL decisions can be independently performed: 1) default ACL action; 2). CPU copy; 3) mirror copy; and 4) kill. The default ACL action may be set to kill or allow. The CPU copy action forwards a copy of the packet to a host 138 coupled to the system. The mirror copy action implements an egress mirroring function (to be discussed in more detail later), in which a copy of the packet is forwarded to mirror FIFO 140 and then on to the egress portion 108 of the packet classification system 102. The kill action either kills the packet or marks it for killing by a downstream Medium Access Control (MAC) processor.
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.
B. Pipelined Packet Processing System
An embodiment of a pipelined packet processing system 1800 is illustrated in FIG. 18. The system 1800 comprises a packet processor 1802 that maintains at least one pipeline having a predetermined number of slots, such as illustrated in FIG. 19, for placement of packet data. Three such slots are identified in FIG. 19 with numerals 1902 a, 1902 b, and 1902 c. The packet processor 1802 is configured to load each of one or more empty ones of the slots with available packet data, process each of one or more filled ones of the slots in sequence during a cycle of processing, and process each of the one or more filled ones of the slots for a predetermined number of cycles of processing.
In one embodiment, the processor 1802 is configured to fill the one or more of the unfilled slots with available packet data as obtained from a queue 1903. In one example, the processor 1802 is configured to bypass unfilled ones of the slots if and while the queue is empty. Thus, in FIG. 19, filled ones of the slots are identified with “P” while unfilled ones of the slots are identified with “X.” In one configuration, the packet data that is taken from queue 1903 and stored in a slot is an identifier of packet data as stored in FIFO buffer 1804. In one application, the queue 1903 is the queue 330, illustrated in FIG. 3, which maintains identifiers of packets that are awaiting classification, and the FIFO buffer 1804 is slicer 306.
In one embodiment, working state data is stored in the slots along with the corresponding packet data. In FIG. 19, this working state data is shown in phantom and identified with numerals 1904 a, 1904 b, 1904 c.
In one implementation example, the predetermined number of slots maintained by the processor 1802 is a programmable variable having a default value of 20 slots, and the predetermined number of processing cycles that each slot undergoes is also a programmable variable having a default value of 5 cycles. In this implementation example, identifiers of packets awaiting processing by processor 1802 are stored in the queue 1903. During a loading mode of operation, each of the slots 1902 a, 1902 b, 1902 c in the pipeline are sequentially loaded with packet identifiers popped off the queue 1903. The process of loading slots is identified in FIG. 19 with numeral 1906. During the loading mode of operation, if the queue 1903 is empty when a slot is presented for loading, the slot is bypassed and not loaded with packet data. This process continues until all the slots have either been filled or bypassed. At that point, the processor enters a processing mode of operation, during which each of the filled slots undergoes the predetermined number of cycles of processing.
Pipeline management data, including:
host/packet indicator, indicating whether the slot is occupied by packet data or data from a CPU host.
cycle count, the number of cycles of processing data in the slot has undergone to date.
first/done indicators, indicating respectively whether the current cycle of processing is the first cycle for the data in the slot, and whether the slot has completed all required cycles of processing.
Packet process state data, including:
Page selector, the page selector applicable to the current processing cycle.
VLAN selector, the VLAN selector applicable to the current processing cycle.
IP selector, the IP header selector applicable to the current processing cycle.
ARAM VLAN flag, indicating whether the working VLAN for the packet is to be taken from the ARAM entry.
SCT index, identifying the address of the next SCT command to be executed.
Static packet information, including:
Packet pointer, a pointer to the packet as stored in a buffer.
Interface type, e.g., EtherNet or POS.
Ingress port number, an identifier of the ingress port of the packet.
Port State flag, a flag indicating whether the Port State Table is being used for this processor slot.
Debug management information.
In one configuration, the AFH data 2004 comprises:
Priority based information, including:
TXMI.
IQoS, EQoS, CQoS.
Egress Mark data.
Non-priority based information, including the following “sticky” flags that, once set, remain set:
Learn flag, a flag that, if asserted, directs a switch-side device to forward a copy of the packet to the host for learn processing.
Redirect flag, a flag that, if asserted, directs a switch-side device to forward a copy of the packet to the host for redirect processing.
Ingress Mirror flag, a flag that, if asserted, directs a switch-side device to forward a copy of the packet to a designated ingress mirror port on the switch.
Egress Mirror flag, a flag that, if asserted, directs a switch-side device to forward a copy of the packet to a designated mirror FIFO on the switch.
Random Early Drop flag, a flag that, if asserted, increases the priority of the packet for dropping.
Jumbo check flag, a flag that, if asserted, directs a device encountering the packet to perform a Jumbo-allowed check.
In one configuration, the statistical data comprises:
Matrix mode statistics, whereby a multi-dimensional statistic for a packet is accumulated over each of the processing cycles undertaken by the packet.
In one embodiment, the pipeline of FIG. 19 comprises three separate but related pipelines, identified with numerals 2102, 2104, 2106 in FIG. 21, that are respectively used to update the control, AFH, and statistical portions of the working state data.
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.
VLAN ARAM—an indicator that the working VLAN for the current processing cycle was derived from an ARAM entry.
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 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.
CID—an identifier of the CAM key as used in the current processing cycle.
RID—a Router identifier as obtained from the PST or VST during the current processing cycle.
CONSTANT—the CONSTANT field from the SCT used in the current processing cycle.
RT0-RT3 RESULTS—the results, respectively, of Reduction Tables 0-3 during the current processing cycle.
IP PROTOCOL—the IP protocol field of the IP Header currently being processed.
ARAM DATA—the ARAM entry data from the previous processing cycle.
current SCT index loaded with initial SCT index as obtained from the Fist Command CAM 1808.
current PAGE SEL set to 0 (representing Page 0).
current VLAN SEL set to 0 (representing the only or outer VLAN of Page 0).
current VLAN set to Page 0, VLAN0 (or in the case of a routed POS service, the current VLAN is set to the VLAN supplied by the First Command CAM 1818).
current context pointer set (C1-C6) loaded with Page 0 context pointers.
current L3 SEL set to 0 (representing the only or outer L3 Header of Page 0).
current IP control set (consisting of Fragment Type, Don't_Fragment, Protocol, Next Header, and Exception Control values) to Page 0 L3 0 (representing the only or outer Header of Page 0).
LKUP COUNT reset to 0 (if counting upwards) or predetermined number of cycles per packet (if counting down).
All the data in the AFH SET is initialized to 0. The data in the STATISTICS SET is initialized to values specified in the PST/VST table.
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.
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.
FIG. 29 illustrates one example 2900 of the data path logic 1808. In this particular example, the data path logic produces a 72 bit CAM key 2902 that comprises 18 4-bit nibbles. Each of the nibbles is produced by a corresponding 4-bit wide multiplexor. Thus, in FIG. 29, nibble 0 of CAM key 2902 is produced by multiplexor 2904 a, while nibble 17 of CAM key 2902 is produced by multiplexor 2904 b. Each of these multiplexors receives the same inputs in the same order, 512 4-bit nibbles, 256 nibbles representing the process data, and 256 nibbles representing the packet data. Each of these multiplexors receives its own 12-bit selection field from the current SCT entry. Thus, multiplexor 2904 a receives the 12-bit SELECT0 field, referred to in FIG. 28 as CAM KEY SEL NIBBLE 0, while multiplexor 2904 b receives the 12-bit SELECT17 field, referred to in FIG. 28 as CAM KEY SEL NIBBLE 17. There are a total of 18 selection fields represented in FIG. 28, which may be referred to respectively as CAM KEY SEL NIBBLE 0-17, each of which is assigned its own multiplexor in the implementation of data path logic illustrated in FIG. 29.
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 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:
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.
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 comprises 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 deriving hash values for packets in a packet processing system. In this embodiment, the system comprises key derivation logic 3902 for deriving a key 3904 from data 3906 representative of at least a portion of a packet, at least a portion of a state of the packet, or both. The key 3904 is configured to drive processing of the packet.
In this embodiment, the system also comprises packet processing logic 3908 for processing the packet responsive to the key 3904, and hash derivation logic 3910 for deriving a hash value 3912 for the packet responsive to the key 3904. This hash value is useful for supporting additional processing of the packet.
In one implementation, the key derivation logic 3902 is configured to derive a key 3904 for each of a plurality of processing cycles, the packet processing logic 3908 is configured to process the packet over the plurality of cycles, the hash derivation logic 3910 is configured to derive a hash value for each of the cycles, and the system 3900 further comprises resolution logic 3914 for resolving the hash values derived during each of the plurality of processing cycles, resulting in a hash value 3916 for the packet.
In the example illustrated, the processing logic 3908 comprises CAM 3918, ARAM 3920, SCT 3928, a register 3922 holding the SCT entry for the current processing cycle, and addressing logic 3924 for determining the address of the SCT entry for the next processing cycle. Also, in this example, the data path logic 3902 comprises the data path logic illustrated and described in relation to FIG. 29; CAM 3918 is the CAM 1810 illustrated and described in relation to FIG. 18, ARAM 3920 is the ARAM 1812 illustrated and described in relation to FIG. 18, and SCT 3928 is the SCT 1806 illustrated and described in relation to FIG. 18. Each SCT entry has the format illustrated in FIG. 28, and each ARAM entry has the format illustrated in FIGS. 32A-32B. The addressing logic 3924 is configured to determine the address of the SCT entry that governs the next processing cycle. As shown, this logic is configured so that any ARAM-supplied SCT address (supplied by means of the NEXT SCT field of FIG. 30), becomes the next SCT address if such is valid, as indicated by assertion of the ARAM-supplied NEXT SCT VALID flag (FIG. 30). Otherwise, the next SCT address is formed from corresponding entries in the current SCT entry 3922. In particular, if there is a hit condition, the next SCT address becomes the SCT address specified by the NXT SCT HIT field (FIG. 28); if there is a miss condition, the next SCT address becomes the SCT address specified by the NXT SCT MISS field (FIG. 28).
In this example, the key derivation logic 3902 has the form illustrated in FIG. 29. In the case of a 72 bit key, the key is formed directly from the output of the key derivation logic 3902. In the case of a 144 bit key, the key is formed from the concatenation of two successive outputs of the key derivation logic 3902 over two successive half cycles.
In this example, the hash derivation logic 3910 has the form illustrated in FIG. 40. Each 4-bit nibble of the key 2902 a, 2902 b, 2902 c is input to a corresponding AND gate, configured to allow the nibble to be masked through a corresponding mask, identified in FIG. 40 as MASK0, MASK1, MASK17. In the example illustrated, each of the masks is a single bit as obtained from the LA MSK field of the current SCT entry 3922 (FIG. 28). This bit allows the entirety of the corresponding nibble to be masked or not, but does not allow individual bits of the nibble to be masked. (On the other hand, one of ordinary skill in the art would appreciate that examples are possible that allow the masking of individual bits of the nibbles.). The masked nibbles 4004 a, 4004 b are then logically combined through logical XOR gates 4004 a, 400 b in the manner shown, resulting in a 4-bit hash value 4006. In the case of a 144-bit key derived over two half cycles, the hash value is formed by logically XORing the half values of the two cycles together. In the case of a 72-bit key which is repeated over two successive half cycles, this logically XORing must be suppressed since the two values will be the same, and logically XORing them would result in 0.
In FIG. 39, the hash value 3930 output by the hash derivation logic 3910 may be superseded by an ARAM-supplied hash value provided in the form of the LAI field (FIG. 30). The ARAM-supplied LAI flag (FIG. 30) indicates whether the ARAM-supplied LAI is valid or not. If so, logic 3926 is configured to substitute the ARAM-supplied value for the value 3930 at the output 3912.
Resolution logic 3914 is configured to resolve the values 3912 received over multiple processing cycles for a packet to result in a hash value 3916 for the packet. In the example illustrated in FIG. 39, two modes are possible as determined by the LAI CTRL field of the current SCT entry (FIG. 28). In a first mode, each value 3912 received during a processing cycle replaces the previous value. Consequently, at the conclusion of all the processing cycles for a packet, the hash value 3916 assigned to the packet is the hash value 3912 derived during the last processing cycle for the packet. In the second mode, the hash values 3912 from the various processing cycles are logically XORed together to result in the hash value 3916 for the packet.
It should be appreciated that many other examples are possible so the particular example illustrated in FIG. 39 should not be construed as limiting. In particular, the illustrated details of the processing logic 3918 are not important to the invention as broadly construed, and therefore should not be construed as limiting.
In one embodiment, the system 3900 further comprises link aggregation logic (not shown) for supporting a link aggregation function, which refers to the process of treating multiple physical links as one logical link, and then utilizing an egress distribution policy to distribute packets intended for the logical link over the physical links. Thus, for example, in FIG. 41, where numeral 4102 identifies a network side device, numeral 4104 identifies a switch side device, and numeral 4106 identified a plurality of physical links between the two devices, link aggregation refers to the function of treating each of the physical links 4106 as a single logical link, thus giving rise to the need for a policy for distributing packets, to be transferred between the two devices over the logical link, amongst the physical links. In one embodiment, a packet is allocated to a physical link based on the hash value assigned to the packet. In this particular application, the hash value may be referred to as a link index. It is assumed in this application that there is a 1-1 or many-to-1 relationship between the possible hash values and the physical links.
In a second embodiment, the system of FIG. 39 further comprises equal cost multi-path logic (not shown) for supporting an equal cost multi-path function. In this application, as illustrated in FIG. 42, there may be several equal cost (referring to the number of hops) layer three or higher paths 4206, 4208 between a source network entity 4202, and a destination network entity 4204. Again, as with the link aggregation function, it may be desirable to transfer packets between the network entities 4202, 4204 over each of the equal cost paths 4206, 4208. To support this application, a policy must again be devised for distributing the packets over the various equal cost paths.
In one embodiment, such a policy is implemented by modifying, responsive to the hash value for the packet, an egress port identifier for the packet derived by the packet processing logic 3908. In this embodiment, an identifier of a packet processing sequence assigned to the packet by the packet processing logic 3908 is also modified responsive to the hash value of the packet. This processing sequence specifies one or more packet processing operations to be performed on the packet prior to egress thereof by the packet processing system.
In one example, where the hash value comprises the 4 bit nibble discussed in relation to FIG. 40, it is assumed there are a maximum of 16 equal cost paths, between the two network entities, each of which is assumed to be assigned a PTI and TXMI that are part of a sixteen element block. In this example, the equal cost multi-path function is implemented by directly replacing the lower four bits of the PTI assigned to the packet with the 4-bit hash value, and the lower four bits of the TXMI assigned to the packet with the 4 bit hash value. One of skill in the art would appreciate that this example may be readily extended to scenarios that assume a different maximum of equal cost paths, e.g. 8, 4. In a second example, an indirect approach is utilized to modify the PTI and TXMI of the packet. According to this indirect approach, the hash value (referred to as the LAI in FIG. 23) forms part of the key in the next processing cycle. In this next processing cycle, an entry in the CAM is retrieved based on this key. This entry contains a PTI and TXMI value that is assigned to the packet.
FIG. 43 is a flowchart of an embodiment 4300 of a method of deriving hash values for packets in a packet processing system. In this embodiment, the method comprises step 4302, deriving a key from data representative of at least a portion of a packet or at least a portion of a state of the packet. In this embodiment, the key is configured to drive the processing of the packet. The method also comprises step 4304, processing the packet responsive to the key. The method further comprises step 4306, deriving a hash value for the packet responsive to the key, wherein the hash value is useful for supporting additional processing of the packet.
In one embodiment, the first deriving step 4302 comprises deriving a key for each of a plurality of processing cycles, the processing step 304 comprises processing the packet over the plurality of cycles, the second deriving step 4306 comprises deriving a hash value for each of the cycles, and the method further comprises resolving the hash values derived during each of the plurality of processing cycles, resulting in a hash value for the packet.
In one application, the method further comprises supporting a link aggregation function by allocating the packet to one of a plurality of physical links comprising a logical link based on the hash value of the packet.
In a second application, the method further comprises supporting an equal cost multi-path function by modifying, responsive to the hash value for the packet, an egress port identifier for the packet derived during or responsive to the processing step.
In one example, the method further comprises supporting an equal cost multi-path function by modifying an identifier of a packet processing sequence assigned to the packet during or responsive to the processing step 4304, the processing sequence specifying one or more packet processing operations to be performed on the packet prior to egress thereof by the packet processing system.
In one embodiment, the method further comprises resolving the hash values for the plurality of processing cycles by substituting the hash value derived during a processing cycle for the hash value derived during a preceding processing cycle. In a second embodiment, the method further comprises resolving the hash values for the plurality of processing cycles by logically combining these hash values into a hash value for the packet.
US6034957 Feb 24, 1998 Mar 7, 2000 Extreme Networks, Inc. Sliced comparison engine architecture and method for a LAN switch
US6295299 Jan 30, 1998 Sep 25, 2001 Extreme Networks, Inc. Data path architecture for a LAN switch
US6738892 Oct 20, 1999 May 18, 2004 Transmeta Corporation Use of enable bits to control execution of selected instructions
US6765881 * Dec 6, 2000 Jul 20, 2004 Covad Communications Group, Inc. Virtual L2TP/VPN tunnel network and spanning tree-based method for discovery of L2TP/VPN tunnels and other layer-2 services
US6871262 * Feb 14, 2002 Mar 22, 2005 Cisco Technology, Inc. Method and apparatus for matching a string with multiple lookups using a single associative memory
US6882642 Oct 14, 1999 Apr 19, 2005 Nokia, Inc. Method and apparatus for input rate regulation associated with a packet processing pipeline
US6917617 Dec 16, 1998 Jul 12, 2005 Cisco Technology, Inc. Use of precedence bits for quality of service
US7079407 Oct 18, 2002 Jul 18, 2006 Netlogic Microsystems, Inc. Content addressable memory (CAM) device including match line sensing
US7152191 Oct 23, 2003 Dec 19, 2006 Hewlett-Packard Development Company, L.P. Fault containment and error recovery in a scalable multiprocessor
US7248584 * Aug 7, 2002 Jul 24, 2007 Intel Corporation Network packet processing
US7248585 * Oct 16, 2002 Jul 24, 2007 Sun Microsystems, Inc. Method and apparatus for a packet classifier
US7274693 Dec 23, 2002 Sep 25, 2007 Cisco Technology, Inc. Search engine for forwarding table content addressable memory
US7292591 * Mar 30, 2004 Nov 6, 2007 Extreme Networks, Inc. Packet processing system architecture and method
US7385984 * Mar 30, 2004 Jun 10, 2008 Extreme Networks, Inc. Packet processing system architecture and method
US20030193949 Feb 26, 2003 Oct 16, 2003 Yuji Kojima Packet processing device
US20040003110 Jun 27, 2002 Jan 1, 2004 International Business Machines Corporation Method and apparatus for implementing frame header alterations
US20040100956 * Nov 20, 2003 May 27, 2004 Akira Watanabe Packet search device, packet processing search method used for the same, and program for the same
US20040205753 Aug 18, 2003 Oct 14, 2004 Globespan Virata Inc. Timing ring mechanism
US20040246981 Jan 28, 2004 Dec 9, 2004 Zhiqun He System and method of accessing and transmitting different data frames in a digital transmission network
US20050074009 Oct 1, 2004 Apr 7, 2005 Tatsuo Kanetake Packet transfer unit
US20050198362 Dec 31, 2003 Sep 8, 2005 Navada Muraleedhara H. Exception packet forwarding
US20050226242 * Apr 28, 2004 Oct 13, 2005 Parker David K Pipelined packet processor
WO2003081857A1 Mar 4, 2003 Oct 2, 2003 Intel Corporation Vlan table management for memory efficient lookups and inserts in hardware-based packet switches
1 Netlogic Microsystems, Product Brief NSE5000GLQ, Copyright 2004, available at: http://www.netlogicmicro.com/datasheets/nse5000glq.html.
2 Network Working Group, RFC 1071-Computing the Internet Checksum, Sep. 1988, available at: http://www.faqs.org/rfcs/rfc1071.html.
3 Network Working Group, RFC 1141-Incremental Updating of the Internet Checksum, Jan. 1990, available at: http://www.faqs.org/rfcs/rfc1141.html.
4 Network Working Group, RFC 1624-Computation of the Internet Checksum via Incremental Update, May 1994, available at: http://www.faqs.org/rfcs/rfc1624.html.
5 Van Ess, D., A Circular FIFO, PSoC Style, Cypress Microsystems, Application Note AN2036, Rev. B, pp. 1-5, Jun. 21, 2002.
6 Zhang, Z., Recovery of Memory and Process in DSM Systems: HA Issue #1, Hewlett-Packard Co. HPL-2001-76, Mar. 30, 2001.
US7554978 * Apr 28, 2004 Jun 30, 2009 Extreme Networks, Inc. System for accessing content-addressable memory in packet processor
US7889750 * Dec 30, 2005 Feb 15, 2011 Extreme Networks, Inc. Method of extending default fixed number of processing cycles in pipelined packet processor architecture
US8085779 Nov 5, 2009 Dec 27, 2011 Extreme Networks, Inc. Systems for supporting packet processing operations
US8139583 * Sep 30, 2008 Mar 20, 2012 Extreme Networks, Inc. Command selection in a packet forwarding device
US9014219 Jan 14, 2013 Apr 21, 2015 International Business Machines Corporation Link aggregation (LAG) information exchange protocol
US9172557 Aug 17, 2012 Oct 27, 2015 International Business Machines Corporation Load balancing overlay network traffic using a teamed set of network interface cards
US9736070 Aug 28, 2015 Aug 15, 2017 International Business Machines Corporation Load balancing overlay network traffic using a teamed set of network interface cards
US9762493 Mar 10, 2015 Sep 12, 2017 International Business Machines Corporation Link aggregation (LAG) information exchange protocol
US20060156129 * Nov 15, 2005 Jul 13, 2006 International Business Machines Corporation System for maintaining data
US20080069114 * Aug 13, 2007 Mar 20, 2008 Fujitsu Limited Communication device and method
US20100054256 * Nov 5, 2009 Mar 4, 2010 Parker David K Systems for supporting packet processing operations
U.S. Classification 370/395.32, 370/401, 370/235, 370/394, 370/392, 709/236, 370/252, 709/238
Cooperative Classification H04L45/745, H04L12/56
European Classification H04L45/745, H04L12/56
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:PARKER, DAVID K.;YIP, MICHAEL K.;REEL/FRAME:015353/0499;SIGNING DATES FROM 20040810 TO 20041008