]>
Commit | Line | Data |
---|---|---|
afd88fbe | 1 | /* |
e25c139f | 2 | * $Id: carp.cc,v 1.4 1998/07/22 20:37:04 wessels Exp $ |
afd88fbe | 3 | * |
4 | * DEBUG: section 44 Cache Array Routing Protocol | |
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 | |
14 | * Duane Wessels and the University of California San Diego. Please | |
15 | * see the COPYRIGHT file for full details. Squid incorporates | |
16 | * software developed and/or copyrighted by other sources. Please see | |
17 | * the CREDITS file for full details. | |
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; | |
45 | float X; | |
46 | float Xn; | |
47 | float n; | |
48 | int k; | |
49 | peer *p; | |
50 | for (p = Config.peers; p; p = p->next) { | |
51 | a += p->carp.load_factor; | |
52 | K++; | |
53 | } | |
0cdcddb9 | 54 | if (a == 0.0) |
afd88fbe | 55 | /* CARP load factors not configured */ |
56 | return; | |
57 | /* | |
58 | * sum of carp-load-factor's for all cache_peer's in squid.conf | |
59 | * must equal 1.0 | |
60 | */ | |
61 | assert(a == 1.0); | |
62 | k = 1; | |
63 | n = 0; | |
64 | Xn = 0; | |
65 | for (p = Config.peers; p; p = p->next) { | |
66 | X = pow(K * p->carp.load_factor, 1 / K); | |
67 | if (Xn == 0) | |
68 | Xn = X; | |
69 | else | |
70 | Xn *= X; | |
71 | p->carp.load_multiplier = ((K - k + 1) * (p->carp.load_factor - n)) / Xn | |
72 | ; | |
73 | k++; | |
74 | n = p->carp.load_factor; | |
75 | } | |
76 | } | |
77 | ||
78 | peer * | |
79 | carpSelectParent(request_t * request) | |
80 | { | |
81 | const char *c; | |
82 | peer *p = NULL; | |
83 | peer *tp; | |
84 | unsigned long url_hash = 0; | |
85 | unsigned long combined_hash; | |
86 | unsigned long high_score = 0; | |
87 | const char *url = urlCanonical(request); | |
88 | /* calculate url hash */ | |
89 | debug(44, 2) ("carpSelectParent: CARP Calculating hash for %s\n", url); | |
90 | for (c = url; *c != 0; c++) | |
91 | url_hash += (url_hash << 19) + *c; | |
92 | /* select peer */ | |
93 | for (tp = Config.peers; tp; tp = tp->next) { | |
94 | if (p->carp.load_factor == 0.0) | |
0cdcddb9 | 95 | continue; |
afd88fbe | 96 | assert(p->type == PEER_PARENT); |
97 | combined_hash = (url_hash ^ tp->carp.hash); | |
98 | combined_hash += combined_hash * 0x62531965; | |
99 | combined_hash = combined_hash << 21; | |
100 | combined_hash = combined_hash * tp->carp.load_multiplier; | |
101 | debug(44, 3) ("carpSelectParent: %s combined_hash %d\n", | |
0cdcddb9 | 102 | tp->host, combined_hash); |
afd88fbe | 103 | if ((combined_hash > high_score) && neighborUp(tp)) { |
104 | p = tp; | |
105 | high_score = combined_hash; | |
106 | } | |
107 | } | |
108 | if (p) | |
0cdcddb9 | 109 | debug(44, 3) ("carpSelectParent: selected CARP %s\n", p->host); |
afd88fbe | 110 | return p; |
111 | } | |
112 | #endif |