Abstract:
A system and method for receiving a server request, determining whether one of a plurality of servers scheduled to receive the server request is available, wherein the availability of the one of the servers scheduled to receive the request is based on a first stored value and a second stored value, incrementing the second stored value by a predetermined amount when the one of the servers is unavailable and directing the server request to another one of the plurality of servers based on the first and second stored values.

Description:
BACKGROUND 
       [0001]    Electronic commerce, or “e-commerce,” is increasingly prevalent in today&#39;s marketplace. Through the use of the Internet, buyers and sellers can securely accomplish transactions regardless of their geographic proximity, and buyers can find sellers of goods that they might not otherwise have access to. 
         [0002]    The ever-increasing use of the Internet for both communications and commerce carries with it a constant increase in network traffic and complexity. Companies that do large amounts of business online typically use systems incorporating multiple servers (sometimes referred to as “server farms”) to handle large amounts of traffic. 
         [0003]    As a result of increasing amounts of traffic traversing through increasingly complicated computer networks, the efficient routing of network traffic is critical to make the user experience pleasant, insure that secure information (e.g., credit card numbers) remains secure, and provide assurance that communications are not lost. 
       SUMMARY OF THE INVENTION 
       [0004]    A method for receiving a server request, determining whether one of a plurality of servers scheduled to receive the server request is available, wherein the availability of the one of the servers scheduled to receive the request is based on a first stored value and a second stored value, incrementing the second stored value by a predetermined amount when the one of the servers is unavailable and directing the server request to another one of the plurality of servers based on the first and second stored values. 
         [0005]    A system having a plurality of servers and a load balancer receiving a server request, the load balancer directing the server request based on a first stored value and an availability of each of the servers. 
     
    
     
       DESCRIPTION OF THE DRAWINGS 
         [0006]      FIG. 1  shows an exemplary system according to the present invention. 
           [0007]      FIG. 2  shows an exemplary method for routing network traffic according to the present invention. 
           [0008]      FIG. 3  shows an exemplary implementation of a system for routing network traffic according to the present invention. 
           [0009]      FIGS. 4A-4D  show the routing of network traffic by applying the exemplary method of  FIG. 2  to the implementation of  FIG. 3 . 
       
    
    
     DETAILED DESCRIPTION 
       [0010]    The present invention may be further understood with reference to the following description and the appended drawings, wherein like elements are referred to with the same reference numerals. The exemplary embodiments of the present invention describe a system and method for balancing loads in server farms. The exemplary embodiments ensure that loading remains balanced among functioning servers within a server farm when one or more servers become non-functional. The exemplary system and method will be discussed in detail below. 
         [0011]    It is noted that the term “server farm” is used throughout this description to refer to a group of servers which host and/or provide content on a network. A “server” may be, for example, a front-end web server that stores and displays web pages. Alternately, a server may be a secure web server that handles secured web traffic, such as a user&#39;s passwords or personal identification numbers. A server may also be a payment server for securely processing online payments using the user&#39;s credit card or bank account information. Additionally, a server may be an application server for storing and providing online applications. A server may also be a database server storing, for example, an online store&#39;s inventory and pricing information. Those of ordinary skill in the art will understand that these examples are intended to be illustrative rather than limiting, and that the term “server” may be applied to any other, similar system. 
         [0012]    E-commerce can be implemented in numerous ways, from consumer-oriented online stores, malls, or auction sites, to business-to-business applications such as Electronic Data Interchange, to back-office functions like electronic payment systems and order management. E-commerce is defined as a process or event that results in the electronic transfer of value between two or more parties, with value represented by cash (or cash equivalents), goods, services, or promises made by buyers or sellers. 
         [0013]    An e-commerce transaction may involve several steps, such as marketing, ordering, payment, and support for delivery. An electronic market allows participating buyers and sellers to exchange goods and services, supported by information technology. Electronic markets have three main functions: (1) matching buyers and sellers, (2) facilitating commercial transactions, and (3) providing legal infrastructure. Information technology permeates all three of these functions to help to increase market efficiency and reduce transaction costs. Electronic trade processes including searching, valuation, payment settlement, logistics and authentication support the interaction between electronic market participants. 
         [0014]    Two important goals in designing an e-commerce system are availability and scalability. Low availability can result in lost revenue, reduced market share, and bad publicity. A system must therefore be sufficiently robust in order to maintain availability. Scalability is critical due to unpredictable customer behavior; infrastructure of an e-commerce system must be designed so that information services scale with demand. For a system to be adequately available and scalable, it must provide adequate service levels even when workload increases above expected levels. 
         [0015]    In order to insure that these standards are met, participants in e-commerce of significant volume will often employ server farms incorporating multiple servers in order to improve efficiency, reliability, stability and availability. In such situations, traffic should be balanced among the multiple servers within a server farm in order to insure substantially even distribution. 
         [0016]    In particular, it is important to maintain such an even distribution in situations when one or more servers within a server farm are unavailable. Unavailability may be, for example, due to an overload condition, a failed network connection, a power outage, etc. In such situations, the remaining available servers must each handle additional traffic, making even distribution especially important. If one or relatively few servers within a server farm receive all of the traffic that would normally be routed to the unavailable servers, this subsequent overloading can result in a domino effect and further server unavailability. 
         [0017]    To insure a desirable distribution of traffic, a server farm may include a load balancer dedicated to monitoring and controlling distribution. The load manager may be, for example, a computer specifically dedicated to this task or a software application running on a computer that also handles other tasks. 
         [0018]      FIG. 1  shows an exemplary system  100  according to the present invention. The exemplary system  100  may act in accordance with the exemplary method  200  shown in  FIG. 2 . The system  100  includes a plurality of N servers  1 ,  2  . . . N. N may be any prime number (e.g., 5, 7, 11, 13, 17, etc.). The exemplary system  100  also includes a load balancer  10  that coordinates the traffic sent to the servers  1 ,  2  . . . N. The load balancer  10  may be, for example, a hardware module such as a computer that is specifically dedicated to coordinating network traffic, or it may be a software module operating on a computer that also performs other tasks. The load balancer is connected to, and receives server requests from, a network  20  (e.g., the Internet, a corporate intranet, etc.). The load balancer stores, among other types of data, an availability vector  30 , the use of which will be described below. 
         [0019]      FIG. 2  shows an exemplary method  200  according to the present invention. In an implementation wherein the exemplary method  200  is performed within the exemplary system  100 , the load balancer  10  performs the steps of the exemplary method  200 . In step  205 , the values next and delta are both set to initial values of 1. The value next indicates which server among the plurality of servers from 1 to N will, if available, receive the next request that is sent to the load balancer  10 . Depending on the function of the servers  1 ,  2  . . . N, the request may be, for example, a user authentication request, a request to serve a webpage, a request to retrieve information (e.g., inventory information from an online store) from a database, a request to verify and charge a user&#39;s credit card, etc. The value delta is an incrementing value, the use of which will be described below. 
         [0020]    In step  210 , the availability of the servers present within the system  100  is determined. In step  215 , the availability status of each of the servers is stored in an availability vector  30  of length N. Each server from 1 to N corresponds to a component within the availability vector  30  from 1 to N; in the exemplary method, each component of the availability vector  30  is set to a value of 1 if the corresponding server is available and to a value of 0 if the corresponding server is unavailable. 
         [0021]    In step  220 , it is determined whether the server corresponding to the next value is available. In the exemplary method, this determination may be made by consulting the component of the availability vector corresponding to the next value. If the appropriate server is available, then in step  225  a request is received, such as from the network  20 . In step  230 , the request received in step  225  is sent to the server corresponding to the next value. Subsequently, in step  235 , the next value is incremented by the delta value. In other words, the delta value is added to the current next value to obtain the new next value; if the sum of the two values is greater than the number of servers N, counting resumes at the first server. This step can be described using the mathematical expression: 
         [0000]      next new =(next old +delta) mod  N    
         [0000]    After incrementing the next value in step  235 , the method returns to step  210 , where the availability of the servers  1  through N is reestablished. 
         [0022]    Alternately, if, in step  220 , it is determined that the server corresponding to the current next value is unavailable, the method proceeds to step  240 . In step  240 , the value next is decremented by performing the operation: 
         [0000]      next new =next old −delta 
         [0000]    In other words, the system returns from the next value of the server that has been determined to be unavailable, to the next value corresponding to the server that previously received a server query. Subsequently, in step  245 , the value of delta is incremented: 
         [0000]      delta new =delta old +1 
         [0023]    In step  250 , it is determined whether delta is equal to N. If this is true, then in step  255 , delta is reset to its initial value of 1. The value of delta must be reset once it reaches N; otherwise, each time next is incremented in step  235 , next new  will be equal to next old . After step  255 , or if it is determined in step  250  that delta is not equal to N, the method continues at step  260 , where next is incremented by the new value of delta. This is performed in the same way as described above for step  235 . After incrementing next in step  260 , the method returns to step  220 . 
         [0024]      FIGS. 3 ,  4 A,  4 B,  4 C and  4 D show an exemplary application of the method  200 . The system  300  includes five servers (i.e., N=5). It will be assumed, for the purposes of this example, that servers  301 ,  302 ,  303  and  304  are available, that server  305  is unavailable, and that this set of assumptions remains constant through the example. In step  205 , the load balancer  310  sets initial values of 1 for both next and delta. In step  210 , the load balancer  310  determines the availability of each of servers  301 ,  302 ,  303 ,  304 ,  305 . In step  215 , the load balancer  310  stores the availability status of the servers in availability vector  330 . 
         [0025]    In step  220 , the load balancer  310  determines whether the server corresponding to the current next value is available, i.e., consults availability vector  330  and determines that server  301  is available. In step  225 , the load balancer  310  waits for and receives a request from network  320 . In step  230 , the load balancer  310  sends the request to server  301 . In step  235 , the value of next is incremented by the value of delta. The method returns to step  220  and repeats the process, incrementing next to a value of three, and then four. Eventually, next is incremented to a value of five.  FIG. 4A  illustrates this initial process. 
         [0026]    When the method returns to step  220  with a next value of five, the load balancer  310  determines that server  305  is unavailable, so the method continues at step  240 . In step  240 , next is decremented, i.e. delta is subtracted from next to return to its immediate previous value. In the present example, this means next returns to a value of four. In step  245 , delta is incremented to two. In step  250 , the load balancer  310  determines whether delta has been incremented to the point that it is equal to N (i.e., five). Because it has not, the method continues at  260 , where next is incremented by the new delta value. In this case: 
         [0000]      next new =(next old +delta) mod  N= (4+2) mod 5=1 
         [0027]    After both delta and next have been incremented, the method returns to step  210 , where the availability status of all the servers  301 ,  302 ,  303 ,  304 ,  305  is reverified. The availability status is updated in step  220 , and the availability of the server corresponding to the new value of next is determined in step  230 . The method continues to iterate with a delta value of two, sending queries to server  301  and server  303 . The method attempts to continue at server  305 , but because server  305  is not available, returns to server  303  as described above in step  240 .  FIG. 4B  shows this portion of the process. 
         [0028]    Delta is then incremented to a value of three, and the method continues, sending queries to server  301 , server  304 , and server  302 . The method would continue at server  305 , but, because server  305  is unavailable, returns to server  302 .  FIG. 4C  shows this portion of the process. 
         [0029]    Delta is then incremented to a value of four, and the process continues at server  301 . It attempts to continue at server  305 , but because server  305  remains unavailable, returns to server  301 .  FIG. 4D  shows this portion of the process. 
         [0030]    Because further incrementing delta would cause it to equal five (i.e. be equal to N), the method proceeds through step  255  (rather than from step  250  directly to step  260 ) and delta is instead reset to its initial value of one. Repetition continues as described above with reference to  FIG. 4A . 
         [0031]    It should be noted that the specific exemplary application shown in  FIGS. 4A-4D  results in four queries routed to server  301  and two queries routed to each of servers  302 ,  303  and  304 . While minor inequalities are present resulting from this method, they become less significant for larger values of N (i.e., systems incorporating more servers). 
         [0032]    The exemplary embodiments of the present invention thus use a simple algorithm, based in number theory, to insure that server requests are evenly distributed among servers within a server farm. A more even distribution enables such a system to be better able to cope with workload above expected levels. As a result, e-commerce systems will function more efficiently and effectively and improve the user experience. 
         [0033]    It will be apparent to those skilled in the art that various modifications may be made in the present invention, without departing from the spirit or scope of the invention. Thus, it is intended that the present invention cover the modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.