Packet queuing, scheduling and ordering

• US 20060056406A1
• Filed: 12/06/2004
• Published: 03/16/2006
• Est. Priority Date: 09/10/2004
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Bouchard, Gregg A., Kessler, Richard E., Lee, Yen, Hummel, Thomas F., Hussain, Muhammed R.
• Granted Patent: US 7,895,431 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 63/164 at the network layer
• CPC Class Codes: H04L 63/166 at the transport layer

Abstract

A method and apparatus for ordering, synchronizing and scheduling work in a multi-core network services processor is provided. Each piece of work is identified by a tag that indicates how the work is to be synchronized and ordered. Throughput is increased by processing work having different tags in parallel on different processor cores. Packet processing can be broken up into different phases, each phase having a different tag dependent on ordering and synchronization constraints for the phase. A tag switch operation initiated by a core switches a tag dependent on the phase. A dedicated tag switch bus minimizes latency for the tag switch operation.

Claims

1. A network services processor comprising:

a plurality of independent processors, each processor operating in parallel to perform work; and

a work order module that dynamically schedules work to be performed in parallel by the processors based on a tag associated with the work such that execution of the work is ordered and synchronized.

2. The network services processor of claim 1, wherein the work to be executed by the processors is stored in an input queue.

3. The network services processor of claim 2, wherein the work order module further comprises:

a plurality of in-flight lists, each in-flight list associated with a different tag for tracking in-flight work associated with the tag, the work order module scheduling work stored on the input queue to an in-flight list dependent on the tag associated with the work.

4. The network services processor of claim 2, wherein the work order module further comprises:

a group identifier per processor, the group identifier indicating groups for which a processor will accept work, the work order module differentiating work on the input queue by groups, such that work is scheduled to a processor that accepts work from the group.

5. The network services processor of claim 2, wherein work in the input queue can be stored in the work order module or in memory external to the work order module.

6. The network services processor of claim 1 further comprising:

a timer, the timer controlling when work is added to the input queue.

7. The network services processor of claim 5, wherein the tag includes a tag type and the in-flight list stores work having an atomic tag type that indicates only work at the head of the list is executable by one of the plurality of processors.

8. The network services processor of claim 5, wherein the tag includes a tag type and the in-flight list stores work having an ordered tag type that indicates all work on the list is executable, work being removable only from the head of the list by one of the plurality of processors.

9. The network services processor of claim 1 further comprising:

a dedicated tag switch bus coupled between the processors and the work order module for transmitting an indication of completion of a tag switch operation by the packet work order module.

10. The network services processor of claim 9, wherein the core initiates a tag switch operation by executing a store instruction and upon detecting the store instruction, the packet work order module modifies the tag and moves the work to an in-flight queue associated with the modified tag.

11. The network services processor of claim 1, wherein the work is performing IPsec decryption.

12. The network services processor of claim 1, wherein the work is performing IPsec encryption.

13. The network services processor of claim 1, wherein the work is de-fragmentation of a Virtual Private Network packet.

14. The network services processor of claim 1, wherein the work is adjusting TCP sequence numbers.

15. The network services processor of claim 2, wherein each input queue has an assigned priority.

16. The network services processor of claim 2, wherein each input queue is assigned for storing a type of work.

17. The network services processor of claim 1, wherein at least one of the processors performs control plane processing and another one of the processors performs data plane processing.

18. A method for processing packets in a network services processor comprising:

processing work in parallel by a plurality of independent processors; and

dynamically scheduling work to be performed in parallel by the processors based on a tag associated with the work such that execution of the work is ordered and synchronized.

19. The method of claim 18, further comprising:

scheduling work stored on an input queue to one of a plurality of in-flight lists dependent on the tag associated with the work, each in-flight list associated with a different tag for tracking in-flight work associated with the tag.

20. The method of claim 19, further comprising:

differentiating work on the input queue by groups, such that work is scheduled to a processor that accepts work from the group, the group identifier indicating groups for which a processor will accept work.

21. The method of claim 19, wherein work in the input queue can be stored in a work order module or in memory external to the work order module.

22. The method of claim 18 further comprising:

controlling, by a timer when work is added to the input queue.

23. The method of claim 18, wherein the tag includes a tag type and the in-flight list stores work having an atomic tag type that indicates only work at the head of the list is executable by one of the plurality of processors.

24. The method of claim 18, wherein the tag includes a tag type and the in-flight list stores work having an ordered tag type that indicates all work on the list is executable, work being removable only from the head of the list by one of the plurality of processors.

25. The method of claim 18 further comprising:

transmitting an indication of completion of a tag switch operation by the packet work order module over a dedicated tag switch bus coupled between the processors and the work order module.

26. The method of claim 25, further comprising:

initiating a tag switch operation by executing a store instruction; and

upon detecting the store instruction, modifying the tag and moving the work to an in-flight queue associated with the modified tag.

27. The method of claim 18, wherein the work is performing IPsec decryption.

28. The method of claim 18, wherein the work is performing IPsec encryption.

29. The method of claim 18, wherein the work is de-fragmentation of a Virtual Private Network packet.

30. The method of claim 18, wherein the work is adjusting TCP sequence numbers.

31. The method of claim 19, wherein each input queue has an assigned priority.

32. The method of claim 19, wherein each input queue is assigned for storing a type of work.

33. The method of claim 19, wherein at least one of the processors performs control plane processing and another one of the processors performs data plane processing.

34. An apparatus for processing packets in a network services processor comprising:

means for processing work in parallel; and

means for dynamically scheduling work to be performed in parallel based on a tag associated with the work such that execution of the work is ordered and synchronized.