GNUnet  0.10.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 99 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 299 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().

300 {
301  struct GetPeerCls *gpc = cls;
302  struct RPS_SamplerElement *s_elem;
303  struct GNUNET_TIME_Relative last_request_diff;
304  struct RPS_Sampler *sampler;
305  double prob_observed_n;
306  uint32_t num_observed;
307 
308  gpc->get_peer_task = NULL;
309  gpc->notify_ctx = NULL;
310  GNUNET_assert((NULL != gpc->req_handle) ||
311  (NULL != gpc->req_single_info_handle));
312  if (NULL != gpc->req_handle)
313  sampler = gpc->req_handle->sampler;
314  else
315  sampler = gpc->req_single_info_handle->sampler;
316 
317  LOG(GNUNET_ERROR_TYPE_DEBUG, "Single peer was requested\n");
318 
319  /* Cycle the #client_get_index one step further */
321 
322  s_elem = sampler->sampler_elements[client_get_index];
323  *gpc->id = s_elem->peer_id;
324  GNUNET_assert(NULL != s_elem);
325 
326  if (EMPTY == s_elem->is_empty)
327  {
329  "Sampler_mod element empty, rescheduling.\n");
330  GNUNET_assert(NULL == gpc->notify_ctx);
331  gpc->notify_ctx =
332  sampler_notify_on_update(sampler,
334  gpc);
335  return;
336  }
337 
338  /* Check whether we may use this sampler to give it back to the client */
340  {
341  // TODO remove this condition at least for the client sampler
342  last_request_diff =
345  /* We're not going to give it back now if it was
346  * already requested by a client this round */
347  if (last_request_diff.rel_value_us < sampler->max_round_interval.rel_value_us)
348  {
350  "Last client request on this sampler was less than max round interval ago -- scheduling for later\n");
352  //inv_last_request_diff =
353  // GNUNET_TIME_absolute_get_difference (last_request_diff,
354  // sampler->max_round_interval);
355  // add a little delay
356  /* Schedule it one round later */
357  GNUNET_assert(NULL == gpc->notify_ctx);
358  gpc->notify_ctx =
359  sampler_notify_on_update(sampler,
361  gpc);
362  return;
363  }
364  }
365  if (2 > s_elem->num_peers)
366  {
368  "This s_elem saw less than two peers -- scheduling for later\n");
369  GNUNET_assert(NULL == gpc->notify_ctx);
370  gpc->notify_ctx =
371  sampler_notify_on_update(sampler,
373  gpc);
374  return;
375  }
376  /* compute probability */
377  /* Currently disabled due to numerical limitations */
378  //prob_observed_n = prob_observed_n_peers (sampler->num_peers_estim,
379  // s_elem->num_peers,
380  // sampler->deficiency_factor);
381  //LOG (GNUNET_ERROR_TYPE_DEBUG,
382  // "Computed sample - prob %f, %" PRIu32 " peers, n: %" PRIu32 ", roh: %f\n",
383  // prob_observed_n,
384  // s_elem->num_peers,
385  // sampler->num_peers_estim,
386  // sampler->deficiency_factor);
388  //if (prob_observed_n < sampler->desired_probability)
389  //{
390  // LOG (GNUNET_ERROR_TYPE_DEBUG,
391  // "Probability of having observed all peers (%f) too small ( < %f).\n",
392  // prob_observed_n,
393  // sampler->desired_probability);
394  // GNUNET_assert (NULL == gpc->notify_ctx);
395  // gpc->notify_ctx =
396  // sampler_notify_on_update (sampler,
397  // &sampler_mod_get_rand_peer,
398  // gpc);
399  // return;
400  //}
401  /* More reasons to wait could be added here */
402 
403 // GNUNET_STATISTICS_set (stats,
404 // "# client sampler element input",
405 // s_elem->num_peers,
406 // GNUNET_NO);
407 // GNUNET_STATISTICS_set (stats,
408 // "# client sampler element change",
409 // s_elem->num_change,
410 // GNUNET_NO);
411 
412  num_observed = s_elem->num_peers;
413  RPS_sampler_elem_reinit(s_elem);
415 
416  if (NULL != gpc->req_handle)
417  {
419  gpc->req_handle->gpc_tail,
420  gpc);
421  }
422  else
423  {
426  gpc);
427  }
428  gpc->cont(gpc->cont_cls, gpc->id, prob_observed_n, num_observed);
429  GNUNET_free(gpc);
430 }
#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:353
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 233 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().

235 {
236  struct RPS_Sampler *sampler;
237 
238  /* Initialise context around extended sampler */
239  min_size = 10; // TODO make input to _samplers_init()
240  max_size = 1000; // TODO make input to _samplers_init()
241 
242  sampler = GNUNET_new(struct RPS_Sampler);
245  //sampler->sampler_elements = GNUNET_new_array(init_size, struct GNUNET_PeerIdentity);
246  //GNUNET_array_grow (sampler->sampler_elements, sampler->sampler_size, min_size);
247 
248  client_get_index = 0;
249 
250  //GNUNET_assert (init_size == sampler->sampler_size);
251 
252  RPS_sampler_resize(sampler, init_size);
253 
254  return sampler;
255 }
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 274 of file rps-sampler_client.c.

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

277 {
278  uint32_t num_peers = num_peers_estim * (1 / deficiency_factor);
279  uint64_t sum = 0;
280 
281  for (uint32_t i = 0; i < num_peers; i++)
282  {
283  uint64_t a = pow(-1, num_peers - i);
284  uint64_t b = binom(num_peers, i);
285  uint64_t c = pow(i, num_peers_observed);
286  sum += a * b * c;
287  }
288 
289  return sum / (double)pow(num_peers, num_peers_observed);
290 }
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 207 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 212 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 222 of file rps-sampler_client.c.