System and method for balancing TCP/IP/workload of multi-processor system based on hash buckets

• US 7,020,713 B1
• Filed: 10/10/2000
• Issued: 03/28/2006
• Est. Priority Date: 10/10/2000
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Shukla, Himanshu, Sarkar, Subrata, Shah, Vipul, Subramanian, Kumar, Agrawal, Alka, Rao, N.S.S. Narasimha
• Primary Examiner(s): Follansdee, John
• Assistant Examiner(s): Nguyen, Dustin
• Application Number:
  US09/685,657
• Time in Patent Office: 1,995 Days
• Field of Search: 709/245, 709/200, 709/235, 713/153, 718/105, 370/392, 707/103
• US Class Current: 709/235
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

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.

Claims

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.

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.

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.