diff options
author | Christian Grothoff <christian@grothoff.org> | 2019-04-24 14:19:38 +0200 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2019-04-24 14:19:38 +0200 |
commit | cceac0d2de9556b5a270570f136cd5324351f55e (patch) | |
tree | 35a37f84c4e39571d83d8bc1841c65e509f381d8 /src | |
parent | 726b882c196f6dd6ad752ef91537e04d749e0924 (diff) | |
download | gnunet-cceac0d2de9556b5a270570f136cd5324351f55e.tar.gz gnunet-cceac0d2de9556b5a270570f136cd5324351f55e.zip |
implement looping over neighbours to call fwd_dv_learn()
Diffstat (limited to 'src')
-rw-r--r-- | src/transport/gnunet-service-tng.c | 236 |
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 | */ | ||
5864 | struct 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 | */ | ||
5916 | static int | ||
5917 | dv_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 | */ | ||
5944 | static int | ||
5945 | dv_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 | */ | ||
6018 | static unsigned int | ||
6019 | calculate_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 | ||