Method for transmitting load balancing in mixed speed environments

A method for transmitting load balancing in mixed speed environments such as physical interface speed changes and client flow speed changes is disclosed. Components such as an association module, a flow redirector, a channel assignment module, and a balancing timer are employed. The association module is a data structure that contains an association between client connections and a network interface. The flow redirector redirects transmitted network packets to the network interfaces based on the data, which is provided by the load balancing association. The channel assignment module is advised when such association data does not exist. The channel assignment module creates the association between the client connection- and the network interface, which is stored in the load balancing association. The decisions that this module makes affect the actual balancing between the network interfaces. The balancing timer computes throughput for client flows and re-associates client flows to the network interfaces.

BACKGROUND

1. Field of the Invention

Embodiments described herein are directed to a method for transmitting load balancing in mixed speed environments such as during physical interface speed changes and client flow speed changes. Specifically, a load balancing association, a main flow redirector, and a channel assignment module are implemented.

2. Related Art

Traffic load-balancing algorithms are necessary for providing an equal share of loads between network interfaces. In order to preserve the transmission order of packets, classical load balancers generally assign client connections to network interfaces. Various parameters may change, however, after assigning clients to these network interfaces. For example, the speed of the physical media interface may dynamically change. The client traffic intensity/flow rate may similarly change.

Such changes cause performance degradation because of a lack of an optimization method that considers these dynamic changes. Furthermore, handling these parameters without the dynamic changes is non-trivial. While transmitting load balancing solutions exist, they do not support mixed speeds proportional load balancing. A common load balancer generally assumes that it is using an equal capabilities lower interface. As such, the necessity for a design that is adaptive to the above-described changes is critical toward providing a high performance solution for mixed speed network interfaces.

DETAILED DESCRIPTION

The following paragraphs describe a method for transmitting load balancing in mixed speed environments such as, but not limited to, physical interface speed changes and client flow speed changes.FIG. 1shows an example of a transmitting load balancing system100whereby client connections120a–dare assigned to different network interfaces140a–cacross a data communication network110. The data communication network110may include the Internet, an Intranet, or any combination of public and private data communication networks. The data communication network110may be configured as a local-area network, wide-area network, or another kind of architecture. Multiple clients may be assigned to one network interface140b, for example. Also coupled to the data communication network110is a server130, which houses the various network interfaces140a–c.FIG. 1illustrates one embodiment of the topology of the transmitting load balancing system100. The server130may further be situated, for example, between the data communication network110and the client connections120a–d.

As shown inFIG. 2, four sub-components, a load balancing association210, a main flow redirector220, a channel assignment module230, and a balancing timer240are used in the load balancing system100. These sub-components reside within the server130. That is, the server130is responsible for decision-making within the transmitting load balancing system100. The load balancing association210, the main flow director220, the channel assignment module230, and the balancing timer240may be software and can be run by one or more software programs.

The load balancing association210is a data structure that contains an association between client connections120a–dand a network interface140a–c. A client connection120a–dprovides representation of a flow between the server130and a client. The main flow redirector220redirects transmitted network packets to the various network interfaces140a–cbased on data, which is provided by the load balancing association210. When such association data does not exist, the channel assignment module230is advised. The channel assignment module230creates the association between the client connection120a–dand the network interface140a–c, which is stored in the load balancing association210. The decisions that the channel assignment module230makes affect the actual balancing between the network interfaces140a–c. The load balancing association210and the main flow redirector220are common modules of load balancing systems. In the present transmitting load balancing system100, connections are added to the load balancing association210, and the channel assignment module230is introduced.

The load balancing association210is extended to maintain statistical information for each client flow for client connections120a–dand for each network interface140a–c. When a new client flow is being created, statistics are temporarily unknown. Statistics include, for example, transmit byte count, load, and throughput information.

The channel assignment module230associates a given client flow of a client connection120a–dwith a network interface140a–cand stores the association in the load balancing association210. Association decisions are made based on variables such as, for example, packet type, client flow statistics, and network interface physical link speed and statistics. The channel assignment module230chooses the least loaded network interface140a–cto be associated with a client flow. A least loaded network interface140a–cis an interface with a maximum adapter gap value, which is provided in the following formula: Adapter Gap=Physical Adapter Link Speed−Adapter Current Load, where Adapter Current Load=Σ(Client Flow History Throughput)+Ψ(Optional Receive Load).

Optional receive load is an optional value that may reflect certain systems where there is a relation between the transmit load and the receive load. Ψ is a constant between zero (0) and one (1) that signifies the multiplicand importance. Σ sums all of the transmit throughput values of client flows, which are associated with the subjected adapter. After associating a channel with a network interface, the adapter current load value is updated by adding the associated client flow throughput. If flow history throughput information, i.e., a new flow with no history information is not provided for the client flow, a constant value is added to the adapter load.

A balancing timer240period is the designated duration to provide correction to a given change in speed configuration. A timer period typically sets up in approximately ten seconds. A periodic balancing timer240function is composed of statistics maintenance, network interface statistics, and channel reassignment. Regarding statistics maintenance, the client history throughput value is updated for each client flow. The throughput is computed by calculating the client flow transmissions over the timer interval.

Concerning network interface statistics, load information is cleared for each network interface140a–c. With respect to channel reassignment, after all statistical information is updated, all of the client flow associations in the load balancing association210are recalculated and reassigned with the network interfaces140a–cto provide optimized load balancing. Sorting the order of client flow, from high throughput to low, and calling the assignment function for the client flow in decreasing order provides for optimal balancing. It is also possible to have non-sorted order reassignments for less optimized implementations. This is achieved by deleting the load balancing association210while maintaining the client flow statistics, which causes an assignment function processing for each client flow during the main flow redirector220operation.

FIG. 3illustrates the steps involved in achieving mixed speed balancing at the packet transmission interface level. As shown in step310, at the packet transmission interface level, it must first be determined whether a packet is balanceable. If the packet is not balanceable, a default network interface140a–cis assigned, as depicted in step320. If the packet is balanceable, it is determined whether a client flow association exists, as shown in step330. If a client flow association does not exist, an association is created as illustrated in step340, and then the association is retrieved as indicated in step350. If a client flow association does exist, the association is retrieved as per step350. Next, the packet is transmitted through a designated interface, as shown in step360.

FIG. 4illustrates the steps involved in achieving mixed speed balancing using the balancing timer240. The throughput for each client flow is computed, as illustrated in step410. Next, as shown in step420, the client flows to network interfaces140a–care reassociated. While the balancing timer240operates independently of the packet transmission interface level, the associations calculated at step420are the same associations that are retrieved at step350.

An example of load balancing follows. Assume the presence of three client flows whereby A has a speed of 85 Mb/s, B operates at 900 Mb/s, and C functions at 50 Mb/s. Now assume the presence of two network interfaces whereby N1has a link speed of 1,000 MB/s, and N2has a link speed of 100 MB/s.

A, B, and C client flows are created instantly. That is, no history information is provided. The flow assignments are as follows for A: gap(N1)=1,000; gap(N2)=100, so A is assigned to N1. Assume that a constant value of 5 Mb/s is added to the network interface load. Now, gap(N1): 1,000−995=5, and gap(N2)=100. When C is assigned, gap(N1)=995, and gap(N2)=100, so C is assigned to N1. Again, assume that a constant value of 5 Mb/s is added to the network interface load. Now, gap(N1): 995−5=990, and gap(N2)=100. Based on these values, B is assigned to N1. Assume again that a 5 Mb/s constant value is added to the network interface load. Now, gap(N1): 990−5=985, and gap(N2)=100.

At this point, a protocol such as, for example, Transmission Control Protocol (“TCP”) [Transmission Control Protocol, Request For Comments (“RFC”) 793, published September 1981] tries to increase the data flow to the physical network/protocol limit. Various other protocols may similarly be used. Assuming that each flow receives a fair relative share, A will have a weighted average of 81 Mb/s; B will have a weighted average of 870 Mb/s; and C will have a weighted average of 48 Mb/s. Next, the periodic balancing timer evaluates the client flow speeds. Network interface load values are cleared, and reassignment occurs. A possible reassignment may occur as follows: gap(N1)=1000; gap(N2)=100, so B remains assigned to N1. Now, gap(N1): 1000−870=130, and gap(N2)=100. A thus remains assigned to N1. Gap(N1): 130−81=49, and gap(N2)=100. As such, C is reassigned to N2which then makes gap(N1)=49 and gap(N2): 100−48=52. At this point, the client protocol, such as TCP for example, tries to increase the data flow to the physical protocol/network level. A can operate at 85 Mb/s; B can function at 900 Mb/s; and C can operate at 50 Mb/s. Such is an example of an optimal assignment. Accordingly, the performance of the transmit load balancing components improve while operating in this mixed speeds environment.

While the above description refers to particular embodiments of the present invention, it will be understood to those of ordinary skill in the art that modifications may be made without departing from the spirit thereof. The accompanying claims are intended to cover any such modifications as would fall within the true scope and spirit of the present invention.