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