Web Caching

Routing Function

The routing function is an algorithm that calculates a score for each member of the cache array. In other words, when forwarding a request, an agent calculates a score for each parent, then routes the request to the cache with the highest score.

A score is calculated from three values: a hash of the URI, a hash of the proxy name, and a load factor multiplier. The proxy name hashes and multipliers don’t change over time, so they are calculated just once. The URI hash is computed for each request that needs to be routed.

I will use a simple implementation of CARP in C to explain how the algorithm works. This is a complete program, but I’ll explain it in chunks. The program consists of the following functions:

• CalcHostHash calculates a hash value for a proxy host name.

• CalcMultipliers calculates the load factor multipliers for all members of the array.

• CalcURIHash calculates a hash value for a URI request.

• CalcScore calculates a score for a (URI, cache) tuple.

• The main function reads URIs and finds the cache with the highest score.

The program begins with some basic header files:

#include <stdio.h>   
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

We also need to define a data structure and an array that holds information about the proxy caches:

/* a structure to hold information about the parent caches */ struct _peer { char *name; unsigned int LF; /* integer load factor */ unsigned int hash; double RLF; /* relative load factor */ double LFM; ...