[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r12862 - gnunet/src/dht
From: |
gnunet |
Subject: |
[GNUnet-SVN] r12862 - gnunet/src/dht |
Date: |
Mon, 6 Sep 2010 22:29:29 +0200 |
Author: nevans
Date: 2010-09-06 22:29:29 +0200 (Mon, 06 Sep 2010)
New Revision: 12862
Modified:
gnunet/src/dht/dht.h
gnunet/src/dht/gnunet-service-dht.c
Log:
messages 'hone in' more the higher the number of hops, still needs some tweaking
Modified: gnunet/src/dht/dht.h
===================================================================
--- gnunet/src/dht/dht.h 2010-09-06 12:46:14 UTC (rev 12861)
+++ gnunet/src/dht/dht.h 2010-09-06 20:29:29 UTC (rev 12862)
@@ -31,7 +31,7 @@
#define DEBUG_DHT_ROUTING GNUNET_YES
-#define DHT_BLOOM_SIZE 32
+#define DHT_BLOOM_SIZE 16
#define DHT_BLOOM_K 8
Modified: gnunet/src/dht/gnunet-service-dht.c
===================================================================
--- gnunet/src/dht/gnunet-service-dht.c 2010-09-06 12:46:14 UTC (rev 12861)
+++ gnunet/src/dht/gnunet-service-dht.c 2010-09-06 20:29:29 UTC (rev 12862)
@@ -44,6 +44,8 @@
#define PRINT_TABLES GNUNET_NO
+#define REAL_DISTANCE GNUNET_YES
+
#define EXTRA_CHECKS GNUNET_NO
/**
* How many buckets will we allow total.
@@ -99,7 +101,7 @@
/**
* Default replication parameter for find peer messages sent by the dht
service.
*/
-#define DHT_DEFAULT_FIND_PEER_REPLICATION 2
+#define DHT_DEFAULT_FIND_PEER_REPLICATION 4
/**
* Default options for find peer requests sent by the dht service.
@@ -162,6 +164,33 @@
*/
#define MAX_REPLY_TIMES 8
+enum ConvergenceOptions
+{
+ /**
+ * Use the linear method for convergence.
+ */
+ DHT_CONVERGE_LINEAR,
+
+ /**
+ * Converge using a fast converging square
+ * function.
+ */
+ DHT_CONVERGE_SQUARE,
+
+ /**
+ * Converge using a slower exponential
+ * function.
+ */
+ DHT_CONVERGE_EXPONENTIAL,
+
+ /**
+ * Don't do any special convergence, allow
+ * the algorithm to hopefully route to closer
+ * peers more often.
+ */
+ DHT_CONVERGE_RANDOM
+};
+
/**
* Linked list of messages to send to clients.
*/
@@ -250,16 +279,6 @@
struct GNUNET_TIME_Relative latency;
/**
- * Number of responses received
- */
- unsigned long long response_count;
-
- /**
- * Number of requests sent
- */
- unsigned long long request_count;
-
- /**
* What is the identity of the peer?
*/
struct GNUNET_PeerIdentity id;
@@ -596,6 +615,11 @@
};
/**
+ * Which kind of convergence will we be using?
+ */
+enum ConvergenceOptions converge_option;
+
+/**
* Recent requests by hash/uid and by time inserted.
*/
static struct RecentRequests recent;
@@ -1875,8 +1899,6 @@
increment_stats(STAT_HELLOS_PROVIDED);
GNUNET_TRANSPORT_offer_hello(transport_handle, hello_msg);
GNUNET_CORE_peer_request_connect(sched, cfg,
GNUNET_TIME_UNIT_FOREVER_REL, &new_peer, NULL, NULL);
- /* peer_request_connect call causes service to segfault */
- /* FIXME: Do we need this (peer_request_connect call)??? */
}
}
}
@@ -2470,17 +2492,14 @@
int bucket_num;
int count;
struct PeerInfo *pos;
-#if INTEGER_DISTANCE
unsigned int my_distance;
-#endif
+
bucket_num = find_current_bucket(target);
if (bucket_num == GNUNET_SYSERR) /* Same key! */
return GNUNET_YES;
bits = matching_bits(&my_identity.hashPubKey, target);
-#if INTEGER_DISTANCE
my_distance = distance(&my_identity.hashPubKey, target);
-#endif
pos = k_buckets[bucket_num].head;
count = 0;
while ((pos != NULL) && (count < bucket_size))
@@ -2496,10 +2515,10 @@
return GNUNET_NO;
else if (other_bits == bits) /* We match the same number of bits, do
distance comparison */
{
- return GNUNET_YES;
- /* FIXME: why not just return GNUNET_YES here? We are certainly
close. */
- /*if (distance(&pos->id.hashPubKey, target) < my_distance)
- return GNUNET_NO;*/
+ if (strict_kademlia != GNUNET_YES) /* Return that we at as close as
any other peer */
+ return GNUNET_YES;
+ else if (distance(&pos->id.hashPubKey, target) < my_distance) /*
Check all known peers, only return if we are the true closest */
+ return GNUNET_NO;
}
pos = pos->next;
}
@@ -2532,6 +2551,77 @@
}
/**
+ * Decide whether to route this request exclusively
+ * to a closer peer (if closer peers exist) or to choose
+ * from the whole set of peers.
+ *
+ * @param hops number of hops this message has already traveled
+ */
+int
+route_closer (const GNUNET_HashCode *target, struct
GNUNET_CONTAINER_BloomFilter *bloom,
+ unsigned int hops)
+{
+ unsigned int my_matching_bits;
+ unsigned int bc;
+ uint32_t random_value;
+ struct PeerInfo *pos;
+ int have_closer;
+ int count;
+ my_matching_bits = matching_bits(target, &my_identity.hashPubKey);
+
+ /**
+ * First check if we know any close (as close as us or closer) peers.
+ */
+ have_closer = GNUNET_NO;
+ count = 0;
+ for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++)
+ {
+ pos = k_buckets[bc].head;
+ count = 0;
+ while ((pos != NULL) && (count < bucket_size))
+ {
+ if ((matching_bits(target, &pos->id.hashPubKey) > my_matching_bits)
&&
+ (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom,
&pos->id.hashPubKey)))
+ {
+ have_closer = GNUNET_YES;
+ break;
+ }
+ pos = pos->next;
+ count++;
+ }
+ if (have_closer == GNUNET_YES)
+ break;
+ }
+
+ if (have_closer == GNUNET_NO) /* We don't have a same distance or closer
node, can't enforce closer only! */
+ return GNUNET_NO;
+
+ switch (converge_option)
+ {
+ case DHT_CONVERGE_LINEAR:
+ /**
+ * Simple linear curve for choosing whether or not to converge.
+ * Choose to route only closer with probability hops/MAX_HOPS.
+ */
+ random_value = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK,
MAX_HOPS);
+ if (random_value < hops)
+ return GNUNET_YES;
+ else
+ return GNUNET_NO;
+ case DHT_CONVERGE_SQUARE:
+ /**
+ * Simple square based curve.
+ */
+ if ((GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK,
(uint32_t)-1) / (double)(uint32_t)-1) < (sqrt(hops) / sqrt(MAX_HOPS)))
+ return GNUNET_YES;
+ else
+ return GNUNET_NO;
+ default:
+ return GNUNET_NO;
+ }
+}
+
+/**
* Select a peer from the routing table that would be a good routing
* destination for sending a message for "target". The resulting peer
* must not be in the set of blocked peers.<p>
@@ -2547,17 +2637,44 @@
*/
static struct PeerInfo *
select_peer (const GNUNET_HashCode * target,
- struct GNUNET_CONTAINER_BloomFilter *bloom)
+ struct GNUNET_CONTAINER_BloomFilter *bloom, unsigned int hops)
{
unsigned int distance;
unsigned int bc;
unsigned int count;
- struct PeerInfo *pos;
- struct PeerInfo *chosen;
+ unsigned int my_matching_bits;
unsigned long long largest_distance;
+#if REAL_DISTANCE
unsigned long long total_distance;
unsigned long long selected;
+#else
+ unsigned int total_distance;
+ unsigned int selected;
+#endif
+ int only_closer;
+ struct PeerInfo *pos;
+ struct PeerInfo *chosen;
+ char *temp_stat;
+
+ my_matching_bits = matching_bits(target, &my_identity.hashPubKey);
+ only_closer = route_closer(target, bloom, hops);
+
+ if (GNUNET_YES == only_closer)
+ {
+ GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "only routing to closer peers!\n");
+ GNUNET_asprintf(&temp_stat, "# closer only routes at hop %u", hops);
+ increment_stats(temp_stat);
+ }
+ else
+ {
+ GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "routing to all possible peers!\n");
+ GNUNET_asprintf(&temp_stat, "# NOT closer only routes at hop %u", hops);
+ increment_stats(temp_stat);
+ }
+
+ GNUNET_free(temp_stat);
+
if (strict_kademlia == GNUNET_YES)
{
largest_distance = 0;
@@ -2568,7 +2685,7 @@
count = 0;
while ((pos != NULL) && (count < bucket_size))
{
- /* If we are doing strict Kademlia like routing, then checking
the bloomfilter is basically cheating! */
+ /* If we are doing strict Kademlia routing, then checking the
bloomfilter is basically cheating! */
if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom,
&pos->id.hashPubKey))
{
distance = inverse_distance (target, &pos->id.hashPubKey);
@@ -2603,8 +2720,19 @@
count = 0;
while ((pos != NULL) && (count < bucket_size))
{
- if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom,
&pos->id.hashPubKey))
- total_distance += (unsigned long long)inverse_distance
(target, &pos->id.hashPubKey);
+ if ((GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom,
&pos->id.hashPubKey)) &&
+ ((only_closer == GNUNET_NO) || (matching_bits(target,
&pos->id.hashPubKey) >= my_matching_bits)))
+ {
+#if REAL_DISTANCE /* Use the "real" distance as computed by the
inverse_distance function */
+ /** The "real" distance is best for routing to the closest
peer, but in practice
+ * (with our routing algorithm) it is usually better to use
the squared bit distance.
+ * This gives us a higher probability of routing towards
close peers.
+ */
+ total_distance += (unsigned long long)inverse_distance
(target, &pos->id.hashPubKey);
+#else
+ total_distance += matching_bits(target, &pos->id.hashPubKey)
* matching_bits(target ,&pos->id.hashPubKey);
+#endif
+ }
#if DEBUG_DHT > 1
GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
"`%s:%s': Total distance is %llu, distance from %s
to %s is %u\n",
@@ -2616,21 +2744,30 @@
}
if (total_distance == 0)
{
+ increment_stats("# select_peer, total_distance == 0");
return NULL;
}
- selected = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
total_distance);
+ selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
total_distance);
for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++)
{
pos = k_buckets[bc].head;
count = 0;
while ((pos != NULL) && (count < bucket_size))
{
- if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom,
&pos->id.hashPubKey))
+ if ((GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom,
&pos->id.hashPubKey)) &&
+ ((only_closer == GNUNET_NO) || (matching_bits(target,
&pos->id.hashPubKey) >= my_matching_bits)))
{
+#if REAL_DISTANCE
distance = inverse_distance (target, &pos->id.hashPubKey);
+#else
+ distance = matching_bits(target, &pos->id.hashPubKey) *
matching_bits(target, &pos->id.hashPubKey);
+#endif
if (distance > selected)
- return pos;
+ {
+ GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Selected peer with
%u matching bits to route to\n", distance);
+ return pos;
+ }
selected -= distance;
}
else
@@ -2650,6 +2787,8 @@
"`%s:%s': peer %s matches bloomfilter.\n",
my_short_id, "DHT", GNUNET_i2s(&pos->id));
#endif
+ increment_stats("# failed to select peer");
+ GNUNET_assert(only_closer == GNUNET_NO);
return NULL;
}
}
@@ -2938,7 +3077,7 @@
for (i = 0; i < forward_count; i++)
{
- selected = select_peer(&message_context->key, message_context->bloom);
+ selected = select_peer(&message_context->key, message_context->bloom,
message_context->hop_count);
if (selected != NULL)
{
@@ -2962,11 +3101,11 @@
}
else
{
-#if DEBUG_DHT
+ increment_stats("# NULL returned from select_peer");
GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
"`%s:%s': No peers selected for forwarding.\n",
my_short_id,
"DHT");
-#endif
+
}
}
#if DEBUG_DHT_ROUTING > 1
@@ -3804,6 +3943,14 @@
}
}
+ converge_option = DHT_CONVERGE_SQUARE;
+ if (GNUNET_YES ==
+ GNUNET_CONFIGURATION_get_value_yesno(cfg, "dht_testing",
+ "converge_linear"))
+ {
+ converge_option = DHT_CONVERGE_LINEAR;
+ }
+
stats = GNUNET_STATISTICS_create(sched, "dht", cfg);
if (stats != NULL)
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r12862 - gnunet/src/dht,
gnunet <=