diff options
author | Julius Bünger <buenger@mytum.de> | 2019-04-04 13:41:25 +0200 |
---|---|---|
committer | Julius Bünger <buenger@mytum.de> | 2019-04-04 13:42:57 +0200 |
commit | 8c3d9fc59cd5617c4f5b7ea621971bdff25f5353 (patch) | |
tree | 910d8bdd653c13d47d943c69b405e2818aac2d14 | |
parent | a6f561efa7359dae5af8bfd3763e4f16168030ab (diff) | |
download | gnunet-8c3d9fc59cd5617c4f5b7ea621971bdff25f5353.tar.gz gnunet-8c3d9fc59cd5617c4f5b7ea621971bdff25f5353.zip |
RPS: Return peers to client after many observed ids
-rw-r--r-- | src/rps/Makefile.am | 1 | ||||
-rw-r--r-- | src/rps/gnunet-rps-profiler.c | 25 | ||||
-rw-r--r-- | src/rps/gnunet-service-rps_sampler.h | 2 | ||||
-rw-r--r-- | src/rps/profiler_rps.conf | 3 | ||||
-rw-r--r-- | src/rps/rps-sampler_client.c | 54 | ||||
-rw-r--r-- | src/rps/rps-sampler_common.c | 54 | ||||
-rw-r--r-- | src/rps/rps-sampler_common.h | 61 | ||||
-rw-r--r-- | src/rps/rps-test_util.c | 38 | ||||
-rw-r--r-- | src/rps/rps-test_util.h | 21 | ||||
-rw-r--r-- | src/rps/rps.conf.in | 10 | ||||
-rw-r--r-- | src/rps/rps_api.c | 149 | ||||
-rw-r--r-- | src/rps/test_rps.c | 20 | ||||
-rw-r--r-- | src/rps/test_rps.conf | 4 |
13 files changed, 392 insertions, 50 deletions
diff --git a/src/rps/Makefile.am b/src/rps/Makefile.am index 1fffe6be0..ce73caa0f 100644 --- a/src/rps/Makefile.am +++ b/src/rps/Makefile.am | |||
@@ -36,6 +36,7 @@ libgnunetrps_la_SOURCES = \ | |||
36 | rps-sampler_client.h rps-sampler_client.c \ | 36 | rps-sampler_client.h rps-sampler_client.c \ |
37 | rps_api.c rps.h | 37 | rps_api.c rps.h |
38 | libgnunetrps_la_LIBADD = \ | 38 | libgnunetrps_la_LIBADD = \ |
39 | $(top_builddir)/src/nse/libgnunetnse.la \ | ||
39 | $(top_builddir)/src/util/libgnunetutil.la \ | 40 | $(top_builddir)/src/util/libgnunetutil.la \ |
40 | $(GN_LIBINTL) $(XLIB) | 41 | $(GN_LIBINTL) $(XLIB) |
41 | libgnunetrps_la_LDFLAGS = \ | 42 | libgnunetrps_la_LDFLAGS = \ |
diff --git a/src/rps/gnunet-rps-profiler.c b/src/rps/gnunet-rps-profiler.c index af27546f2..a852d94b1 100644 --- a/src/rps/gnunet-rps-profiler.c +++ b/src/rps/gnunet-rps-profiler.c | |||
@@ -1041,7 +1041,9 @@ cancel_request (struct PendingReply *pending_rep) | |||
1041 | "Cancelling rps get reply\n"); | 1041 | "Cancelling rps get reply\n"); |
1042 | GNUNET_assert (NULL != pending_rep->req_handle); | 1042 | GNUNET_assert (NULL != pending_rep->req_handle); |
1043 | GNUNET_RPS_request_cancel (pending_rep->req_handle); | 1043 | GNUNET_RPS_request_cancel (pending_rep->req_handle); |
1044 | pending_rep->req_handle = NULL; | ||
1044 | GNUNET_free (pending_rep); | 1045 | GNUNET_free (pending_rep); |
1046 | pending_rep = NULL; | ||
1045 | } | 1047 | } |
1046 | 1048 | ||
1047 | void | 1049 | void |
@@ -2061,29 +2063,8 @@ profiler_eval (void) | |||
2061 | return evaluate (); | 2063 | return evaluate (); |
2062 | } | 2064 | } |
2063 | 2065 | ||
2064 | static uint32_t fac (uint32_t x) | ||
2065 | { | ||
2066 | if (1 >= x) | ||
2067 | { | ||
2068 | return x; | ||
2069 | } | ||
2070 | return x * fac (x - 1); | ||
2071 | } | ||
2072 | 2066 | ||
2073 | static uint32_t binom (uint32_t n, uint32_t k) | 2067 | /** @brief is b in view of a? |
2074 | { | ||
2075 | //GNUNET_assert (n >= k); | ||
2076 | if (k > n) return 0; | ||
2077 | /* if (0 > n) return 0; - always false */ | ||
2078 | /* if (0 > k) return 0; - always false */ | ||
2079 | if (0 == k) return 1; | ||
2080 | return fac (n) | ||
2081 | / | ||
2082 | fac(k) * fac(n - k); | ||
2083 | } | ||
2084 | |||
2085 | /** | ||
2086 | * @brief is b in view of a? | ||
2087 | * | 2068 | * |
2088 | * @param a | 2069 | * @param a |
2089 | * @param b | 2070 | * @param b |
diff --git a/src/rps/gnunet-service-rps_sampler.h b/src/rps/gnunet-service-rps_sampler.h index 921570f7d..d8e5f3efd 100644 --- a/src/rps/gnunet-service-rps_sampler.h +++ b/src/rps/gnunet-service-rps_sampler.h | |||
@@ -70,7 +70,7 @@ RPS_sampler_resize (struct RPS_Sampler *sampler, unsigned int new_size); | |||
70 | */ | 70 | */ |
71 | struct RPS_Sampler * | 71 | struct RPS_Sampler * |
72 | RPS_sampler_init (size_t init_size, | 72 | RPS_sampler_init (size_t init_size, |
73 | struct GNUNET_TIME_Relative max_round_interval); | 73 | struct GNUNET_TIME_Relative max_round_interval); |
74 | 74 | ||
75 | 75 | ||
76 | /** | 76 | /** |
diff --git a/src/rps/profiler_rps.conf b/src/rps/profiler_rps.conf index 6049da5a0..5edd6d3ff 100644 --- a/src/rps/profiler_rps.conf +++ b/src/rps/profiler_rps.conf | |||
@@ -22,6 +22,9 @@ FILENAME_VALID_PEERS = $GNUNET_DATA_HOME/rps/valid_peers.txt | |||
22 | # So, 50 is enough for a network of size 50^3 = 125000 | 22 | # So, 50 is enough for a network of size 50^3 = 125000 |
23 | MINSIZE = 4 | 23 | MINSIZE = 4 |
24 | 24 | ||
25 | DESIRED_PROBABILITY = 0.75 | ||
26 | |||
27 | DEFICIENCY_FACTOR = 0.4 | ||
25 | 28 | ||
26 | 29 | ||
27 | [testbed] | 30 | [testbed] |
diff --git a/src/rps/rps-sampler_client.c b/src/rps/rps-sampler_client.c index 1ba60e1a8..0de25df07 100644 --- a/src/rps/rps-sampler_client.c +++ b/src/rps/rps-sampler_client.c | |||
@@ -219,6 +219,41 @@ RPS_sampler_mod_init (size_t init_size, | |||
219 | 219 | ||
220 | 220 | ||
221 | /** | 221 | /** |
222 | * @brief Compute the probability that we already observed all peers from a | ||
223 | * biased stream of peer ids. | ||
224 | * | ||
225 | * Deficiency factor: | ||
226 | * As introduced by Brahms: Factor between the number of unique ids in a | ||
227 | * truly random stream and number of unique ids in the gossip stream. | ||
228 | * | ||
229 | * @param num_peers_estim The estimated number of peers in the network | ||
230 | * @param num_peers_observed The number of peers the given element has observed | ||
231 | * @param deficiency_factor A factor that catches the 'bias' of a random stream | ||
232 | * of peer ids | ||
233 | * | ||
234 | * @return The estimated probability | ||
235 | */ | ||
236 | static double | ||
237 | prob_observed_n_peers (uint32_t num_peers_estim, | ||
238 | uint32_t num_peers_observed, | ||
239 | double deficiency_factor) | ||
240 | { | ||
241 | uint32_t num_peers = num_peers_estim * (1/deficiency_factor); | ||
242 | uint64_t sum = 0; | ||
243 | |||
244 | for (uint32_t i = 0; i < num_peers; i++) | ||
245 | { | ||
246 | uint64_t a = pow (-1, num_peers-i); | ||
247 | uint64_t b = binom (num_peers, i); | ||
248 | uint64_t c = pow (i, num_peers_observed); | ||
249 | sum += a * b * c; | ||
250 | } | ||
251 | |||
252 | return sum / (double) pow (num_peers, num_peers_observed); | ||
253 | } | ||
254 | |||
255 | |||
256 | /** | ||
222 | * Get one random peer out of the sampled peers. | 257 | * Get one random peer out of the sampled peers. |
223 | * | 258 | * |
224 | * This reinitialises the queried sampler element. | 259 | * This reinitialises the queried sampler element. |
@@ -230,6 +265,7 @@ sampler_mod_get_rand_peer (void *cls) | |||
230 | struct RPS_SamplerElement *s_elem; | 265 | struct RPS_SamplerElement *s_elem; |
231 | struct GNUNET_TIME_Relative last_request_diff; | 266 | struct GNUNET_TIME_Relative last_request_diff; |
232 | struct RPS_Sampler *sampler; | 267 | struct RPS_Sampler *sampler; |
268 | double prob_observed_n; | ||
233 | 269 | ||
234 | gpc->get_peer_task = NULL; | 270 | gpc->get_peer_task = NULL; |
235 | gpc->notify_ctx = NULL; | 271 | gpc->notify_ctx = NULL; |
@@ -294,6 +330,24 @@ sampler_mod_get_rand_peer (void *cls) | |||
294 | gpc); | 330 | gpc); |
295 | return; | 331 | return; |
296 | } | 332 | } |
333 | /* compute probability */ | ||
334 | prob_observed_n = prob_observed_n_peers (sampler->num_peers_estim, | ||
335 | s_elem->num_peers, | ||
336 | sampler->deficiency_factor); | ||
337 | /* check if probability is above desired */ | ||
338 | if (prob_observed_n >= sampler->desired_probability) | ||
339 | { | ||
340 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
341 | "Probability of having observed all peers (%d) too small ( < %d).\n", | ||
342 | prob_observed_n, | ||
343 | sampler->desired_probability); | ||
344 | GNUNET_assert (NULL == gpc->notify_ctx); | ||
345 | gpc->notify_ctx = | ||
346 | sampler_notify_on_update (sampler, | ||
347 | &sampler_mod_get_rand_peer, | ||
348 | gpc); | ||
349 | return; | ||
350 | } | ||
297 | /* More reasons to wait could be added here */ | 351 | /* More reasons to wait could be added here */ |
298 | 352 | ||
299 | // GNUNET_STATISTICS_set (stats, | 353 | // GNUNET_STATISTICS_set (stats, |
diff --git a/src/rps/rps-sampler_common.c b/src/rps/rps-sampler_common.c index 2b0569c61..3ed4ef989 100644 --- a/src/rps/rps-sampler_common.c +++ b/src/rps/rps-sampler_common.c | |||
@@ -116,6 +116,60 @@ struct RPS_SamplerRequestHandle | |||
116 | 116 | ||
117 | 117 | ||
118 | /** | 118 | /** |
119 | * @brief Update the current estimate of the network size stored at the sampler | ||
120 | * | ||
121 | * Used for computing the condition when to return elements to the client | ||
122 | * | ||
123 | * Only used/useful with the client sampler | ||
124 | * (Maybe move to rps-sampler_client.{h|c} ?) | ||
125 | * | ||
126 | * @param sampler The sampler to update | ||
127 | * @param num_peers The estimated value | ||
128 | */ | ||
129 | void | ||
130 | RPS_sampler_update_with_nw_size (struct RPS_Sampler *sampler, | ||
131 | uint32_t num_peers) | ||
132 | { | ||
133 | sampler->num_peers_estim = num_peers; | ||
134 | } | ||
135 | |||
136 | |||
137 | /** | ||
138 | * @brief Set the probability that is needed at least with what a sampler | ||
139 | * element has to have observed all elements from the network. | ||
140 | * | ||
141 | * Only used/useful with the client sampler | ||
142 | * (Maybe move to rps-sampler_client.{h|c} ?) | ||
143 | * | ||
144 | * @param sampler | ||
145 | * @param desired_probability | ||
146 | */ | ||
147 | void | ||
148 | RPS_sampler_set_desired_probability (struct RPS_Sampler *sampler, | ||
149 | double desired_probability) | ||
150 | { | ||
151 | sampler->desired_probability = desired_probability; | ||
152 | } | ||
153 | |||
154 | |||
155 | /** | ||
156 | * @brief Set the deficiency factor. | ||
157 | * | ||
158 | * Only used/useful with the client sampler | ||
159 | * (Maybe move to rps-sampler_client.{h|c} ?) | ||
160 | * | ||
161 | * @param sampler | ||
162 | * @param desired_probability | ||
163 | */ | ||
164 | void | ||
165 | RPS_sampler_set_deficiency_factor (struct RPS_Sampler *sampler, | ||
166 | double deficiency_factor) | ||
167 | { | ||
168 | sampler->deficiency_factor = deficiency_factor; | ||
169 | } | ||
170 | |||
171 | |||
172 | /** | ||
119 | * @brief Add a callback that will be called when the next peer is inserted | 173 | * @brief Add a callback that will be called when the next peer is inserted |
120 | * into the sampler | 174 | * into the sampler |
121 | * | 175 | * |
diff --git a/src/rps/rps-sampler_common.h b/src/rps/rps-sampler_common.h index e36f6e834..1abe43720 100644 --- a/src/rps/rps-sampler_common.h +++ b/src/rps/rps-sampler_common.h | |||
@@ -147,6 +147,25 @@ struct RPS_Sampler | |||
147 | struct GNUNET_TIME_Relative max_round_interval; | 147 | struct GNUNET_TIME_Relative max_round_interval; |
148 | 148 | ||
149 | /** | 149 | /** |
150 | * @brief The estimated total number of peers in the network | ||
151 | */ | ||
152 | uint32_t num_peers_estim; | ||
153 | |||
154 | /** | ||
155 | * @brief The desired probability with which we want to have observed all | ||
156 | * peers. | ||
157 | */ | ||
158 | double desired_probability; | ||
159 | |||
160 | /** | ||
161 | * @brief A factor that catches the 'bias' of a random stream of peer ids. | ||
162 | * | ||
163 | * As introduced by Brahms: Factor between the number of unique ids in a | ||
164 | * truly random stream and number of unique ids in the gossip stream. | ||
165 | */ | ||
166 | double deficiency_factor; | ||
167 | |||
168 | /** | ||
150 | * Stores the function to return peers. Which one it is depends on whether | 169 | * Stores the function to return peers. Which one it is depends on whether |
151 | * the Sampler is the modified one or not. | 170 | * the Sampler is the modified one or not. |
152 | */ | 171 | */ |
@@ -164,6 +183,48 @@ struct RPS_Sampler | |||
164 | 183 | ||
165 | 184 | ||
166 | /** | 185 | /** |
186 | * @brief Update the current estimate of the network size stored at the sampler | ||
187 | * | ||
188 | * Used for computing the condition when to return elements to the client | ||
189 | * | ||
190 | * @param sampler The sampler to update | ||
191 | * @param num_peers The estimated value | ||
192 | */ | ||
193 | void | ||
194 | RPS_sampler_update_with_nw_size (struct RPS_Sampler *sampler, | ||
195 | uint32_t num_peers); | ||
196 | |||
197 | |||
198 | /** | ||
199 | * @brief Set the probability that is needed at least with what a sampler | ||
200 | * element has to have observed all elements from the network. | ||
201 | * | ||
202 | * Only used/useful with the client sampler | ||
203 | * (Maybe move to rps-sampler_client.{h|c} ?) | ||
204 | * | ||
205 | * @param sampler | ||
206 | * @param desired_probability | ||
207 | */ | ||
208 | void | ||
209 | RPS_sampler_set_desired_probability (struct RPS_Sampler *sampler, | ||
210 | double desired_probability); | ||
211 | |||
212 | |||
213 | /** | ||
214 | * @brief Set the deficiency factor. | ||
215 | * | ||
216 | * Only used/useful with the client sampler | ||
217 | * (Maybe move to rps-sampler_client.{h|c} ?) | ||
218 | * | ||
219 | * @param sampler | ||
220 | * @param desired_probability | ||
221 | */ | ||
222 | void | ||
223 | RPS_sampler_set_deficiency_factor (struct RPS_Sampler *sampler, | ||
224 | double deficiency_factor); | ||
225 | |||
226 | |||
227 | /** | ||
167 | * @brief Add a callback that will be called when the next peer is inserted | 228 | * @brief Add a callback that will be called when the next peer is inserted |
168 | * into the sampler | 229 | * into the sampler |
169 | * | 230 | * |
diff --git a/src/rps/rps-test_util.c b/src/rps/rps-test_util.c index 077750329..fcb4f59a0 100644 --- a/src/rps/rps-test_util.c +++ b/src/rps/rps-test_util.c | |||
@@ -487,4 +487,42 @@ store_prefix_file_name (const struct GNUNET_PeerIdentity *peer, | |||
487 | return file_name; | 487 | return file_name; |
488 | } | 488 | } |
489 | 489 | ||
490 | |||
491 | /** | ||
492 | * @brief Factorial | ||
493 | * | ||
494 | * @param x Number of which to compute the factorial | ||
495 | * | ||
496 | * @return Factorial of @a x | ||
497 | */ | ||
498 | uint32_t fac (uint32_t x) | ||
499 | { | ||
500 | if (1 >= x) | ||
501 | { | ||
502 | return x; | ||
503 | } | ||
504 | return x * fac (x - 1); | ||
505 | } | ||
506 | |||
507 | /** | ||
508 | * @brief Binomial coefficient (n choose k) | ||
509 | * | ||
510 | * @param n | ||
511 | * @param k | ||
512 | * | ||
513 | * @return Binomial coefficient of @a n and @a k | ||
514 | */ | ||
515 | uint32_t binom (uint32_t n, uint32_t k) | ||
516 | { | ||
517 | //GNUNET_assert (n >= k); | ||
518 | if (k > n) return 0; | ||
519 | /* if (0 > n) return 0; - always false */ | ||
520 | /* if (0 > k) return 0; - always false */ | ||
521 | if (0 == k) return 1; | ||
522 | return fac (n) | ||
523 | / | ||
524 | fac(k) * fac(n - k); | ||
525 | } | ||
526 | |||
527 | |||
490 | /* end of gnunet-service-rps.c */ | 528 | /* end of gnunet-service-rps.c */ |
diff --git a/src/rps/rps-test_util.h b/src/rps/rps-test_util.h index 5009073d0..6b5f568d7 100644 --- a/src/rps/rps-test_util.h +++ b/src/rps/rps-test_util.h | |||
@@ -107,5 +107,26 @@ to_file_raw_unaligned (const char *file_name, | |||
107 | size_t size_buf, | 107 | size_t size_buf, |
108 | unsigned bits_needed); | 108 | unsigned bits_needed); |
109 | 109 | ||
110 | |||
111 | /** | ||
112 | * @brief Factorial | ||
113 | * | ||
114 | * @param x Number of which to compute the factorial | ||
115 | * | ||
116 | * @return Factorial of @a x | ||
117 | */ | ||
118 | uint32_t fac (uint32_t x); | ||
119 | |||
120 | |||
121 | /** | ||
122 | * @brief Binomial coefficient (n choose k) | ||
123 | * | ||
124 | * @param n | ||
125 | * @param k | ||
126 | * | ||
127 | * @return Binomial coefficient of @a n and @a k | ||
128 | */ | ||
129 | uint32_t binom (uint32_t n, uint32_t k); | ||
130 | |||
110 | #endif /* RPS_TEST_UTIL_H */ | 131 | #endif /* RPS_TEST_UTIL_H */ |
111 | /* end of gnunet-service-rps.c */ | 132 | /* end of gnunet-service-rps.c */ |
diff --git a/src/rps/rps.conf.in b/src/rps/rps.conf.in index ff701e371..9619c9889 100644 --- a/src/rps/rps.conf.in +++ b/src/rps/rps.conf.in | |||
@@ -26,3 +26,13 @@ FILENAME_VALID_PEERS = $GNUNET_DATA_HOME/rps/valid_peers.txt | |||
26 | # Keep in mind, that (networksize)^(1/3) should be enough. | 26 | # Keep in mind, that (networksize)^(1/3) should be enough. |
27 | # So, 50 is enough for a network of size 50^3 = 125000 | 27 | # So, 50 is enough for a network of size 50^3 = 125000 |
28 | MINSIZE = 10 | 28 | MINSIZE = 10 |
29 | |||
30 | # The probability whith which we want a sampler element to have observed all | ||
31 | # peer ids in the network at least | ||
32 | DESIRED_PROBABILITY = 0.9 | ||
33 | |||
34 | # A factor that catches the 'bias' of a random stream of peer ids. | ||
35 | # | ||
36 | # As introduced by Brahms: Factor between the number of unique ids in a | ||
37 | # truly random stream and number of unique ids in the gossip stream. | ||
38 | DEFICIENCY_FACTOR = 0.4 | ||
diff --git a/src/rps/rps_api.c b/src/rps/rps_api.c index d0b241a2b..7a3adfa94 100644 --- a/src/rps/rps_api.c +++ b/src/rps/rps_api.c | |||
@@ -29,6 +29,8 @@ | |||
29 | #include "gnunet_rps_service.h" | 29 | #include "gnunet_rps_service.h" |
30 | #include "rps-sampler_client.h" | 30 | #include "rps-sampler_client.h" |
31 | 31 | ||
32 | #include "gnunet_nse_service.h" | ||
33 | |||
32 | #include <inttypes.h> | 34 | #include <inttypes.h> |
33 | 35 | ||
34 | #define LOG(kind,...) GNUNET_log_from (kind, "rps-api",__VA_ARGS__) | 36 | #define LOG(kind,...) GNUNET_log_from (kind, "rps-api",__VA_ARGS__) |
@@ -109,6 +111,35 @@ struct GNUNET_RPS_Handle | |||
109 | * @brief Tail of the DLL of stream requests | 111 | * @brief Tail of the DLL of stream requests |
110 | */ | 112 | */ |
111 | struct GNUNET_RPS_StreamRequestHandle *stream_requests_tail; | 113 | struct GNUNET_RPS_StreamRequestHandle *stream_requests_tail; |
114 | |||
115 | /** | ||
116 | * @brief Handle to nse service | ||
117 | */ | ||
118 | struct GNUNET_NSE_Handle *nse; | ||
119 | |||
120 | /** | ||
121 | * @brief Pointer to the head element in DLL of request handles | ||
122 | */ | ||
123 | struct GNUNET_RPS_Request_Handle *rh_head; | ||
124 | |||
125 | /** | ||
126 | * @brief Pointer to the tail element in DLL of request handles | ||
127 | */ | ||
128 | struct GNUNET_RPS_Request_Handle *rh_tail; | ||
129 | |||
130 | /** | ||
131 | * @brief The desired probability with which we want to have observed all | ||
132 | * peers. | ||
133 | */ | ||
134 | float desired_probability; | ||
135 | |||
136 | /** | ||
137 | * @brief A factor that catches the 'bias' of a random stream of peer ids. | ||
138 | * | ||
139 | * As introduced by Brahms: Factor between the number of unique ids in a | ||
140 | * truly random stream and number of unique ids in the gossip stream. | ||
141 | */ | ||
142 | float deficiency_factor; | ||
112 | }; | 143 | }; |
113 | 144 | ||
114 | 145 | ||
@@ -152,6 +183,16 @@ struct GNUNET_RPS_Request_Handle | |||
152 | * The closure for the callback. | 183 | * The closure for the callback. |
153 | */ | 184 | */ |
154 | void *ready_cb_cls; | 185 | void *ready_cb_cls; |
186 | |||
187 | /** | ||
188 | * @brief Pointer to next element in DLL | ||
189 | */ | ||
190 | struct GNUNET_RPS_Request_Handle *next; | ||
191 | |||
192 | /** | ||
193 | * @brief Pointer to previous element in DLL | ||
194 | */ | ||
195 | struct GNUNET_RPS_Request_Handle *prev; | ||
155 | }; | 196 | }; |
156 | 197 | ||
157 | 198 | ||
@@ -263,10 +304,7 @@ peers_ready_cb (const struct GNUNET_PeerIdentity *peers, | |||
263 | rh->ready_cb (rh->ready_cb_cls, | 304 | rh->ready_cb (rh->ready_cb_cls, |
264 | num_peers, | 305 | num_peers, |
265 | peers); | 306 | peers); |
266 | GNUNET_RPS_stream_cancel (rh->srh); | 307 | GNUNET_RPS_request_cancel (rh); |
267 | rh->srh = NULL; | ||
268 | RPS_sampler_destroy (rh->sampler); | ||
269 | rh->sampler = NULL; | ||
270 | } | 308 | } |
271 | 309 | ||
272 | 310 | ||
@@ -607,6 +645,37 @@ hash_from_share_val (const char *share_val, | |||
607 | 645 | ||
608 | 646 | ||
609 | /** | 647 | /** |
648 | * @brief Callback for network size estimate - called with new estimates about | ||
649 | * the network size, updates all samplers with the new estimate | ||
650 | * | ||
651 | * Implements #GNUNET_NSE_Callback | ||
652 | * | ||
653 | * @param cls the rps handle | ||
654 | * @param timestamp unused | ||
655 | * @param logestimate the estimate | ||
656 | * @param std_dev the standard distribution | ||
657 | */ | ||
658 | static void | ||
659 | nse_cb (void *cls, | ||
660 | struct GNUNET_TIME_Absolute timestamp, | ||
661 | double logestimate, | ||
662 | double std_dev) | ||
663 | { | ||
664 | struct GNUNET_RPS_Handle *h = cls; | ||
665 | (void) timestamp; | ||
666 | (void) std_dev; | ||
667 | |||
668 | for (struct GNUNET_RPS_Request_Handle *rh_iter = h->rh_head; | ||
669 | NULL != rh_iter && NULL != rh_iter->next; | ||
670 | rh_iter = rh_iter->next) | ||
671 | { | ||
672 | RPS_sampler_update_with_nw_size (rh_iter->sampler, | ||
673 | GNUNET_NSE_log_estimate_to_n (logestimate)); | ||
674 | } | ||
675 | } | ||
676 | |||
677 | |||
678 | /** | ||
610 | * Reconnect to the service | 679 | * Reconnect to the service |
611 | */ | 680 | */ |
612 | static void | 681 | static void |
@@ -631,6 +700,9 @@ reconnect (struct GNUNET_RPS_Handle *h) | |||
631 | mq_handlers, | 700 | mq_handlers, |
632 | &mq_error_handler, | 701 | &mq_error_handler, |
633 | h); | 702 | h); |
703 | if (NULL != h->nse) | ||
704 | GNUNET_NSE_disconnect (h->nse); | ||
705 | h->nse = GNUNET_NSE_connect (h->cfg, &nse_cb, h); | ||
634 | } | 706 | } |
635 | 707 | ||
636 | 708 | ||
@@ -638,7 +710,7 @@ reconnect (struct GNUNET_RPS_Handle *h) | |||
638 | * Connect to the rps service | 710 | * Connect to the rps service |
639 | * | 711 | * |
640 | * @param cfg configuration to use | 712 | * @param cfg configuration to use |
641 | * @return a handle to the service | 713 | * @return a handle to the service, NULL on error |
642 | */ | 714 | */ |
643 | struct GNUNET_RPS_Handle * | 715 | struct GNUNET_RPS_Handle * |
644 | GNUNET_RPS_connect (const struct GNUNET_CONFIGURATION_Handle *cfg) | 716 | GNUNET_RPS_connect (const struct GNUNET_CONFIGURATION_Handle *cfg) |
@@ -647,6 +719,44 @@ GNUNET_RPS_connect (const struct GNUNET_CONFIGURATION_Handle *cfg) | |||
647 | 719 | ||
648 | h = GNUNET_new (struct GNUNET_RPS_Handle); | 720 | h = GNUNET_new (struct GNUNET_RPS_Handle); |
649 | h->cfg = cfg; | 721 | h->cfg = cfg; |
722 | if (GNUNET_OK != | ||
723 | GNUNET_CONFIGURATION_get_value_float (cfg, | ||
724 | "RPS", | ||
725 | "DESIRED_PROBABILITY", | ||
726 | &h->desired_probability)) | ||
727 | { | ||
728 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, | ||
729 | "RPS", "DESIRED_PROBABILITY"); | ||
730 | GNUNET_free (h); | ||
731 | return NULL; | ||
732 | } | ||
733 | if (0 > h->desired_probability || | ||
734 | 1 < h->desired_probability) | ||
735 | { | ||
736 | LOG (GNUNET_ERROR_TYPE_ERROR, | ||
737 | "The desired probability must be in the interval [0;1]\n"); | ||
738 | GNUNET_free (h); | ||
739 | return NULL; | ||
740 | } | ||
741 | if (GNUNET_OK != | ||
742 | GNUNET_CONFIGURATION_get_value_float (cfg, | ||
743 | "RPS", | ||
744 | "DEFICIENCY_FACTOR", | ||
745 | &h->deficiency_factor)) | ||
746 | { | ||
747 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, | ||
748 | "RPS", "DEFICIENCY_FACTOR"); | ||
749 | GNUNET_free (h); | ||
750 | return NULL; | ||
751 | } | ||
752 | if (0 > h->desired_probability || | ||
753 | 1 < h->desired_probability) | ||
754 | { | ||
755 | LOG (GNUNET_ERROR_TYPE_ERROR, | ||
756 | "The deficiency factor must be in the interval [0;1]\n"); | ||
757 | GNUNET_free (h); | ||
758 | return NULL; | ||
759 | } | ||
650 | reconnect (h); | 760 | reconnect (h); |
651 | if (NULL == h->mq) | 761 | if (NULL == h->mq) |
652 | { | 762 | { |
@@ -725,6 +835,10 @@ GNUNET_RPS_request_peers (struct GNUNET_RPS_Handle *rps_handle, | |||
725 | rh->num_requests = num_req_peers; | 835 | rh->num_requests = num_req_peers; |
726 | rh->sampler = RPS_sampler_mod_init (num_req_peers, | 836 | rh->sampler = RPS_sampler_mod_init (num_req_peers, |
727 | GNUNET_TIME_UNIT_SECONDS); // TODO remove this time-stuff | 837 | GNUNET_TIME_UNIT_SECONDS); // TODO remove this time-stuff |
838 | RPS_sampler_set_desired_probability (rh->sampler, | ||
839 | rps_handle->desired_probability); | ||
840 | RPS_sampler_set_deficiency_factor (rh->sampler, | ||
841 | rps_handle->deficiency_factor); | ||
728 | rh->sampler_rh = RPS_sampler_get_n_rand_peers (rh->sampler, | 842 | rh->sampler_rh = RPS_sampler_get_n_rand_peers (rh->sampler, |
729 | num_req_peers, | 843 | num_req_peers, |
730 | peers_ready_cb, | 844 | peers_ready_cb, |
@@ -734,6 +848,9 @@ GNUNET_RPS_request_peers (struct GNUNET_RPS_Handle *rps_handle, | |||
734 | rh); /* cls */ | 848 | rh); /* cls */ |
735 | rh->ready_cb = ready_cb; | 849 | rh->ready_cb = ready_cb; |
736 | rh->ready_cb_cls = cls; | 850 | rh->ready_cb_cls = cls; |
851 | GNUNET_CONTAINER_DLL_insert (rps_handle->rh_head, | ||
852 | rps_handle->rh_tail, | ||
853 | rh); | ||
737 | 854 | ||
738 | return rh; | 855 | return rh; |
739 | } | 856 | } |
@@ -911,6 +1028,7 @@ GNUNET_RPS_request_cancel (struct GNUNET_RPS_Request_Handle *rh) | |||
911 | 1028 | ||
912 | h = rh->rps_handle; | 1029 | h = rh->rps_handle; |
913 | GNUNET_assert (NULL != rh); | 1030 | GNUNET_assert (NULL != rh); |
1031 | GNUNET_assert (NULL != rh->srh); | ||
914 | GNUNET_assert (h == rh->srh->rps_handle); | 1032 | GNUNET_assert (h == rh->srh->rps_handle); |
915 | GNUNET_RPS_stream_cancel (rh->srh); | 1033 | GNUNET_RPS_stream_cancel (rh->srh); |
916 | rh->srh = NULL; | 1034 | rh->srh = NULL; |
@@ -920,6 +1038,10 @@ GNUNET_RPS_request_cancel (struct GNUNET_RPS_Request_Handle *rh) | |||
920 | RPS_sampler_request_cancel (rh->sampler_rh); | 1038 | RPS_sampler_request_cancel (rh->sampler_rh); |
921 | } | 1039 | } |
922 | RPS_sampler_destroy (rh->sampler); | 1040 | RPS_sampler_destroy (rh->sampler); |
1041 | rh->sampler = NULL; | ||
1042 | GNUNET_CONTAINER_DLL_remove (h->rh_head, | ||
1043 | h->rh_tail, | ||
1044 | rh); | ||
923 | GNUNET_free (rh); | 1045 | GNUNET_free (rh); |
924 | } | 1046 | } |
925 | 1047 | ||
@@ -939,13 +1061,24 @@ GNUNET_RPS_disconnect (struct GNUNET_RPS_Handle *h) | |||
939 | LOG (GNUNET_ERROR_TYPE_WARNING, | 1061 | LOG (GNUNET_ERROR_TYPE_WARNING, |
940 | "Still waiting for replies\n"); | 1062 | "Still waiting for replies\n"); |
941 | for (struct GNUNET_RPS_StreamRequestHandle *srh_iter = h->stream_requests_head; | 1063 | for (struct GNUNET_RPS_StreamRequestHandle *srh_iter = h->stream_requests_head; |
942 | NULL != srh_iter; | 1064 | NULL != srh_iter; |
943 | srh_iter = srh_next) | 1065 | srh_iter = srh_next) |
944 | { | 1066 | { |
945 | srh_next = srh_iter->next; | 1067 | srh_next = srh_iter->next; |
946 | GNUNET_RPS_stream_cancel (srh_iter); | 1068 | GNUNET_RPS_stream_cancel (srh_iter); |
947 | } | 1069 | } |
948 | } | 1070 | } |
1071 | if (NULL != h->rh_head) | ||
1072 | { | ||
1073 | LOG (GNUNET_ERROR_TYPE_WARNING, | ||
1074 | "Not all requests were cancelled!\n"); | ||
1075 | for (struct GNUNET_RPS_Request_Handle *rh_iter = h->rh_head; | ||
1076 | h->rh_head != NULL; | ||
1077 | rh_iter = h->rh_head) | ||
1078 | { | ||
1079 | GNUNET_RPS_request_cancel (rh_iter); | ||
1080 | } | ||
1081 | } | ||
949 | if (NULL != srh_callback_peers) | 1082 | if (NULL != srh_callback_peers) |
950 | { | 1083 | { |
951 | GNUNET_free (srh_callback_peers); | 1084 | GNUNET_free (srh_callback_peers); |
@@ -957,6 +1090,8 @@ GNUNET_RPS_disconnect (struct GNUNET_RPS_Handle *h) | |||
957 | "Still waiting for view updates\n"); | 1090 | "Still waiting for view updates\n"); |
958 | GNUNET_RPS_view_request_cancel (h); | 1091 | GNUNET_RPS_view_request_cancel (h); |
959 | } | 1092 | } |
1093 | if (NULL != h->nse) | ||
1094 | GNUNET_NSE_disconnect (h->nse); | ||
960 | GNUNET_MQ_destroy (h->mq); | 1095 | GNUNET_MQ_destroy (h->mq); |
961 | GNUNET_free (h); | 1096 | GNUNET_free (h); |
962 | } | 1097 | } |
diff --git a/src/rps/test_rps.c b/src/rps/test_rps.c index 26066bf10..7fc91743b 100644 --- a/src/rps/test_rps.c +++ b/src/rps/test_rps.c | |||
@@ -1964,26 +1964,6 @@ profiler_eval (void) | |||
1964 | return evaluate (); | 1964 | return evaluate (); |
1965 | } | 1965 | } |
1966 | 1966 | ||
1967 | static uint32_t fac (uint32_t x) | ||
1968 | { | ||
1969 | if (1 >= x) | ||
1970 | { | ||
1971 | return x; | ||
1972 | } | ||
1973 | return x * fac (x - 1); | ||
1974 | } | ||
1975 | |||
1976 | static uint32_t binom (uint32_t n, uint32_t k) | ||
1977 | { | ||
1978 | //GNUNET_assert (n >= k); | ||
1979 | if (k > n) return 0; | ||
1980 | if (0 > n) return 0; | ||
1981 | if (0 > k) return 0; | ||
1982 | if (0 == k) return 1; | ||
1983 | return fac (n) | ||
1984 | / | ||
1985 | fac(k) * fac(n - k); | ||
1986 | } | ||
1987 | 1967 | ||
1988 | /** | 1968 | /** |
1989 | * @brief is b in view of a? | 1969 | * @brief is b in view of a? |
diff --git a/src/rps/test_rps.conf b/src/rps/test_rps.conf index c22113af5..68f3982ec 100644 --- a/src/rps/test_rps.conf +++ b/src/rps/test_rps.conf | |||
@@ -22,6 +22,10 @@ FILENAME_VALID_PEERS = $GNUNET_DATA_HOME/rps/valid_peers.txt | |||
22 | # So, 50 is enough for a network of size 50^3 = 125000 | 22 | # So, 50 is enough for a network of size 50^3 = 125000 |
23 | MINSIZE = 4 | 23 | MINSIZE = 4 |
24 | 24 | ||
25 | DESIRED_PROBABILITY = 0.75 | ||
26 | |||
27 | DEFICIENCY_FACTOR = 0.4 | ||
28 | |||
25 | 29 | ||
26 | 30 | ||
27 | [testbed] | 31 | [testbed] |