System, device and method for scheduling information processing with load-balancing
View Patent ↗Packets are spread among a number of packet processors with load-balancing. The incoming packets are logically divided into a number of packet flows, where the number of packet flows is greater than the number of packet processors. Each packet flow is assigned to a particular packet processor. When a packet is received, the packet flow for the packet is determined, and the packet is queued for the packet processor associated with the flow based upon a predetermined queuing scheme. The mapping of packet flows to packet processors is not fixed, but rather is dynamically updated based upon the amount of data associated with each packet flow and each packet processor.
1. A method for scheduling information processing using load balancing, the method comprising:
associating each of a number of information units with one of a number of flows;
assigning each of the number of flows to one of a number of processors, wherein the number of flows is greater than the number of processors, and wherein the assignment of each of the number of flows to one of the number of processors substantially balances the information processing load among the number of processors; and
dynamically allocating each information unit to, including indexing into a flow table using a flow number of the flow to obtain a flow table entry, obtaining a processor identifier from the flow table entry and allocating the information unit to the processor associated with the process identifier, wherein processor identifiers stored in the flow table based upon the an amount of data associated with each of the number of flows and each of the number of processors.
2. The method of claim 1 , wherein assigning each of the number of flows to one of a number of processors comprises:
maintaining the flow table, the flow table having a flow table entry for each flow; and
storing in each flow table entry a processor identifier for the corresponding flow.
3. The method of claim 1 , wherein dynamically allocating each information unit to a processor comprises:
receiving an information unit;
determining the flow associated with the information unit; and
determining the processor associated with the flow responsive to the flow table entry.
4. The method of claim 3 , wherein determining the flow associated with the information unit comprises:
determining a flow for the information unit based upon the contents of the information unit using a predetermined scheme.
5. The method of claim 4 , wherein the contents of the information unit comprise addressing information.
6. The method of claim 4 , wherein the predetermined scheme comprises a hashing function.
7. The method of claim 3 , further comprising:
updating statistics for the flow based upon an information unit size.
8. The method of claim 7 , further comprising:
dynamically updating the assignment of flows to processors based upon updated statistics for the flows.
9. A method for scheduling information processing using load balancing, the method comprising:
associating each of a number of information units with one of a number of flows;
assigning each of the number of flows to one of a number of processors, wherein the number of flows is greater than the number of processors, and wherein the assignment of each of the number of flows to one of the number of processors substantially balances the information processing load among the number of processors; and
allocating each information unit to a processor based upon the flow associated with the information unit and the processor associated with the flow by determining a flow associated with each information unit, determining the processor associated with the flow; indexing into a flow table using a flow number of the flow to obtain a flow table entry, obtaining a processor identifier from the flow table entry and allocating the information unit to the processor associated with the process identifier.
10. A method for scheduling information processing using load balancing, the method comprising:
associating each of a number of information units with one of a number of flows;
assigning each of the number of flows to one of a number of processors, wherein the number of flows is greater than the number of processors, and wherein the assignment of each of the number of flows to one of the number of processors substantially balances the information processing load among the number of processors; and
allocating each information unit to a processor associated with the flow by
determining a priority for the information unit;
determining an amount of data in a queue associated with the processor;
queuing the information unit for the processor, if the priority for the information unit is within a set of acceptable priorities for the amount of data in the queue; and
dropping the information unit without queuing the information unit for the processor, if the priority for the information unit is not within a set of acceptable priorities for the amount of data in the queue.
11. The method of claim 10 , wherein determining a priority for the information unit comprises:
determining the priority for the information unit based upon the contents of the information unit and a quality-of-service table.
12. An apparatus comprising:
an interface over which information units are received;
a number of processors for processing information units; and
scheduling logic for dynamically allocating each information unit to a processor, wherein the scheduling logic is operably coupled to receive an information unit over the interface, determine a flow associated with the information unit by indexing into a flow table using a flow number of the flow to obtain a flow table entry comprising a processor identifier, determine a processor associated with the flow using the processor identifier from the flow table entry, and allocate the information unit to the processor identified by the processor identifier, wherein the processor identifiers are stored in the flow table entry responsive to an amount of data associated with each of the plurality of flows and at the plurality of processors.
13. The apparatus of claim 12 , wherein the scheduling logic is operably coupled to determine the flow associated with the information based upon the contents of the information unit according to a predetermined scheme.
14. The apparatus of claim 13 , wherein the contents of the information unit comprise addressing information.
15. The apparatus of claim 13 , wherein the predetermined scheme comprises a hashing function.
16. The apparatus of claim 12 , wherein the scheduling logic is operably coupled to update statistics for the flow based upon an information unit size.
17. An apparatus comprising:
an interface over which information units are received;
a number of processors for processing information units; and
scheduling logic for allocating each information unit to a processor, wherein the scheduling logic is operably coupled to receive an information unit over the interface, determine a flow associated with the information unit, determine a processor associated with the flow, and allocate the information unit to the processor associated with the flow;
wherein the scheduling logic is operably coupled to determine a priority for the information unit, determine an amount of data in a queue associated with the processor, queue the information unit for the processor, if the priority for the information unit is within a set of acceptable priorities for the amount of data in the queue, and drop the information unit without queuing the information unit for the processor, if the priority for the information unit is not within a set of acceptable priorities for the amount of data in the queue.
18. The apparatus of claim 17 , wherein the scheduling logic is operably coupled to determine a priority for the information unit based upon the contents of the information unit and a quality-of-service table.
19. A system for scheduling comprising:
means for associating each of a number of information units with one of a number of flows;
means for dynamically assigning each of the number of flows to one of a number of processors, wherein the number of flows is greater than the number of processors, and wherein the assignment of each of the number of flows to one of the number of processors substantially balances the information processing load among the number of processors by periodically assigning flows to processors responsive to an amount of data associated with each of the number of flows and at each of the number of processors, wherein the processors are assigned to flows using a flow table comprising a plurality of flow table entries, each flow table entry comprising a processor identifier, the flow table being indexed by a flow number associated with a received information unit to provide a flow table entry comprising a processor identifier identifying a processor associated with the flow; and
means for allocating each information unit to a processor based upon the flow associated with the information unit and the processor associated with the flow.
20. The system of claim 19 , further comprising:
means for updating statistics for the flow based upon an information unit size.
21. The system of claim 20 , further comprising:
means for dynamically updating the assignment of flows to processors based upon updated statistics for the flows.