Methods, systems and computer program products for packet ordering for parallel packet transform processing

• US 8,189,591 B2
• Filed: 10/30/2001
• Issued: 05/29/2012
• Est. Priority Date: 10/30/2001
• Status: Expired due to Fees

• Current Assignee: Hifn, Inc. (Maxlinear Incorporated)
• Original Assignee: Exar Corporation (Maxlinear Incorporated)
• Inventors: Blaker, David M., Savarda, Raymond
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): NGO, NGUYEN HOANG
• Application Number:
  US09/999,647
• Publication Number:
  US 20030081600A1
• Time in Patent Office: 3,864 Days
• Field of Search: 370/394, 370/473, 370/474
• US Class Current: 370/394
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Packets are processed while maintaining a sequence of the packets. Packets are received and a sequence identifier assigned to the packets. The sequence identifier specifies a serial order associated with the packet. The packets are provided to a plurality of parallel packet transform processors and the packets are processed utilizing the packet transform processors. The processed packets are ordered based on the sequence identifier of the packets. The packets may be evaluated to classify the packets so as to identify related packets. A sequence identifier is assigned to the packets such that the sequence identifier identifies an ordering of the related packets. The processed packets are ordered based on the classification of the packets and the sequence identifier of the packets. Parallel packet transform processing may be particularly well suite to parallel cryptographic processing.

Claims

1. A method of transformation processing packets, comprising:

receiving packets;

assigning a sequence identifier to the packets, wherein the sequence identifier specifies a serial order associated with the packet;

providing the packets to a plurality of parallel packet transform processors;

processing the packets utilizing the packet transform processors so as to provide processed packets that have been transformed; and

ordering the processed packets based on the sequence identifier of the packets.

2. The method of claim 1, further comprising a step of evaluating packets to classify the packets so as to identify related packets;

wherein the step of assigning a sequence identifier to the packets comprises a step of assigning a sequence identifier to related packets, wherein the sequence identifier identifies an ordering of the related packets; and

wherein the step of ordering the processed packets based on the sequence identifier of the packets comprises a step of ordering the processed packets based on the classification of the packets and the sequence identifier of the packets.

3. The method of claim 2, further comprising a step of assigning a flow identifier to related packets based on the evaluation of the packets.

4. The method of claim 3, wherein the step of evaluating packets comprises evaluating a source address, a destination address and a protocol associated with the packets;

and

wherein the step of assigning a flow identifier to related packets comprises assigning a flow identifier to related packets based on the source address, destination address and protocol associated with the packets.

5. The method of claim 3, wherein the step of evaluating packets comprises evaluating a destination address, a security parameter index and a protocol associated with the packets;

and

wherein the step of assigning a flow identifier to related packets comprises assigning a flow identifier to related packets based on the destination address, security parameter index and protocol associated with the packets.

6. The method of claim 5, wherein the step of assigning a flow identifier to related packets based on the destination address, security parameter index and protocol associated with the packets comprises assigning a flow identifier to related packets based on the destination address, security parameter index, port and protocol associated with the packets.

7. The method of claim 3, further comprising a step of generating the flow identifier of related packets based on information contained in the related packets.

8. The method of claim 7, wherein the packets comprise cryptographic packets.

9. The method of claim 8, further comprising a step of determining if the packet is a packet of an encrypting flow;

and

wherein the step of generating the flow identifier comprises hashing a source address, a destination address and a cryptographic protocol contained in the packets so as to provide the flow identifier if the packet is a packet of an encrypting flow.

10. The method of claim 8, further comprising a step of determining if the packet is a packet of a decrypting flow;

and

wherein the step of generating the flow identifier comprises hashing a destination address, a security parameter index and a cryptographic protocol contained in the packets so as to provide the flow identifier if the packet is a packet of a decrypting flow.

11. The method of claim 6, wherein the step of generating the flow identifier comprises a step of hashing fields of a packet to provide the flow identifier.

12. The method of claim 11, wherein the step of hashing fields of a packet comprises:

multiplying the fields of the packet by respective prime numbers to provide multiplied values;

summing the multiplied values so as to provide a sum; and

determining a modulo of the largest prime number not greater than 2ⁿ and the sum, wherein n is a number of bits in the resulting flow identifier.

13. The method of claim 11, wherein the step of hashing fields of a packet comprises:

determining a modulo of the largest prime number not greater than 2ⁿ and respective fields of the packet, wherein n is a number of bits in the resulting flow identifier so as to provide modulo results,

multiplying the modulo results by respective prime numbers to provide multiplied values;

summing the multiplied values.

14. The method of claim 2, wherein the step of ordering the processed packets based on the classification of the packets and the sequence identifier of the packets, comprises:

controlling timing of an output of each of the parallel packet transform processors processing a related packet based on an output sequence value associated with the related packets so as to admit outputs of the parallel packet transform processors processing related packets in a sequence corresponding to the ordering of the related packets.

15. The method of claim 14, wherein the step of controlling timing of an output comprises:

maintaining a current output sequence value associated with the related packets;

determining if an output packet of one of the parallel packet transform processors has a sequence identifier corresponding to the current output sequence value; and

allowing the one of the parallel processors to output the output packet if the output packet has a sequence identifier corresponding to the current output sequence value.

16. The method of claim 15, further comprising a step of assigning a flow identifier to related packets based on the evaluation of the packets and wherein related packets are assigned a common identifier and different groups of related packets are assigned different flow identifiers.

17. The method of claim 16, further comprising a step of controlling output of the parallel processors based on the flow identifier of a processed packet and a sequence identifier of a processed packet.

18. The method of claim 17, wherein the step of controlling output of the parallel processors based on the flow identifier of a processed packet comprises controlling the output of the parallel processors so as to assure that processed packets with different flow identifiers will have an opportunity to be output.

19. The method of claim 1, wherein the packet transform processor comprise cryptographic processors and wherein the packets comprise cryptographic packets.

20. A method of controlling the processing of packets in a processing system having a plurality of parallel packet transform processors, comprising:

assigning a flow identifier to related packets;

assigning a sequence identifier to each packet of the related packets;

encapsulating the packet, the flow identifier and the sequence identifier to provide a packet-object;

providing the packet-object to one of the packet transform processor of the parallel packet transform processors;

processing the packet-object utilizing the one of the packet transform processors to provide a processed packet-object that has been transformed; and

selectively outputting the processed packet-object based on the flow identifier and the sequence identifier of the processed packet-object.

21. The method of claim 20, wherein the step of assigning a flow identifier comprises:

extracting selector values from a packet; and

hashing the selector values so as to provide the flow identifier.

22. The method of claim 21, wherein the packet transform processors comprise cryptographic processors and wherein the step of extracting selector values comprises:

determining if the packet is an inbound cryptographic packet or an outbound cryptographic packet;

extracting a source address, a destination address and protocol from the packet if the packet is an outbound cryptographic packet; and

extracting the destination address, security parameter index and protocol from the packet if the packet is an inbound cryptographic packet.

23. The method of claim 22, wherein the step of hashing the selector values so as to provide the flow identifier comprises:

multiplying the selector values by prime numbers;

summing results of the multiplication; and

determining a modulo of a largest prime number not greater than 2ⁿ and the results of the sum, wherein n is a number of bits in the flow identifier.

24. The method of claim 22, wherein the step of hashing the selector values so as to provide the flow identifier comprises:

determining a modulo of a largest prime number not greater than 2ⁿ and respective ones of the selector values to provide modulo values, wherein n is a number of bits in the flow identifier;

multiplying the modulo values by corresponding prime numbers; and

summing results of the multiplication.

25. The method of claim 20, further comprising a step of maintaining a table of sequence identifiers associated with flow identifiers;

and

wherein the step of assigning a sequence identifier to each packet of the related packets comprises;

looking up a current sequence identifier in the table utilizing the flow identifier of the packet;

assigning the current sequence identifier to the packet;

incrementing the current sequence identifier to provide an updated current sequence identifier; and

storing the updated current sequence identifier in the table associated with the flow identifier of the packet.

26. The method of claim 20, wherein the step of selectively outputting the processed packet-object based on the flow identifier and the sequence identifier of the processed packet-object comprises:

determining if the sequence identifier of a processed packet-object corresponds to a current output sequence identifier for the flow identifier of the processed packet-object; and

outputting the processed packet-object if the current output sequence identifier for the flow identifier of the processed packet-object corresponds to the current output sequence identifier.

27. The method of claim 26, further comprising a step of maintaining a table of current output sequence identifiers associated with flow identifiers;

and wherein the step of determining if the sequence identifier of a processed packet-object corresponds to a current output sequence identifier for the flow identifier of the processed packet-object comprises;

extracting the flow identifier and sequence identifier from a processed packet-object;

looking up a current output sequence identifier in the table utilizing the flow identifier of the processed packet-object;

comparing the current output sequence identifier from the table with the sequence identifier extracted from the processed packet-object to determine if they are equal;

incrementing the current output sequence identifier to provide an updated current output sequence identifier if the current output sequence identifier and the extracted sequence identifier are equal; and

storing the updated current output sequence identifier in the table associated with the flow identifier of the processed packet-object.

28. A parallel packet transform processing system, comprising:

a plurality of packet transform processing units;

a packet-input demux configured to receive a serial stream of packets, identify a sequence of the received packets by assigning a sequence identifier to related packets, wherein the sequence identifier identifies an ordering of the related packets, and provide the packets to the plurality of packet transform processing units so as to allow parallel processing and transformation of the received packets; and

a packet-output mux configured to receive processed packets from the plurality of packet transform processing units to order the processed packets based on the sequence identifier of the packets, and output the processed packets in the sequence identified by the packet-input demux.

29. The processing system of claim 28, wherein the plurality of packet transform processing units are configured to buffer processed packets for output so as to allow the packet transform processing units to process a plurality of packets prior to a processed packet being output by the packet-output mux.

30. The processing system of claim 28, wherein the packet-input demux is further configured to evaluate the received packets and assign a flow identifier to related packets based on the evaluation of the packets.

31. The processing system of claim 30, wherein the packet-input demux is configured to evaluate a source address, a destination address and a protocol associated with the packets assign a flow identifier to related packets based on the source address, destination address and protocol associated with the packets.

32. The processing system of claim 30, wherein the packet-input demux is further configured to evaluate a destination address, a security parameter index and a protocol associated with the packets and assign a flow identifier to related packets based on the destination address, security parameter index and protocol associated with the packets.

33. The processing system of claim 30, wherein the packet-input demux is configured to generate the flow identifier of related packets based on information contained in the related packets.

34. The processing system of claim 33, wherein the packet-input demux is further configured to determine if the packet is a packet of an encrypting flow and generate the flow identifier by hashing a source address, a destination address and a cryptographic protocol contained in the packets so as to provide the flow identifier if the packet is a packet of an encrypting flow.

35. The processing system of claim 33, wherein the packet-input demux is further configured to determine if the packet is a packet of a decrypting flow and generate the flow identifier by hashing a destination address, a security parameter index and a protocol contained in the packets so as to provide the flow identifier if the packet is a packet of a decrypting flow.

36. The processing system of claim 33, wherein the packet-input demux is configured to generate the flow identifier by hashing fields of a packet to provide the flow identifier.

37. The processing system of claim 36, wherein the packet-input demux is configured to hash fields of a packet by multiplying the fields of the packet by respective prime numbers to provide multiplied values, summing the multiplied values so as to provide a sum and determining a modulo 2ⁿ of the sum, wherein n is a number of bits in the resulting flow identifier.

38. The processing system of claim 36, wherein the packet-input demux is configured to hash fields of a packet by determining a modulo 2ⁿ of the fields to provide modulo values, wherein n is a number of bits in the resulting flow identifier, multiplying the modulo values by respective prime numbers to provide multiplied values and summing the multiplied values so as to provide a sum.

39. The processing system of claim 28, wherein the packet-output mux is configured to order the processed packets based on the sequence identifier of the packets by controlling timing of an output of each of the parallel packet transform processors processing a related packet based on an output sequence value associated with the related packets so as to admit outputs of the parallel packet transform processors processing related packets in a sequence corresponding to the ordering of the related packets.

40. The processing system of claim 39, wherein the packet-output mux is configured to control timing of the output by maintaining a current output sequence value associated with the related packets, determining if an output packet of one of the parallel processors has a sequence identifier corresponding to the current output sequence value and allowing the one of the parallel processors to output the output packet if the output packet has a sequence identifier corresponding to the current output sequence value.

41. The processing system of claim 40, wherein the packet-input demux is further configured to assign a flow identifier to related packets based on the evaluation of the packets, wherein the related packets comprise respective different related packets such that plurality of flow identifiers are assigned to the different related packets.

42. The processing system of claim 41, wherein the packet-output mux is further configured to control output of the parallel processors based on the flow identifier of a processed packet and a sequence identifier of a processed packet.

43. The processing system of claim 42, wherein the packet-output mux is configured to control output of the parallel processors based on the flow identifier of a processed packet by controlling the output of the parallel processors so as to assure that processed packets with different flow identifiers will have an opportunity to be output.

44. The processing system of claim 28, wherein the packet transform processors are cryptographic processors.

45. The processing system of claim 28, wherein the packet transform processors are compression processors.

46. A packet transformation processing system, comprising:

means for receiving packets;

means for assigning a sequence identifier to the packets, wherein the sequence identifier specifies a serial order associated with the packet;

means for providing the packets to a plurality of parallel packet transform processors;

means for processing the packets utilizing the packet transform processors so as to provide processed packets that have been transformed; and

means for ordering the processed packets based on the sequence identifier of the packets.

47. A system for processing of packets, comprising:

a plurality of parallel packet transform processors;

means for assigning a flow identifier to related packets;

means for assigning a sequence identifier to each packet of the related packets;

means for encapsulating the packet, the flow identifier and the sequence identifier to provide a packet-object;

means for providing the packet-object to one of the packet transform processor of the parallel packet transform processors;

means for processing the packet-object utilizing the one of the packet transform processors to provide a processed packet-object that has been transformed; and

means for selectively outputting the processed packet-object based on the flow identifier and the sequence identifier of the processed packet-object.

48. A computer program product of packet transformation processing, comprising:

a non-transitory computer readable medium having computer readable program code embodied therein, the computer readable program code comprising;

computer readable program code configured to receive packets;

computer readable program code configured to assign a sequence identifier to the packets, wherein the sequence identifier specifies a serial order associated with the packet;

computer readable program code configured to provide the packets to a plurality of parallel packet transform processors;

computer readable program code configured to process the packets utilizing the packet transform processors so as to provide processed packets that have been transformed; and

computer readable program code configured to order the processed packets based on the sequence identifier of the packets.

49. A computer program product for processing of packets utilizing a plurality of parallel packet transform processors, comprising:

a non-transitory computer readable medium having computer readable program code embodied therein, the computer readable program code comprising;

computer readable program code configured to assign a flow identifier to related packets;

computer readable program code configured to assign a sequence identifier to each packet of the related packets;

computer readable program code configured to encapsulate the packet, the flow identifier and the sequence identifier to provide a packet-object;

computer readable program code configured to provide the packet-object to one of the packet transform processor of the parallel packet transform processors;

computer readable program code configured to process the packet-object utilizing the one of the packet transform processors to provide a processed packet-object that has been transformed; and

computer readable program code configured to selectively output the processed packet-object based on the flow identifier and the sequence identifier of the processed packet-object.