Our aim is to assign each client request to the best server such that client experiences minimum latency between HTTP request and reception of requested object.
First level decision can be taken by DNS itself, DNS can resolve IP address of cluster which can give better service to this client. Parameters affecting delay in service of HTTP request are load at selected server (and hence cluster) and path characteristics between client and server. So to take this decision, DNS should have recent cluster state information and proximity of client with clusters. DNS has information about client IP address and cluster IP addresses. Since clusters are under control of website administrator, they can provide any state information required by DNS. Since only server side components can be modified, they will have to gather the proximity information themselves. There are various metrics to measure proximity between the client and clusters. Some metrics are:
Geographical distance is significant only when time taken for transmission of requested object and propagation delay on wire are comparable, i.e. propagation delay is also significant. Propagation delay is significant for very large distances even at speed of light (can be 100s of milliseconds). But transmission media used for long distances (usually optical fiber) has very low delays and if satellite communication is used for even local connections, geographical distances may not correspond to actual delays on network. Nevertheless, it results in lesser traffic on long distance lines and usually corresponds to lower delays in practice. Geographical distance can be approximated by IP address of client if such database is available. According to RFC 1466 [19] different IP address ranges were allocated to different geographical regions to keep routing tables shorter. Using higher 8 bits of IP address only, geographical region of client can be approximated.
Network distance in hops is also a good metric and can be obtained from routers. But it does not take into account bandwidth available in path, current traffic on the path between cluster and server. In short, available bandwidth for transfer on path and delays in each hop are not taken into account. It is usually a static measure of proximity, since as found by Paxon [28] that 68% routes on the Internet are stable for at least a week and 87% routes on Internet are stable for at least six hours. Also, studies by Crovella et al [14] have found that the hop count has very low correlation (0.16) with response time (measured at client side). So it does not seem very good metric to use.
Round trip time is another metric that can give better and relatively accurate delay experienced in path and to some extent, a lower RTT indicates higher available bandwidth. However, it is very dynamic in nature, it changes quickly over relatively short period of time. It has much more variation for different clusters compared to hop count, it gives better path information between client and cluster. On the downside, it is relatively costlier to measure and requires more frequent refreshes.
Measuring bandwidth, by using tools like pathchar [22] or even using other more efficient current techniques [23], generates lots of additional network traffic and takes long time, so use of this metric is not practical.
Last two metrics can be used only after a number of clusters are tried (which result in degraded performance for client) and a huge database is maintained. Still, load on clusters can change over time and older information may not predict good cluster. These metrics are really useful for client side server selection only.
After comparing these metrics for client-cluster proximity, we conclude that RTT is the best metric to use for getting path information. It requires periodic refresh and is relatively costlier to measure (compared to hop count or geographical information) but it provides current and better network characteristics information. So we should try to limit overheads in measuring it. Crovella et al [14] found in their study that when used at client side it resulted in less than 1% additional network traffic and gave very good results when three ping messages were used to measure RTT information.
To further minimize overhead, instead of all clusters measuring RTT for each client, we propose to do the measurement only for a small subset of clients with very high request rate. Arlitt et al [5] find out that 75% of total HTTP requests to any server come from 10% of networks. So if we collect information about only very high request rate generating clients, we can use that information for all clients on the same network. We can further limit number of clusters which should measure RTT based on geographical information (approximated by use of client IP address) and having less load to certain maximum number(say at most 3).
In our approach, each server gives state information to front node in the cluster and this aggregated state information is used for assigning requests within the cluster and is propagated to DNS in aggregated form to make coarse grain (per client IP based) request assignment to cluster. More details can be found in section 3.6. We gather this proximity information once high request rate is reported by cluster to DNS, so it does not delay reply from DNS, however first reply for even those clients is based on geographical proximity information approximated using IP addresses (it is used for all clients, who either do not generate large number of requests or query DNS first time after long interval).