Technique for generating hash-tuple independent of precedence order of applied rules
View Patent ↗Techniques have been developed to facilitate evaluation of match and hash rule entries in ways that allow an implementation to decouple (i) the order in which match rules are applied to a first subset of packet header fields from (ii) the ordering of a second subset of packet header fields over which a non-commutative hash is computed. In short, the set and ordering of fields evaluated in accordance with a precedence order of rules need not correspond to the set or ordering of fields over which a hash is computed in a communications controller.
1. An apparatus comprising:
a communication controller that, for at least some received information frames, computes a non-commutative hash over an ordered subset of field values from respective headers associated with the received information frames,
wherein the communication controller determines a particular ordered subset of field values for inclusion in the non-commutative hash based on execution of match rules that, for respective information frames, evaluate selected ones of the field values in an order that differs from that of the ordered subset of field values over which the non-commutative hash is computed.
2. The apparatus of claim 1 , further comprising:
plural processing elements configured to operate on content from respective information frames in accord with protocols layered atop those implemented by the communication controller,
the communication controller configured to distribute the content from respective information frames amongst the plural processing elements in accord with the computed non-commutative hashes.
3. The apparatus of claim 2 , wherein
the processing elements configured to receive the content distributed thereto together with respective ones of the non-commutative hashes computed at the communications controller; and
the processing elements configured to use a particular non-commutative hash received together with particular content as an index to retrieve a context for processing the particular content in connection with one or more of the layered atop protocols.
4. The apparatus of claim 3 ,
wherein distribution by the communication controller of hypertext transfer protocol data from a particular one of the information frames to a particular one of the processing elements is based on the computed non-commutative hash and is in accord with a load balance criterion; and
wherein the retrieval of a processing context particular to the hypertext transfer protocol (HTTP) data from the particular information frame is also based on the computed hash and is in accord with a targeted website context identified, at least in part, using the computed hash as a key therefor.
5. The apparatus of claim 3 , wherein the processing context retrieved based on the particular hash is one of:
a web server context HTTP protocol traffic;
a cached L2 or L3 lookup table identified for a packet forwarding application;
a session initiation protocol (SIP) routing table indexed for particular SIP traffic; and
media content indexed for a particular source, wherein the particular hash includes in the hashed over set of field values an addressing field for particular media transfer protocol traffic.
6. The apparatus of claim 1 ,
wherein for at least a first subset of the received information frames, the communications controller computes respective hashes over a first ordered subset of field values; and
wherein for at least a second subset of the received information frames, the communications controller computes respective hashes over a second ordered subset of field values, the first and second subsets of field values being dissimilar in either or both of constituent fields and ordering thereof.
7. The apparatus of claim 6 ,
wherein the first subset of received information frames includes respective Internet Protocol (IP) packet headers that encode an IP_source_address, an IP_destination_address and a transmission control protocol (TCP) protocol and further include data that identify a hypertext transport protocol (HTTP) associated destination_port, and
wherein the first ordered subset of field values over which a respective hash is computed is {IP_source_address, IP_destination_address, protocol, source_port, destination_port}.
8. The apparatus of claim 6 ,
wherein the second subset of received information frames includes respective Internet Protocol (IP) packet headers that encode an IP_source_address, an IP_destination_address, and a internet message control protocol (ICMP) protocol, and
wherein the second ordered subset of field values over which a respective hash is computed is {IP_source_address, IP_destination_address}.
9. The apparatus of claim 1 , wherein the communications controller further includes:
storage for field values parsed from the received information frames;
evaluation logic that evaluates match rules against respective ones of the parsed field values in accordance with an evaluation order; and
hash logic that applies the non-commutative hash based on respective ones of the parsed field values in accordance with a hash order that differs from the evaluation order.
10. The apparatus of claim 9 ,
wherein the evaluation logic and the hash logic are coupled to receive parsed field values from the storage in accord with the respective evaluation and hash orders.
11. The apparatus of claim 9 ,
wherein the evaluation logic includes plural elements that evaluate respective match rules in parallel based on field values retrieved from the storage; and
wherein the hash logic is configured as a hash chain of plural stages, each stage corresponding to one of the evaluation logic elements and coupled to selectively introduce a successive contribution to the non-commutative hash based on a respective one of the parsed field values and on a match result computed at the corresponding evaluation logic elements.
12. A method of processing information frames, the method comprising:
at a communications controller, evaluating in an evaluation order a first subset of field values parsed from a particular one of plural information frames;
based on results of the evaluation, selecting a second subset of the parsed field values and applying a non-commutative hash thereto, wherein the non-commutative hash is applied in a hash order that differs from the evaluation order;
for at least a first subset of the information frames, computing the respective non-commutative hashes over a first ordered subset of field values; and
for at least a second subset of information frames, computing respective non-commutative hashes over a second ordered subset of field values, the first and second subsets of field values being dissimilar with respect to either or both of constituent fields and ordering thereof.
13. The method of claim 12 , further comprising:
storing the parsed field values in storage accessible to both evaluation logic and hash logic of the communications controller.
14. The method of claim 12 , further comprising:
parsing the field values from one or more headers associated with the particular information frame.
15. The method of claim 12 , further comprising:
distributing content from respective information frames, including the particular information frame, amongst plural processing elements, wherein the distribution is in accord with respective non-commutative hashes applied to respective ordered subsets of field values parsed from the respective information frames.
16. The method of claim 15 , further comprising:
at the plural processing elements, operating on content from the respective information frames in accord with protocols layered atop those implemented by the communication controller; and
using the respective non-commutative hashes computed at the communications controller as hash keys to retrieve relevant processing contexts in connection with one or more of the layered atop protocols.
17. A method of processing information frames, the method comprising:
at a communications controller, evaluating in a first order a first subset of field values parsed from a first information frame; and
based on results of the evaluation, selecting a second subset of the parsed field values and applying a non-commutative hash thereto, wherein the non-commutative hash is applied in a second order that differs from the first order, wherein the non-commutative hash is selected from a set that includes:
an ORD-type hash; and
a CRC-type hash.
18. A method of processing information frames, the method comprising:
at a communications controller, parsing headers associated with respective information frames and computing respective non-commutative hashes over respective ordered subsets of field values parsed from the respective headers;
using the non-commutative hashes to distribute the respective information frames amongst plural processing elements in accordance with a load balance criterion, the processing elements operating on content of the distributed information frames in accord with protocols layered atop those implemented by the communication controller;
at each of the plural processing elements, processing respective ones of the information frames distributed thereto; and
for at least some of the distributed information frames, using the non-commutative hashes computed at the communications controller and used to distribute the respective information frames as a hash key to retrieve a processing context relevant to a particular execution instance of the respective layered atop protocol.
19. The method of claim 18 ,
wherein for at least a first subset of the information frames, the respective non-commutative hashes are computed over a first subset of field values, and
wherein for at least a second subset of the information frames, the respective hashes are computed over a second subset of field values, the first and second subsets of field values being dissimilar.