High data rate stateful protocol processing

• US 20040024894A1
• Filed: 08/02/2002
• Published: 02/05/2004
• Est. Priority Date: 08/02/2002
• Status: Active Grant

• Current Assignee: Ikanos Communications Incorporated (Qualcomm, Inc.)
• Original Assignee: Astute Networks, Inc.
• Inventors: Osman, Fazil Ismet, Knee, Simon John
• Granted Patent: US 8,015,303 B2
• Time in Patent Office: Days
• US Class Current: 709/230
• CPC Class Codes: H04L 69/10 Streamlined, light-weight or high-speed protocols, e.g. express transfer protocol [XTP] or byte stream
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols

Abstract

A method, system, and apparatus for processing messages according to one or more stateful protocols in a data communication system. Messages belonging to various communication flows (such as TCP transport layer “connections”) are processed according to a selected stateful protocol. Messages belonging to a single unified flow are distributed among different protocol processing cores (PPCs) at different times. Assignment of flows to PPCs is typically modifiable at the level of specific individual flows, permitting flexible load balancing between PPCs. The architecture of the system facilitates the method by providing a mix of pipelined and parallel processing structures.

Claims

1. A method of processing data in a stateful protocol processing system (“

SPPS”

) that processes a multiplicity of flows of messages, each flow being associated with a uniquely corresponding flow identification (“

FID”

) that is conveyed by messages belonging to such flow, the method comprising;

a) receiving a plurality of messages belonging to a particular flow;

b) deriving SPPS events associated with the particular flow from the received messages;

c) specifically assigning a first protocol processing core (“

PPC”

) to process one or more events of the particular flow in accordance with a stateful protocol (SP) of the particular flow; and

d) specifically assigning a different second PPC to process one or more other events of the particular flow in accordance with the SP of the particular flow.

2. The method of claim 1, wherein assigning PPCs in steps c) and d) further comprises following an algorithm to balance loading between different PPCs.

3. The method of claim 2, wherein the algorithm to balance loading between different PPCs includes round-robin distribution among a set of PPCs.

4. The method of claim 2, further comprising:

e) storing some number of events in a local queue for each PPC; and

f) identifying a low-load PPC within a relevant group of PPCs that has less events stored in the local queue of the low-load PPC than are stored in the queue of a different PPC within the relevant group; and

wherein

g) the algorithm to balance loading between different PPCs includes assigning the low-load PPC to process an event of a flow that has no events presently assigned to a PPC.

5. The method of claim 1, further comprising:

e) assigning events of a combination of different flows concurrently to the first PPC; and

f) assigning subsequent events of one of the combination of different flows to the second PPC while the first PPC continues to process events of another of the combination of different flows.

6. The method of claim 1, further comprising:

e) assigning events of a combination of different flows concurrently to the first PPC; and

f) explicitly releasing the assignment of the first PPC to process events of one of the combination of different flows while the first PPC continues to be assigned to process events of another of the combination of different flows.

7. The method of claim 1, further comprising:

e) receiving a message of an unassigned flow for which event processing is presently assigned to no PPC, the unassigned flow having a corresponding FID;

f) identifying a plurality of compatible PPCs that are configured to process events of a general type of events of the unassigned flow; and

g) selecting a PPC to process one or more events of the unassigned flow from among the compatible PPCs without regard to the FID corresponding to the unassigned flow.

8. The method of claim 1, further comprising:

e) receiving a message of an unassigned flow for which event processing is presently assigned to no PPC; and

f) selecting a PPC to process one or more events of the unassigned flow from among a plurality of PPCs compatible with such events without regard to FIDs of flows presently queued to be processed by the plurality of compatible PPCs.

9. The method of claim 1, further comprising explicitly determining whether a particular event belongs to a flow for which a PPC is presently assigned before selecting a PPC to process the particular event.

10. The method of claim 9, further comprising processing all incoming events that will affect a state of a corresponding flow through a previously selected PPC if the previously selected PPC is determined to be presently assigned to the corresponding flow.

11. The method of claim 9, further comprising releasing a previous assignment of a PPC to process events of a particular flow without regard to the FID of any flow.

12. The method of claim 1, further comprising releasing a previous assignment of a PPC to process events of a first flow based on an indication that no events that are relevant to affect a state of the first flow are presently being processed.

13. The method of claim 12, wherein the indication that no relevant events of the first flow are presently being processed is based on a counter that counts introduction and completion of relevant events of the first flow.

14. The method of claim 1, further comprising determining a type for an event before selecting a PPC to process the event.

15. The method of claim 1, further comprising:

e) determining event type prior to selecting a PPC for a number of events derived from received messages belonging to various flows, a multiplicity of distinct event types being determined including at least;

i) good events of a flow employing a first stateful protocol (“

SP”

);

ii) good events of a flow employing a different second SP; and

iii) events of a flow employing the first SP that are determined to have errors.

16. The method of claim 15, wherein the distinct event types determined further include iv) packet fragments.

17. The method of claim 1, further comprising recirculating information encapsulated in a first message for stateful protocol processing within the SPPS as a second stateful protocol message.

18. A method of processing data in a data communication stateful protocol processing system that processes a multiplicity of flows of data communication messages, each flow being associated with a uniquely corresponding flow identification (“

FID”

) that is conveyed by messages belonging to such flow, the method comprising;

a) receiving messages belonging to a particular flow and messages belonging to other flows;

b) deriving events from the received messages that are associated with the flow indicated by the FID of the message from which they are derived, including events associated with the particular flow and events associated with the other flows;

c) placing each event in one of a group of one or more preliminary processing queues;

d) assigning a first protocol processor core (“

PPC”

) to process a first event of the particular flow without regard to the preliminary processing queue in which the first event is located, and subsequently transferring the first event to a local queue of the assigned first PPC; and

e) assigning a different second PPC to process a different second event of the particular flow without regard to the preliminary processing queue in which the second event is located, and subsequently transferring the second event to a local queue of the assigned second PPC.

19. The method of claim 18, wherein the first and second PPCs are substantially dedicated to performing stateful protocol message processing.

20. The method of claim 18, wherein step b) further comprises substantially excluding payload data of the received messages from the derived events.

21. The method of claim 20, wherein step b) further comprises disposing an indication of event type in events that do not include an event type indication.

22. The method of claim 18, further comprising f) validating integrity of events prior to transferring the events to PPCs.

23. The method of claim 18, further comprising performing step b) in a packet processor that is physically distinct from all stateful protocol PPCs.

24. The method of claim 23, further comprising f) determining a local proxy ID for an event of a flow that is not presently assigned for processing by a PPC, via acts of a lookup processor that performs program steps that are not performed by the packet processor and are not performed by the PPCs.

25. The method of claim 24, further comprising f) accessing a flowstate at a memory address dependent upon the local proxy ID, the flowstate having been previously stored for the flow that is not presently assigned for processing by a PPC.

26. The method of claim 18, further comprising f) determining a local flow proxy ID, at least for events belonging to flows that are not presently assigned for processing by a particular PPC, via actions of dedicated lookup hardware.

27. The method of claim 26, wherein the dedicated lookup hardware includes a microprocessor.

28. The method of claim 18, further comprising:

f) maintaining data of the first event and associated flowstate data in a first memory uniquely associated with the first PPC; and

g) concurrently maintaining data of an event of a different flow and a corresponding flowstate of the different flow in a memory that is accessible by a different PPC without regard to access of the first memory by the first PPC.

29. The method of claim 28, further comprising maintaining both event data and corresponding flowstate data in memory local to a PPC assigned to process such event until processing of such event by the assigned PPC is completed.

30. The method of claim 18, further comprising assigning PPCs to process events based upon an algorithm for balancing loading between different PPCs.

31. A method of processing data in a stateful protocol processing system (“

SPPS”

) that processes a multiplicity of flows of messages, each flow being associated with a uniquely corresponding flow identification (“

FID”

) that is conveyed by messages belonging to such flow, the method comprising;

a) steps to effect receipt of a plurality of messages belonging to a particular flow;

b) steps to define events based upon the received messages;

c) steps to effect assignment of a first event of a particular flow to a first protocol processor core (“

PPC”

) for stateful protocol (“

SP”

) processing; and

d) steps to effect assignment of a second event of the particular flow to a different second PPC for SP processing.

32. The method of claim 31, further comprising steps to determine whether any PPC is presently processing an event of a flow associated with the FID of a new event.

33. The method of claim 31, further comprising steps to determine when processing has been completed for all present events associated with a particular FID.

34. A system for terminating a data communication transport layer, comprising:

a) a message receiver module configured to

i) receive numerous data communication messages, each such message associated with a flow uniquely identified by a flow identification (“

FID”

) of such message, and

ii) derive events from the received messages, each event associated with the flow associated with the message from which it is derived;

b) a plurality of protocol processor core (“

PPC”

) modules configured to process events in accordance with a stateful protocol of the flow of the event; and

c) an event dispatching module for dispatching events among the plurality of PPC modules, the event dispatching module configured to;

iv) receive events from the message receiver module;

v) determine, for each received event, whether a PPC module is presently assigned to process events of the flow of the received event; and

vi) select, from among a plurality of compatible PPC modules without regard to the FID of the flow of a particular received event, a PPC module to process a received event that was determined in step ii) to have no PPC module presently assigned for processing.

35. The system of claim 34, wherein the event dispatching module further comprises a lookup submodule configured to determine local proxy identification for flows of received events determined in step ii) to have no PPC module presently assigned for processing.

36. The system of claim 34, wherein the event dispatching module further comprises

d) an event-tracking submodule configured to

i) store flow processing status information regarding events dispatched to PPC modules so as to determine whether a PPC module is presently assigned to process events of particular flows.

37. The system of claim 36, wherein (d) the event-tracking submodule is further configured to

ii) retain a count of events according to the flow of the event, and to

iii) increase the count of a particular flow when an event of the particular flow is dispatched to a PPC module assigned to the flow, and

iv) reduce the count of the particular flow upon indication that the assigned PPC module has completed processing an event of the particular flow.

38. The system of claim 34, further comprising e) a scratchpad memory configured to store payload data of messages that is separated from events derived from the messages.

39. The system of claim 34, further comprising e) a message output processing module configured to assemble an output message according to instructions from a PPC module processing a flow of the output message.

40. The system of claim 34, wherein the message receiver module further comprises a processor configured to establish an event type field within events.

41. An apparatus for processing messages according to a data communication stateful protocol, the apparatus comprising:

a) means for receiving messages from a physical layer;

b) a plurality of means for stateful protocol (SP) processing of information of a particular communication flow;

c) means for selecting one among the plurality of SP processing means to process information of the particular communication flow so as to balance processor loading irrespective of flow identification (“

FID”

) data provided in messages of the particular communication flow.

42. The apparatus of claim 41, wherein the

c) means for selecting comprises

i) means for assigning a specific SP processing means for processing information of the particular communication flow, and

ii) means for releasing the assigned SP processing means from processing information of the particular communication flow without a need to release the assigned SP processing means from processing information of any other communication flow.

43. The apparatus of claim 42, further comprising d) means for deriving events of corresponding flows from received messages of such corresponding flows.

44. The apparatus of claim 43, wherein the c) means for selecting further comprises means to determine when processing is completed for all events of a flow that have been transferred to an assigned SP processing means.

45. A stateful protocol processing apparatus, comprising:

a) more than one protocol processing core (“

PPC”

) microprocessor, each PPC microprocessor including;

i) local memory sufficient to substantially store a flowstate that is accessible by the PPC without interference to other PPCs, and

ii) program memory configured to contain instruction code, during operation of the apparatus, sufficient to cause the microprocessor to process a received data message in accordance with an appropriate stateful protocol (SP), including updating an associated flowstate stored in local memory in response to state-relevant information in the received data message; and

b) a dispatcher including an input for receiving data messages, and processing circuitry that is configured, at least during operation of the apparatus, to

iv) forward information of a first received data message associated with a particular flow to a first PPC for SP processing, and

v) forward information of at least a different second message associated with the particular flow to a different second PPC for SP processing.

46. The apparatus of claim 45, wherein each PPC further comprises dual-port local memory.

47. A method within a data communication system for distributing communication events belonging to corresponding communication flows among a plurality of compatible protocol processors, the method comprising:

a) receiving a first event belonging to a first flow in a queue for distribution;

b) selecting a first protocol processor to process the first event from among a plurality of protocol processors that are compatible with the first event;

c) transferring the first event from the queue to the first protocol processor;

d) transferring other events belonging to other flows from the queue to the first protocol processor;

e) receiving a second event belonging to the particular flow in the queue;

f) selecting a different second protocol processor to process the second event from among the plurality of compatible protocol processors; and

g) transferring the second event from the queue to the second protocol processor while the first protocol processor continues to process other events from the queue.

48. The method of claim 47, further comprising releasing the first protocol processor from processing events of the first flow in response to completion by the first protocol processor of all events of the first flow that have been transferred to the first protocol processor.

49. The method of claim 47, further comprising:

h) receiving, after step c) and before the first protocol processor has completed processing the first event, a third event of the particular flow; and

i) consequently selecting the first protocol processor to process the third event of the particular flow.