aboutsummaryrefslogtreecommitdiff
path: root/src/transport/gnunet-service-tng.c
diff options
context:
space:
mode:
authorChristian Grothoff <christian@grothoff.org>2019-04-24 14:19:38 +0200
committerChristian Grothoff <christian@grothoff.org>2019-04-24 14:19:38 +0200
commitcceac0d2de9556b5a270570f136cd5324351f55e (patch)
tree35a37f84c4e39571d83d8bc1841c65e509f381d8 /src/transport/gnunet-service-tng.c
parent726b882c196f6dd6ad752ef91537e04d749e0924 (diff)
downloadgnunet-cceac0d2de9556b5a270570f136cd5324351f55e.tar.gz
gnunet-cceac0d2de9556b5a270570f136cd5324351f55e.zip
implement looping over neighbours to call fwd_dv_learn()
Diffstat (limited to 'src/transport/gnunet-service-tng.c')
-rw-r--r--src/transport/gnunet-service-tng.c236
1 files changed, 224 insertions, 12 deletions
diff --git a/src/transport/gnunet-service-tng.c b/src/transport/gnunet-service-tng.c
index e128a4abf..f327976ee 100644
--- a/src/transport/gnunet-service-tng.c
+++ b/src/transport/gnunet-service-tng.c
@@ -24,13 +24,13 @@
24 * 24 *
25 * TODO: 25 * TODO:
26 * Implement next: 26 * Implement next:
27 * - FIXME: looping over neighbours when calling forward_dv_learn()!
28 * - FIXME: transmit_on_queue: track dvh we may be using and pass it to 27 * - FIXME: transmit_on_queue: track dvh we may be using and pass it to
29 * fragment_message() and reliability_box_message() if applicable 28 * fragment_message() and reliability_box_message() if applicable
30 * - proper use/initialization of timestamps in messages exchanged 29 * - proper use/initialization of timestamps in messages exchanged
31 * during DV learning 30 * during DV learning
32 * - persistence of monotonic time from DVInit to prevent 31 * - persistence of monotonic time from DVInit to prevent
33 * replay attacks using DVInit messages 32 * replay attacks using DVInit messages
33 * - dv hop-by-hop signature verification (at least at initiator)
34 * - persistence of monotonic time obtained from other peers 34 * - persistence of monotonic time obtained from other peers
35 * in PEERSTORE (by message type) -- done for backchannel, needed elsewhere? 35 * in PEERSTORE (by message type) -- done for backchannel, needed elsewhere?
36 * - change transport-core API to provide proper flow control in both 36 * - change transport-core API to provide proper flow control in both
@@ -117,6 +117,12 @@
117#define GOODPUT_AGING_SLOTS 4 117#define GOODPUT_AGING_SLOTS 4
118 118
119/** 119/**
120 * Maximum number of peers we select for forwarding DVInit
121 * messages at the same time (excluding initiator).
122 */
123#define MAX_DV_DISCOVERY_SELECTION 16
124
125/**
120 * Minimum number of hops we should forward DV learn messages 126 * Minimum number of hops we should forward DV learn messages
121 * even if they are NOT useful for us in hope of looping 127 * even if they are NOT useful for us in hope of looping
122 * back to the initiator? 128 * back to the initiator?
@@ -5853,6 +5859,195 @@ validate_dv_initiator_signature (
5853 5859
5854 5860
5855/** 5861/**
5862 * Closure for #dv_neighbour_selection and #dv_neighbour_transmission.
5863 */
5864struct NeighbourSelectionContext
5865{
5866 /**
5867 * Original message we received.
5868 */
5869 const struct TransportDVLearnMessage *dvl;
5870
5871 /**
5872 * The hops taken.
5873 */
5874 const struct DVPathEntryP *hops;
5875
5876 /**
5877 * Time we received the message.
5878 */
5879 struct GNUNET_TIME_Absolute in_time;
5880
5881 /**
5882 * Offsets of the selected peers.
5883 */
5884 uint32_t selections[MAX_DV_DISCOVERY_SELECTION];
5885
5886 /**
5887 * Number of peers eligible for selection.
5888 */
5889 unsigned int num_eligible;
5890
5891 /**
5892 * Number of peers that were selected for forwarding.
5893 */
5894 unsigned int num_selections;
5895
5896 /**
5897 * Number of hops in @e hops
5898 */
5899 uint16_t nhops;
5900
5901 /**
5902 * Bitmap of bidirectional connections encountered.
5903 */
5904 uint16_t bi_history;
5905};
5906
5907
5908/**
5909 * Function called for each neighbour during #handle_dv_learn.
5910 *
5911 * @param cls a `struct NeighbourSelectionContext *`
5912 * @param pid identity of the peer
5913 * @param value a `struct Neighbour`
5914 * @return #GNUNET_YES (always)
5915 */
5916static int
5917dv_neighbour_selection (void *cls,
5918 const struct GNUNET_PeerIdentity *pid,
5919 void *value)
5920{
5921 struct NeighbourSelectionContext *nsc = cls;
5922
5923 (void) value;
5924 if (0 == GNUNET_memcmp (pid, &nsc->dvl->initiator))
5925 return GNUNET_YES; /* skip initiator */
5926 for (unsigned int i = 0; i < nsc->nhops; i++)
5927 if (0 == GNUNET_memcmp (pid, &nsc->hops[i].hop))
5928 return GNUNET_YES; /* skip peers on path */
5929 nsc->num_eligible++;
5930 return GNUNET_YES;
5931}
5932
5933
5934/**
5935 * Function called for each neighbour during #handle_dv_learn.
5936 * We call #forward_dv_learn() on the neighbour(s) selected
5937 * during #dv_neighbour_selection().
5938 *
5939 * @param cls a `struct NeighbourSelectionContext *`
5940 * @param pid identity of the peer
5941 * @param value a `struct Neighbour`
5942 * @return #GNUNET_YES (always)
5943 */
5944static int
5945dv_neighbour_transmission (void *cls,
5946 const struct GNUNET_PeerIdentity *pid,
5947 void *value)
5948{
5949 struct NeighbourSelectionContext *nsc = cls;
5950
5951 (void) value;
5952 if (0 == GNUNET_memcmp (pid, &nsc->dvl->initiator))
5953 return GNUNET_YES; /* skip initiator */
5954 for (unsigned int i = 0; i < nsc->nhops; i++)
5955 if (0 == GNUNET_memcmp (pid, &nsc->hops[i].hop))
5956 return GNUNET_YES; /* skip peers on path */
5957 for (unsigned int i = 0; i < nsc->num_selections; i++)
5958 {
5959 if (nsc->selections[i] == nsc->num_eligible)
5960 {
5961 forward_dv_learn (pid,
5962 nsc->dvl,
5963 nsc->bi_history,
5964 nsc->nhops,
5965 nsc->hops,
5966 nsc->in_time);
5967 break;
5968 }
5969 }
5970 nsc->num_eligible++;
5971 return GNUNET_YES;
5972}
5973
5974
5975/**
5976 * Computes the number of neighbours we should forward a DVInit
5977 * message to given that it has so far taken @a hops_taken hops
5978 * though the network and that the number of neighbours we have
5979 * in total is @a neighbour_count, out of which @a eligible_count
5980 * are not yet on the path.
5981 *
5982 * NOTE: technically we might want to include NSE in the formula to
5983 * get a better grip on the overall network size. However, for now
5984 * using NSE here would create a dependency issue in the build system.
5985 * => Left for later, hardcoded to 50 for now.
5986 *
5987 * The goal of the fomula is that we want to reach a total of LOG(NSE)
5988 * peers via DV (`target_total`). We want the reach to be spread out
5989 * over various distances to the origin, with a bias towards shorter
5990 * distances.
5991 *
5992 * We make the strong assumption that the network topology looks
5993 * "similar" at other hops, in particular the @a neighbour_count
5994 * should be comparable at other hops.
5995 *
5996 * If the local neighbourhood is densely connected, we expect that @a
5997 * eligible_count is close to @a neighbour_count minus @a hops_taken
5998 * as a lot of the path is already known. In that case, we should
5999 * forward to few(er) peers to try to find a path out of the
6000 * neighbourhood. OTOH, if @a eligible_count is close to @a
6001 * neighbour_count, we should forward to many peers as we are either
6002 * still close to the origin (i.e. @a hops_taken is small) or because
6003 * we managed to get beyond a local cluster. We express this as
6004 * the `boost_factor` using the square of the fraction of eligible
6005 * neighbours (so if only 50% are eligible, we boost by 1/4, but if
6006 * 99% are eligible, the 'boost' will be almost 1).
6007 *
6008 * Second, the more hops we have taken, the larger the problem of an
6009 * exponential traffic explosion gets. So we take the `target_total`,
6010 * and compute our degree such that at each distance d 2^{-d} peers
6011 * are selected (corrected by the `boost_factor`).
6012 *
6013 * @param hops_taken number of hops DVInit has travelled so far
6014 * @param neighbour_count number of neighbours we have in total
6015 * @param eligible_count number of neighbours we could in
6016 * theory forward to
6017 */
6018static unsigned int
6019calculate_fork_degree (unsigned int hops_taken,
6020 unsigned int neighbour_count,
6021 unsigned int eligible_count)
6022{
6023 double target_total = 50.0; /* FIXME: use LOG(NSE)? */
6024 double eligible_ratio =
6025 ((double) eligible_count) / ((double) neighbour_count);
6026 double boost_factor = eligible_ratio * eligible_ratio;
6027 unsigned int rnd;
6028 double left;
6029
6030 if (hops_taken >= 64)
6031 return 0; /* precaution given bitshift below */
6032 for (unsigned int i = 1; i < hops_taken; i++)
6033 {
6034 /* For each hop, subtract the expected number of targets
6035 reached at distance d (so what remains divided by 2^d) */
6036 target_total -= (target_total * boost_factor / (1LLU << i));
6037 }
6038 rnd =
6039 (unsigned int) floor (target_total * boost_factor / (1LLU << hops_taken));
6040 /* round up or down probabilistically depending on how close we were
6041 when floor()ing to rnd */
6042 left = target_total - (double) rnd;
6043 if (UINT32_MAX * left >
6044 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX))
6045 rnd++; /* round up */
6046 return rnd;
6047}
6048
6049
6050/**
5856 * Communicator gave us a DV learn message. Process the request. 6051 * Communicator gave us a DV learn message. Process the request.
5857 * 6052 *
5858 * @param cls a `struct CommunicatorMessageContext` (must call 6053 * @param cls a `struct CommunicatorMessageContext` (must call
@@ -6036,17 +6231,34 @@ handle_dv_learn (void *cls, const struct TransportDVLearnMessage *dvl)
6036 if ((do_fwd) || ((nhops < MIN_DV_PATH_LENGTH_FOR_INITIATOR) && 6231 if ((do_fwd) || ((nhops < MIN_DV_PATH_LENGTH_FOR_INITIATOR) &&
6037 (GNUNET_NO == did_initiator))) 6232 (GNUNET_NO == did_initiator)))
6038 { 6233 {
6039 /* FIXME: loop over all neighbours, pick those with low 6234 /* Pick random neighbours that are not yet on the path */
6040 queues AND that are not yet on the path; possibly 6235 struct NeighbourSelectionContext nsc;
6041 adapt threshold to nhops! */ 6236 unsigned int n_cnt;
6042#if FIXME 6237
6043 forward_dv_learn (NULL, // fill in peer from iterator here! 6238 n_cnt = GNUNET_CONTAINER_multipeermap_size (neighbours);
6044 dvl, 6239 nsc.nhops = nhops;
6045 bi_history, 6240 nsc.dvl = dvl;
6046 nhops, 6241 nsc.bi_history = bi_history;
6047 hops, 6242 nsc.hops = hops;
6048 in_time); 6243 nsc.in_time = in_time;
6049#endif 6244 nsc.num_eligible = 0;
6245 GNUNET_CONTAINER_multipeermap_iterate (neighbours,
6246 &dv_neighbour_selection,
6247 &nsc);
6248 if (0 == nsc.num_eligible)
6249 return; /* done here, cannot forward to anyone else */
6250 nsc.num_selections = calculate_fork_degree (nhops, n_cnt, nsc.num_eligible);
6251 nsc.num_selections =
6252 GNUNET_MIN (MAX_DV_DISCOVERY_SELECTION, nsc.num_selections);
6253 for (unsigned int i = 0; i < nsc.num_selections; i++)
6254 nsc.selections[i] =
6255 (nsc.num_selections == n_cnt)
6256 ? i /* all were selected, avoid collisions by chance */
6257 : GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, n_cnt);
6258 nsc.num_eligible = 0;
6259 GNUNET_CONTAINER_multipeermap_iterate (neighbours,
6260 &dv_neighbour_transmission,
6261 &nsc);
6050 } 6262 }
6051} 6263}
6052 6264