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_service_lib.h"
45 #include "gnunet_server_lib.h"
46 #include "gnunet_core_service.h"
47 #include "gnunet_time_lib.h"
48 #include "gnunet_nse_service.h"
51 #define DEFAULT_HISTORY_SIZE 10
53 #define DEFAULT_CORE_QUEUE_SIZE 32
55 #define MILLISECONDS_PER_DAY 86400000
58 * Entry in the list of clients which
59 * should be notified upon a new network
60 * size estimate calculation.
62 struct ClientListEntry
65 * Pointer to previous entry
67 struct ClientListEntry *prev;
70 * Pointer to next entry
72 struct ClientListEntry *next;
77 struct GNUNET_SERVER_Client *client;
81 * Handle to our current configuration.
83 static const struct GNUNET_CONFIGURATION_Handle *cfg;
86 * Handle to the core service.
88 struct GNUNET_CORE_Handle *coreAPI;
91 * Copy of this peer's identity.
93 static struct GNUNET_PeerIdentity my_identity;
96 * Head of global list of clients.
98 static struct ClientListEntry *cle_head;
101 * Tail of global list of clients.
103 static struct ClientListEntry *cle_tail;
106 * The current network size estimate.
108 static double current_size_estimate;
111 * The standard deviation of the last
112 * DEFAULT_HISTORY_SIZE network size estimates.
114 static double current_std_dev;
117 * Array of the last DEFAULT_HISTORY_SIZE
118 * network size estimates.
120 //static double *size_estimates[DEFAULT_HISTORY_SIZE];
123 * Task scheduled to send flood message.
125 static GNUNET_SCHEDULER_TaskIdentifier flood_task;
128 * Notification context, simplifies client broadcasts.
130 static struct GNUNET_SERVER_NotificationContext *nc;
133 * The previous major time.
135 struct GNUNET_TIME_Absolute previous_timestamp;
138 * The next major time.
140 static struct GNUNET_TIME_Absolute next_timestamp;
143 * Base increment of time to add to send time.
145 static struct GNUNET_TIME_Relative increment;
148 * The current network size estimate message.
150 static struct GNUNET_NSE_ClientMessage current_estimate_message;
153 * Handler for START message from client, triggers an
154 * immediate current network estimate notification.
155 * Also, we remember the client for updates upon future
156 * estimate measurements.
159 * @param client who sent the message
160 * @param message the message received
163 handle_start_message (void *cls,
164 struct GNUNET_SERVER_Client *client,
165 const struct GNUNET_MessageHeader *message)
167 if ((ntohs (message->size) != sizeof(struct GNUNET_MessageHeader))
168 || (ntohs (message->type) != GNUNET_MESSAGE_TYPE_NSE_START))
172 GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG, "NSE", "Received START message from client\n");
174 GNUNET_SERVER_notification_context_add (nc, client);
175 GNUNET_SERVER_notification_context_unicast (nc, client,
176 ¤t_estimate_message.header,
178 GNUNET_SERVER_receive_done(client, GNUNET_OK);
182 * Core handler for size estimate flooding messages.
185 * @param message message
186 * @param peer peer identity this notification is about
187 * @param atsi performance data
191 handle_p2p_size_estimate (void *cls,
192 const struct GNUNET_PeerIdentity *peer,
193 const struct GNUNET_MessageHeader *message,
194 const struct GNUNET_TRANSPORT_ATS_Information
203 * Send a flood message containing our peer's public key
204 * and the hashed current timestamp.
207 send_flood_message (void *cls,
208 const struct GNUNET_SCHEDULER_TaskContext * tc)
210 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
215 * A client disconnected. Remove it from the
216 * global DLL of clients.
218 * @param cls closure, NULL
219 * @param client identification of the client
222 handle_client_disconnect (void *cls,
223 struct GNUNET_SERVER_Client* client)
225 struct ClientListEntry *cle;
227 while (NULL != (cle = cle_head))
232 GNUNET_SERVER_client_drop(cle->client);
233 GNUNET_CONTAINER_DLL_remove(cle_head,
240 GNUNET_CORE_disconnect(coreAPI);
246 * Task run during shutdown.
252 shutdown_task (void *cls,
253 const struct GNUNET_SCHEDULER_TaskContext *tc)
255 struct ClientListEntry *cle;
257 GNUNET_SERVER_notification_context_destroy (nc);
259 while (NULL != (cle = cle_head))
261 GNUNET_SERVER_client_drop (cle->client);
262 GNUNET_CONTAINER_DLL_remove (cle_head,
270 GNUNET_CORE_disconnect(coreAPI);
278 * Task to schedule a flood message to be sent.
281 * @param tc context information (why was this task triggered now)
283 static void schedule_flood_message (void *cls,
285 GNUNET_SCHEDULER_TaskContext * tc)
287 GNUNET_HashCode timestamp_hash;
288 struct GNUNET_TIME_Absolute curr_time;
289 unsigned int matching_bits;
291 /* Get the current UTC time */
292 curr_time = GNUNET_TIME_absolute_get();
293 /* Find the previous interval start time */
294 previous_timestamp.abs_value = (curr_time.abs_value / GNUNET_NSE_INTERVAL) * GNUNET_NSE_INTERVAL;
295 /* Find the next interval start time */
296 next_timestamp.abs_value = (curr_time.abs_value / GNUNET_NSE_INTERVAL) * (GNUNET_NSE_INTERVAL + 1);
298 GNUNET_CRYPTO_hash(&next_timestamp.abs_value, sizeof(uint64_t), ×tamp_hash);
299 matching_bits = GNUNET_CRYPTO_hash_matching_bits(×tamp_hash, &my_identity.hashPubKey);
301 GNUNET_SCHEDULER_add_delayed (
302 GNUNET_TIME_relative_add (
303 GNUNET_TIME_relative_multiply (
306 GNUNET_TIME_absolute_get_remaining (
308 &send_flood_message, NULL);
312 * Called on core init/fail.
314 * @param cls service closure
315 * @param server handle to the server for this service
316 * @param identity the public identity of this peer
317 * @param publicKey the public key of this peer
320 core_init (void *cls,
321 struct GNUNET_CORE_Handle *server,
322 const struct GNUNET_PeerIdentity *identity,
323 const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *publicKey)
328 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
329 "%s: Connection to core FAILED!\n", "nse",
330 GNUNET_i2s (identity));
332 GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
336 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
337 "%s: Core connection initialized, I am peer: %s\n", "nse",
338 GNUNET_i2s (identity));
341 /* Copy our identity so we can use it */
342 memcpy (&my_identity, identity, sizeof (struct GNUNET_PeerIdentity));
344 flood_task = GNUNET_SCHEDULER_add_now(&schedule_flood_message, NULL);
348 * Handle network size estimate clients.
351 * @param server the initialized server
352 * @param c configuration to use
356 struct GNUNET_SERVER_Handle *server,
357 const struct GNUNET_CONFIGURATION_Handle *c)
359 static const struct GNUNET_SERVER_MessageHandler handlers[] = {
360 {&handle_start_message, NULL, GNUNET_MESSAGE_TYPE_NSE_START, 0},
364 static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
365 {&handle_p2p_size_estimate, GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD, 0},
370 GNUNET_SERVER_add_handlers (server, handlers);
371 nc = GNUNET_SERVER_notification_context_create (server, 16);
372 GNUNET_SERVER_disconnect_notify (server,
373 &handle_client_disconnect,
376 /** Connect to core service and register core handlers */
377 coreAPI = GNUNET_CORE_connect (cfg, /* Main configuration */
378 DEFAULT_CORE_QUEUE_SIZE, /* queue size */
379 NULL, /* Closure passed to functions */
380 &core_init, /* Call core_init once connected */
381 NULL, /* Handle connects */
382 NULL, /* Handle disconnects */
383 NULL, /* Do we care about "status" updates? */
384 NULL, /* Don't want notified about all incoming messages */
385 GNUNET_NO, /* For header only inbound notification */
386 NULL, /* Don't want notified about all outbound messages */
387 GNUNET_NO, /* For header only outbound notification */
388 core_handlers); /* Register these handlers */
392 GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
397 = GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS,
399 / (sizeof(GNUNET_HashCode)
401 /* Set we have no idea defaults for network size estimate */
402 current_size_estimate = NAN;
403 current_std_dev = NAN;
405 current_estimate_message.header.size = htons(sizeof(struct GNUNET_NSE_ClientMessage));
406 current_estimate_message.header.type = htons(GNUNET_MESSAGE_TYPE_NSE_ESTIMATE);
407 current_estimate_message.size_estimate = current_size_estimate;
408 current_estimate_message.std_deviation = current_std_dev;
410 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL,
417 * The main function for the statistics service.
419 * @param argc number of arguments from the command line
420 * @param argv command line arguments
421 * @return 0 ok, 1 on error
424 main (int argc, char *const *argv)
427 GNUNET_SERVICE_run (argc,
430 GNUNET_SERVICE_OPTION_NONE,
431 &run, NULL)) ? 0 : 1;
434 /* End of gnunet-service-nse.c */