- Fixes in routing table functions

3 files changed, 269 insertions, 192 deletions

diff --git a/src/dht/gnunet-service-xdht_neighbours.c b/src/dht/gnunet-service-xdht_neighbours.c
index 00b4580c7..f56abf093 100644
--- a/src/dht/gnunet-service-xdht_neighbours.c
+++ b/src/dht/gnunet-service-xdht_neighbours.c
@@ -47,12 +47,7 @@
 /* TODO:
  1. to randomly choose one of the routes in case there are multiple
     routes to reach to the finger. 
- 2. Use a global array of all known peers in find_successor, Only when 
-    a new peer is added in finger or friend peer map, then re calculate
-    the array. Or else use the old one. The benefit of having this list is something
-    I am not sure. only when the code is complete and working I will do this part. 
  3. Structure alignment.
- 4. Check where do you set all_friends_trail_threshold? In select_random_friend?
  5. In put, we don't have anything like put result. so we are not adding anything
     in the routing table. 
 */
@@ -598,6 +593,19 @@ struct FriendInfo
   unsigned int pending_count;
   
   /**
+   * FIXME: Refer to time.c and gnunet_time_lib.h for correct functions.
+   * in handle_dht_p2p_trail_rejection, you should update these values
+   * and whenever you are selecting a friend in select_random_friend()
+   * and find_successor(), you should check congestion_duration = 0,
+   * then proceed else if congestion_duration < your current time then also
+   * proceed. 
+   *        struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
+   *        struct GNUNET_TIME_Relative congestion_timeout =  
+   * congestion_duration = GNUNET_TIME_absolute_add (start,congestion_timeout);
+   */
+  struct GNUNET_TIME_Absolute congestion_duration;
+  
+  /**
    * Head of pending messages to be sent to this friend.
    */
   struct P2PPendingMessage *head;
@@ -1591,6 +1599,9 @@ send_find_finger_trail_message (void *cls,
 
 
 /**
+ * FIXME: You need to handle the case of predecessor in case you don't get
+ * the call from finger table add then you should not send a trail teardown message
+ * because no one has added that in their trail. 
  * Scan the trail to check if any of my own friend is part of trail. If yes
  * then shortcut the trail, send a trail teardown for the discarded trail,
  * update trail list and trail_length. 
@@ -1607,20 +1618,24 @@ scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
 {
   int i;
   struct FriendInfo *target_friend;
-
-  /* If finger is my friend, then send a trail teardown message and then set
-   * trail_length = 0; */
+   
+  if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger))
+  {
+    *trail_length = 0;
+    trail = NULL;
+    return;    
+  }
   if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger))
   {
     int discarded_trail_length = *trail_length;
     target_friend = GNUNET_CONTAINER_multipeermap_get(friend_peermap, &trail[0]);
     GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, trail,
                                         discarded_trail_length, target_friend, finger);
-    trail_length = 0;
+    *trail_length = 0;
     trail = NULL;
     return;
   }
-  
+ 
   i = *trail_length - 1;
   while (i > 1)
   {
@@ -1646,7 +1661,6 @@ scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
       discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
       memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
       target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
-
       GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
                                          discarded_trail_length, target_friend,
                                          &trail[i]);
@@ -1726,7 +1740,7 @@ void send_trail_teardown (struct FingerInfo *removed_finger)
    finger_trail = finger_trail->next;
    i++;
  }
- 
+
  GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(removed_finger->finger_identity),
                                      peer_list, removed_finger_trail_length, friend,
                                      &(removed_finger->finger_identity)); 
@@ -2024,7 +2038,7 @@ int select_closest_finger (struct FingerInfo *existing_finger,
        this case you don't need to check the trails. Exit. */
       return GNUNET_NO;
     }
-    if (trail_length > 1)
+    if (trail_length > 0)
     {
       scan_and_compress_trail (trail, &trail_length, new_finger);
     }
@@ -2056,8 +2070,10 @@ int select_closest_finger (struct FingerInfo *existing_finger,
     decrement_friend_trail_count (existing_finger);
     free_finger (existing_finger);
     
-    if (trail_length > 1)
+    if (trail_length > 0)
+    {
       scan_and_compress_trail (trail, &trail_length, new_finger);
+    }
     return GNUNET_YES;
   }
   else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index))
@@ -2090,6 +2106,7 @@ compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
   struct FingerInfo *new_finger_entry;
   struct FriendInfo *first_friend_trail;
   int i;
+  int old_entry_found = GNUNET_NO;
   
   finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap); 
   for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
@@ -2099,6 +2116,7 @@ compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
     {
       if (PREDECESSOR_FINGER_ID == existing_finger->finger_map_index)
       {
+        old_entry_found = GNUNET_YES;
         if( GNUNET_NO == select_closest_finger (existing_finger, peer, trail, 
                                                 trail_length,PREDECESSOR_FINGER_ID))
           return GNUNET_NO;
@@ -2108,6 +2126,11 @@ compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
     }
   }
   GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
+  if(GNUNET_NO == old_entry_found)
+  {
+    trail_length = 0;
+    trail = NULL;
+  }
   
   new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
   memcpy (&(new_finger_entry->finger_identity), peer, sizeof (struct GNUNET_PeerIdentity));
@@ -2115,7 +2138,7 @@ compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
   new_finger_entry->first_trail_length = trail_length;
   new_finger_entry->trail_count = 1;
   
-  if (trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */
+  if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity,peer)) /* finger_trail is NULL in case I am my own finger identity. */
   {
     /* FIXME: Currently we are not handling the second trail. In that case, finger
      trail count = min (first_friend, second_friend) trail count. */
@@ -2239,7 +2262,7 @@ add_new_entry (const struct GNUNET_PeerIdentity *finger_identity,
   new_finger_entry->first_trail_length = finger_trail_length;
   new_finger_entry->trail_count = 1;
   
-  if (finger_trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */
+  if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity)) /* finger_trail is NULL in case I am my own finger identity. */
   {
     /* Incrementing the friend trails count. */
     if (finger_trail_length > 0)   
@@ -2303,6 +2326,7 @@ int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
   struct FingerInfo *existing_finger;
   struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
   int i;
+  int old_entry_found = GNUNET_NO;
   int new_entry_added = GNUNET_NO;
    
   if (PREDECESSOR_FINGER_ID == finger_map_index)
@@ -2324,6 +2348,7 @@ int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
     {
       if (existing_finger->finger_map_index == finger_map_index)
       {
+        old_entry_found = GNUNET_YES;
         if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity, 
                                                  finger_trail, finger_trail_length,
                                                  finger_map_index)) 
@@ -2334,6 +2359,14 @@ int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
     } 
   }
   GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
+  
+  if (GNUNET_NO == old_entry_found)
+  {
+    if (finger_trail_length > 0)
+    {
+      scan_and_compress_trail (finger_trail, &finger_trail_length, finger_identity);
+    }
+  }
   /* SUPU: in this case you get GNUNET_NO, only when insertion fails in the peer map.
    so its an error as we already have decided to add the entry into finger peer map. */
   if(GNUNET_OK == add_new_entry (finger_identity,finger_trail,finger_trail_length, finger_map_index))
@@ -2357,7 +2390,6 @@ int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
     current_search_finger_index = current_search_finger_index - 1;
   }
   
-
   return new_entry_added;
 }
  
@@ -2947,11 +2979,12 @@ handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
   memcpy (&key_value, &(put->key), sizeof (uint64_t));
   if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_destination, &my_identity)))
   {
-     next_hop = GDS_ROUTING_search (&current_source, &current_destination, peer);
-     if (next_hop == NULL)
-     {
+    GDS_ROUTING_print();
+    next_hop = GDS_ROUTING_search (&current_source, &current_destination, peer);
+    if (next_hop == NULL)
+    {
        /* refer to handle_dht_p2p_trail_setup. */
-     }
+    }
   }
   else
   {
@@ -3044,11 +3077,12 @@ handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
   memcpy (&key_value, &(get->key), sizeof (uint64_t));
   if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_destination, &my_identity)))
   {
-     next_hop = GDS_ROUTING_search (&current_source, &current_destination, peer);
-     if (next_hop == NULL)
-     {
+    GDS_ROUTING_print();
+    next_hop = GDS_ROUTING_search (&current_source, &current_destination, peer);
+    if (next_hop == NULL)
+    {
        /* refer to handle_dht_p2p_trail_setup. */
-     }
+    }
   }
   else
   {
@@ -3245,6 +3279,7 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
   /* Check if you are current_destination or not. */
   if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_destination, &my_identity)))
   {
+    GDS_ROUTING_print();
     next_hop = GDS_ROUTING_search (&current_source, &current_destination, peer);
     /* OPTIMIZATION: Choose a peer from find_successor and choose the closest one.
      In case the closest one is from routing table and it is NULL, then update
@@ -3282,7 +3317,6 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
     }
     
     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
-    
     /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
     if (PREDECESSOR_FINGER_ID != finger_map_index)
     {
@@ -3305,7 +3339,6 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
       memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
     peer_list[trail_length] = my_identity;
     trail_length++;
-    
     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
     GDS_NEIGHBOURS_send_trail_setup (&source,
                                      destination_finger_value,
@@ -3386,8 +3419,13 @@ handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *p
     if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
                                                &(trail_result->finger_identity))))
     {
+      /* FIXME: First call GDS_ROUTING_search, only if it returns NULL, call
+       GDS_ROUTING_add. But in case we have same 3 fields but 1 different next hop
+       then we should add the entry but in current implementation of GDS_ROUTNG_search
+       we don't handle it. */
       GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
                        peer, &next_hop); 
+      GDS_ROUTING_print();
     }
     
     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
@@ -3551,6 +3589,12 @@ handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *pee
   {
    int my_index;
    
+   if (trail_length == 0)
+   {
+     GNUNET_break (0);
+     return GNUNET_SYSERR;
+   }
+   
    my_index = search_my_index (trail_peer_list, trail_length);
    if (my_index == GNUNET_SYSERR)
    {
@@ -3999,9 +4043,10 @@ int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *p
     my_index = search_my_index (discarded_trail, discarded_trail_length);
     if(GNUNET_SYSERR == my_index)
       return GNUNET_SYSERR;
-  
+
+    GDS_ROUTING_print();
     if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
-                                             &(trail_teardown->destination_peer),peer))
+                                               &(trail_teardown->destination_peer),peer))
     {
       /* Here we get GNUNET_NO, only if there is no matching entry found in routing
          table. */
@@ -4011,7 +4056,6 @@ int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *p
     
     memcpy (&next_hop, &discarded_trail[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); 
-    
     GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer), 
                                         &(trail_teardown->destination_peer),
                                         discarded_trail, discarded_trail_length, 
@@ -4022,87 +4066,6 @@ int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *p
 }
 
 
-#if 0
-/**
- * FIXME: we don't send trail teardown to finger for which the trail was setup.
- * Trail teardown only aim is to remove entries from the routing table. Destination
- * finger does not have any entry in its routing table. So, it does not need 
- * a trail teardown. 
- * Core handle for p2p trail tear down messages.
- * @param cls closure
- * @param message message
- * @param peer peer identity this notification is about
- * @return GNUNET_OK on success, GNUNET_SYSERR on error
- */
-static
-int handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
-                                   const struct GNUNET_MessageHeader *message)
-{
-  struct PeerTrailTearDownMessage *trail_teardown;
-  struct GNUNET_PeerIdentity *trail_peer_list;
-  struct GNUNET_PeerIdentity next_hop;
-  struct FriendInfo *target_friend;
-  uint32_t trail_length;
-  size_t msize;
-  int my_index;
-  
-  msize = ntohs (message->size);
-  if (msize < sizeof (struct PeerTrailTearDownMessage))
-  {
-    GNUNET_break_op (0);
-    return GNUNET_YES;
-  }
-  
-  trail_teardown = (struct PeerTrailTearDownMessage *) message;
-  trail_length = ntohl (trail_teardown->trail_length);
-  
-  if ((msize < sizeof (struct PeerTrailTearDownMessage) +
-               trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
-      (trail_length >
-       GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
-  {
-    GNUNET_break_op (0);
-    return GNUNET_YES;
-  }
-  
-  trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
-  
-  if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer), &my_identity)))
-  {
-    /* I am the destination of the trail, but I am not part of trail. I don't
-     need to remove any entry from my routing table. So, I should not get this
-     message. */
-    GNUNET_break (0);
-    return GNUNET_YES;
-  }
-  
-  my_index = search_my_index (trail_peer_list, trail_length);
-  if(GNUNET_SYSERR == my_index)
-    return GNUNET_SYSERR;
-  
-  if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
-                                             &(trail_teardown->destination_peer),peer))
-  {
-    /* Here we get GNUNET_NO, only if there is no matching entry found in routing
-     table. */
-    GNUNET_break (0);
-    return GNUNET_YES;
-  }
-  
-  /* I am the last element of the trail. */
-  if(my_index == trail_length - 1)
-    return GNUNET_YES;
-    
-  memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
-  target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); 
-  /* FIXME:add a new field new_first_friend. */
-  GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer), 
-                                      &(trail_teardown->destination_peer),
-                                      trail_peer_list, trail_length, target_friend);
-  return GNUNET_YES;
-}
-#endif
-
 /**
  * Iterate over finger_peermap, and remove entries with peer as the first element
  * of their trail.  
@@ -4170,6 +4133,7 @@ handle_core_disconnect (void *cls,
    * FIXME: Here do we only remove the entry from our own routing table
    * or do we also inform other peers which are part of trail. It seems to be
    * too much of messages exchanged. */
+  GDS_ROUTING_print();
   GDS_ROUTING_remove_entry (peer);
   
   /* Remove the peer from friend_peermap. */
@@ -4330,4 +4294,4 @@ GDS_NEIGHBOURS_get_my_id (void)
 }
 
 
-/* end of gnunet-service-xdht_neighbours.c */
+/* end of gnunet-service-xdht_neighbours.c */
\ No newline at end of file
diff --git a/src/dht/gnunet-service-xdht_routing.c b/src/dht/gnunet-service-xdht_routing.c
index 3601a4186..7bf96e9d0 100644
--- a/src/dht/gnunet-service-xdht_routing.c
+++ b/src/dht/gnunet-service-xdht_routing.c
@@ -34,11 +34,6 @@
  3. do we need next_hop to uniquely identify a trail in remove_trail. */
 
 /**
- * Number of requests we track at most (for routing replies).
- */
-#define DHT_MAX_RECENT (1024 * 16)
-
-/**
  * Maximum number of entries in routing table. 
  */
 #define ROUTING_TABLE_THRESHOLD 64
@@ -76,59 +71,76 @@ struct RoutingTrail
  */
 static struct GNUNET_CONTAINER_MultiPeerMap *routing_table;
 
+
 /**
- * Iterate over routing table and remove entries for which peer is a part. 
- * @param cls closure
- * @param key current public key
- * @param value value in the hash map
- * @return #GNUNET_YES if we should continue to
- *         iterate,
- *         #GNUNET_NO if not.
+ * Get next hop from the trail with source peer, destination peer and next hop
+ * same as the argument to this function. 
+ * @param source_peer  Source peer of the trail. 
+ * @param destination_peer Destination peer of the trail. 
+ * @param prev_hop Previous hop of the trail. 
+ * @return #GNUNET_YES if we found the matching trail. 
+ *         #GNUNET_NO if we found no matching trail.
  */
 static int
-remove_routing_entry (void *cls,
-                      const struct GNUNET_PeerIdentity *key,
-                      void *value)
+get_next_hop (struct RoutingTrail *trail,
+              struct GNUNET_PeerIdentity *source_peer,
+              struct GNUNET_PeerIdentity *destination_peer, 
+              const struct GNUNET_PeerIdentity *prev_hop)
 {
-  struct RoutingTrail *remove_entry = value;
-  const struct GNUNET_PeerIdentity *disconnected_peer = cls;
-  
-  if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->source), disconnected_peer)) ||
-      (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->destination), disconnected_peer)) ||    
-      (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->next_hop), disconnected_peer)) ||
-      (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->prev_hop), disconnected_peer)))
+  if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->source),source_peer))
   {
-    GNUNET_assert (GNUNET_YES ==
-                   GNUNET_CONTAINER_multipeermap_remove (routing_table,
-                                                         key, 
-                                                         remove_entry));
+    if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->prev_hop),prev_hop))
+    {
+      return GNUNET_YES;
+    }
+    else 
+      return GNUNET_NO;
   }
-  return GNUNET_YES;
+  return GNUNET_NO;
 }
 
 
 /**
- * Iterate over multiple entries for same destination value and get
- * the correct next hop.
- * @param cls struct RoutingTrail
- * @param key Destination identity
- * @param value struct RoutingTrail
- * @return #GNUNET_YES to continue looking, #GNUNET_NO if we found the next hop
+ * FIXME: How to ensure that with only 3 fields also we have a unique trail.
+ * in case of redundant routes we can have different next hop.
+ * in that case we have to call this function on each entry of routing table
+ * and from multiple next hop we return one. Here also we are going to return one.
+ * URGENT. 
+ * Assumption - there can be only on one trail with all these fields. But if
+ * we consider only 3 fields then it is possible that next hop is differet. 
+ * Update prev_hop field to source_peer. Trail from source peer to destination
+ * peer is compressed such that I am the first friend in the trail. 
+ * @param source_peer Source of the trail.
+ * @param destination_peer Destination of the trail.
+ * @param prev_hop Peer before me in the trail.
+ * @return #GNUNET_YES trail is updated.
+ *         #GNUNET_NO, trail not found. 
  */
 int
-get_next_hop (void *cls, const struct GNUNET_PeerIdentity *key, void *value)
+GDS_ROUTING_trail_update (struct GNUNET_PeerIdentity *source_peer,
+                          struct GNUNET_PeerIdentity *destination_peer,
+                          struct GNUNET_PeerIdentity *prev_hop)
 {
-  /* Here you should match if source, prev hop matches if yes then send 
-   GNUNET_NO as you don't need to check more entries. */
-  struct RoutingTrail *request = cls;
-  struct RoutingTrail *existing_entry = (struct RoutingTrail *)value;
+  /* 1. find the trail corresponding to these values. 
+   2. update the prev hop to source peer. */  
+  struct RoutingTrail *trail;
+  struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
+  int i;
   
-  if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(request->source), &(existing_entry->source)))
+  iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
+  for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
   {
-    if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(request->prev_hop), &(existing_entry->prev_hop)))
+    if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
+                                                                 (const void **)&trail)) 
     {
-      memcpy (&(request->next_hop), &(existing_entry->next_hop), sizeof (struct GNUNET_PeerIdentity));
-      return GNUNET_YES;
+      if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer))
+      {
+        if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop))
+        {
+          memcpy (&(trail->prev_hop), source_peer, sizeof (struct GNUNET_PeerIdentity));
+          return GNUNET_YES;
+        }
+      }
     }
   }
   return GNUNET_NO;
@@ -136,6 +148,42 @@ get_next_hop (void *cls, const struct GNUNET_PeerIdentity *key, void *value)
 
 
 /**
+ * Find the next hop to send packet to.
+ * @param source_peer Source of the trail.
+ * @param destination_peer Destination of the trail.
+ * @param prev_hop Previous hop in the trail. 
+ * @return Next hop in the trail from source to destination.
+ */
+struct GNUNET_PeerIdentity *
+GDS_ROUTING_search (struct GNUNET_PeerIdentity *source_peer,
+                    struct GNUNET_PeerIdentity *destination_peer,
+                    const struct GNUNET_PeerIdentity *prev_hop)
+{
+  struct RoutingTrail *trail;
+  struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
+  int i;
+  
+  iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
+  for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
+  {
+    if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
+                                                                 (const void **)&trail)) 
+    {
+      if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer))
+      {
+        if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop))
+        {
+          return &(trail->next_hop);
+        }
+      }
+    }
+  }
+  GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator);
+  return NULL;
+}
+
+
+/**
  * Add a new entry to our routing table.
  * @param source peer Source of the trail.
  * @param destintation Destination of the trail.
@@ -171,71 +219,100 @@ GDS_ROUTING_add (const struct GNUNET_PeerIdentity *source,
 
 /**
  * Iterate over routing table and remove entries for which peer is a part. 
- * @param peer
- * @return 
+ * @param cls closure
+ * @param key current public key
+ * @param value value in the hash map
+ * @return #GNUNET_YES if we should continue to
+ *         iterate,
+ *         #GNUNET_NO if not.
+ */
+static int
+remove_routing_entry (void *cls,
+                      const struct GNUNET_PeerIdentity *key,
+                      void *value)
+{
+  struct RoutingTrail *remove_entry = value;
+  const struct GNUNET_PeerIdentity *disconnected_peer = cls;
+  
+  if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->source), disconnected_peer)) ||
+      (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->destination), disconnected_peer)) ||    
+      (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->next_hop), disconnected_peer)) ||
+      (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->prev_hop), disconnected_peer)))
+  {
+    GNUNET_assert (GNUNET_YES ==
+                   GNUNET_CONTAINER_multipeermap_remove (routing_table,
+                                                         key, 
+                                                         remove_entry));
+  }
+  return GNUNET_YES;
+}
+
+
+/**
+ * FIXME: add a return value. 
+ * Iterate over routing table and remove all entries for which peer is a part. 
+ * @param peer Peer to be searched for in the trail to remove that trail.
  */
 void
 GDS_ROUTING_remove_entry (const struct GNUNET_PeerIdentity *peer)
 {
   GNUNET_CONTAINER_multipeermap_iterate (routing_table, &remove_routing_entry,
-                                         (void *)peer);
+                                        (void *)peer);
 }
 
 
-/** FIXME:TODO URGNET  Need to understand if we need next hop to uniquely identify an entry 
- * in routing table or not. 
- * Remove the trail as result of trail tear down message. 
+/**
+ * In response to trail teardown message, remove the trail with source peer, 
+ * destination peer and next hop same as the argument to this function. 
+ * Assumption - there can be only one possible trail with these 4 values. 
  * @param source_peer Source of the trail.
  * @param destination_peer Destination of the trail.
  * @param next_hop Next hop
- * @param prev_hop Previous hop. 
+ * @param prev_hop Previous hop.
+ * @return #GNUNET_YES Matching trail deleted from routing table. 
+ *         #GNUNET_NO No matching trail found.
+ *          
  */
 int
 GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer,
                           struct GNUNET_PeerIdentity *destination_peer, 
                           const struct GNUNET_PeerIdentity *prev_hop)
 {
+  struct RoutingTrail *trail;
+  struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
+  int i;
+  
+  iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
+  for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
+  {
+    if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
+                                                                 (const void **)&trail)) 
+    {
+      if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer))
+      {
+        GNUNET_assert (GNUNET_YES ==
+                       GNUNET_CONTAINER_multipeermap_remove (routing_table,
+                                                             &(trail->destination), 
+                                                             trail));
+        return GNUNET_YES; 
+      }
+    }
+  }
+  GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator);
   return GNUNET_NO;
 }
 
-/**
- * Find the next hop to send packet to.
- * @param source_peer Source of the trail.
- * @param destination_peer Destination of the trail.
- * @param prev_hop Previous hop in the trail. 
- * @return Next hop in the trail from source to destination. 
- */
-struct GNUNET_PeerIdentity *
-GDS_ROUTING_search(struct GNUNET_PeerIdentity *source_peer,
-                   struct GNUNET_PeerIdentity *destination_peer,
-                   const struct GNUNET_PeerIdentity *prev_hop)
-{
-  struct RoutingTrail *trail;
-  trail = GNUNET_malloc (sizeof (struct RoutingTrail));
-  memcpy (&(trail->destination), destination_peer, sizeof (struct GNUNET_PeerIdentity));
-  memcpy (&(trail->source), source_peer, sizeof (struct GNUNET_PeerIdentity));
-  memcpy (&(trail->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity));
-
-  GNUNET_CONTAINER_multipeermap_get_multiple (routing_table, destination_peer,
-                                              get_next_hop, trail);
-  if(trail != NULL)
-    return &(trail->next_hop);
-  else
-    return NULL;
-}
 
 
 /**
- * FIXME:URGENT:Better name.
  * Check if the size of routing table has crossed threshold. 
  * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
  */
 int
 GDS_ROUTING_check_threshold ()
 {
-  int ret;
-  ret = (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
-  return ret;    
+  return (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) ?
+          GNUNET_YES:GNUNET_NO;    
 }
 
 
@@ -245,11 +322,42 @@ GDS_ROUTING_check_threshold ()
 void
 GDS_ROUTING_init (void)
 { 
-  routing_table = GNUNET_CONTAINER_multipeermap_create (DHT_MAX_RECENT * 4 / 3, GNUNET_NO);
+  routing_table = GNUNET_CONTAINER_multipeermap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
+                                                        GNUNET_NO);
 }
 
-
 /**
+ * ONLY FOR TESTING.  
+ */
+void 
+GDS_ROUTING_print (void)
+{
+  struct RoutingTrail *trail;
+  struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
+  int i;
+  
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing table entries \n");
+  iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
+  for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
+  {
+    if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
+                                                                 (const void **)&trail)) 
+    {
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->source)));
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->destination)));
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->next_hop)));
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->prev_hop)));
+    }
+  }
+  
+}
+/**
+ * FIXME: here you can have routing table with size 0, only when you delete
+ * the entries correctly. Possible scenarios where we delete the entries are
+ * 1. when one of my friend gets disconnected then I remove any trail (does not
+ * matter if that friend is source, destination, next hop or previous hop).
+ * 2. if I get a trail teardown message then I remove the entry.
+ * Is there any other case that I may have missed? 
  * Shutdown routing subsystem.
  */
 void
diff --git a/src/dht/gnunet-service-xdht_routing.h b/src/dht/gnunet-service-xdht_routing.h
index 63007c7e4..0b0c80862 100644
--- a/src/dht/gnunet-service-xdht_routing.h
+++ b/src/dht/gnunet-service-xdht_routing.h
@@ -78,6 +78,11 @@ GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer,
                           struct GNUNET_PeerIdentity *destination_peer, 
                           const struct GNUNET_PeerIdentity *prev_hop);
 
+/**
+ * FOR TESTING. 
+ */
+void 
+GDS_ROUTING_print (void);
 
 /**
  * Check if size of routing table is greater than threshold or not.