From b046370d179073ed9a3a5ee2eb61269a5178767a Mon Sep 17 00:00:00 2001 From: Supriti Singh Date: Tue, 5 Aug 2014 13:24:53 +0000 Subject: [PATCH] Exponential backoff for find_finger_trail_task --- src/dht/gnunet-service-xdht_neighbours.c | 117 +++++++++++++++++------ src/dht/gnunet-service-xdht_routing.c | 4 +- 2 files changed, 90 insertions(+), 31 deletions(-) diff --git a/src/dht/gnunet-service-xdht_neighbours.c b/src/dht/gnunet-service-xdht_neighbours.c index 90e89af08..d5139ca73 100644 --- a/src/dht/gnunet-service-xdht_neighbours.c +++ b/src/dht/gnunet-service-xdht_neighbours.c @@ -1514,12 +1514,9 @@ GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer, adm->source_peer = source_peer; adm->destination_peer = destination_peer; adm->trail_id = trail_id; - - if (trail_length > 0) - { - peer_list = (struct GNUNET_PeerIdentity *)&adm[1]; - memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length); - } + peer_list = (struct GNUNET_PeerIdentity *)&adm[1]; + memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length); + /* Send the message to chosen friend. */ GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); target_friend->pending_count++; @@ -1590,16 +1587,14 @@ search_my_index (const struct GNUNET_PeerIdentity *trail, int trail_length) { int i; - int lowest_index = -1; for (i = 0; i < trail_length; i++) { if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i])) - //lowest_index = i; return i; } - return lowest_index; + return -1; } @@ -2491,6 +2486,7 @@ compute_finger_identity_value (unsigned int finger_index) } } +static struct GNUNET_TIME_Relative next_send_time; /* * Choose a random friend. Calculate the next finger identity to search,from @@ -2505,19 +2501,16 @@ send_find_finger_trail_message (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) { struct FriendInfo *target_friend; - struct GNUNET_TIME_Relative next_send_time; + //struct GNUNET_TIME_Relative next_send_time; struct GNUNET_HashCode trail_id; struct GNUNET_HashCode intermediate_trail_id; unsigned int is_predecessor; uint64_t finger_id_value; - + /* Schedule another send_find_finger_trail_message task. */ - next_send_time.rel_value_us = - DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us + - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us); find_finger_trail_task = - GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message, + GNUNET_SCHEDULER_add_delayed (next_send_time, + &send_find_finger_trail_message, NULL); /* No space in my routing table. (Source and destination peers also store entries @@ -3066,7 +3059,6 @@ scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity, i++; } *new_trail_length = j+1; - GNUNET_assert((j+1) == (trail_length - 1)); //FIXME: remove it afterwards. return new_trail; } } @@ -3375,12 +3367,16 @@ finger_table_add (struct GNUNET_PeerIdentity finger_identity, &successor->finger_identity)) { current_search_finger_index = 0; + /* We slow down the find_finger_trail_task as we have completed the circle. */ + next_send_time = GNUNET_TIME_STD_BACKOFF(next_send_time); + return; } - struct FingerInfo *prev_finger; - prev_finger = &finger_table[finger_table_index - 1]; + + struct FingerInfo prev_finger; + prev_finger = finger_table[finger_table_index - 1]; if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, - &prev_finger->finger_identity)) + &prev_finger.finger_identity)) { current_search_finger_index--; return; @@ -3904,6 +3900,41 @@ get_local_best_known_next_hop (uint64_t final_dest_finger_val, return peer; } +#if 0 +/** + * Check if peer is already present in the trail. + * @param peer + * @param trail + * @param trail_length + * @return + */ +static struct GNUNET_PeerIdentity * +check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail, + unsigned int trail_length, + unsigned int *updated_trail_length) +{ + struct GNUNET_PeerIdentity *updated_trail; + unsigned int i; + unsigned int j; + + /* It may happen that there are more than one peer present twice. + but we don't want to*/ + for(i = 0;i < trail_length; i++) + { + for(j = i+1; j < trail_length; j++) + { + if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail[i],&trail[j])) + continue; + + /* If you found a duplicate entry in the trail, then you should + * have the entry at i should point to next of entry stored at j*/ + + /* In case j = (trail_length - 1), then it should NULL. */ + + } + } +} +#endif /* * Core handle for PeerTrailSetupMessage. @@ -3926,6 +3957,7 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer, struct GNUNET_HashCode trail_id; unsigned int is_predecessor; uint32_t trail_length; + unsigned int i; size_t msize; msize = ntohs (message->size); @@ -3954,6 +3986,14 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer, is_predecessor = ntohl (trail_setup->is_predecessor); intermediate_trail_id = trail_setup->intermediate_trail_id; + /* Did the friend insert its ID in the trail list? */ + if (trail_length > 0 && + 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (*peer))) + { + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + /* If I was the source and got the message back, then set trail length to 0.*/ if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source)) { @@ -3971,14 +4011,21 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer, trail_length = 0; } - /* Did the friend insert its ID in the trail list? */ - if (trail_length > 0 && - 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (*peer))) + /* Check if you are present in the trail seen so far? */ + if(trail_length > 0) { - GNUNET_break_op (0); - return GNUNET_SYSERR; + for (i = 0; i < trail_length ; i++) + { + if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity)) + { + //Here if you already were present in the trail. then you + // shoudl trail length to i + 1 + trail_length = i+1; + break; + } + } } - + /* Is my routing table full? */ if (GNUNET_YES == GDS_ROUTING_threshold_reached()) { @@ -4208,6 +4255,9 @@ handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *p } #endif + /*TODO:URGENT Check if I am already present in the trail. If yes then its an error, + as in trail setup we ensure that it should never happen. */ + /* Am I the one who initiated the query? */ if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity))) { @@ -4646,9 +4696,9 @@ handle_dht_p2p_verify_successor(void *cls, &source_peer))) { trail_src_to_curr_pred = get_trail_src_to_curr_pred (source_peer, - trail, - trail_length, - &trail_src_to_curr_pred_len); + trail, + trail_length, + &trail_src_to_curr_pred_len); } else { @@ -4819,6 +4869,8 @@ compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ, /* Remove the existing successor. */ remove_existing_finger (current_successor, 0); + /* TODO URGENT: Check if any peer is present more than once, if yes then shorten + the trail. before sending it across the network. */ /* Generate a new trail id to reach to your new successor. */ GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG, &trail_id, sizeof (trail_id)); @@ -5319,6 +5371,7 @@ handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer, msize = ntohs (message->size); /* In this message we pass the whole trail from source to destination as we * are adding that trail.*/ + //FIXME: failed when run with 1000 pears. check why. if (msize < sizeof (struct PeerAddTrailMessage)) { GNUNET_break_op (0); @@ -5627,7 +5680,13 @@ handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity) /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/ if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task) + { + next_send_time.rel_value_us = + DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us + + GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, + DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us); find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL); + } } diff --git a/src/dht/gnunet-service-xdht_routing.c b/src/dht/gnunet-service-xdht_routing.c index de5255cb7..087d4dcff 100644 --- a/src/dht/gnunet-service-xdht_routing.c +++ b/src/dht/gnunet-service-xdht_routing.c @@ -320,8 +320,8 @@ GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id, ret = GNUNET_CONTAINER_multihashmap_put (routing_table, - &new_trail_id, new_entry, - GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); + &new_trail_id, new_entry, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); //GNUNET_assert(ret == GNUNET_OK); return ret; } -- 2.25.1