fix correction according to paper, minimum NSE should be our neighour set

[oweals/gnunet.git] / src / nse / gnunet-service-nse.c

diff --git a/src/nse/gnunet-service-nse.c b/src/nse/gnunet-service-nse.c
index c82180dfdd1a5c4bccc27d8153efe08e49a03115..bc46a537cdd3b2f5b614740c3b4dd07f4c433d75 100644 (file)
--- a/src/nse/gnunet-service-nse.c
+++ b/src/nse/gnunet-service-nse.c
@@ -1,17 +1,17 @@
 /*
   This file is part of GNUnet.
   (C) 2009, 2010, 2011 Christian Grothoff (and other contributing authors)
-  
+
   GNUnet is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published
   by the Free Software Foundation; either version 3, or (at your
   option) any later version.
-  
+
   GNUnet is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.
-  
+
   You should have received a copy of the GNU General Public License
   along with GNUnet; see the file COPYING.  If not, write to the
   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
@@ -148,7 +148,7 @@ struct GNUNET_NSE_FloodMessage
   /**
    * Number of hops this message has taken so far.
    */
-  uint32_t hop_count;
+  uint32_t hop_count GNUNET_PACKED;
 
   /**
    * Purpose.
@@ -166,7 +166,7 @@ struct GNUNET_NSE_FloodMessage
    * of timestamp and the initiator's public
    * key.
    */
-  uint32_t matching_bits;
+  uint32_t matching_bits GNUNET_PACKED;
 
   /**
    * Public key of the originator.
@@ -176,7 +176,7 @@ struct GNUNET_NSE_FloodMessage
   /**
    * Proof of work, causing leading zeros when hashed with pkey.
    */
-  uint64_t proof_of_work;
+  uint64_t proof_of_work GNUNET_PACKED;
 
   /**
    * Signature (over range specified in purpose).
@@ -207,7 +207,7 @@ static struct GNUNET_CONTAINER_MultiHashMap *peers;
 
 /**
  * The current network size estimate.  Number of bits matching on
- * average thus far. 
+ * average thus far.
  */
 static double current_size_estimate;
 
@@ -308,6 +308,7 @@ setup_estimate_message (struct GNUNET_NSE_ClientMessage *em)
   double q;
   double r;
   double temp;
+  double nsize;
 
   /* Weighted incremental algorithm for stddev according to West (1979) */
   mean = 0.0;
@@ -333,12 +334,15 @@ setup_estimate_message (struct GNUNET_NSE_ClientMessage *em)
   std_dev = sqrt (variance);
   current_std_dev = std_dev;
   current_size_estimate = mean;
-
+  
   em->header.size = htons (sizeof (struct GNUNET_NSE_ClientMessage));
   em->header.type = htons (GNUNET_MESSAGE_TYPE_NSE_ESTIMATE);
   em->reserved = htonl (0);
   em->timestamp = GNUNET_TIME_absolute_hton (GNUNET_TIME_absolute_get ());
-  em->size_estimate = mean - 1.0 / 3.0;
+  em->size_estimate = mean - 0.332747;
+  nsize = log2 (GNUNET_CONTAINER_multihashmap_size (peers) + 1);
+  if (em->size_estimate < nsize)
+    em->size_estimate = nsize;
   em->std_deviation = std_dev;
   GNUNET_STATISTICS_set (stats, "# nodes in the network (estimate)",
                          (uint64_t) pow (2, mean - 1.0 / 3.0), GNUNET_NO);
@@ -396,7 +400,7 @@ get_matching_bits_delay (uint32_t matching_bits)
  * What delay randomization should we apply for a given number of matching bits?
  *
  * @param matching_bits number of matching bits
- * @return random delay to apply 
+ * @return random delay to apply
  */
 static struct GNUNET_TIME_Relative
 get_delay_randomization (uint32_t matching_bits)
@@ -439,7 +443,7 @@ get_matching_bits (struct GNUNET_TIME_Absolute timestamp,
 
 
 /**
- * Get the transmission delay that should be applied for a 
+ * Get the transmission delay that should be applied for a
  * particular round.
  *
  * @param round_offset -1 for the previous round (random delay between 0 and 50ms)
@@ -627,7 +631,8 @@ setup_flood_message (unsigned int slot, struct GNUNET_TIME_Absolute ts)
   fm->timestamp = GNUNET_TIME_absolute_hton (ts);
   fm->pkey = my_public_key;
   fm->proof_of_work = my_proof;
-  GNUNET_CRYPTO_rsa_sign (my_private_key, &fm->purpose, &fm->signature);
+  GNUNET_assert (GNUNET_OK ==
+                GNUNET_CRYPTO_rsa_sign (my_private_key, &fm->purpose, &fm->signature));
 }
 
 
@@ -815,9 +820,10 @@ find_proof (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
         if (ntohl (size_estimate_messages[i].hop_count) == 0)
         {
           size_estimate_messages[i].proof_of_work = my_proof;
-          GNUNET_CRYPTO_rsa_sign (my_private_key,
-                                  &size_estimate_messages[i].purpose,
-                                  &size_estimate_messages[i].signature);
+          GNUNET_assert (GNUNET_OK ==
+                        GNUNET_CRYPTO_rsa_sign (my_private_key,
+                                                &size_estimate_messages[i].purpose,
+                                                &size_estimate_messages[i].signature));
         }
       write_proof ();
       return;
@@ -902,7 +908,7 @@ update_flood_times (void *cls, const GNUNET_HashCode * key, void *value)
     return GNUNET_OK;           /* trigger of the update */
   if (peer_entry->previous_round == GNUNET_NO)
   {
-    /* still stuck in previous round, no point to update, check that 
+    /* still stuck in previous round, no point to update, check that
      * we are active here though... */
     GNUNET_break ((peer_entry->transmit_task != GNUNET_SCHEDULER_NO_TASK) ||
                   (peer_entry->th != NULL));