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 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, wherein the packet is assigned to a hash bucket based on a combination of a source address, a source port, a destination address, and a destination port parameters from the header section of the packet to identify the hash bucket; and
queuing the hash bucket to a processor so that the workloads of all the processors are balanced, wherein the queuing includes applying a queuing model to packets in the hash bucket to prevent packets from a particular connection from utilizing an excessive amount of the processor's time by distributing the hash buckets in proportion to an imbalance distribution index and in reverse proportion to a total imbalance index;
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. The method of claim 1 wherein the hash function is designed to assign a plurality of packets from a connection to the same hash bucket.
3. The method of claim 1 further comprising monitoring the workload of each processor involved in the system.
4. A method for processing a plurality of connections with a plurality of timer threads by a plurality of computer processors in a multiple processor computer system, the method comprising:
providing a plurality of hash buckets related to a hash function;
mapping a connection to one of the hash buckets, wherein the mapping is based on a combination of four parameters of the connection, the four parameters including a local address, a local port, a remote address, and a remote port, and wherein the one of the hash buckets is identified by the combination; and
assigning one or more hash buckets to a processor timer thread based on a workload thereof so that the processor only processes the connection mapped to the assigned hash buckets by distributing the hash buckets in proportion to an imbalance distribution index and in reverse proportion to a total imbalance index, wherein a plurality of timer threads for the computer processors thus process a plurality of connections simultaneously; and
for each of the hash buckets, applying a queuing model to packets in the hash bucket to prevent packets from a particular one of the connections from utilizing an excessive amount of the processor's time.
5. The method of claim 4 further comprising monitoring the workload of each processor.
6. A system for processing a plurality of connections with a plurality of timer threads by a plurality of computer processors in a multiple processor computer system, the system comprising:
a plurality of processors;
a plurality of hash buckets stored in storage means accessible by the processors and related to a predetermined hash function;
a parallelizer comprising instructions stored on a computer-readable medium and executable by one of the processors for mapping a connection to one of the hash buckets, wherein the mapping is based on a combination of four parameters of the connection, the four parameters including a local address, a local port, a remote address, and a remote port, and wherein the one of the hash buckets is identified by the combination; and
a load balancer comprising instructions stored on a computer-readable medium and executable by one of the processors for assigning a plurality of hash buckets to a processor timer thread based on a workload thereof so that the processor only processes the connection mapped to the assigned hash buckets, wherein a plurality of timer threads for the computer processors thus process a plurality of connections simultaneously;
wherein for each of the hash buckets, a queuing model is applied to packets in the hash bucket to prevent packets from a particular connection from utilizing an excessive amount of the processor's time by distributing the hash buckets in proportion to an imbalance distribution index and in reverse proportion to a total imbalance index.
7. The system of claim 6 wherein the load balancer further monitors the workload of the each of the processors.