aboutsummaryrefslogtreecommitdiff
path: root/src/dht
diff options
context:
space:
mode:
authorChristian Grothoff <christian@grothoff.org>2022-01-02 23:55:18 +0100
committerChristian Grothoff <christian@grothoff.org>2022-01-02 23:55:18 +0100
commitf30d3de6fb8bbd01072df00815b5f18a1808312e (patch)
tree1932f5174084f5df09cf1c95f599d15266022736 /src/dht
parent7b6ad5eedc4444ed8739932a388189bfd4e35e44 (diff)
downloadgnunet-f30d3de6fb8bbd01072df00815b5f18a1808312e.tar.gz
gnunet-f30d3de6fb8bbd01072df00815b5f18a1808312e.zip
-DHT: clean up peer selection logic
Diffstat (limited to 'src/dht')
-rw-r--r--src/dht/gnunet-service-dht_neighbours.c335
1 files changed, 197 insertions, 138 deletions
diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c
index 6b1b73103..eb64d6202 100644
--- a/src/dht/gnunet-service-dht_neighbours.c
+++ b/src/dht/gnunet-service-dht_neighbours.c
@@ -944,18 +944,22 @@ GDS_am_closest_peer (const struct GNUNET_HashCode *key,
944 944
945/** 945/**
946 * Select a peer from the routing table that would be a good routing 946 * Select a peer from the routing table that would be a good routing
947 * destination for sending a message for "key". The resulting peer 947 * destination for sending a message for @a key. The resulting peer
948 * must not be in the set of blocked peers.<p> 948 * must not be in the set of @a bloom blocked peers.
949 * 949 *
950 * Note that we should not ALWAYS select the closest peer to the 950 * Note that we should not ALWAYS select the closest peer to the
951 * target, peers further away from the target should be chosen with 951 * target, we do a "random" peer selection if the number of @a hops
952 * exponentially declining probability. 952 * is below the logarithm of the network size estimate.
953 *
954 * FIXME: double-check that this is fine
955 * 953 *
954 * In all cases, we only consider at most the first #bucket_size peers of any
955 * #k_buckets. The other peers in the bucket are there because GNUnet doesn't
956 * really allow the DHT to "reject" connections, but we only use the first
957 * #bucket_size, even if more exist. (The idea is to ensure that those
958 * connections are frequently used, and for others to be not used by the DHT,
959 * and thus possibly dropped by transport due to disuse).
956 * 960 *
957 * @param key the key we are selecting a peer to route to 961 * @param key the key we are selecting a peer to route to
958 * @param bloom a bloomfilter containing entries this request has seen already 962 * @param bloom a Bloom filter containing entries this request has seen already
959 * @param hops how many hops has this message traversed thus far 963 * @param hops how many hops has this message traversed thus far
960 * @return Peer to route to, or NULL on error 964 * @return Peer to route to, or NULL on error
961 */ 965 */
@@ -964,141 +968,196 @@ select_peer (const struct GNUNET_HashCode *key,
964 const struct GNUNET_CONTAINER_BloomFilter *bloom, 968 const struct GNUNET_CONTAINER_BloomFilter *bloom,
965 uint32_t hops) 969 uint32_t hops)
966{ 970{
967 unsigned int bc; 971 if (0 == closest_bucket)
968 unsigned int count; 972 {
969 unsigned int selected; 973 GNUNET_STATISTICS_update (GDS_stats,
970 struct PeerInfo *pos; 974 "# Peer selection failed",
971 struct PeerInfo *chosen; 975 1,
972 976 GNUNET_NO);
977 return NULL; /* we have zero connections */
978 }
973 if (hops >= GDS_NSE_get ()) 979 if (hops >= GDS_NSE_get ())
974 { 980 {
975 /* greedy selection (closest peer that is not in bloomfilter) */ 981 /* greedy selection (closest peer that is not in Bloom filter) */
976 unsigned int best_bucket = 0; 982 struct PeerInfo *chosen = NULL;
977 uint64_t best_in_bucket = UINT64_MAX; 983 int best_bucket;
984 int bucket_offset;
978 985
979 chosen = NULL;
980 for (bc = 0; bc < closest_bucket; bc++)
981 { 986 {
982 count = 0; 987 struct GNUNET_HashCode xor;
983 for (pos = k_buckets[bc].head; 988
984 (pos != NULL) && 989 GNUNET_CRYPTO_hash_xor (key,
985 (count < bucket_size); 990 &my_identity_hash,
991 &xor);
992 best_bucket = GNUNET_CRYPTO_hash_count_leading_zeros (&xor);
993 }
994 if (best_bucket >= closest_bucket)
995 bucket_offset = closest_bucket - 1;
996 else
997 bucket_offset = best_bucket;
998 while (-1 != bucket_offset)
999 {
1000 struct PeerBucket *bucket = &k_buckets[bucket_offset];
1001 unsigned int count = 0;
1002
1003 for (struct PeerInfo *pos = bucket->head;
1004 NULL != pos;
986 pos = pos->next) 1005 pos = pos->next)
987 { 1006 {
988 struct GNUNET_HashCode xor; 1007 if (count >= bucket_size)
989 unsigned int bucket; 1008 break; /* we only consider first #bucket_size entries per bucket */
990 uint64_t dist; 1009 count++;
991 1010 if (GNUNET_YES ==
992 GNUNET_CRYPTO_hash_xor (key, 1011 GNUNET_CONTAINER_bloomfilter_test (bloom,
993 &pos->phash, 1012 &pos->phash))
994 &xor); 1013 {
995 bucket = GNUNET_CRYPTO_hash_count_leading_zeros (&xor); 1014 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
996 dist = GNUNET_CRYPTO_hash_bucket_distance (&xor, 1015 "Excluded peer `%s' due to BF match in greedy routing for %s\n",
997 bucket); 1016 GNUNET_i2s (pos->id),
998 if (bucket < best_bucket) 1017 GNUNET_h2s (key));
999 continue;
1000 if (dist > best_in_bucket)
1001 continue; 1018 continue;
1002 best_bucket = bucket; 1019 }
1003 best_in_bucket = dist; 1020 if (NULL == chosen)
1004 if ( (NULL == bloom) ||
1005 (GNUNET_NO ==
1006 GNUNET_CONTAINER_bloomfilter_test (bloom,
1007 &pos->phash)) )
1008 { 1021 {
1022 /* First candidate */
1009 chosen = pos; 1023 chosen = pos;
1010 } 1024 }
1011 else 1025 else
1012 { 1026 {
1013 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 1027 int delta = GNUNET_CRYPTO_hash_xorcmp (&pos->phash,
1014 "Excluded peer `%s' due to BF match in greedy routing for %s\n", 1028 &chosen->phash,
1015 GNUNET_i2s (pos->id), 1029 key);
1016 GNUNET_h2s (key)); 1030 switch (delta)
1017 GNUNET_STATISTICS_update (GDS_stats, 1031 {
1018 gettext_noop ( 1032 case -1: /* pos closer */
1019 "# Peers excluded from routing due to Bloomfilter"), 1033 chosen = pos;
1020 1, 1034 break;
1021 GNUNET_NO); 1035 case 0: /* identical, impossible! */
1022 chosen = NULL; 1036 GNUNET_assert (0);
1037 break;
1038 case 1: /* chosen closer */
1039 break;
1040 }
1023 } 1041 }
1024 count++; 1042 count++;
1043 } /* for all (#bucket_size) peers in bucket */
1044
1045 /* If we chose nothing in first iteration, first go through
1046 all (!) deeper buckets (best chance to find a good match),
1047 and if we still found nothing, then to shallower buckets
1048 (but here terminate on any match, as it can only get worse
1049 as we keep going). */
1050 if (bucket_offset > best_bucket)
1051 {
1052 /* Go through more deeper buckets */
1053 bucket_offset++;
1054 if (bucket_offset == closest_bucket)
1055 {
1056 /* Can't go any deeper, if nothing selected,
1057 go for shallower buckets */
1058 if (NULL != chosen)
1059 break;
1060 bucket_offset = best_bucket - 1;
1061 }
1025 } 1062 }
1026 } 1063 else
1064 {
1065 /* We're either at the 'best_bucket' or already moving
1066 on to shallower buckets; any selection means the end. */
1067 if (NULL != chosen)
1068 break;
1069 if (bucket_offset == best_bucket)
1070 bucket_offset++; /* go for deeper buckets */
1071 else
1072 bucket_offset--; /* go for shallower buckets */
1073 }
1074 } /* for applicable buckets (starting at best match) */
1027 if (NULL == chosen) 1075 if (NULL == chosen)
1076 {
1028 GNUNET_STATISTICS_update (GDS_stats, 1077 GNUNET_STATISTICS_update (GDS_stats,
1029 gettext_noop ("# Peer selection failed"), 1078 "# Peer selection failed",
1030 1, 1079 1,
1031 GNUNET_NO); 1080 GNUNET_NO);
1032 else 1081 return NULL;
1033 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 1082 }
1034 "Selected peer `%s' in greedy routing for %s\n", 1083 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1035 GNUNET_i2s (chosen->id), 1084 "Selected peer `%s' in greedy routing for %s\n",
1036 GNUNET_h2s (key)); 1085 GNUNET_i2s (chosen->id),
1086 GNUNET_h2s (key));
1037 return chosen; 1087 return chosen;
1038 } 1088 } /* end of 'greedy' peer selection */
1039 1089
1040 /* select "random" peer */ 1090 /* select "random" peer */
1041 /* count number of peers that are available and not filtered */ 1091 /* count number of peers that are available and not filtered,
1042 count = 0; 1092 but limit to at most #bucket_size peers, starting with
1043 for (bc = 0; bc < closest_bucket; bc++) 1093 those 'furthest' from us. */
1044 { 1094 {
1045 pos = k_buckets[bc].head; 1095 unsigned int total = 0;
1046 while ((NULL != pos) && (count < bucket_size)) 1096 unsigned int selected;
1097
1098 for (unsigned int bc = 0; bc < closest_bucket; bc++)
1047 { 1099 {
1048 if ((NULL != bloom) && 1100 unsigned int count = 0;
1049 (GNUNET_YES == 1101
1050 GNUNET_CONTAINER_bloomfilter_test (bloom, 1102 for (struct PeerInfo *pos = k_buckets[bc].head;
1051 &pos->phash))) 1103 NULL != pos;
1104 pos = pos->next)
1052 { 1105 {
1053 GNUNET_STATISTICS_update (GDS_stats, 1106 count++;
1054 gettext_noop 1107 if (count > bucket_size)
1055 ( 1108 break; /* limits search to #bucket_size peers per bucket */
1056 "# Peers excluded from routing due to Bloomfilter"), 1109 if (GNUNET_YES ==
1057 1, GNUNET_NO); 1110 GNUNET_CONTAINER_bloomfilter_test (bloom,
1058 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 1111 &pos->phash))
1059 "Excluded peer `%s' due to BF match in random routing for %s\n", 1112 {
1060 GNUNET_i2s (pos->id), 1113 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1061 GNUNET_h2s (key)); 1114 "Excluded peer `%s' due to BF match in random routing for %s\n",
1062 pos = pos->next; 1115 GNUNET_i2s (pos->id),
1063 continue; /* Ignore bloomfiltered peers */ 1116 GNUNET_h2s (key));
1064 } 1117 continue; /* Ignore filtered peers */
1065 count++; 1118 }
1066 pos = pos->next; 1119 total++;
1120 } /* for all peers in bucket */
1121 } /* for all buckets */
1122 if (0 == total) /* No peers to select from! */
1123 {
1124 GNUNET_STATISTICS_update (GDS_stats,
1125 "# Peer selection failed",
1126 1,
1127 GNUNET_NO);
1128 return NULL;
1067 } 1129 }
1068 } 1130
1069 if (0 == count) /* No peers to select from! */ 1131 /* Now actually choose a peer */
1070 { 1132 selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1071 GNUNET_STATISTICS_update (GDS_stats, 1133 total);
1072 gettext_noop ("# Peer selection failed"), 1, 1134 for (unsigned int bc = 0; bc < closest_bucket; bc++)
1073 GNUNET_NO);
1074 return NULL;
1075 }
1076 /* Now actually choose a peer */
1077 selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1078 count);
1079 count = 0;
1080 for (bc = 0; bc < closest_bucket; bc++)
1081 {
1082 for (pos = k_buckets[bc].head; ((pos != NULL) && (count < bucket_size));
1083 pos = pos->next)
1084 { 1135 {
1085 if ((bloom != NULL) && 1136 unsigned int count = 0;
1086 (GNUNET_YES == 1137
1087 GNUNET_CONTAINER_bloomfilter_test (bloom, 1138 for (struct PeerInfo *pos = k_buckets[bc].head;
1088 &pos->phash))) 1139 pos != NULL;
1089 { 1140 pos = pos->next)
1090 continue; /* Ignore bloomfiltered peers */
1091 }
1092 if (0 == selected--)
1093 { 1141 {
1094 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 1142 count++;
1095 "Selected peer `%s' in random routing for %s\n", 1143 if (count > bucket_size)
1096 GNUNET_i2s (pos->id), 1144 break; /* limits search to #bucket_size peers per bucket */
1097 GNUNET_h2s (key)); 1145
1098 return pos; 1146 if (GNUNET_YES ==
1099 } 1147 GNUNET_CONTAINER_bloomfilter_test (bloom,
1100 } 1148 &pos->phash))
1101 } 1149 continue; /* Ignore bloomfiltered peers */
1150 if (0 == selected--)
1151 {
1152 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1153 "Selected peer `%s' in random routing for %s\n",
1154 GNUNET_i2s (pos->id),
1155 GNUNET_h2s (key));
1156 return pos;
1157 }
1158 } /* for peers in bucket */
1159 } /* for all buckets */
1160 } /* random peer selection scope */
1102 GNUNET_break (0); 1161 GNUNET_break (0);
1103 return NULL; 1162 return NULL;
1104} 1163}
@@ -1109,13 +1168,13 @@ select_peer (const struct GNUNET_HashCode *key,
1109 * forwarded to. 1168 * forwarded to.
1110 * 1169 *
1111 * @param key routing key 1170 * @param key routing key
1112 * @param bloom bloom filter excluding peers as targets, all selected 1171 * @param[in,out] bloom Bloom filter excluding peers as targets,
1113 * peers will be added to the bloom filter 1172 * all selected peers will be added to the Bloom filter
1114 * @param hop_count number of hops the request has traversed so far 1173 * @param hop_count number of hops the request has traversed so far
1115 * @param target_replication desired number of replicas 1174 * @param target_replication desired number of replicas
1116 * @param targets where to store an array of target peers (to be 1175 * @param[out] targets where to store an array of target peers (to be
1117 * free'd by the caller) 1176 * free()ed by the caller)
1118 * @return number of peers returned in 'targets'. 1177 * @return number of peers returned in @a targets.
1119 */ 1178 */
1120static unsigned int 1179static unsigned int
1121get_target_peers (const struct GNUNET_HashCode *key, 1180get_target_peers (const struct GNUNET_HashCode *key,
@@ -1124,23 +1183,24 @@ get_target_peers (const struct GNUNET_HashCode *key,
1124 uint32_t target_replication, 1183 uint32_t target_replication,
1125 struct PeerInfo ***targets) 1184 struct PeerInfo ***targets)
1126{ 1185{
1127 unsigned int ret; 1186 unsigned int target;
1128 unsigned int off; 1187 unsigned int off;
1129 struct PeerInfo **rtargets; 1188 struct PeerInfo **rtargets;
1130 struct PeerInfo *nxt;
1131 1189
1132 GNUNET_assert (NULL != bloom); 1190 GNUNET_assert (NULL != bloom);
1133 ret = get_forward_count (hop_count, 1191 target = get_forward_count (hop_count,
1134 target_replication); 1192 target_replication);
1135 if (0 == ret) 1193 if (0 == target)
1136 { 1194 {
1137 *targets = NULL; 1195 *targets = NULL;
1138 return 0; 1196 return 0;
1139 } 1197 }
1140 rtargets = GNUNET_new_array (ret, 1198 rtargets = GNUNET_new_array (target,
1141 struct PeerInfo *); 1199 struct PeerInfo *);
1142 for (off = 0; off < ret; off++) 1200 for (off = 0; off < target; off++)
1143 { 1201 {
1202 struct PeerInfo *nxt;
1203
1144 nxt = select_peer (key, 1204 nxt = select_peer (key,
1145 bloom, 1205 bloom,
1146 hop_count); 1206 hop_count);
@@ -1159,7 +1219,7 @@ get_target_peers (const struct GNUNET_HashCode *key,
1159 GNUNET_CONTAINER_multipeermap_size (all_connected_peers), 1219 GNUNET_CONTAINER_multipeermap_size (all_connected_peers),
1160 (unsigned int) hop_count, 1220 (unsigned int) hop_count,
1161 GNUNET_h2s (key), 1221 GNUNET_h2s (key),
1162 ret); 1222 target);
1163 if (0 == off) 1223 if (0 == off)
1164 { 1224 {
1165 GNUNET_free (rtargets); 1225 GNUNET_free (rtargets);
@@ -1171,11 +1231,13 @@ get_target_peers (const struct GNUNET_HashCode *key,
1171 "Forwarding query `%s' to %u peers (goal was %u peers)\n", 1231 "Forwarding query `%s' to %u peers (goal was %u peers)\n",
1172 GNUNET_h2s (key), 1232 GNUNET_h2s (key),
1173 off, 1233 off,
1174 ret); 1234 target);
1175 return off; 1235 return off;
1176} 1236}
1177 1237
1178 1238
1239// FIXME-CG: REVIEW from here...
1240
1179enum GNUNET_GenericReturnValue 1241enum GNUNET_GenericReturnValue
1180GDS_NEIGHBOURS_handle_put (const struct GDS_DATACACHE_BlockData *bd, 1242GDS_NEIGHBOURS_handle_put (const struct GDS_DATACACHE_BlockData *bd,
1181 enum GNUNET_DHT_RouteOption options, 1243 enum GNUNET_DHT_RouteOption options,
@@ -1247,8 +1309,7 @@ GDS_NEIGHBOURS_handle_put (const struct GDS_DATACACHE_BlockData *bd,
1247 { 1309 {
1248 /* skip */ 1310 /* skip */
1249 GNUNET_STATISTICS_update (GDS_stats, 1311 GNUNET_STATISTICS_update (GDS_stats,
1250 gettext_noop ( 1312 "# P2P messages dropped due to full queue",
1251 "# P2P messages dropped due to full queue"),
1252 1, 1313 1,
1253 GNUNET_NO); 1314 GNUNET_NO);
1254 skip_count++; 1315 skip_count++;
@@ -1316,7 +1377,7 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1316 1377
1317 GNUNET_assert (NULL != peer_bf); 1378 GNUNET_assert (NULL != peer_bf);
1318 GNUNET_STATISTICS_update (GDS_stats, 1379 GNUNET_STATISTICS_update (GDS_stats,
1319 gettext_noop ("# GET requests routed"), 1380 "# GET requests routed",
1320 1, 1381 1,
1321 GNUNET_NO); 1382 GNUNET_NO);
1322 target_count = get_target_peers (key, 1383 target_count = get_target_peers (key,
@@ -1359,8 +1420,7 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1359 return GNUNET_NO; 1420 return GNUNET_NO;
1360 } 1421 }
1361 GNUNET_STATISTICS_update (GDS_stats, 1422 GNUNET_STATISTICS_update (GDS_stats,
1362 gettext_noop ( 1423 "# GET messages queued for transmission",
1363 "# GET messages queued for transmission"),
1364 target_count, 1424 target_count,
1365 GNUNET_NO); 1425 GNUNET_NO);
1366 /* forward request */ 1426 /* forward request */
@@ -1372,8 +1432,7 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1372 { 1432 {
1373 /* skip */ 1433 /* skip */
1374 GNUNET_STATISTICS_update (GDS_stats, 1434 GNUNET_STATISTICS_update (GDS_stats,
1375 gettext_noop ( 1435 "# P2P messages dropped due to full queue",
1376 "# P2P messages dropped due to full queue"),
1377 1, GNUNET_NO); 1436 1, GNUNET_NO);
1378 skip_count++; 1437 skip_count++;
1379 continue; 1438 continue;
@@ -1581,7 +1640,7 @@ handle_dht_p2p_put (void *cls,
1581 if (GNUNET_TIME_absolute_is_past (bd.expiration_time)) 1640 if (GNUNET_TIME_absolute_is_past (bd.expiration_time))
1582 { 1641 {
1583 GNUNET_STATISTICS_update (GDS_stats, 1642 GNUNET_STATISTICS_update (GDS_stats,
1584 gettext_noop ("# Expired PUTs discarded"), 1643 "# Expired PUTs discarded",
1585 1, 1644 1,
1586 GNUNET_NO); 1645 GNUNET_NO);
1587 return; 1646 return;
@@ -1943,11 +2002,11 @@ handle_dht_p2p_get (void *cls,
1943 options = ntohl (get->options); 2002 options = ntohl (get->options);
1944 xquery = (const void *) &get[1]; 2003 xquery = (const void *) &get[1];
1945 GNUNET_STATISTICS_update (GDS_stats, 2004 GNUNET_STATISTICS_update (GDS_stats,
1946 gettext_noop ("# P2P GET requests received"), 2005 "# P2P GET requests received",
1947 1, 2006 1,
1948 GNUNET_NO); 2007 GNUNET_NO);
1949 GNUNET_STATISTICS_update (GDS_stats, 2008 GNUNET_STATISTICS_update (GDS_stats,
1950 gettext_noop ("# P2P GET bytes received"), 2009 "# P2P GET bytes received",
1951 msize, 2010 msize,
1952 GNUNET_NO); 2011 GNUNET_NO);
1953 if (GNUNET_YES == log_route_details_stderr) 2012 if (GNUNET_YES == log_route_details_stderr)