diff options
author | Nathan S. Evans <evans@in.tum.de> | 2010-09-06 20:29:29 +0000 |
---|---|---|
committer | Nathan S. Evans <evans@in.tum.de> | 2010-09-06 20:29:29 +0000 |
commit | 423736ee4df736eb39ec8072526c9a61d341b5d6 (patch) | |
tree | 93bacde7d8492c9df16019642adeeb97de6c71b8 | |
parent | 83bfe795348dfcdb83cb565dd81d0a32fcb43dba (diff) | |
download | gnunet-423736ee4df736eb39ec8072526c9a61d341b5d6.tar.gz gnunet-423736ee4df736eb39ec8072526c9a61d341b5d6.zip |
messages 'hone in' more the higher the number of hops, still needs some tweaking
-rw-r--r-- | src/dht/dht.h | 2 | ||||
-rw-r--r-- | src/dht/gnunet-service-dht.c | 213 |
2 files changed, 181 insertions, 34 deletions
diff --git a/src/dht/dht.h b/src/dht/dht.h index 04931e1c3..0f662f0b1 100644 --- a/src/dht/dht.h +++ b/src/dht/dht.h | |||
@@ -31,7 +31,7 @@ | |||
31 | 31 | ||
32 | #define DEBUG_DHT_ROUTING GNUNET_YES | 32 | #define DEBUG_DHT_ROUTING GNUNET_YES |
33 | 33 | ||
34 | #define DHT_BLOOM_SIZE 32 | 34 | #define DHT_BLOOM_SIZE 16 |
35 | 35 | ||
36 | #define DHT_BLOOM_K 8 | 36 | #define DHT_BLOOM_K 8 |
37 | 37 | ||
diff --git a/src/dht/gnunet-service-dht.c b/src/dht/gnunet-service-dht.c index 38797127c..5150321df 100644 --- a/src/dht/gnunet-service-dht.c +++ b/src/dht/gnunet-service-dht.c | |||
@@ -44,6 +44,8 @@ | |||
44 | 44 | ||
45 | #define PRINT_TABLES GNUNET_NO | 45 | #define PRINT_TABLES GNUNET_NO |
46 | 46 | ||
47 | #define REAL_DISTANCE GNUNET_YES | ||
48 | |||
47 | #define EXTRA_CHECKS GNUNET_NO | 49 | #define EXTRA_CHECKS GNUNET_NO |
48 | /** | 50 | /** |
49 | * How many buckets will we allow total. | 51 | * How many buckets will we allow total. |
@@ -99,7 +101,7 @@ | |||
99 | /** | 101 | /** |
100 | * Default replication parameter for find peer messages sent by the dht service. | 102 | * Default replication parameter for find peer messages sent by the dht service. |
101 | */ | 103 | */ |
102 | #define DHT_DEFAULT_FIND_PEER_REPLICATION 2 | 104 | #define DHT_DEFAULT_FIND_PEER_REPLICATION 4 |
103 | 105 | ||
104 | /** | 106 | /** |
105 | * Default options for find peer requests sent by the dht service. | 107 | * Default options for find peer requests sent by the dht service. |
@@ -162,6 +164,33 @@ | |||
162 | */ | 164 | */ |
163 | #define MAX_REPLY_TIMES 8 | 165 | #define MAX_REPLY_TIMES 8 |
164 | 166 | ||
167 | enum ConvergenceOptions | ||
168 | { | ||
169 | /** | ||
170 | * Use the linear method for convergence. | ||
171 | */ | ||
172 | DHT_CONVERGE_LINEAR, | ||
173 | |||
174 | /** | ||
175 | * Converge using a fast converging square | ||
176 | * function. | ||
177 | */ | ||
178 | DHT_CONVERGE_SQUARE, | ||
179 | |||
180 | /** | ||
181 | * Converge using a slower exponential | ||
182 | * function. | ||
183 | */ | ||
184 | DHT_CONVERGE_EXPONENTIAL, | ||
185 | |||
186 | /** | ||
187 | * Don't do any special convergence, allow | ||
188 | * the algorithm to hopefully route to closer | ||
189 | * peers more often. | ||
190 | */ | ||
191 | DHT_CONVERGE_RANDOM | ||
192 | }; | ||
193 | |||
165 | /** | 194 | /** |
166 | * Linked list of messages to send to clients. | 195 | * Linked list of messages to send to clients. |
167 | */ | 196 | */ |
@@ -250,16 +279,6 @@ struct PeerInfo | |||
250 | struct GNUNET_TIME_Relative latency; | 279 | struct GNUNET_TIME_Relative latency; |
251 | 280 | ||
252 | /** | 281 | /** |
253 | * Number of responses received | ||
254 | */ | ||
255 | unsigned long long response_count; | ||
256 | |||
257 | /** | ||
258 | * Number of requests sent | ||
259 | */ | ||
260 | unsigned long long request_count; | ||
261 | |||
262 | /** | ||
263 | * What is the identity of the peer? | 282 | * What is the identity of the peer? |
264 | */ | 283 | */ |
265 | struct GNUNET_PeerIdentity id; | 284 | struct GNUNET_PeerIdentity id; |
@@ -596,6 +615,11 @@ struct RecentRequest | |||
596 | }; | 615 | }; |
597 | 616 | ||
598 | /** | 617 | /** |
618 | * Which kind of convergence will we be using? | ||
619 | */ | ||
620 | enum ConvergenceOptions converge_option; | ||
621 | |||
622 | /** | ||
599 | * Recent requests by hash/uid and by time inserted. | 623 | * Recent requests by hash/uid and by time inserted. |
600 | */ | 624 | */ |
601 | static struct RecentRequests recent; | 625 | static struct RecentRequests recent; |
@@ -1875,8 +1899,6 @@ static int route_result_message(void *cls, | |||
1875 | increment_stats(STAT_HELLOS_PROVIDED); | 1899 | increment_stats(STAT_HELLOS_PROVIDED); |
1876 | GNUNET_TRANSPORT_offer_hello(transport_handle, hello_msg); | 1900 | GNUNET_TRANSPORT_offer_hello(transport_handle, hello_msg); |
1877 | GNUNET_CORE_peer_request_connect(sched, cfg, GNUNET_TIME_UNIT_FOREVER_REL, &new_peer, NULL, NULL); | 1901 | GNUNET_CORE_peer_request_connect(sched, cfg, GNUNET_TIME_UNIT_FOREVER_REL, &new_peer, NULL, NULL); |
1878 | /* peer_request_connect call causes service to segfault */ | ||
1879 | /* FIXME: Do we need this (peer_request_connect call)??? */ | ||
1880 | } | 1902 | } |
1881 | } | 1903 | } |
1882 | } | 1904 | } |
@@ -2470,17 +2492,14 @@ am_closest_peer (const GNUNET_HashCode * target, struct GNUNET_CONTAINER_BloomFi | |||
2470 | int bucket_num; | 2492 | int bucket_num; |
2471 | int count; | 2493 | int count; |
2472 | struct PeerInfo *pos; | 2494 | struct PeerInfo *pos; |
2473 | #if INTEGER_DISTANCE | ||
2474 | unsigned int my_distance; | 2495 | unsigned int my_distance; |
2475 | #endif | 2496 | |
2476 | bucket_num = find_current_bucket(target); | 2497 | bucket_num = find_current_bucket(target); |
2477 | if (bucket_num == GNUNET_SYSERR) /* Same key! */ | 2498 | if (bucket_num == GNUNET_SYSERR) /* Same key! */ |
2478 | return GNUNET_YES; | 2499 | return GNUNET_YES; |
2479 | 2500 | ||
2480 | bits = matching_bits(&my_identity.hashPubKey, target); | 2501 | bits = matching_bits(&my_identity.hashPubKey, target); |
2481 | #if INTEGER_DISTANCE | ||
2482 | my_distance = distance(&my_identity.hashPubKey, target); | 2502 | my_distance = distance(&my_identity.hashPubKey, target); |
2483 | #endif | ||
2484 | pos = k_buckets[bucket_num].head; | 2503 | pos = k_buckets[bucket_num].head; |
2485 | count = 0; | 2504 | count = 0; |
2486 | while ((pos != NULL) && (count < bucket_size)) | 2505 | while ((pos != NULL) && (count < bucket_size)) |
@@ -2496,10 +2515,10 @@ am_closest_peer (const GNUNET_HashCode * target, struct GNUNET_CONTAINER_BloomFi | |||
2496 | return GNUNET_NO; | 2515 | return GNUNET_NO; |
2497 | else if (other_bits == bits) /* We match the same number of bits, do distance comparison */ | 2516 | else if (other_bits == bits) /* We match the same number of bits, do distance comparison */ |
2498 | { | 2517 | { |
2499 | return GNUNET_YES; | 2518 | if (strict_kademlia != GNUNET_YES) /* Return that we at as close as any other peer */ |
2500 | /* FIXME: why not just return GNUNET_YES here? We are certainly close. */ | 2519 | return GNUNET_YES; |
2501 | /*if (distance(&pos->id.hashPubKey, target) < my_distance) | 2520 | else if (distance(&pos->id.hashPubKey, target) < my_distance) /* Check all known peers, only return if we are the true closest */ |
2502 | return GNUNET_NO;*/ | 2521 | return GNUNET_NO; |
2503 | } | 2522 | } |
2504 | pos = pos->next; | 2523 | pos = pos->next; |
2505 | } | 2524 | } |
@@ -2532,6 +2551,77 @@ am_closest_peer (const GNUNET_HashCode * target, struct GNUNET_CONTAINER_BloomFi | |||
2532 | } | 2551 | } |
2533 | 2552 | ||
2534 | /** | 2553 | /** |
2554 | * Decide whether to route this request exclusively | ||
2555 | * to a closer peer (if closer peers exist) or to choose | ||
2556 | * from the whole set of peers. | ||
2557 | * | ||
2558 | * @param hops number of hops this message has already traveled | ||
2559 | */ | ||
2560 | int | ||
2561 | route_closer (const GNUNET_HashCode *target, struct GNUNET_CONTAINER_BloomFilter *bloom, | ||
2562 | unsigned int hops) | ||
2563 | { | ||
2564 | unsigned int my_matching_bits; | ||
2565 | unsigned int bc; | ||
2566 | uint32_t random_value; | ||
2567 | struct PeerInfo *pos; | ||
2568 | int have_closer; | ||
2569 | int count; | ||
2570 | my_matching_bits = matching_bits(target, &my_identity.hashPubKey); | ||
2571 | |||
2572 | /** | ||
2573 | * First check if we know any close (as close as us or closer) peers. | ||
2574 | */ | ||
2575 | have_closer = GNUNET_NO; | ||
2576 | count = 0; | ||
2577 | for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++) | ||
2578 | { | ||
2579 | pos = k_buckets[bc].head; | ||
2580 | count = 0; | ||
2581 | while ((pos != NULL) && (count < bucket_size)) | ||
2582 | { | ||
2583 | if ((matching_bits(target, &pos->id.hashPubKey) > my_matching_bits) && | ||
2584 | (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))) | ||
2585 | { | ||
2586 | have_closer = GNUNET_YES; | ||
2587 | break; | ||
2588 | } | ||
2589 | pos = pos->next; | ||
2590 | count++; | ||
2591 | } | ||
2592 | if (have_closer == GNUNET_YES) | ||
2593 | break; | ||
2594 | } | ||
2595 | |||
2596 | if (have_closer == GNUNET_NO) /* We don't have a same distance or closer node, can't enforce closer only! */ | ||
2597 | return GNUNET_NO; | ||
2598 | |||
2599 | switch (converge_option) | ||
2600 | { | ||
2601 | case DHT_CONVERGE_LINEAR: | ||
2602 | /** | ||
2603 | * Simple linear curve for choosing whether or not to converge. | ||
2604 | * Choose to route only closer with probability hops/MAX_HOPS. | ||
2605 | */ | ||
2606 | random_value = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, MAX_HOPS); | ||
2607 | if (random_value < hops) | ||
2608 | return GNUNET_YES; | ||
2609 | else | ||
2610 | return GNUNET_NO; | ||
2611 | case DHT_CONVERGE_SQUARE: | ||
2612 | /** | ||
2613 | * Simple square based curve. | ||
2614 | */ | ||
2615 | if ((GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, (uint32_t)-1) / (double)(uint32_t)-1) < (sqrt(hops) / sqrt(MAX_HOPS))) | ||
2616 | return GNUNET_YES; | ||
2617 | else | ||
2618 | return GNUNET_NO; | ||
2619 | default: | ||
2620 | return GNUNET_NO; | ||
2621 | } | ||
2622 | } | ||
2623 | |||
2624 | /** | ||
2535 | * Select a peer from the routing table that would be a good routing | 2625 | * Select a peer from the routing table that would be a good routing |
2536 | * destination for sending a message for "target". The resulting peer | 2626 | * destination for sending a message for "target". The resulting peer |
2537 | * must not be in the set of blocked peers.<p> | 2627 | * must not be in the set of blocked peers.<p> |
@@ -2547,16 +2637,43 @@ am_closest_peer (const GNUNET_HashCode * target, struct GNUNET_CONTAINER_BloomFi | |||
2547 | */ | 2637 | */ |
2548 | static struct PeerInfo * | 2638 | static struct PeerInfo * |
2549 | select_peer (const GNUNET_HashCode * target, | 2639 | select_peer (const GNUNET_HashCode * target, |
2550 | struct GNUNET_CONTAINER_BloomFilter *bloom) | 2640 | struct GNUNET_CONTAINER_BloomFilter *bloom, unsigned int hops) |
2551 | { | 2641 | { |
2552 | unsigned int distance; | 2642 | unsigned int distance; |
2553 | unsigned int bc; | 2643 | unsigned int bc; |
2554 | unsigned int count; | 2644 | unsigned int count; |
2555 | struct PeerInfo *pos; | 2645 | unsigned int my_matching_bits; |
2556 | struct PeerInfo *chosen; | ||
2557 | unsigned long long largest_distance; | 2646 | unsigned long long largest_distance; |
2647 | #if REAL_DISTANCE | ||
2558 | unsigned long long total_distance; | 2648 | unsigned long long total_distance; |
2559 | unsigned long long selected; | 2649 | unsigned long long selected; |
2650 | #else | ||
2651 | unsigned int total_distance; | ||
2652 | unsigned int selected; | ||
2653 | #endif | ||
2654 | |||
2655 | int only_closer; | ||
2656 | struct PeerInfo *pos; | ||
2657 | struct PeerInfo *chosen; | ||
2658 | char *temp_stat; | ||
2659 | |||
2660 | my_matching_bits = matching_bits(target, &my_identity.hashPubKey); | ||
2661 | only_closer = route_closer(target, bloom, hops); | ||
2662 | |||
2663 | if (GNUNET_YES == only_closer) | ||
2664 | { | ||
2665 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "only routing to closer peers!\n"); | ||
2666 | GNUNET_asprintf(&temp_stat, "# closer only routes at hop %u", hops); | ||
2667 | increment_stats(temp_stat); | ||
2668 | } | ||
2669 | else | ||
2670 | { | ||
2671 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "routing to all possible peers!\n"); | ||
2672 | GNUNET_asprintf(&temp_stat, "# NOT closer only routes at hop %u", hops); | ||
2673 | increment_stats(temp_stat); | ||
2674 | } | ||
2675 | |||
2676 | GNUNET_free(temp_stat); | ||
2560 | 2677 | ||
2561 | if (strict_kademlia == GNUNET_YES) | 2678 | if (strict_kademlia == GNUNET_YES) |
2562 | { | 2679 | { |
@@ -2568,7 +2685,7 @@ select_peer (const GNUNET_HashCode * target, | |||
2568 | count = 0; | 2685 | count = 0; |
2569 | while ((pos != NULL) && (count < bucket_size)) | 2686 | while ((pos != NULL) && (count < bucket_size)) |
2570 | { | 2687 | { |
2571 | /* If we are doing strict Kademlia like routing, then checking the bloomfilter is basically cheating! */ | 2688 | /* If we are doing strict Kademlia routing, then checking the bloomfilter is basically cheating! */ |
2572 | if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)) | 2689 | if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)) |
2573 | { | 2690 | { |
2574 | distance = inverse_distance (target, &pos->id.hashPubKey); | 2691 | distance = inverse_distance (target, &pos->id.hashPubKey); |
@@ -2603,8 +2720,19 @@ select_peer (const GNUNET_HashCode * target, | |||
2603 | count = 0; | 2720 | count = 0; |
2604 | while ((pos != NULL) && (count < bucket_size)) | 2721 | while ((pos != NULL) && (count < bucket_size)) |
2605 | { | 2722 | { |
2606 | if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)) | 2723 | if ((GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)) && |
2607 | total_distance += (unsigned long long)inverse_distance (target, &pos->id.hashPubKey); | 2724 | ((only_closer == GNUNET_NO) || (matching_bits(target, &pos->id.hashPubKey) >= my_matching_bits))) |
2725 | { | ||
2726 | #if REAL_DISTANCE /* Use the "real" distance as computed by the inverse_distance function */ | ||
2727 | /** The "real" distance is best for routing to the closest peer, but in practice | ||
2728 | * (with our routing algorithm) it is usually better to use the squared bit distance. | ||
2729 | * This gives us a higher probability of routing towards close peers. | ||
2730 | */ | ||
2731 | total_distance += (unsigned long long)inverse_distance (target, &pos->id.hashPubKey); | ||
2732 | #else | ||
2733 | total_distance += matching_bits(target, &pos->id.hashPubKey) * matching_bits(target ,&pos->id.hashPubKey); | ||
2734 | #endif | ||
2735 | } | ||
2608 | #if DEBUG_DHT > 1 | 2736 | #if DEBUG_DHT > 1 |
2609 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 2737 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, |
2610 | "`%s:%s': Total distance is %llu, distance from %s to %s is %u\n", | 2738 | "`%s:%s': Total distance is %llu, distance from %s to %s is %u\n", |
@@ -2616,21 +2744,30 @@ select_peer (const GNUNET_HashCode * target, | |||
2616 | } | 2744 | } |
2617 | if (total_distance == 0) | 2745 | if (total_distance == 0) |
2618 | { | 2746 | { |
2747 | increment_stats("# select_peer, total_distance == 0"); | ||
2619 | return NULL; | 2748 | return NULL; |
2620 | } | 2749 | } |
2621 | 2750 | ||
2622 | selected = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, total_distance); | 2751 | selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, total_distance); |
2623 | for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++) | 2752 | for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++) |
2624 | { | 2753 | { |
2625 | pos = k_buckets[bc].head; | 2754 | pos = k_buckets[bc].head; |
2626 | count = 0; | 2755 | count = 0; |
2627 | while ((pos != NULL) && (count < bucket_size)) | 2756 | while ((pos != NULL) && (count < bucket_size)) |
2628 | { | 2757 | { |
2629 | if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)) | 2758 | if ((GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)) && |
2759 | ((only_closer == GNUNET_NO) || (matching_bits(target, &pos->id.hashPubKey) >= my_matching_bits))) | ||
2630 | { | 2760 | { |
2761 | #if REAL_DISTANCE | ||
2631 | distance = inverse_distance (target, &pos->id.hashPubKey); | 2762 | distance = inverse_distance (target, &pos->id.hashPubKey); |
2763 | #else | ||
2764 | distance = matching_bits(target, &pos->id.hashPubKey) * matching_bits(target, &pos->id.hashPubKey); | ||
2765 | #endif | ||
2632 | if (distance > selected) | 2766 | if (distance > selected) |
2633 | return pos; | 2767 | { |
2768 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Selected peer with %u matching bits to route to\n", distance); | ||
2769 | return pos; | ||
2770 | } | ||
2634 | selected -= distance; | 2771 | selected -= distance; |
2635 | } | 2772 | } |
2636 | else | 2773 | else |
@@ -2650,6 +2787,8 @@ select_peer (const GNUNET_HashCode * target, | |||
2650 | "`%s:%s': peer %s matches bloomfilter.\n", | 2787 | "`%s:%s': peer %s matches bloomfilter.\n", |
2651 | my_short_id, "DHT", GNUNET_i2s(&pos->id)); | 2788 | my_short_id, "DHT", GNUNET_i2s(&pos->id)); |
2652 | #endif | 2789 | #endif |
2790 | increment_stats("# failed to select peer"); | ||
2791 | GNUNET_assert(only_closer == GNUNET_NO); | ||
2653 | return NULL; | 2792 | return NULL; |
2654 | } | 2793 | } |
2655 | } | 2794 | } |
@@ -2938,7 +3077,7 @@ static int route_message(void *cls, | |||
2938 | 3077 | ||
2939 | for (i = 0; i < forward_count; i++) | 3078 | for (i = 0; i < forward_count; i++) |
2940 | { | 3079 | { |
2941 | selected = select_peer(&message_context->key, message_context->bloom); | 3080 | selected = select_peer(&message_context->key, message_context->bloom, message_context->hop_count); |
2942 | 3081 | ||
2943 | if (selected != NULL) | 3082 | if (selected != NULL) |
2944 | { | 3083 | { |
@@ -2962,11 +3101,11 @@ static int route_message(void *cls, | |||
2962 | } | 3101 | } |
2963 | else | 3102 | else |
2964 | { | 3103 | { |
2965 | #if DEBUG_DHT | 3104 | increment_stats("# NULL returned from select_peer"); |
2966 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 3105 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, |
2967 | "`%s:%s': No peers selected for forwarding.\n", my_short_id, | 3106 | "`%s:%s': No peers selected for forwarding.\n", my_short_id, |
2968 | "DHT"); | 3107 | "DHT"); |
2969 | #endif | 3108 | |
2970 | } | 3109 | } |
2971 | } | 3110 | } |
2972 | #if DEBUG_DHT_ROUTING > 1 | 3111 | #if DEBUG_DHT_ROUTING > 1 |
@@ -3804,6 +3943,14 @@ run (void *cls, | |||
3804 | } | 3943 | } |
3805 | } | 3944 | } |
3806 | 3945 | ||
3946 | converge_option = DHT_CONVERGE_SQUARE; | ||
3947 | if (GNUNET_YES == | ||
3948 | GNUNET_CONFIGURATION_get_value_yesno(cfg, "dht_testing", | ||
3949 | "converge_linear")) | ||
3950 | { | ||
3951 | converge_option = DHT_CONVERGE_LINEAR; | ||
3952 | } | ||
3953 | |||
3807 | stats = GNUNET_STATISTICS_create(sched, "dht", cfg); | 3954 | stats = GNUNET_STATISTICS_create(sched, "dht", cfg); |
3808 | 3955 | ||
3809 | if (stats != NULL) | 3956 | if (stats != NULL) |