Packet ordering system using an atomic ticket release command of a transactional memory

• US 9,641,448 B1
• Filed: 01/31/2015
• Issued: 05/02/2017
• Est. Priority Date: 01/31/2015
• Status: Active Grant

• Current Assignee: Netronome Systems Incorporated
• Original Assignee: Netronome Systems Incorporated
• Inventors: Telfer, Christopher A.
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): Solinsky, Peter G
• Application Number:
  US14/611,231
• Time in Patent Office: 822 Days
• Field of Search: 370394
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 47/624 Altering the ordering of packets in an individual queue

Abstract

An Island-Based Network Flow Processor (IB-NFP) receives packets of many flows, and classifies them as belonging to an ordering context. These packets are distributed to a set of Worker Processors (WPs), so that each packet of the context is processed by one WP, but multiple WPs operate on packets of the context at a given time. The WPs use an atomic ticket release functionality of a transactional memory to assist in determining when to release packets to another set of Output Processors (OP). The packets are indicated to the set of OPs in the correct order, even though the WPs may complete their processing of the packets in an out-of-order fashion. For a packet that is indicated as to be released, an OP generates a “transmit command” such that the packet (or a descriptor of the packet) is then put into a properly ordered stream for output from the IB-NFP.

Claims

1. A method comprising:

(a) receiving packets of a plurality of flows onto an integrated circuit;

(b) assigning the packets of some but not all of the flows to an ordering context, wherein each packet of the ordering context is assigned a corresponding ordering sequence number, wherein the ordering sequence number is not a part of the packet as the packet is received in (a) onto the integrated circuit;

(c) maintaining a ticket release bitmap in a transactional memory;

(d) using the ticket release bitmap to track which packets of the ordering context have been flagged for future release by an ordering system but have not yet been released from the ordering system; and

(e) using a plurality of processors to perform application layer processing on the packets, wherein each processor further executes a corresponding amount of ordering system code, wherein each packet of the ordering context is processed by one of the processors as a result of execution of the amount of ordering system code such that after the application layer processing of the packet the processor issues an atomic ticket release command to the transactional memory thereby accessing the ticket release bitmap and such that the processor receives information in return back from the transactional memory, wherein the ordering system includes;

     1) a plurality of ticket release bitmaps, one of which is the ticket release bitmap of (d), and

     2) the amount of ordering system code executing on each processor of the plurality of processors, and wherein the transactional memory and the plurality of processors are parts of the integrated circuit.

2. The method of claim 1, wherein multiple ones of the processors perform application layer processing on packets of the ordering context, the method further comprising:

(f) outputting release messages from the multiple processors, wherein each release message indicates that one or more packets of the ordering context is to be released, wherein the release messages indicate packets to be released such that the packets are released in sequential order in accordance with their ordering sequence numbers, and wherein a packet is only indicated to be released by one of the release messages if the application layer processing of (e) has been completed on the packet.

3. The method of claim 1, wherein the ticket release bitmap of (c) includes a plurality of flag bits, wherein there is one flag bit of the plurality of flag bits for each corresponding ordering sequence number of the ordering context.

4. The method of claim 3, wherein there is a next sequence number expected value for the ordering context, and wherein the bitmap of (c) further includes a value indicative of the next sequence number expected value of the ordering context.

5. The method of claim 1, wherein the atomic ticket release command issued by the processor in (e) includes an ordering sequence number.

6. A method involving a plurality of packets of an ordering context, wherein each packet of the ordering context has an ordering sequence number, the method comprising:

(a) using a ticket release bitmap in a packet ordering system to track which packets of the ordering context of packets have been flagged for future release but have not yet been released, wherein the ticket release bitmap includes a flag bit for each ordering sequence number in the ordering context, and wherein the ticket release bitmap is maintained in one or more transactional memories.

7. The method of claim 6, wherein the using in (a) of the ticket release bitmap involves supplying atomic ticket release commands to the one or more transactional memories such that the one or more transactional memories access the ticket release bitmap.

8. The method of claim 7, further comprising:

(b) assigning ordering sequence numbers to the plurality of packets of the ordering context, wherein the packets of the ordering context are received onto an integrated circuit, wherein the one or more transactional memories are parts of the integrated circuit, and wherein none of the packets includes any of the assigned ordering sequence numbers upon being received onto the integrated circuit.

9. The method of claim 8, further comprising:

(c) outputting one or more release messages, wherein each release message indicates one or more of the packets of the ordering context that are to be released, wherein the release messages are output such that the packets of the ordering context are indicated to be released in sequential order in accordance with their ordering sequence numbers.

10. The method of claim 9, wherein a packet is only indicated to be released by a release message if an amount of application layer processing has first been performed on the packet after the assigning of ordering sequence numbers.

11. The method of claim 8, wherein the ordering context has an associated next sequence number expected value, and wherein the ticket release bitmap stores an indication of the next sequence number expected value.

12. The method of claim 11, wherein the packet ordering system indicates packets to be released, and wherein the atomic ticket release command updates the indicated next sequence number expected value as the packet ordering system indicates packets are to be released.

13. The method of claim 8, wherein each atomic ticket release command supplied to the one or more transactional memories includes an ordering sequence number.

14. The method of claim 8, wherein each atomic ticket release command supplied to the one or more transactional memories includes an ordering sequence number and an identification of a ticket release bitmap.

15. The method of claim 6, further comprising:

storing a second ticket release bitmap in the one or more transactional memories, wherein the second ticket release bitmap is used by the packet ordering system to track which packets of a second ordering context have been flagged for future release but have not yet been released.

16. The method of claim 6, wherein a packet is flagged for future release by supplying an atomic ticket release command to the one or more transactional memories, wherein the atomic ticket release command includes the ordering sequence number of the packet to be flagged.

17. A packet ordering system for ordering packets of an ordering context, wherein each packet of the ordering context has an ordering sequence number, the packet ordering system comprising:

a transactional memory that stores a ticket release bitmap, wherein the ticket release bitmap tracks which packets of the ordering context have been flagged for future release but have not yet been released from the packet ordering system, wherein the ticket release bitmap includes a flag bit for each ordering sequence number in the ordering context; and

means for;

     1) supplying atomic ticket release commands to the transactional memory, wherein each atomic ticket release command includes an ordering sequence number.

18. The packet ordering system of claim 17, wherein the means is also for:

2) receiving data back from the transactional memory in response to the atomic ticket release commands, and

     3) generating release messages, wherein each release message generated by the means indicates one or more of the packets of the ordering context that is/are to be released, wherein the release messages are generated such that the packets of the ordering context are indicated to be released in sequential order in accordance with their ordering sequence numbers.

19. The packet ordering system of claim 18, wherein the means comprises a plurality of processors, and wherein the packet ordering system is embodied in a network flow processor integrated circuit.

20. The packet ordering system of claim 18, wherein the transactional memory also stores a second ticket release bitmap, wherein the second ticket release bitmap tracks which packets of a second ordering context have been flagged for future release but have not yet been released from the packet ordering system.