GNUnet  0.11.x
Data Structures | Macros | Typedefs | Functions | Variables
rps-sampler_client.c File Reference
#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_statistics_service.h"
#include "rps.h"
#include "rps-sampler_common.h"
#include "gnunet-service-rps_sampler.h"
#include "gnunet-service-rps_sampler_elem.h"
#include <math.h>
#include <inttypes.h>
#include "rps-test_util.h"
Include dependency graph for rps-sampler_client.c:

Go to the source code of this file.

Data Structures

struct  SamplerNotifyUpdateCTX
 Context for a callback. More...
 
struct  RPS_SamplerRequestHandle
 Closure to _get_n_rand_peers_ready_cb() More...
 
struct  RPS_SamplerRequestHandleSingleInfo
 Closure to _get_rand_peer_info() More...
 

Macros

#define LOG(kind, ...)   GNUNET_log_from (kind, "rps-sampler", __VA_ARGS__)
 

Typedefs

typedef void(* SamplerNotifyUpdateCB) (void *cls)
 Callback called each time a new peer was put into the sampler. More...
 
typedef void(* RPS_get_peers_type) (void *cls)
 Type of function used to differentiate between modified and not modified Sampler. More...
 

Functions

static void sampler_mod_get_rand_peer (void *cls)
 Get one random peer out of the sampled peers. More...
 
struct RPS_SamplerRPS_sampler_mod_init (size_t init_size, struct GNUNET_TIME_Relative max_round_interval)
 Initialise a modified tuple of sampler elements. More...
 
static double prob_observed_n_peers (uint32_t num_peers_estim, uint32_t num_peers_observed, double deficiency_factor)
 Compute the probability that we already observed all peers from a biased stream of peer ids. More...
 

Variables

static size_t min_size
 Global sampler variable. More...
 
static size_t max_size
 The maximal size the extended sampler elements should grow to. More...
 
static uint32_t client_get_index
 The size the extended sampler elements currently have. More...
 

Macro Definition Documentation

◆ LOG

#define LOG (   kind,
  ... 
)    GNUNET_log_from (kind, "rps-sampler", __VA_ARGS__)

Definition at line 40 of file rps-sampler_client.c.

Referenced by sampler_mod_get_rand_peer().

Typedef Documentation

◆ SamplerNotifyUpdateCB

typedef void(* SamplerNotifyUpdateCB) (void *cls)

Callback called each time a new peer was put into the sampler.

Parameters
clsA possibly given closure

Definition at line 64 of file rps-sampler_client.c.

◆ RPS_get_peers_type

typedef void(* RPS_get_peers_type) (void *cls)

Type of function used to differentiate between modified and not modified Sampler.

Definition at line 100 of file rps-sampler_client.c.

Function Documentation

◆ sampler_mod_get_rand_peer()

static void sampler_mod_get_rand_peer ( void *  cls)
static

Get one random peer out of the sampled peers.

We might want to reinitialise this sampler after giving the corrsponding peer to the client.

This reinitialises the queried sampler element.

  • How many time remains untile the next round has started? */
  • check if probability is above desired */

Definition at line 302 of file rps-sampler_client.c.

References GNUNET_TIME_Absolute::abs_value_us, SamplerNotifyUpdateCTX::cls, GetPeerCls::cont, GetPeerCls::cont_cls, EMPTY, GetPeerCls::get_peer_task, GNUNET_assert, GNUNET_CONTAINER_DLL_remove, GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_TIME_absolute_get(), GNUNET_TIME_absolute_get_difference(), GNUNET_TIME_UNIT_FOREVER_ABS, RPS_SamplerRequestHandle::gpc_head, RPS_SamplerRequestHandleSingleInfo::gpc_head, RPS_SamplerRequestHandle::gpc_tail, RPS_SamplerRequestHandleSingleInfo::gpc_tail, GetPeerCls::id, RPS_SamplerElement::is_empty, RPS_SamplerElement::last_client_request, LOG, RPS_Sampler::max_round_interval, GetPeerCls::notify_ctx, RPS_SamplerElement::num_peers, RPS_SamplerElement::peer_id, GNUNET_TIME_Relative::rel_value_us, GetPeerCls::req_handle, GetPeerCls::req_single_info_handle, RPS_sampler_elem_reinit(), RPS_SamplerRequestHandle::sampler, RPS_SamplerRequestHandleSingleInfo::sampler, RPS_Sampler::sampler_elements, sampler_notify_on_update(), and RPS_Sampler::sampler_size.

Referenced by RPS_sampler_mod_init().

303 {
304  struct GetPeerCls *gpc = cls;
305  struct RPS_SamplerElement *s_elem;
306  struct GNUNET_TIME_Relative last_request_diff;
307  struct RPS_Sampler *sampler;
308  double prob_observed_n;
309  uint32_t num_observed;
310 
311  gpc->get_peer_task = NULL;
312  gpc->notify_ctx = NULL;
313  GNUNET_assert ((NULL != gpc->req_handle) ||
314  (NULL != gpc->req_single_info_handle));
315  if (NULL != gpc->req_handle)
316  sampler = gpc->req_handle->sampler;
317  else
318  sampler = gpc->req_single_info_handle->sampler;
319 
320  LOG (GNUNET_ERROR_TYPE_DEBUG, "Single peer was requested\n");
321 
322  /* Cycle the #client_get_index one step further */
324 
325  s_elem = sampler->sampler_elements[client_get_index];
326  *gpc->id = s_elem->peer_id;
327  GNUNET_assert (NULL != s_elem);
328 
329  if (EMPTY == s_elem->is_empty)
330  {
332  "Sampler_mod element empty, rescheduling.\n");
333  GNUNET_assert (NULL == gpc->notify_ctx);
334  gpc->notify_ctx =
335  sampler_notify_on_update (sampler,
337  gpc);
338  return;
339  }
340 
341  /* Check whether we may use this sampler to give it back to the client */
342  if (GNUNET_TIME_UNIT_FOREVER_ABS.abs_value_us !=
344  {
345  // TODO remove this condition at least for the client sampler
346  last_request_diff =
349  /* We're not going to give it back now if it was
350  * already requested by a client this round */
351  if (last_request_diff.rel_value_us <
353  {
355  "Last client request on this sampler was less than max round interval ago -- scheduling for later\n");
357  // inv_last_request_diff =
358  // GNUNET_TIME_absolute_get_difference (last_request_diff,
359  // sampler->max_round_interval);
360  // add a little delay
361  /* Schedule it one round later */
362  GNUNET_assert (NULL == gpc->notify_ctx);
363  gpc->notify_ctx =
364  sampler_notify_on_update (sampler,
366  gpc);
367  return;
368  }
369  }
370  if (2 > s_elem->num_peers)
371  {
373  "This s_elem saw less than two peers -- scheduling for later\n");
374  GNUNET_assert (NULL == gpc->notify_ctx);
375  gpc->notify_ctx =
376  sampler_notify_on_update (sampler,
378  gpc);
379  return;
380  }
381  /* compute probability */
382  /* Currently disabled due to numerical limitations */
383  // prob_observed_n = prob_observed_n_peers (sampler->num_peers_estim,
384  // s_elem->num_peers,
385  // sampler->deficiency_factor);
386  // LOG (GNUNET_ERROR_TYPE_DEBUG,
387  // "Computed sample - prob %f, %" PRIu32 " peers, n: %" PRIu32 ", roh: %f\n",
388  // prob_observed_n,
389  // s_elem->num_peers,
390  // sampler->num_peers_estim,
391  // sampler->deficiency_factor);
393  // if (prob_observed_n < sampler->desired_probability)
394  // {
395  // LOG (GNUNET_ERROR_TYPE_DEBUG,
396  // "Probability of having observed all peers (%f) too small ( < %f).\n",
397  // prob_observed_n,
398  // sampler->desired_probability);
399  // GNUNET_assert (NULL == gpc->notify_ctx);
400  // gpc->notify_ctx =
401  // sampler_notify_on_update (sampler,
402  // &sampler_mod_get_rand_peer,
403  // gpc);
404  // return;
405  // }
406  /* More reasons to wait could be added here */
407 
408 // GNUNET_STATISTICS_set (stats,
409 // "# client sampler element input",
410 // s_elem->num_peers,
411 // GNUNET_NO);
412 // GNUNET_STATISTICS_set (stats,
413 // "# client sampler element change",
414 // s_elem->num_change,
415 // GNUNET_NO);
416 
417  num_observed = s_elem->num_peers;
418  RPS_sampler_elem_reinit (s_elem);
420 
421  if (NULL != gpc->req_handle)
422  {
424  gpc->req_handle->gpc_tail,
425  gpc);
426  }
427  else
428  {
431  gpc);
432  }
433  gpc->cont (gpc->cont_cls, gpc->id, prob_observed_n, num_observed);
434  GNUNET_free (gpc);
435 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
uint32_t num_peers
How many times a PeerID was put in this sampler.
uint64_t rel_value_us
The actual value.
RPS_sampler_rand_peer_ready_cont cont
The callback.
A sampler element sampling one PeerID at a time.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_TIME_Absolute last_client_request
Time of last request.
#define LOG(kind,...)
void RPS_sampler_elem_reinit(struct RPS_SamplerElement *sampler_elem)
Reinitialise a previously initialised sampler element.
struct RPS_SamplerRequestHandle * req_handle
The RPS_SamplerRequestHandle this single request belongs to.
struct GNUNET_TIME_Relative max_round_interval
Maximum time a round takes.
uint64_t abs_value_us
The actual value.
#define GNUNET_TIME_UNIT_FOREVER_ABS
Constant used to specify "forever".
struct SamplerNotifyUpdateCTX * notify_ctx
Context to the given callback.
static uint32_t client_get_index
The size the extended sampler elements currently have.
struct RPS_Sampler * sampler
Sampler.
enum RPS_SamplerEmpty is_empty
Flag that indicates that we are not holding a valid PeerID right now.
struct GNUNET_PeerIdentity peer_id
The PeerID this sampler currently samples.
static void sampler_mod_get_rand_peer(void *cls)
Get one random peer out of the sampled peers.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:118
struct GetPeerCls * gpc_head
Head and tail for the DLL to store the tasks for single requests.
struct RPS_SamplerRequestHandleSingleInfo * req_single_info_handle
The RPS_SamplerRequestHandleSingleInfo this single request belongs to.
void * cont_cls
The closure to the callback cont.
struct SamplerNotifyUpdateCTX * sampler_notify_on_update(struct RPS_Sampler *sampler, SamplerNotifyUpdateCB notify_cb, void *cls)
Add a callback that will be called when the next peer is inserted into the sampler.
Closure for sampler_mod_get_rand_peer() and sampler_get_rand_peer.
unsigned int sampler_size
Number of sampler elements we hold.
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_difference(struct GNUNET_TIME_Absolute start, struct GNUNET_TIME_Absolute end)
Compute the time difference between the given start and end times.
Definition: time.c:354
struct RPS_SamplerElement ** sampler_elements
All sampler elements in one array.
Sampler with its own array of SamplerElements.
struct GNUNET_PeerIdentity * id
The address of the id to be stored at.
struct GNUNET_SCHEDULER_Task * get_peer_task
The task for this function.
struct GetPeerCls * gpc_head
Head and tail for the DLL to store the tasks for single requests.
#define GNUNET_free(ptr)
Wrapper around free.
Time for relative time used by GNUnet, in microseconds.
struct RPS_Sampler * sampler
Sampler.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ RPS_sampler_mod_init()

struct RPS_Sampler* RPS_sampler_mod_init ( size_t  init_size,
struct GNUNET_TIME_Relative  max_round_interval 
)

Initialise a modified tuple of sampler elements.

Parameters
init_sizethe size the sampler is initialised with
max_round_intervalmaximum time a round takes
Returns
a handle to a sampler that consists of sampler elements.

Definition at line 236 of file rps-sampler_client.c.

References RPS_Sampler::get_peers, GNUNET_new, RPS_Sampler::max_round_interval, RPS_sampler_resize(), and sampler_mod_get_rand_peer().

Referenced by GNUNET_RPS_request_peer_info(), and GNUNET_RPS_request_peers().

238 {
239  struct RPS_Sampler *sampler;
240 
241  /* Initialise context around extended sampler */
242  min_size = 10; // TODO make input to _samplers_init()
243  max_size = 1000; // TODO make input to _samplers_init()
244 
245  sampler = GNUNET_new (struct RPS_Sampler);
248  // sampler->sampler_elements = GNUNET_new_array(init_size, struct GNUNET_PeerIdentity);
249  // GNUNET_array_grow (sampler->sampler_elements, sampler->sampler_size, min_size);
250 
251  client_get_index = 0;
252 
253  // GNUNET_assert (init_size == sampler->sampler_size);
254 
255  RPS_sampler_resize (sampler, init_size);
256 
257  return sampler;
258 }
static size_t min_size
Global sampler variable.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
struct GNUNET_TIME_Relative max_round_interval
Maximum time a round takes.
static size_t max_size
The maximal size the extended sampler elements should grow to.
static uint32_t client_get_index
The size the extended sampler elements currently have.
static void sampler_mod_get_rand_peer(void *cls)
Get one random peer out of the sampled peers.
void RPS_sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
Grow or shrink the size of the sampler.
RPS_get_peers_type get_peers
Stores the function to return peers.
Sampler with its own array of SamplerElements.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ prob_observed_n_peers()

static double prob_observed_n_peers ( uint32_t  num_peers_estim,
uint32_t  num_peers_observed,
double  deficiency_factor 
)
static

Compute the probability that we already observed all peers from a biased stream of peer ids.

Deficiency factor: As introduced by Brahms: Factor between the number of unique ids in a truly random stream and number of unique ids in the gossip stream.

Parameters
num_peers_estimThe estimated number of peers in the network
num_peers_observedThe number of peers the given element has observed
deficiency_factorA factor that catches the 'bias' of a random stream of peer ids
Returns
The estimated probability

Definition at line 277 of file rps-sampler_client.c.

References binom(), RPS_Sampler::deficiency_factor, and num_peers.

280 {
281  uint32_t num_peers = num_peers_estim * (1 / deficiency_factor);
282  uint64_t sum = 0;
283 
284  for (uint32_t i = 0; i < num_peers; i++)
285  {
286  uint64_t a = pow (-1, num_peers - i);
287  uint64_t b = binom (num_peers, i);
288  uint64_t c = pow (i, num_peers_observed);
289  sum += a * b * c;
290  }
291 
292  return sum / (double) pow (num_peers, num_peers_observed);
293 }
uint32_t num_peers_estim
The estimated total number of peers in the network.
uint32_t binom(uint32_t n, uint32_t k)
Binomial coefficient (n choose k)
static unsigned int num_peers
double deficiency_factor
A factor that catches the &#39;bias&#39; of a random stream of peer ids.
Here is the call graph for this function:

Variable Documentation

◆ min_size

size_t min_size
static

Global sampler variable.

The minimal size for the extended sampler elements.

Definition at line 210 of file rps-sampler_client.c.

◆ max_size

size_t max_size
static

The maximal size the extended sampler elements should grow to.

Definition at line 215 of file rps-sampler_client.c.

◆ client_get_index

uint32_t client_get_index
static

The size the extended sampler elements currently have.

Inedex to the sampler element that is the next to be returned

Definition at line 225 of file rps-sampler_client.c.