Modified round robin load balancing technique based on IP identifier

• US 7,469,295 B1
• Filed: 06/25/2001
• Issued: 12/23/2008
• Est. Priority Date: 06/25/2001
• Status: Expired due to Term

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Gangadharan, SushilKumar
• Primary Examiner(s): Nguyen; Dustin
• Application Number:
  US09/888,677
• Time in Patent Office: 2,738 Days
• Field of Search: 709/232, 709/250, 709/228, 709/238, 709/224, 709/245, 709/237, 370/229, 370/402, 370/310, 370/392, 370/230, 370/395, 370/469, 370/472, 370/401, 370/395.32, 370/230.1, 370/238, 718/105, 713/201
• US Class Current: 709/232
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/326 in the transport layer [OSI layer 4] H04L69/16 takes precedence
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A load balancing technique uniformly distributes data transmitted by a server over a plurality of underlying physical links of a virtual interface or aggregate within a computer network. According to the invention, the unit of data granularity is preferably a datagram, rather than an Internet protocol (IP) fragment or packet. The load balancing technique implements a round robin scheduling policy among the links based on an identifier (ID) associated with each datagram. As a result, the technique ensures that all fragments of a datagram are forwarded over the same physical link of the aggregate on the basis of a similar IP ID.

Claims

1. A method for uniformly distributing data transmitted by a server over a plurality of underlying links of an aggregate within a computer network, comprising:

defining a unit of data as a datagram;

apportioning each datagram into at least one fragment at the server;

associating each fragment to an underlying link of the aggregate on the basis of an Internet protocol (IP) identifier (ID) of each datagram and a number of active links of the aggregate, wherein the step of associating includes;

logically combining the IP ID with a predetermined mask to produce a quantity,

right shifting the quantity a predetermined number of places,

establishing a threshold at which a group of data is forwarded to each underlying link of the aggregate,

producing a result representing a remainder upon dividing the right shifted logically combined quantity IP ID and predetermined mask by the number of active links, wherein the IP ID is a 16-bit value, the predetermined mask is 0xFF80 and predetermined number of right shifted places is 7, and wherein the group of data comprises 128 IP IDs;

transmitting the fragment over its associated underlying link from the server to the computer network.

2. The method of claim 1 wherein the step of associating further comprises producing a result representing a remainder upon dividing the IP ID by the number of active links.

3. The method of claim 1 wherein the group of data comprises one of 128 different transport control protocol (TCP) fragments and 128 different user datagram protocol (UDP) datagrams.

4. The method of claim 3 wherein each UDP datagram comprises up to 23 fragments.

5. The method of claim 1 further comprising:

loading at least one data buffer of the server with the at least one fragment;

fetching the fragment from the data buffer; and

loading at least one queue of the server with the fragment, the queue associated with the underlying link.

6. The method of claim 1 wherein the step of associating further comprises apportioning data equally over the plurality of underlying links of the aggregate within the computer network.

7. A computer readable medium, comprising:

the medium storing executable program instructions for uniformly distributing data transmitted by a server over a plurality of underlying links of an aggregate within a computer network, the executable program instructions having program instructions for;

defining a unit of data as a datagram;

apportioning each datagram into at least one fragment at the server;

associating each fragment to an underlying link of the aggregate on the basis of an Internet protocol (IP) identifier (ID) of each datagram and a number of active links of the aggregate, wherein the step of associating includes;

logically combining the IP ID with a predetermined mask to produce a quantity,

right shifting the quantity a predetermined number of places,

establishing a threshold at which a group of data is forwarded to each underlying link of the aggregate,

producing a result representing a remainder upon dividing the right shifted logically combined quantity IP ID and predetermined mask by the number of active links, wherein the IP ID is a 16-bit value, the predetermined mask is 0xFF80 and predetermined number of right shifted places is 7, and wherein the group of data comprises 128 IP IDs;

transmitting the fragment over its associated underlying link from the server to the computer network.

8. The computer readable medium of claim 7 wherein the program instruction for associating comprises a program instruction for producing a result representing a remainder upon dividing the IP ID by the number of active links.

9. The computer readable medium of claim 8 wherein the program instruction for associating further comprises program instructions for:

calculating the IP ID of each datagram in a sequential manner; and

rotating the fragments of each datagram among all the underlying links to thereby ensure that all fragments having the same IP ID are provided to the same physical link of the aggregate.

10. The computer readable medium of claim 7 wherein the program instruction for associating further comprises program instructions for:

logically combining the IP ID with a predetermined mask to produce a quantity;

right shifting the quantity a predetermined number of places; and

establishing a threshold at which a group of data is forwarded to each underlying link of the aggregate.

11. The computer readable medium of claim 10 wherein the program instruction for associating further comprises the program instruction for producing a result representing a remainder upon dividing the right shifted logically combined quantity IP ID and predetermined mask by the number of active links.

12. A method for uniformly distributing data transmitted by a server over a number of underlying links of an aggregate within a computer network, comprising:

providing the plurality of links as a connection to a network node;

selecting one link of the plurality of links for transmitting a datagram to the network node (hereinafter the selected link) using a round robin selection technique, the data identified by an Internet protocol (IP) identifier (ID), the IP ID indicating an end point destination for the data;

apportioning the datagram into at least one fragment;

performing a logical AND operation to combine the IP ID and a predetermined mask, wherein the predetermined mask is 0xFF80;

dividing the result of the logical AND operation by the number of underlying links to generate a remainder;

using the remainder as the link identifier;

associating the fragments with the selected link; and

transmitting the fragments over the selected link.

13. A method for uniformly distributing data transmitted by a server over a number of underlying links of an aggregate within a computer network, comprising:

providing the plurality of links as a connection to a network node;

selecting one link of the plurality of links for transmitting a datagram to the network node (hereinafter the selected link) using a round robin selection technique, the data identified by an Internet protocol (IP) identifier (ID), the IP ID indicating an end point destination for the data;

apportioning the datagram into at least one fragment;

performing a logical AND operation to combine the IP ID and a predetermined mask, wherein the predetermined mask is 0xFF80 and the predetermined number of bits is 7 bits;

right shifting the result of the logical AND by a predetermined number of bits;

dividing the result of right shifting by the number of underlying links to generate a remainder;

using the remainder as the link identifier;

associating the fragments with the selected link; and

transmitting the fragments over the selected link.