2 This file is part of GNUnet.
3 (C) 2009, 2010, 2011 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file nse/gnunet-service-nse.c
23 * @brief network size estimation service
24 * @author Nathan Evans
26 * The purpose of this service is to estimate the size of the network.
27 * Given a specified interval, each peer hashes the most recent
28 * timestamp which is evenly divisible by that interval. This hash
29 * is compared in distance to the peer identity to choose an offset.
30 * The closer the peer identity to the hashed timestamp, the earlier
31 * the peer sends out a "nearest peer" message. The closest peer's
32 * message should thus be received before any others, which stops
33 * those peer from sending their messages at a later duration. So
34 * every peer should receive the same nearest peer message, and
35 * from this can calculate the expected number of peers in the
40 #include "gnunet_client_lib.h"
41 #include "gnunet_constants.h"
42 #include "gnunet_container_lib.h"
43 #include "gnunet_protocols.h"
44 #include "gnunet_signatures.h"
45 #include "gnunet_service_lib.h"
46 #include "gnunet_server_lib.h"
47 #include "gnunet_core_service.h"
48 #include "gnunet_time_lib.h"
49 #include "gnunet_nse_service.h"
52 #define DEFAULT_HISTORY_SIZE 10
54 #define DEFAULT_CORE_QUEUE_SIZE 32
56 #define DEFAULT_NSE_PRIORITY 0
59 * Entry in the list of clients which
60 * should be notified upon a new network
61 * size estimate calculation.
63 struct ClientListEntry
66 * Pointer to previous entry
68 struct ClientListEntry *prev;
71 * Pointer to next entry
73 struct ClientListEntry *next;
78 struct GNUNET_SERVER_Client *client;
82 * Per-peer information.
87 * Next peer entry (DLL)
89 struct NSEPeerEntry *next;
92 * Prev peer entry (DLL)
94 struct NSEPeerEntry *prev;
97 * Pending message for this peer.
99 struct GNUNET_MessageHeader *pending_message;
102 * Core handle for sending messages to this peer.
104 struct GNUNET_CORE_TransmitHandle *th;
107 * What is the identity of the peer?
109 struct GNUNET_PeerIdentity id;
113 * Handle to our current configuration.
115 static const struct GNUNET_CONFIGURATION_Handle *cfg;
118 * Handle to the core service.
120 static struct GNUNET_CORE_Handle *coreAPI;
123 * Head of global list of peers.
125 static struct NSEPeerEntry *peers_head;
128 * Head of global list of clients.
130 static struct NSEPeerEntry *peers_tail;
133 * Head of global list of clients.
135 static struct ClientListEntry *cle_head;
138 * Tail of global list of clients.
140 static struct ClientListEntry *cle_tail;
143 * The current network size estimate.
144 * Number of bits matching on average
147 static double current_size_estimate;
150 * The standard deviation of the last
151 * DEFAULT_HISTORY_SIZE network size estimates.
153 static double current_std_dev;
156 * Array of the last DEFAULT_HISTORY_SIZE
157 * network size estimates (matching bits, actually).
159 static unsigned int size_estimates[DEFAULT_HISTORY_SIZE];
162 * Array of size estimate messages.
164 static struct GNUNET_NSE_FloodMessage size_estimate_messages[DEFAULT_HISTORY_SIZE];
167 * Index of most recent estimate.
169 static unsigned int estimate_index;
172 * Task scheduled to send flood message.
174 static GNUNET_SCHEDULER_TaskIdentifier flood_task;
177 * Task to schedule flood message and update state.
179 static GNUNET_SCHEDULER_TaskIdentifier schedule_flood_task;
182 * Notification context, simplifies client broadcasts.
184 static struct GNUNET_SERVER_NotificationContext *nc;
187 * The previous major time.
189 static struct GNUNET_TIME_Absolute previous_timestamp;
192 * The next major time.
194 static struct GNUNET_TIME_Absolute next_timestamp;
197 * Base increment of time to add to send time.
199 static struct GNUNET_TIME_Relative increment;
202 * The current network size estimate message.
204 static struct GNUNET_NSE_ClientMessage current_estimate_message;
207 * The public key of this peer.
209 static struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded my_public_key;
212 * The private key of this peer.
214 static struct GNUNET_CRYPTO_RsaPrivateKey *my_private_key;
217 * The peer identity of this peer.
219 static struct GNUNET_PeerIdentity my_identity;
222 * Our flood message, updated whenever a flood is sent.
224 static struct GNUNET_NSE_FloodMessage flood_message;
227 * Handler for START message from client, triggers an
228 * immediate current network estimate notification.
229 * Also, we remember the client for updates upon future
230 * estimate measurements.
233 * @param client who sent the message
234 * @param message the message received
237 handle_start_message (void *cls,
238 struct GNUNET_SERVER_Client *client,
239 const struct GNUNET_MessageHeader *message)
241 if ((ntohs (message->size) != sizeof(struct GNUNET_MessageHeader))
242 || (ntohs (message->type) != GNUNET_MESSAGE_TYPE_NSE_START))
246 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG, "NSE", "Received START message from client\n");
248 GNUNET_SERVER_notification_context_add (nc, client);
249 GNUNET_SERVER_receive_done(client, GNUNET_OK);
254 * Called when core is ready to send a message we asked for
255 * out to the destination.
257 * @param cls closure (NULL)
258 * @param size number of bytes available in buf
259 * @param buf where the callee should write the message
260 * @return number of bytes written to buf
263 transmit_ready (void *cls, size_t size, void *buf)
265 struct NSEPeerEntry *peer_entry = cls;
269 peer_entry->th = NULL;
270 if (buf == NULL) /* client disconnected */
273 if (peer_entry->pending_message == NULL)
276 msize = ntohs(peer_entry->pending_message->size);
278 memcpy(cbuf, peer_entry->pending_message, msize);
284 * We sent on our flood message or one that we received
285 * which was validated and closer than ours. Update the
286 * global list of recent messages and the average. Also
287 * re-broadcast the message to any clients.
289 * @param message the network flood message
291 static void update_network_size_estimate(struct GNUNET_NSE_FloodMessage *message)
297 size_estimates[estimate_index] = htons(message->distance);
298 memcpy(&size_estimate_messages[estimate_index], message, sizeof(struct GNUNET_NSE_FloodMessage));
301 for (i = 0; i < DEFAULT_HISTORY_SIZE; i++)
303 if (size_estimate_messages[i].distance != 0)
305 average += 1 << htons(size_estimate_messages[i].distance);
309 average /= (double)count;
310 current_estimate_message.size_estimate = average;
311 /* Finally, broadcast the current estimate to all clients */
312 GNUNET_SERVER_notification_context_broadcast (nc,
313 ¤t_estimate_message.header,
318 send_flood_message (void *cls,
319 const struct GNUNET_SCHEDULER_TaskContext * tc);
322 * Schedule a flood message to be sent.
325 * @param tc context for this message
327 * This should be called on startup,
328 * when a valid flood message is received (and
329 * the next send flood message hasn't been
330 * scheduled yet) and when this peer sends
331 * a valid flood message. As such, there should
332 * always be a message scheduled to be sent.
335 schedule_flood_message (void *cls,
336 const struct GNUNET_SCHEDULER_TaskContext *tc)
338 GNUNET_HashCode timestamp_hash;
339 struct GNUNET_TIME_Absolute curr_time;
340 struct GNUNET_TIME_Relative offset;
341 struct GNUNET_CRYPTO_RsaSignaturePurpose purpose;
342 unsigned int matching_bits;
343 double millisecond_offset;
345 schedule_flood_task = GNUNET_SCHEDULER_NO_TASK;
346 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
349 GNUNET_assert(flood_task == GNUNET_SCHEDULER_NO_TASK);
351 if (0 != GNUNET_TIME_absolute_get_remaining(next_timestamp).rel_value)
353 GNUNET_break(0); /* Shouldn't ever happen! */
354 schedule_flood_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining(next_timestamp), &schedule_flood_message, NULL);
357 /* Get the current UTC time */
358 curr_time = GNUNET_TIME_absolute_get();
359 /* Find the previous interval start time */
360 previous_timestamp.abs_value = (curr_time.abs_value / GNUNET_NSE_INTERVAL) * GNUNET_NSE_INTERVAL;
361 /* Find the next interval start time */
362 next_timestamp.abs_value = (curr_time.abs_value / GNUNET_NSE_INTERVAL) * (GNUNET_NSE_INTERVAL + 1);
364 GNUNET_CRYPTO_hash(&next_timestamp.abs_value, sizeof(uint64_t), ×tamp_hash);
365 matching_bits = GNUNET_CRYPTO_hash_matching_bits(×tamp_hash, &my_identity.hashPubKey);
367 flood_message.timestamp = GNUNET_TIME_absolute_hton(next_timestamp);
368 flood_message.distance = htons(matching_bits);
369 flood_message.enc_type = htons(0);
370 flood_message.proof_of_work = htonl(0);
371 purpose.purpose = GNUNET_SIGNATURE_PURPOSE_NSE_SEND;
372 purpose.size = sizeof(struct GNUNET_NSE_FloodMessage) - sizeof(struct GNUNET_MessageHeader) - sizeof(flood_message.proof_of_work) - sizeof(flood_message.signature);
373 GNUNET_CRYPTO_rsa_sign(my_private_key, &purpose, &flood_message.signature);
375 /*S + f/2 - (f / pi) * (atan(x - p'))*/
377 // S is next_timestamp
378 // f is frequency (GNUNET_NSE_INTERVAL)
379 // x is matching_bits
380 // p' is current_size_estimate
381 millisecond_offset = ((double)GNUNET_NSE_INTERVAL / (double)2) - ((GNUNET_NSE_INTERVAL / M_PI) * atan(matching_bits - current_size_estimate));
383 fprintf(stderr, "my id matches %d bits, offset is %lu\n", matching_bits, (uint64_t)millisecond_offset);
387 if (estimate_index >= DEFAULT_HISTORY_SIZE)
390 offset.rel_value = (uint64_t)millisecond_offset + GNUNET_TIME_absolute_get_remaining (next_timestamp).rel_value;
391 flood_task = GNUNET_SCHEDULER_add_delayed (offset,
392 &send_flood_message, NULL);
397 * Core handler for size estimate flooding messages.
399 * @param cls closure unused
400 * @param message message
401 * @param peer peer identity this message is from (ignored)
402 * @param atsi performance data (ignored)
406 handle_p2p_size_estimate(void *cls, const struct GNUNET_PeerIdentity *peer,
407 const struct GNUNET_MessageHeader *message,
408 const struct GNUNET_TRANSPORT_ATS_Information *atsi)
410 struct GNUNET_NSE_FloodMessage *incoming_flood;
412 if (ntohs(message->size) != sizeof(struct GNUNET_NSE_FloodMessage))
415 incoming_flood = (struct GNUNET_NSE_FloodMessage *)message;
416 if (ntohs(incoming_flood->distance) <= ntohs(size_estimate_messages[estimate_index].distance)) /* Not closer than our most recent message */
419 /* Have a new, better size estimate! */
420 update_network_size_estimate(incoming_flood);
422 if (schedule_flood_task != GNUNET_SCHEDULER_NO_TASK)
423 GNUNET_SCHEDULER_cancel(schedule_flood_task);
424 schedule_flood_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining(next_timestamp), &schedule_flood_message, NULL);
430 * Send a flood message.
432 * If we've gotten here, it means we haven't received
433 * a network size estimate message closer than ours.
436 send_flood_message (void *cls,
437 const struct GNUNET_SCHEDULER_TaskContext * tc)
439 struct NSEPeerEntry *peer_entry;
441 flood_task = GNUNET_SCHEDULER_NO_TASK;
442 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
445 peer_entry = peers_head;
447 while (peer_entry != NULL)
450 = GNUNET_CORE_notify_transmit_ready (coreAPI,
452 DEFAULT_NSE_PRIORITY,
453 GNUNET_TIME_absolute_get_remaining (
456 ntohs (flood_message.header.size),
457 &transmit_ready, peer_entry);
458 peer_entry = peer_entry->next;
461 update_network_size_estimate(&flood_message);
462 if (schedule_flood_task != GNUNET_SCHEDULER_NO_TASK)
463 GNUNET_SCHEDULER_cancel(schedule_flood_task);
464 schedule_flood_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining(next_timestamp), &schedule_flood_message, NULL);
468 * Method called whenever a peer connects.
471 * @param peer peer identity this notification is about
472 * @param atsi performance data
475 handle_core_connect (void *cls,
476 const struct GNUNET_PeerIdentity *peer,
477 const struct GNUNET_TRANSPORT_ATS_Information *atsi)
479 struct NSEPeerEntry *peer_entry;
481 peer_entry = GNUNET_malloc(sizeof(struct NSEPeerEntry));
482 memcpy(&peer_entry->id, peer, sizeof(struct GNUNET_PeerIdentity));
483 GNUNET_CONTAINER_DLL_insert(peers_head, peers_tail, peer_entry);
488 * Method called whenever a peer disconnects.
491 * @param peer peer identity this notification is about
494 handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer)
496 struct NSEPeerEntry *pos;
499 while ((NULL != pos) && (0 != memcmp(&pos->id, peer, sizeof(struct GNUNET_PeerIdentity))))
503 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Received disconnect before connect!\n");
504 GNUNET_break(0); /* Should never receive a disconnect message for a peer we don't know about... */
508 if (pos->pending_message != NULL)
509 GNUNET_free(pos->pending_message);
512 GNUNET_CORE_notify_transmit_ready_cancel(pos->th);
513 GNUNET_CONTAINER_DLL_remove(peers_head, peers_tail, pos);
519 * A client disconnected. Remove it from the
520 * global DLL of clients.
522 * @param cls closure, NULL
523 * @param client identification of the client
526 handle_client_disconnect (void *cls,
527 struct GNUNET_SERVER_Client* client)
529 struct ClientListEntry *cle;
531 while (NULL != (cle = cle_head))
536 GNUNET_SERVER_client_drop(cle->client);
537 GNUNET_CONTAINER_DLL_remove(cle_head,
544 GNUNET_CORE_disconnect(coreAPI);
550 * Task run during shutdown.
556 shutdown_task (void *cls,
557 const struct GNUNET_SCHEDULER_TaskContext *tc)
559 struct ClientListEntry *cle;
561 if (flood_task != GNUNET_SCHEDULER_NO_TASK)
562 GNUNET_SCHEDULER_cancel(flood_task);
563 GNUNET_SERVER_notification_context_destroy (nc);
565 while (NULL != (cle = cle_head))
567 GNUNET_SERVER_client_drop (cle->client);
568 GNUNET_CONTAINER_DLL_remove (cle_head,
576 GNUNET_CORE_disconnect(coreAPI);
584 * Called on core init/fail.
586 * @param cls service closure
587 * @param server handle to the server for this service
588 * @param identity the public identity of this peer
589 * @param publicKey the public key of this peer
592 core_init (void *cls,
593 struct GNUNET_CORE_Handle *server,
594 const struct GNUNET_PeerIdentity *identity,
595 const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *publicKey)
600 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
601 "%s: Connection to core FAILED!\n", "nse",
602 GNUNET_i2s (identity));
604 GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
608 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
609 "%s: Core connection initialized, I am peer: %s\n", "nse",
610 GNUNET_i2s (identity));
613 /* Copy our identity so we can use it */
614 memcpy (&my_identity, identity, sizeof (struct GNUNET_PeerIdentity));
615 /* Copy our public key for inclusion in flood messages */
616 memcpy (&my_public_key, publicKey, sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
618 flood_message.header.size = htons(sizeof(struct GNUNET_NSE_FloodMessage));
619 flood_message.header.type = htons(GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD);
620 memcpy(&flood_message.pkey, &my_public_key, sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
622 if (flood_task != GNUNET_SCHEDULER_NO_TASK)
623 GNUNET_SCHEDULER_cancel(flood_task);
625 schedule_flood_task = GNUNET_SCHEDULER_add_now(&schedule_flood_message, NULL);
627 GNUNET_SERVER_notification_context_broadcast (nc,
628 ¤t_estimate_message.header,
633 * Handle network size estimate clients.
636 * @param server the initialized server
637 * @param c configuration to use
641 struct GNUNET_SERVER_Handle *server,
642 const struct GNUNET_CONFIGURATION_Handle *c)
645 static const struct GNUNET_SERVER_MessageHandler handlers[] = {
646 {&handle_start_message, NULL, GNUNET_MESSAGE_TYPE_NSE_START, 0},
650 static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
651 {&handle_p2p_size_estimate, GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD, 0},
658 GNUNET_CONFIGURATION_get_value_filename (c,
660 "HOSTKEY", &keyfile))
662 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
664 ("NSE service is lacking key configuration settings. Exiting.\n"));
665 GNUNET_SCHEDULER_shutdown ();
669 my_private_key = GNUNET_CRYPTO_rsa_key_create_from_file (keyfile);
670 GNUNET_free (keyfile);
671 if (my_private_key == NULL)
673 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
674 _("NSE Service could not access hostkey. Exiting.\n"));
675 GNUNET_SCHEDULER_shutdown ();
679 GNUNET_SERVER_add_handlers (server, handlers);
680 nc = GNUNET_SERVER_notification_context_create (server, 16);
681 GNUNET_SERVER_disconnect_notify (server,
682 &handle_client_disconnect,
685 flood_task = GNUNET_SCHEDULER_NO_TASK;
686 /** Connect to core service and register core handlers */
687 coreAPI = GNUNET_CORE_connect (cfg, /* Main configuration */
688 DEFAULT_CORE_QUEUE_SIZE, /* queue size */
689 NULL, /* Closure passed to functions */
690 &core_init, /* Call core_init once connected */
691 &handle_core_connect, /* Handle connects */
692 &handle_core_disconnect, /* Handle disconnects */
693 NULL, /* Do we care about "status" updates? */
694 NULL, /* Don't want notified about all incoming messages */
695 GNUNET_NO, /* For header only inbound notification */
696 NULL, /* Don't want notified about all outbound messages */
697 GNUNET_NO, /* For header only outbound notification */
698 core_handlers); /* Register these handlers */
702 GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
707 = GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS,
709 / (sizeof(GNUNET_HashCode)
711 /* Set we have no idea defaults for network size estimate */
712 current_size_estimate = 0.0;
713 current_std_dev = NAN;
714 size_estimates[estimate_index] = 0;
715 current_estimate_message.header.size = htons(sizeof(struct GNUNET_NSE_ClientMessage));
716 current_estimate_message.header.type = htons(GNUNET_MESSAGE_TYPE_NSE_ESTIMATE);
717 current_estimate_message.size_estimate = current_size_estimate;
718 current_estimate_message.std_deviation = current_std_dev;
720 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL,
727 * The main function for the statistics service.
729 * @param argc number of arguments from the command line
730 * @param argv command line arguments
731 * @return 0 ok, 1 on error
734 main (int argc, char *const *argv)
737 GNUNET_SERVICE_run (argc,
740 GNUNET_SERVICE_OPTION_NONE,
741 &run, NULL)) ? 0 : 1;
744 /* End of gnunet-service-nse.c */