Network thread scheduling

• US 7,054,950 B2
• Filed: 04/15/2002
• Issued: 05/30/2006
• Est. Priority Date: 04/15/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Putzolu, David M.
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): Taylor, Nicholas R.
• Application Number:
  US10/123,622
• Publication Number:
  US 20030195916A1
• Time in Patent Office: 1,506 Days
• Field of Search: 709/238
• US Class Current: 709/238
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections

Abstract

A method, system or product that identifies data packets with a common characteristic and routes all data packets having the same characteristic to the same thread of execution or device in a system which processes data packets in parallel.

Claims

1. A method comprising:

identifying a common characteristic for each data packet; and

routing data packets from one or more source hosts, which appear in an order in a series of data packets, to respective ones of a plurality of end hosts in a manner to preserve the order of at least some of the packets that are related by a common characteristic, wherein the routing comprises;

applying a first function to the data packets to produce a data packet identifier H for each data packet;

sending each data packet having a given data packet identifier to a same thread in a multi-threaded task; and

using function H Modulo K to identify the same thread for the given data packet, wherein K comprises a number of threads in the multi-threaded task.

2. The method of claim 1, wherein the first function comprises a mask, the method further comprising corresponding a number of bits of the mask to at least a maximum value of a number of threads used for any multi-threaded task in the routing.

3. The method of claim 2, further comprising storing each data packet identifier, wherein all threads are utilized for the multi-threaded task.

4. The method of claim 3, wherein each data packet identifier is stored as an addendum to each data packet.

5. The method of claim 1 wherein the common characteristic comprises an identity of the end host to which the packets are bound.

6. The method of claim 1 wherein the common characteristic comprises an identity of the source host from which the data packets are coming.

7. The method of claim 1 wherein the function applied to each data packet comprises a mask of at least one bit of a destination Internet Protocol address associated with each data packet.

8. The method of claim 1 wherein the first function applied to each data packet comprises a mask of at least one bit of the Destination Media Access Control (DMAC) address associated with each packet in an Ethernet-based network.

9. The method of claim 1 wherein the first function applied to each data packet comprises a hash of at least one bit of the label associated with each packet provided by a label edge router in a Multi-Protocol Label Switching-based network.

10. The method of claim 1 wherein the first function applied to each data packet comprises a hash of at least one bit of the Virtual Path Identifier (VPI) associated with each packet in a network using Asynchronous Transfer Mode (ATM) technology.

11. The method of claim 1 wherein the threads comprise microengines within a network processor.

12. The method of claim 1 wherein the threads comprise multiple application specific integrated circuits.

13. A method comprising:

receiving a sequence of data packets;

applying a first function to the data packets to generate a data packet identifier H that classifies the packets into groups such that a sequential order of packets in each of the groups is to be maintained;

using the classification information in a second function to assign each group to a thread in a multi-threaded task, wherein the second function comprises H Modulo K, and wherein K comprises a number of threads in the multi-threaded task; and

routing the data packets classified in a given group to the assigned thread.

14. The method of claim 13, wherein the multi-threaded task processes the data packets in each thread in parallel.

15. The method of claim 14, wherein the first function comprises a mask of a destination address associated with each packet.

16. The method of claim 14, wherein the first function comprises a hash of a source address associated with each packet.

17. The method of claim 13, wherein the classification information is stored as an addendum to each data packet.

18. The method of claim 14, wherein the threads comprise microengines of a network processor.

19. A system comprising:

a packet identifier for data packets configured to use a first function based on a common characteristic of the data packets to produce a data packet identifier H for each data packet;

a router configured to send each data packet having given packet identifier to a common thread for a multi-threaded task, wherein the router is further configured to use function H modulo K to assign each data package to the respective common thread, and wherein K comprises a number of threads in the multi-threaded task; and

a processor configured to simultaneously process data packets in at least two threads of the multi-threaded task.

20. The system of claim 19 wherein the processor comprises an application specific integrated circuit.

21. The system of claim 19 wherein the processor comprises a network processor.

22. The system of claim 19 wherein the products of the first function are to be stored on a computer readable medium.

23. The system of claim 20 wherein the packet identifier is hard wired into the application specific integrated circuit.

24. The system of claim 19, wherein the first function comprises a mask, and wherein a number of bits of the mask corresponds to at least a maximum value of a number of threads used for any multi-threaded task processed by the processor.

25. The system of claim 19, wherein the common characteristic comprises an identity of an end host to which the packets are bound.

26. The system of claim 19, wherein the common characteristic comprises an identity of a source from where the packets are coming.

27. A computer program product residing on a computer readable medium having instructions stored thereon that, when executed, cause a processor to:

identify a common characteristic for each data packet; and

route data packets from one or more source hosts, which appear in an order in a series of data packets, to respective ones of a plurality of end hosts in a manner to preserve the order of at least some of the packets that are related by a common characteristic, wherein the routing comprises;

applying a first function to the data packets to produce a data packet identifier H for each data packet;

sending each data packet having a given data packet identifier to a same thread in a multi-threaded task; and

using function H Modulo K to identify the same thread for the given data packet, wherein K comprises a number of threads in the multi-threaded task.

28. The computer program product of claim 27, further causing the processor to:

store the data packet identifier for each data packet.

29. The computer program product of claim 28, wherein the first function to produce a data packet identifier comprises a mask of at least one bit of information associated with each data packet.

30. The computer program of claim 29, wherein the mask comprises at least one bit of the destination Internet Protocol address of each packet.

31. The computer program of claim 29, wherein the mask comprises at least one bit of the Virtual Channel Identifier in a network using Asynchronous Mode Transfer technology.

32. The computer program product of claim 27, wherein the first function comprises a hash of at least one bit of information associated with each data packet.

33. The computer program product of claim 27 wherein the processor comprises a multi-threaded network processor.

34. The computer program product of claim 33 wherein the multi-threaded network processor comprises a plurality of application specific integrated circuits.