Both of these parts can be carried out either locally or globally. Load balancing can be classified according to the decision base and migration space [29]. If migration decision is carried out according to local load situation and that of neighbors, it is called local decision base. If this decision is based on load condition of subset of the whole network, then it is called global decision base. Similarly if load unit is migrated to direct neighbors, then it is called local migration space, otherwise it is called global migration space. So according to decision base and migration space, four different categories of schemes emerge:
A taxonomy for load balancing in distributed systems is presented in [10].
However, these approaches for load balancing are not suitable for load balancing in the web context for several reasons. First, in the web context there are multiple points for load balancing (e.g. at the DNS or at the server) while traditional techniques assume a single point. Secondly, the cost factors are not homogeneous in web and can vary a lot, while in traditional systems most servers are assumed to be generally of similar capacity and capability. Thirdly, the jobs were assumed to be compute intensive and hence the focus was to distribute the compute load. In the web, on the other hand, the load is mostly I/O oriented where caching plays a very significant role in performance and will impact the schemes. Even cost of migration of load unit and granularity of load varies for different points of load balancing. Due to these, and other reasons, it is best to consider the load balancing problem in the Web as a new problem, which requires different approaches.
In web context, which server to select has been mostly studied from client point of view, i.e. either client side DNS or client proxy or clients themselves decide which server to choose. Usually, these entities send probes to multiple servers and select best server based on probe results or they take into account previous history of responses sent by server. But these probes are usually not sufficient to accurately measure server load conditions, since load on servers can change easily with time and usually these probes can not find current load on the servers and until all clients use such softwares and there is co-operation with server side entities (it is however very difficult to reach at common method acceptable to all), they will either incur too much overhead or will not give much better performance.
Example of client themselves selecting server is Netscape [15] or Java Applet running at client to probe servers is [31]. In scheme proposed by Beck and Moore [7] in their I2-DSI system, DNS resolver at client side sends probes to server to select server with minimum response time. In scheme proposed by Baentsh et al [6] servers send information about other servers in hierarchy through extra http headers to client side proxy and then client side proxy selects server.
There are various proximity metrics considered for selection for best server by clients. Crovella et al [14] compare random server selection, hop count and round trip time based selection and find that RTT has relatively higher correlation with latency perceived by client. Sayal et al [25] also include HTTP latency (time measured by sending HTTP HEAD request) and all server polling in their study and find HTTP latency has highest correlation with actual server response time for other requests and present refresh based algorithms for best server selection at client side.
Client side approaches are not general, since they assume modification in client side components, some approaches even modify protocols. Thus these types of approaches can not improve performance for all the clients.
Gwertzman et al [21] first pointed out the need of creating cache server on other side of USA when demand from that side increases. Guyton et al [20] focus on hop count based metric and cost of collection of information for server selection.
Server selection at server side DNS is done based on geographical proximity approximated using client IP address or hop count information obtained from routers in Cisco's Distributed director [11]. Given that clients are distributed geographically far apart, static and relatively less costlier metrics like hop count for proximity information are not found good in study by [14]. Ammar et al [32],[17] propose local anycast resolver that is near a large number of clients, to which servers push their performance information and probing agent probes servers for path information. This proposal assumes use of anycasting domain name(ADN) and anycast resolver near clients, which once again lacks general applicability.
In next section we present a brief survey of mechanisms used for distribution of client requests.