Bi-directional affinity within a load-balancing multi-node network interface

A new network load balancing/firewall node for use in a system including multiple network load balancing/firewall nodes is disclosed. The network load balancing/firewall applies bi-directional load balancing affinity with regard to requests from external clients and corresponding responses from internal network servers. An external network load balancing adapter executes a load-balancing algorithm to determine whether a received client request is accepted by the network load balancing/firewall node. A firewall utility processes the received client request and maintains state information associated with the received client request. An internal network load balancing adapter ensures that the same network load balancing/firewall node accepts a response from an internal network server corresponding to the received client request.

AREA OF THE INVENTION

The present invention generally relates to the area of computer networks and implementation of load balancing within such networks. More particularly, the present invention is directed to load balancing in connection with multi-node network interfaces interposed between external clients and servers on an internal network.

BACKGROUND OF THE INVENTION

More and more today computer end users are reaching out over the Internet to gather information and news located at remote servers. Often, in order to meet user demand, the requested information resides on multiple servers working in concert to fulfill information requests. Allowing multiple users to access the same data servers and execute the same application requires sophisticated network management capable of ensuring that servers are reliable, highly available and scalable. One of the more challenging aspects of network management is balancing server load in order to handle overwhelming demand for access to Internet locales.

“Load balancing” is the term given to a technique for apportioning the work of serving a network task, function, application etc. among two or more servers (also referred to as “hosts”). According to the technique, a number of servers are grouped in a “cluster” such that client requests are distributed amongst the servers in the cluster ensuring that no one server becomes overloaded. For example, load balancing is especially important for networks where it is difficult to predict the number of requests that will be issued to any given server, such as a high-traffic website host.

One common approach to load balancing is referred to as the “round-robin” approach. Under this method, application requests are evenly distributed amongst servers in a cluster such that each server gets an equal share of the load. The round-robin approach, however, has limitations such as not taking into consideration the different performance characteristics of individual servers in the cluster and not determining whether the designated server is actually available. Consequently, it is possible to overload a slower server in the cluster or send a request to a server that is not available.

Other approaches to load balancing require the use of dedicated hardware utilized solely for the purpose of load balancing. For example, dedicated computers executing only load-balancing applications are used to accept connections on behalf of all servers in a cluster, monitor the cluster and assign application requests to servers in the cluster on the basis of performance and availability. Another hardware example is the use of network switches to create a cluster of servers and to divide traffic amongst the available servers in the cluster. A dedicated hardware solution, however, is problematic because it presents a single point of failure for the system such that if the computer or switch fails, the cluster of servers also fails.

An alternative to dedicated hardware, and a solution to the overhead expenses and hardware failure, is software-based load balancing. An example of a software-based solution is the MICROSOFT NETWORK LOAD BALANCING server, also referred to as the “NLB.” Microsoft's NLB executes as a network driver on all servers in the cluster. The NLB drivers executing concurrently on each server communicate with each other to monitor the availability of each server and to determine mutually which server in the cluster handles the application request.

An example of a typical implementation of load balancing in the prior art is illustrated inFIG. 1. Networked computer system100includes one or more external client computers110connected via data links115and Internet120to a cluster of external network interface servers130. The cluster of external network interface servers130is connected to a series of published servers150via data links135and155and a router140. With continued reference toFIG. 1, when the external client110, having IP Address A, makes a connection to one of the internal published servers150, a data request message117is routed to server cluster130, having IP Address B. Upon receipt, server cluster130executes a server selection algorithm based upon the source and destination IP addresses and then one of the servers in the cluster130accepts data request message117. Following message path1in the example ofFIG. 1, data request message117arrives at Server M as a result of executing the selection algorithm using IP Address A and IP Address B.

Server M then makes a connection to the appropriate published server150by translating the IP address of public Server M to the private IP address of the published server. In this example, the IP address of Server M identified in data request message137translates to IP Address C. In this instance, data request message137follows message path2from Server M to Published Server N. When constructing a response message, Published Server N swaps the source and destination IP addresses in the response message. In the above example, the source IP address changes from IP Address A to IP Address C and the destination IP address changes from IP Address C to IP Address A. Thereafter, data response message157is routed back to server cluster130, the predefined default gateway for published servers150. Because the destination address of the response message is unknown to the published server, all response messages from published servers150are forwarded to the MAC (i.e., Media Access Control) address of the predefined default gateway, which in this example is the MAC address of server cluster130.

Upon arrival, server cluster130executes a server selection algorithm based on the source and destination addresses. In this scenario, the response message may be sent to a server different than the server that processed the client data request117and initiated the connection with the published server. Following message path3in the example ofFIG. 1, data response message157arrives at Server2as a result of executing the selection algorithm.

Under the above known load-balancing scheme, the server cluster determines which server processes the message by repeatedly executing the selection algorithm using the source and destination IP addresses. Thus, the return path through the external network interface is not ensured to be the same as the original path from the external client into the external network interface.

SUMMARY OF THE INVENTION

The present invention comprises a new method and structure for implementing “bi-directional affinity” in a load-balancing environment. Bi-directional affinity ensures that requests from external clients and corresponding responses from internal servers are processed by the same external network interface server. More particularly, the present invention generates a list of criteria that is surveyed during load balancing to ensure that the data response from the internal server is accepted by the same external network interface server that accepted and processed the data request.

The present invention comprises a new network load balancing/external network interface node for use in a system including multiple network load balancing/external network interface nodes. The network load balancing/external network interface ensures bi-directional load balancing affinity with regard to requests from external clients and corresponding responses from internal network servers. During the load-balancing process, an external network load balancing adapter executes a load-balancing algorithm to determine whether a received client request is accepted by the network load balancing/external network interface node. After server selection, an external network interface utility processes the received client request and maintains state information associated with the received client request. Thereafter, the client request is routed to an internal network server that processes the request and responds by routing a message to the internal load balancing adapter.

After receiving the response message, an internal network load balancing adapter executes either a default load-balancing algorithm or a complementary load-balancing algorithm to determine whether a received client request is accepted by the network load balancing/external network interface node. The default load-balancing algorithm can be any acceptable load-balancing algorithm adopted by the internal network adapters. The complementary load-balancing algorithm, however, ensures that the same network load balancing/external network interface node accepts a response from an internal network server corresponding to the received client request. In one embodiment of the invention, the list of criteria includes internal network source addresses for which the complementary load-balancing algorithm is selectively invoked.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

In some situations, it is beneficial if the same server in a cluster processing a data request from an external client also processes a data response from a published server. It can be seen that there is a need for a method for effectuating “bi-directional affinity” such that a data response from a published server is always processed by the same server that processed the initial data request.

In an embodiment of the present invention, a bi-directional affinity load-balancing technique comprises server communication system software executed within a server computer operating environment such as the one depicted inFIG. 2, and in particular one that is configured to support potentially hundreds of thousands of concurrent network connections and data requests. Such a computing environment is potentially present in popular website server configurations that exist today.FIG. 2illustratively depicts an example of a suitable operating environment within which the invention is implemented. The example network includes several computers200a-fcommunicating with one another over a network220, represented as a cloud. Network220may include any of many well-known components, such as routers, gateways, hubs, etc. and may allow computers200a-fto communicate via wired and/or wireless media. The example network also includes a firewall protected server cluster230connected to network220.

Referring toFIG. 3, an example of a basic configuration for a load-balancing external network interface computer on which the invention described herein may be implemented is shown. In its most basic configuration, computers200a-ftypically include at least one processing unit212and memory214. Depending on the exact configuration and type of the computer, the memory214may be volatile (such as RAM), non-volatile (such as ROM or flash memory) or some combination of the two. This most basic configuration is illustrated inFIG. 3by dashed line210. Additionally, the computer may also have additional features/functionality. For example, computers200a-fmay also include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Computer storage media includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disk (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to stored the desired information and which can be accessed by computers200a-f.Any such computer storage media may be part of computers200a-f.

Computers200a-fmay also contain communications connections that allow the device to communicate with other devices. A communication connection is an example of a communication medium. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. The term computer readable media as used herein includes both storage media and communication media. Computers200a-fmay also have input devices such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output devices such as a display218, speakers, a printer, etc. may also be included. All these devices are well known in the art and need not be discussed at length here.

Having described an exemplary computing environment for executing a method for load balancing interfaces in a multi-node network embodying the present invention, attention is directed toFIGS. 4a-ethat depict an exemplary computer network application environment within which the present invention is practiced. As shown inFIG. 4a,networked computer system300includes one or more external client computers310connected via data links315and Internet320to a cluster of M servers330(referenced as ISA/NLB 1, ISA/NLB 2 and ISA/NLB M). Data links315comprise any appropriate data link, for example, a local area network or a wide area network. Various data links are employed in alternative embodiments of the invention. The cluster of servers330is also connected, via data links335and355and a router340, to a series of N published servers350(referenced as Published Server1, Published Server2and Published Server N). Published servers350comprise any appropriate server accessible for the purpose of providing content, for example, a website host.

In an embodiment of the present invention as shown inFIG. 4a,the networked computer system300includes one or more internal client computers360connected to the cluster of servers330and the series of published servers350via data links335,355and365and router340. As will be explained further herein below, external clients310and internal clients360request/receive data information from published servers350by sending/receiving a request/response message. In order to manage the traffic associated with data requests and responses, computer network system300includes a technique for load balancing data traffic across the cluster of servers330.

In an embodiment of the present invention, each server within the cluster330functions as a firewall simultaneously acting as a secure gateway to Internet320for internal clients360and protecting against intrusions from external clients310. An implementation example of such a firewall is Microsoft's Internet Security and Acceleration Server also referred to as “ISA” (a product of Microsoft Corp. of Redmond, Wash.). To load balance the data traffic amongst the cluster of ISA servers330, each ISA server executes Microsoft's NLB application as a network driver. As described above, the NLB drivers, executing concurrently on each ISA server, communicate with each other to monitor the availability of each ISA server and to determine mutually which ISA server in the cluster accepts the application request.

Turning briefly toFIG. 5, an exemplary cluster330of ISA/NLB servers is schematically depicted having a plurality of M servers (referenced as ISA/NLB #1370, ISA/NLB #2380and ISA/NLB #M390). Each ISA server uses an NLB to balance traffic on the external interfaces323and internal interfaces343of the ISA server cluster330. During the load-balancing process, incoming data requests from external clients310via Internet320and outgoing data requests from internal clients360via router340are routed to the appropriate ISA server. The process of determining the appropriate ISA server is performed by the NLB, however, any appropriate load-balancing application can be used. The goal of the load-balancing process is to balance incoming and outgoing data requests amongst the servers in the ISA cluster330. According to an embodiment of the invention, data responses from the published server350, however, are not balanced amongst the ISA servers330, but rather incorporate bi-directional affinity that ensures responses are routed to the same ISA server that processed the external request.

With reference toFIG. 5, each server includes an external network load balancing adapter370a,380aand390athat executes a load-balancing algorithm to determine whether a received client request is accepted by one of the servers370b,380bor390b. Similarly, each server includes an internal network load balancing adapter370c,380c, and390cthat executes a load-balancing algorithm ensuring that the server370b,380bor390bthat accepts a response from the published server corresponds to the same server that accepted the external client request. As will be explained further herein below, each internal network load balancing adapter370c,380c, and390ccomprises a default load-balancing algorithm, a complementary load-balancing algorithm and a list of criteria.

According to the present invention, a mapping of NLB adapters is used to provide global load balancing state for all external and internal load balancing adapters participating in the bi-directional affinity process. In one embodiment of the present invention, external load balancing adapters are grouped in an external NLB cluster and internal load balancing adapters are grouped in an internal NLB cluster. With reference to server cluster330inFIG. 5, external load balancing adapters370a,380aand390aare grouped in an external NLB cluster331. Similarly, internal load balancing adapters370c,380cand390care grouped in an internal NLB cluster332. According to the present invention, external NLB cluster331and internal NLB cluster332use the same global load balancing state to implement bi-directional affinity. Using the same global load balancing state, along with appropriate use of the complementary algorithm, ensures that request messages and response messages are processed by the same network interface server.

Turning toFIG. 4b,when a connection request is initiated by external client310to a published server behind the ISA firewall330, the external client310first connects to the external interface of ISA/NLB cluster330by forwarding a request message317. In this example, data request message317, having a source IP address of IP Address A and a destination IP address of IP Address B, follows message path1. When message request317arrives at the external interface of the cluster330, the external NLB adapters370a,380aand390a(as shown inFIG. 5) execute a server selection algorithm based upon the source or destination IP addresses (i.e., IP Address A or IP Address B) as a method for load balancing incoming data requests. Alternatively, the server selection algorithm uses any part of the communication header, alone or in combination, as a method for load balancing. In one embodiment of the invention, NLB adapters370a,380aand390a(as shown inFIG. 5) execute the server selection algorithm using the source IP address. The result of the server selection algorithm determines which ISA server370b,380bor390b(as shown inFIG. 5) in the ISA server cluster330accepts request message317. In the example ofFIG. 4b,the server selection algorithm determines that ISA/NLB M accepts message317.

Turning toFIG. 4c,data request message317is routed to ISA/NLB M along message path2. After determining which published server in the series of published servers350should receive message request317, ISA/NLB M routes the request message337to the appropriate published server by effectively translating the destination IP address to that of the appropriate published server. In the example, data message337translates the destination IP address from IP Address B to IP Address C. Before routing data message337to Published Server N (i.e., IP Address C), ISA/NLB M saves the state information associated with the external client request.

Turning toFIG. 4d,ISA/NLB M routes data request message337to Published Server N having IP Address C along message path3. When Published Server N responds to the request, it first swaps the source and destination information stored in data message357. As depicted inFIG. 4d,data response message357swaps the source and destination IP addresses such that the source address changes to IP Address C (i.e., Published Server N) and the destination address changes to IP Address A (i.e., external client310).

Next, as depicted inFIG. 4e,data response message357is routed back through the network and router to the cluster of NLB/ISA servers330. In order to preserve bi-directional affinity, when response message357arrives at the internal interface of server cluster330, NLB first determines whether the source IP address for response message357is a member of a list333of criteria provided to NLB by ISA. The list333of criteria contains network source addresses for all published servers that select to have the data response message routed to the same NLB/ISA server that accepted and processed the client request. In one embodiment of the present invention, a network administrator populates list333with the IP addresses of those published servers for which the NLB/ISA servers330ensure bi-directional affinity. Alternatively, list333may include destination network MAC addresses or any other criteria in a network packet that uniquely identifies components of the system for which to invoke the complementary load-balancing algorithm. In another embodiment of the present invention, the ISA370b,380bor390bstatically configures the internal NLB370c,380cor390c, on a per-adapter basis, to routinely invoke bi-directional affinity for messages arriving on the internal adapter side. In yet another embodiment of the present invention, criteria relating to data request messages (i.e., inbound packets) are individually assessed by the ISA370b,380bor390bwhich, in turn, directs the NLB370c,380cor390cto invoke either the default or complementary load-balancing algorithm.

According to one aspect of the exemplary load-balancing technique, if the published server address is a member of the list333or the internal NLB is statically configured to perform bi-directional affinity, NLB executes a complementary server selection algorithm to determine which NLB/ISA server accepts response message357. In one embodiment of the present invention, the complementary server selection algorithm executes based upon the destination address (i.e., the IP address of the client computer310) in response message357, rather than the source IP address. Alternatively, if the published server address is not a member of the list333and the internal NLB is not statically configured to perform bi-directional affinity, NLB executes a default server selection algorithm to determine which NLB/ISA server accepts response message357. In one embodiment of the invention, the default algorithm executes based upon the source address.

With reference toFIG. 4e,a comparison of the source IP address in response data message357(i.e., IP Address C) with the network addresses in the list333reveals that IP Address C is on the list333. Consequently, the NLB executes the complementary server selection algorithm upon the destination IP address (i.e., IP Address A) instead of executing the default algorithm upon the source IP address (i.e., IP Address C). Executing the server selection algorithm based upon IP Address A ensures that response message357is accepted by ISA/NLB M, the same ISA server that accepted and processed client request317. One benefit of utilizing the same ISA server to process requests and responses is that stateful inspection of the data request processed is made possible.

Having described structures that support an exemplary load-balancing technique of bi-directional affinity embodying the present invention, attention is now directed toFIG. 6that depicts a set of steps performed by a multi-node external network interface incorporating bi-directional affinity in load balancing. The steps described herein below are exemplary. As those skilled in the art will readily appreciate, the present invention can be carried out in a variety of manners and the steps described herein below can be rearranged and modified in accordance with alternative embodiments of the present invention.

The procedure begins at step500where the external network interface receives a request from an external client310. Request message317includes a source IP address, a destination IP address and other data. In response to receipt of the message, during step502a load-balancing algorithm is executed to select which interface node will process the data request. For example, in an embodiment of the present invention, the external network interface adapters apply a modulo algorithm on a hash of the source IP address to select the interface node. Thereafter, at step504, the selected interface node creates state information for request message317. At step506, request message337is passed to the published server by the selected interface node.

After receiving request message337, published server350sends response message357to the internal network interface at step508. Thereafter, at steps510and512, a determination is made whether to invoke the default or complementary load-balancing algorithm. At step510, the internal interface node determines whether it is statically configured to always invoke bi-directional affinity. If the internal interface node has not been configured as such, at step512, list333is examined to determine if the address of the published server350is on the list333. If the address is not on the list333of criteria that includes internal network source addresses, then control passes to step514. At step514, the internal network interface adapters execute a default load-balancing algorithm to select an interface node. In a particular example of default load balancing, the internal network interface adapters apply a modulo algorithm on a hash of the source IP address to select the interface node. The default load-balancing algorithm can be any acceptable load-balancing algorithm adopted by the internal network adapters.

Alternatively, if the internal interface node is statically configured to always invoke bi-directional affinity as determined in step510or the address of the published server350is on the list333of criteria that includes internal network source addresses as determined in step512, then control passes to step516. At step516, the internal network interface executes a complementary load-balancing algorithm to select an interface node. Execution of a complementary load-balancing algorithm ensures that response message357is accepted by the same interface node that processed request message317. In a particular example of complementary load balancing, the internal network interface adapters apply a modulo algorithm on a hash of the destination IP address to select the interface node.

At step518, the interface node selected during execution of the load-balancing algorithm accepts response message357. Thereafter at step520, response message357is processed by the selected interface node and passed to external client computer310.

Attention is now directed toFIG. 7that depicts a set of steps performed by the external interface nodes in the server cluster after receiving a request message from an external client. The steps described herein below are exemplary.

The procedure begins at step600wherein the external interface node adapters receive a message request317from external client310. Thereafter, at step602the external interface node adapters execute a load-balancing algorithm to determine whether the node is selected to accept request message317. The load-balancing algorithm can be any acceptable load-balancing algorithm adopted by the external network adapters. In a particular example of load balancing, the external network interface adapters apply a modulo algorithm on a hash of the source IP address to select the interface node. At step604, if the external interface node is selected, then control passes to step606. At step606, the external interface node accepts request message317and the process ends.

Attention is now directed toFIG. 8that depicts a set of steps performed by the internal interface nodes in the server cluster after receiving a request/response message from an internal server. The steps described herein below are exemplary.

The procedure begins at step700wherein the internal interface node adapters receive a request/response message from an internal client360or an internal server350. At steps702and704, a determination is made whether to invoke the default or complementary load-balancing algorithm. At step702, the internal interface determines whether it is statically configured to always invoke bi-directional affinity. If the internal interface has not been configured as such, at step704, list333is examined to determine if the address of internal client360or internal server350is on the list333. If the address is not on the list333of internal network source addresses, then control passes to step706. At step706, the internal network interface executes a default load-balancing algorithm to select an interface node.

Alternatively, if the internal interface node is statically configured to always invoke bi-directional affinity as determined in step702or the address of internal server350or internal client360is on the list333of internal network source addresses, then control passes to step708. At step708, the internal network interface executes a complementary load-balancing algorithm to select an interface node. Execution of a complementary load-balancing algorithm ensures that response message357from internal server350is accepted by the same interface node that accepted and processed request message317.

At step710, if the internal interface node is selected, then control passes to step712. At step712, the internal interface node accepts the request/response message and the process ends.

Illustrative embodiments of the present invention and certain variations thereof have been provided in the Figures and accompanying written description. The present invention is not intended to be limited to the disclosed embodiments. Rather the present invention is intended to cover the disclosed embodiments as well as others falling within the scope and spirit of the invention to the fullest extent permitted in view of this disclosure and the inventions defined by the claims appended herein below.