C.2 Routing Function

only for RuBoard - do not distribute or recompile

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;          /* load factor multiplier */     int reqs; }; /* a hardcoded list of parents */ #define N_MEMBERS 4 static struct _peer Peers[N_MEMBERS] = {     {"cache1.carp.net", 1},     {"cache2.carp.net", 2},     {"cache3.carp.net", 3},     {"cache4.carp.net", 4} };

Note that this code initializes the array with proxy names and integer load factors. In this case, all the load factors add up to 10, so cache1 should get 1/10; of all requests , cache2 2/10, cache3 3/10, and cache4 4/10. We'll need to convert these integer load factors into floating point values later.

The algorithm uses bitwise left rotation when computing hash values. This operation rotates the set of bits from right to left by a certain number of positions . Bits that fall off the left side are wrapped back around to the right side. The following C macro implements left rotation for 32-bit integers:

 #define ROTATE_LEFT(x, n) (((x) << (n))  ((x) >> (32-(n))))

The following is the function that calculates a hash value for a proxy hostname:

 unsigned int CalcHostHash(const char *hostname) {     unsigned int HostHash = 0;     char *c;         for (c = hostname; *c != 0; c++)         HostHash += ROTATE_LEFT(HostHash, 19) + (unsigned int) *c;     HostHash += (HostHash * 0x62531965);     HostHash = ROTATE_LEFT(HostHash, 21);     return HostHash; }

We also need to calculate a load factor multiplier for each member of the cache array. The load factor multiplier is based on the integer load factor values specified previously. The first step is to convert the integer load factors into floating point relative load factors (RLF) so they all add up to 1. In other words, divide each factor by the sum of all factors:

 void CalcMultipliers(void) {     int i;     unsigned int load_sum = 0;    /* sum of all integer load factors */     double ProdLFM;          for (i = 0; i < N_MEMBERS; i++)         load_sum += Peers[i].LF;     for (i = 0; i < N_MEMBERS; i++)         Peers[i].RLF = (double) Peers[i].LF / (double) load_sum;

Next comes the trickiest part of the algorithm. The load factor multipliers (LFM) are calculated iteratively. For this reason, they must be calculated in order from the smallest to the largest RLF. I cheated here by initializing the array with ascending load factors. Here's the rest of the function:

 Peers[0].LFM = pow((Peers[0].RLF * N_MEMBERS), (1.0 / N_MEMBERS));     ProdLFM = Peers[0].LFM;     for (i = 1; i < N_MEMBERS; i++) {         double j = N_MEMBERS - i;         Peers[i].LFM = (j * (Peers[i].RLF - Peers[i - 1].RLF)) / ProdLFM;         Peers[i].LFM += pow(Peers[i - 1].LFM, j);         Peers[i].LFM = pow(Peers[i].LFM, 1.0 / j);         ProdLFM *= Peers[i].LFM;     } }

The URI hash function is similar to the proxy name hash function, but simpler:

 unsigned int CalcURIHash(const char *uri) {     unsigned int URIHash = 0;     const char *c;     for (c = uri; *c != 0; c++)         URIHash += ROTATE_LEFT(URIHash, 19) + (unsigned int) *c;     return URIHash; }

Now that we know how to calculate each value, we can write the function that combines them to calculate a score:

 double CalcScore(unsigned int URIHash, unsigned int HostHash, double multiplier) {     /* multiplier is a peer->LFM */     unsigned int CombinedHash = (URIHash ^ HostHash);     CombinedHash += (CombinedHash * 0x62531965);     CombinedHash = ROTATE_LEFT(CombinedHash, 21);     return (multiplier * CombinedHash); }

Now we have everything needed to actually implement CARP. The following main function reads URIs from standard input and determines the best proxy cache for each. Before exiting, it prints the distribution of requests among the array members:

 int main(int argc, char *argv[]) {        char uri[512];        int n = 0;     int i;     for (i = 0; i < N_MEMBERS; i++)         Peers[i].hash = CalcHostHash(Peers[i].name);     CalcMultipliers();     while (NULL != fgets(uri, 512, stdin)) {         unsigned int URIHash;         double score;         double high_score = 0.0;         int high_index = 0;         strtok(uri, "\r\n");     /* truncate end-of-line characters */         URIHash = CalcURIHash(uri);         for (i = 0; i < N_MEMBERS; i++) {             score = CalcScore(URIHash, Peers[i].hash, Peers[i].LFM);             if (score > high_score) {                 high_score = score;                 high_index = i;             }         }         Peers[high_index].reqs++;         n++;     }     for (i = 0; i < N_MEMBERS; i++) {         printf("%20.20s %d reqs, %f%%\n",             Peers[i].name,             Peers[i].reqs,             (double) Peers[i].reqs / (double) n);     }     return 0; }

only for RuBoard - do not distribute or recompile