diff options
Diffstat (limited to 'src/rps/rps-sampler_client.c')
-rw-r--r-- | src/rps/rps-sampler_client.c | 54 |
1 files changed, 54 insertions, 0 deletions
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, |