The LARD strategy

The LARD strategy yields scalable performance by achieving both load balancing and cache locality at the back-end servers. For the purpose of achieving cache locality, LARD maintains mappings between targets and back-end nodes, such that a target is considered to be cached on its associated back-end nodes. To achieve a balance between load distribution and locality, LARD uses three cost metrics: cost_balancing, cost_locality and cost_replacement. The intuition for the definition of these metrics can be explained using Figure 3, which shows the throughput and delay characteristics of a typical back-end server as a function of load (measured in number of active connections).

  

Figure 3: Server Throughput and Delay

The load point L_idle defines a value below which a back-end node is potentially underutilized. L_overload is defined such that the difference in delay between a back-end node operating at or above this load, compared to a back-end node operating at the point L_idle, becomes unacceptable.

The metric $cost\_balancing$ captures the delay in the servicing of a request because of other queued requests. $Cost\_locality$, on the other hand, reflects the delay arising due to the presence or absence of the target in the cache. $Cost\_replacement$ is a cost that reflects the potential future overhead caused by the replacement of a target in the cache. The three cost metrics are then defined as shown in Figure 4.

The unit of cost (and also of load) is defined to be the delay experienced by a request for a cached target at an otherwise unloaded server.

  

Figure 4: LARD Cost Metrics

The aggregate cost for sending the request to a particular server is defined as the sum of the values returned by the above three cost metrics. When a request arrives at the front-end, the LARD policy assigns the request to the back-end node that yields the minimum aggregate cost among all nodes, and updates the mappings to reflect that the requested target will be cached at that back-end node².

Our experimental results with the Apache 1.3.3 webserver running on FreeBSD-2.2.6 indicate settings of L_overload to 130, L_idleto 30 and $Miss\ Cost$ to 50. We have used these settings both for our simulator as well as for our prototype results in this paper.