src/carp.cc

   1
   2 /*
   3  * $Id: carp.cc,v 1.11 2000/08/01 22:01:29 wessels Exp $
   4  *
   5  * DEBUG: section 39    Cache Array Routing Protocol
   6  * AUTHOR: Eric Stern
   7  *
   8  * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from the
  12  *  Internet community.  Development is led by Duane Wessels of the
  13  *  National Laboratory for Applied Network Research and funded by the
  14  *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
  15  *  the Regents of the University of California.  Please see the
  16  *  COPYRIGHT file for full details.  Squid incorporates software
  17  *  developed and/or copyrighted by other sources.  Please see the
  18  *  CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37
  38 #if USE_CARP
  39
  40 void
  41 carpInit(void)
  42 {
  43     /* calculate load factors */
  44     int K = 0;
  45     float a = 0.0;
  46     float Xn;
  47     float P_last;
  48     float X_last;
  49     int k;
  50     peer *p;
  51     for (p = Config.peers; p; p = p->next) {
  52         a += p->carp.load_factor;
  53         K++;
  54     }
  55     if (a == 0.0) {
  56         for (p = Config.peers; p; p = p->next)
  57             p->carp.load_multiplier = 1;
  58         return;
  59     }
  60     /*
  61      * sum of carp-load-factor's for all cache_peer's in squid.conf
  62      * must equal 1.0
  63      */
  64     assert(1000 == (int) (1000.0 * a));
  65     k = 1;
  66     P_last = 0;
  67     p = Config.peers;
  68     p->carp.load_multiplier = pow(K * p->carp.load_factor, 1 / K);
  69     Xn = p->carp.load_multiplier;
  70     P_last = p->carp.load_factor;
  71     X_last = p->carp.load_multiplier;
  72     if (!p->next)
  73         return;
  74     for (p = p->next; p; p = p->next) {
  75         p->carp.load_multiplier = ((K - k + 1) * (p->carp.load_factor - P_last)) / Xn;
  76         p->carp.load_multiplier += pow(X_last, K - k + 1);
  77         p->carp.load_multiplier = pow(p->carp.load_multiplier, 1 / (K - k + 1));
  78         Xn *= p->carp.load_multiplier;
  79         X_last = p->carp.load_multiplier;
  80         k++;
  81         P_last = p->carp.load_factor;
  82     }
  83 }
  84
  85 peer *
  86 carpSelectParent(request_t * request)
  87 {
  88 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> ((sizeof(u_long)*8)-(n))))
  89     const char *c;
  90     peer *p = NULL;
  91     peer *tp;
  92     unsigned long url_hash = 0;
  93     unsigned long combined_hash;
  94     unsigned long high_score = 0;
  95     const char *url = urlCanonical(request);
  96     /* calculate url hash */
  97     debug(39, 2) ("carpSelectParent: CARP Calculating hash for %s\n", url);
  98     for (c = url; *c != 0; c++)
  99         url_hash += ROTATE_LEFT(url_hash, 19) + *c;
 100     /* select peer */
 101     for (tp = Config.peers; tp; tp = tp->next) {
 102         if (0.0 == tp->carp.load_factor)
 103             continue;
 104         if (tp->tcp_up != PEER_TCP_MAGIC_COUNT)
 105             continue;
 106         assert(tp->type == PEER_PARENT);
 107         combined_hash = (url_hash ^ tp->carp.hash);
 108         combined_hash += combined_hash * 0x62531965;
 109         combined_hash = ROTATE_LEFT(combined_hash, 21);
 110         combined_hash = combined_hash * tp->carp.load_multiplier;
 111         debug(39, 3) ("carpSelectParent: %s combined_hash %d\n",
 112             tp->host, combined_hash);
 113         if ((combined_hash > high_score) && neighborUp(tp)) {
 114             p = tp;
 115             high_score = combined_hash;
 116         }
 117     }
 118     if (p)
 119         debug(39, 3) ("carpSelectParent: selected CARP %s\n", p->host);
 120     return p;
 121 }
 122 #endif