System and method for balancing TCP/IP/workload of multi-processor system based on hash buckets
View Patent ↗A method and system is provided for balancing work load for a plurality of computer processors in a multiple processor computer system. In such a system, there are a plurality of packets to be processed. First, a plurality of hash buckets are generated and each packet is assigned to a bucket by performing a predetermined hash function. The different hash buckets are then assigned to the processors based on the workload of all the processors. In connection with processing connections with a timer thread, a plurality of connections are processed with a plurality of timer threads. A plurality of hash buckets are provided, and each connection is mapped to one of the hash buckets. Further, each hash bucket is assigned to a processor timer thread based on a workload thereof.
1. A method for balancing a workload for a plurality of processors in a multiple processor computer system, the system designed for processing a plurality of packets from a plurality of connections, the method comprising:
assigning a packet to a hash bucket determined by performing a predetermined hash function; and
queuing the hash bucket to a processor so that the workload of all the processors are balanced, wherein the queuing includes
identifying statistically a percentage of capacity usage for each processor;
obtaining an imbalance distribution index for each processor from the identified percentage of capacity usage; and
distributing the hash buckets in proportion to the imbalance distribution index and in reverse proportion to a total imbalance index, wherein the total imbalance index is a summation of all obtained imbalance distribution indexes,
wherein the hash function relates to a predetermined number of hash buckets, and wherein a plurality of packets from different connections can be assigned to the same hash bucket.
2. A computer program for balancing workload for a plurality of processors in a multiple processor computer system, the system designed for processing a plurality of packets from a plurality of connections, the computer program stored on a computer readable medium:
means for calculating a number of hash buckets to assign to a processor based on a ratio of an imbalance index of the processor and a total imbalance index, wherein the processor's imbalance index is based on a utilization rate of the processor and the system, and wherein the total imbalance index is based on the imbalance index of each processor;
means for assigning a packet to a hash bucket determined by performing a predetermined hash function; and
means for queuing the hash bucket to a processor so that the workload of all the processors are balanced,
wherein the hash function has a predetermined number of hash buckets, and wherein a plurality of packets from different connections can be assigned to the same hash bucket.
3. The computer program of claim 2 wherein the means for assigning includes means for using a source address, source port, destination address, and destination port parameters from the header section of the packet to identify the hash bucket.
4. The computer program of claim 2 wherein the hash function is designed to assign a plurality of packets from a connection to the same hash bucket.
5. The computer program of claim 2 further comprising means for monitoring the workload of each processor involved in the system.
6. A computer program for balancing workload for a plurality of processors in a multiple processor computer system, the system designed for processing a plurality of packets from a plurality of connections, the computer program stored on a computer readable medium:
means for assigning a packet to a hash bucket determined by performing a predetermined hash function; and
means for queuing the hash bucket to a processor so that the workload of all the processors are balanced, wherein the means for queuing includes
identifying statistically a percentage of capacity usage for each processor;
obtaining an imbalance distribution index for each processor from the identified percentage of capacity usage; and
distributing the hash buckets in proportion to the imbalance distribution index and in reverse proportion to a total imbalance index, wherein the total imbalance index is a summation of all obtained imbalance distribution indexes,
wherein the hash function has a predetermined number of hash buckets, and wherein a plurality of packets from different connections can be assigned to the same hash bucket.
7. The computer program of claim 2 wherein the means for queuing further includes means for applying a queuing model for packets in the hash bucket to assure that packets from a particular connection do not unduly occupy the processor for an undesirable time period.