diff options
author | Christian Grothoff <christian@grothoff.org> | 2017-01-29 23:41:23 +0100 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2017-01-29 23:41:23 +0100 |
commit | 4a2c91ed9f94920b4c7771a618e4177dd8d91bc1 (patch) | |
tree | 262688ad47cac1a0794e9992a50bd2e536df48bb /src/cadet | |
parent | 93ea24d9cde704d1c8465bb5b2665855b37256a3 (diff) | |
download | gnunet-4a2c91ed9f94920b4c7771a618e4177dd8d91bc1.tar.gz gnunet-4a2c91ed9f94920b4c7771a618e4177dd8d91bc1.zip |
add path desirability calculations
Diffstat (limited to 'src/cadet')
-rw-r--r-- | src/cadet/desirability_table.c | 35 | ||||
-rw-r--r-- | src/cadet/gnunet-service-cadet-new_paths.c | 12 | ||||
-rw-r--r-- | src/cadet/gnunet-service-cadet-new_peer.c | 69 | ||||
-rw-r--r-- | src/cadet/gnunet-service-cadet-new_peer.h | 14 |
4 files changed, 128 insertions, 2 deletions
diff --git a/src/cadet/desirability_table.c b/src/cadet/desirability_table.c new file mode 100644 index 000000000..21ec3e388 --- /dev/null +++ b/src/cadet/desirability_table.c | |||
@@ -0,0 +1,35 @@ | |||
1 | /* This file is in the public domain. */ | ||
2 | |||
3 | /** | ||
4 | * @brief Program to simulate results from #GCP_get_desirability_of_path() | ||
5 | * for various plausible inputs. | ||
6 | * @author Christian Grothoff | ||
7 | */ | ||
8 | #include <stdio.h> | ||
9 | |||
10 | int | ||
11 | main () | ||
12 | { | ||
13 | for (unsigned int num_alts=1; num_alts<10; num_alts++) | ||
14 | for (unsigned int off=0; off<10; off++) | ||
15 | for (double delta=-(int) off;delta<=5;delta += 0.25) | ||
16 | { | ||
17 | double weight_alts; | ||
18 | |||
19 | if (delta <= - 1.0) | ||
20 | weight_alts = - 1.0 * num_alts / delta; /* discount alternative paths */ | ||
21 | else if (delta >= 1.0) | ||
22 | weight_alts = 1.0 * num_alts * delta; /* overcount alternative paths */ | ||
23 | else | ||
24 | weight_alts = 1.0 * num_alts; /* count alternative paths normally */ | ||
25 | |||
26 | fprintf (stderr, | ||
27 | "Paths: %u Offset: %u Delta: %5.2f SCORE: %f\n", | ||
28 | num_alts, | ||
29 | off, | ||
30 | delta, | ||
31 | ((off + 1.0) / (weight_alts * weight_alts))); | ||
32 | } | ||
33 | |||
34 | |||
35 | } | ||
diff --git a/src/cadet/gnunet-service-cadet-new_paths.c b/src/cadet/gnunet-service-cadet-new_paths.c index 05d702717..05565c043 100644 --- a/src/cadet/gnunet-service-cadet-new_paths.c +++ b/src/cadet/gnunet-service-cadet-new_paths.c | |||
@@ -76,8 +76,16 @@ struct CadetPeerPath | |||
76 | static void | 76 | static void |
77 | recalculate_path_desirability (struct CadetPeerPath *path) | 77 | recalculate_path_desirability (struct CadetPeerPath *path) |
78 | { | 78 | { |
79 | /* FIXME: update path desirability! */ | 79 | double result = 0.0; |
80 | GNUNET_break (0); // not implemented | 80 | |
81 | for (unsigned int i=0;i<path->entries_length;i++) | ||
82 | { | ||
83 | struct CadetPeer *cp = path->entries[i]->peer; | ||
84 | |||
85 | result += GCP_get_desirability_of_path (cp, | ||
86 | i); | ||
87 | } | ||
88 | path->desirability = (GNUNET_CONTAINER_HeapCostType) result; | ||
81 | } | 89 | } |
82 | 90 | ||
83 | 91 | ||
diff --git a/src/cadet/gnunet-service-cadet-new_peer.c b/src/cadet/gnunet-service-cadet-new_peer.c index 9e84550ec..cc13f6da6 100644 --- a/src/cadet/gnunet-service-cadet-new_peer.c +++ b/src/cadet/gnunet-service-cadet-new_peer.c | |||
@@ -208,6 +208,12 @@ struct CadetPeer | |||
208 | unsigned int num_paths; | 208 | unsigned int num_paths; |
209 | 209 | ||
210 | /** | 210 | /** |
211 | * Sum over all of the offsets of all of the paths in the @a path_heads DLLs. | ||
212 | * Used to speed-up @GCP_get_desirability_of_path() calculation. | ||
213 | */ | ||
214 | unsigned int off_sum; | ||
215 | |||
216 | /** | ||
211 | * Number of message queue managers of this peer that have a message in waiting. | 217 | * Number of message queue managers of this peer that have a message in waiting. |
212 | * | 218 | * |
213 | * Used to quickly see if we need to bother scanning the @e msm_head DLL. | 219 | * Used to quickly see if we need to bother scanning the @e msm_head DLL. |
@@ -245,6 +251,67 @@ GCP_2s (const struct CadetPeer *cp) | |||
245 | 251 | ||
246 | 252 | ||
247 | /** | 253 | /** |
254 | * Calculate how desirable a path is for @a cp if @a cp | ||
255 | * is at offset @a off. | ||
256 | * | ||
257 | * The 'desirability_table.c' program can be used to compute a list of | ||
258 | * sample outputs for different scenarios. Basically, we score paths | ||
259 | * lower if there are many alternatives, and higher if they are | ||
260 | * shorter than average, and very high if they are much shorter than | ||
261 | * average and without many alternatives. | ||
262 | * | ||
263 | * @param cp a peer reachable via a path | ||
264 | * @param off offset of @a cp in the path | ||
265 | * @return score how useful a path is to reach @a cp, | ||
266 | * positive scores mean path is more desirable | ||
267 | */ | ||
268 | double | ||
269 | GCP_get_desirability_of_path (struct CadetPeer *cp, | ||
270 | unsigned int off) | ||
271 | { | ||
272 | unsigned int num_alts = cp->num_paths; | ||
273 | unsigned int off_sum; | ||
274 | double avg_sum; | ||
275 | double path_delta; | ||
276 | double weight_alts; | ||
277 | |||
278 | GNUNET_assert (num_alts >= 1); /* 'path' should be in there! */ | ||
279 | GNUNET_assert (0 != cp->path_dll_length); | ||
280 | |||
281 | /* We maintain 'off_sum' in 'peer' and thereby | ||
282 | avoid the SLOW recalculation each time. Kept here | ||
283 | just to document what is going on. */ | ||
284 | #if SLOW | ||
285 | off_sum = 0; | ||
286 | for (unsigned int j=0;j<cp->path_dll_length;j++) | ||
287 | for (struct CadetPeerPathEntry *pe = cp->path_heads[j]; | ||
288 | NULL != pe; | ||
289 | pe = pe->next) | ||
290 | off_sum += j; | ||
291 | GNUNET_assert (off_sum == cp->off_sum); | ||
292 | #else | ||
293 | off_sum = cp->off_sum; | ||
294 | #endif | ||
295 | avg_sum = off_sum * 1.0 / cp->path_dll_length; | ||
296 | path_delta = off - avg_sum; | ||
297 | /* path_delta positiv: path off of peer above average (bad path for peer), | ||
298 | path_delta negativ: path off of peer below average (good path for peer) */ | ||
299 | if (path_delta <= - 1.0) | ||
300 | weight_alts = - num_alts / path_delta; /* discount alternative paths */ | ||
301 | else if (path_delta >= 1.0) | ||
302 | weight_alts = num_alts * path_delta; /* overcount alternative paths */ | ||
303 | else | ||
304 | weight_alts = num_alts; /* count alternative paths normally */ | ||
305 | |||
306 | |||
307 | /* off+1: long paths are generally harder to find and thus count | ||
308 | a bit more as they get longer. However, above-average paths | ||
309 | still need to count less, hence the squaring of that factor. */ | ||
310 | return (off + 1.0) / (weight_alts * weight_alts); | ||
311 | } | ||
312 | |||
313 | |||
314 | /** | ||
248 | * This peer is no longer be needed, clean it up now. | 315 | * This peer is no longer be needed, clean it up now. |
249 | * | 316 | * |
250 | * @param cls peer to clean up | 317 | * @param cls peer to clean up |
@@ -757,6 +824,7 @@ GCP_path_entry_add (struct CadetPeer *cp, | |||
757 | GNUNET_CONTAINER_DLL_insert (cp->path_heads[off], | 824 | GNUNET_CONTAINER_DLL_insert (cp->path_heads[off], |
758 | cp->path_tails[off], | 825 | cp->path_tails[off], |
759 | entry); | 826 | entry); |
827 | cp->off_sum += off; | ||
760 | cp->num_paths++; | 828 | cp->num_paths++; |
761 | 829 | ||
762 | /* If we have a tunnel to this peer, tell the tunnel that there is a | 830 | /* If we have a tunnel to this peer, tell the tunnel that there is a |
@@ -797,6 +865,7 @@ GCP_path_entry_remove (struct CadetPeer *cp, | |||
797 | cp->path_tails[off], | 865 | cp->path_tails[off], |
798 | entry); | 866 | entry); |
799 | GNUNET_assert (0 < cp->num_paths); | 867 | GNUNET_assert (0 < cp->num_paths); |
868 | cp->off_sum -= off; | ||
800 | cp->num_paths--; | 869 | cp->num_paths--; |
801 | if ( (NULL == cp->core_mq) && | 870 | if ( (NULL == cp->core_mq) && |
802 | (NULL != cp->t) && | 871 | (NULL != cp->t) && |
diff --git a/src/cadet/gnunet-service-cadet-new_peer.h b/src/cadet/gnunet-service-cadet-new_peer.h index aaaef15b8..e1d6fc33a 100644 --- a/src/cadet/gnunet-service-cadet-new_peer.h +++ b/src/cadet/gnunet-service-cadet-new_peer.h | |||
@@ -60,6 +60,20 @@ GCP_get (const struct GNUNET_PeerIdentity *peer_id, | |||
60 | 60 | ||
61 | 61 | ||
62 | /** | 62 | /** |
63 | * Calculate how desirable a path is for @a cp if | ||
64 | * @a cp is at offset @a off in the path. | ||
65 | * | ||
66 | * @param cp a peer reachable via a path | ||
67 | * @param off offset of @a cp in a path | ||
68 | * @return score how useful a path is to reach @a cp, | ||
69 | * positive scores mean path is more desirable | ||
70 | */ | ||
71 | double | ||
72 | GCP_get_desirability_of_path (struct CadetPeer *cp, | ||
73 | unsigned int off); | ||
74 | |||
75 | |||
76 | /** | ||
63 | * Obtain the peer identity for a `struct CadetPeer`. | 77 | * Obtain the peer identity for a `struct CadetPeer`. |
64 | * | 78 | * |
65 | * @param cp our peer handle | 79 | * @param cp our peer handle |