diff options
-rw-r--r-- | src/transport/gnunet-service-tng.c | 193 |
1 files changed, 154 insertions, 39 deletions
diff --git a/src/transport/gnunet-service-tng.c b/src/transport/gnunet-service-tng.c index 5c51ed59a..e128a4abf 100644 --- a/src/transport/gnunet-service-tng.c +++ b/src/transport/gnunet-service-tng.c | |||
@@ -24,27 +24,9 @@ | |||
24 | * | 24 | * |
25 | * TODO: | 25 | * TODO: |
26 | * Implement next: | 26 | * Implement next: |
27 | * - track RTT, distance, loss, etc. => requires extra data structures! | 27 | * - FIXME: looping over neighbours when calling forward_dv_learn()! |
28 | * => fragment UUIDs should be 'sequential' 32-bit numbers, for cummulative | 28 | * - FIXME: transmit_on_queue: track dvh we may be using and pass it to |
29 | * acks with Bitmask | 29 | * fragment_message() and reliability_box_message() if applicable |
30 | * => fragments carry their own offsets, so receiver will NOT require | ||
31 | * seeing all the possible values | ||
32 | * => can generate 'fresh' UUIDs for each retransmission to track it | ||
33 | * => but need to keep 'map' of 32-bit UUID to queue! | ||
34 | * => message UUIDs are currently overkill with 256 bits | ||
35 | * => cummulative acks for messages include full UUID list | ||
36 | * => message UUID size should be chosen to result in 8 byte alignment | ||
37 | * => could encode 32-bit counter + 32-bit queue UUID in 64-bit message | ||
38 | * UUID? | ||
39 | * => Use multihashmap32 on counter for lookup in hashmap? | ||
40 | * => FIXME: 2x32 bit introduced, but still set to random value | ||
41 | * instead of using the generators! | ||
42 | * (and generators not initialized to random starting values either) | ||
43 | * - consider replacing random `struct GNUNET_ShortHashCode` message UUIDs | ||
44 | * with (incrementing) 64-bit numbers (compacting both | ||
45 | * `struct TransportReliabilityBox` and `struct | ||
46 | * TransportReliabilityAckMessage`), and using *different* UUIDs for each | ||
47 | * transmission (even of the same message!) | ||
48 | * - proper use/initialization of timestamps in messages exchanged | 30 | * - proper use/initialization of timestamps in messages exchanged |
49 | * during DV learning | 31 | * during DV learning |
50 | * - persistence of monotonic time from DVInit to prevent | 32 | * - persistence of monotonic time from DVInit to prevent |
@@ -60,12 +42,11 @@ | |||
60 | * | 42 | * |
61 | * Later: | 43 | * Later: |
62 | * - review retransmission logic, right now there is no smartness there! | 44 | * - review retransmission logic, right now there is no smartness there! |
63 | * => congestion control, flow control, etc (requires RTT, loss, etc.) | 45 | * => congestion control, flow control, etc |
64 | * | 46 | * |
65 | * Optimizations: | 47 | * Optimizations: |
66 | * - use shorthashmap on msg_uuid's when matching reliability/fragment ACKs | 48 | * - AcknowledgementUUIDPs are overkill with 256 bits (128 would do) |
67 | * against our pending message queue (requires additional per neighbour | 49 | * => Need 128 bit hash map though! |
68 | * hash map to be maintained, avoids possible linear scan on pending msgs) | ||
69 | * - queue_send_msg and route_message both by API design have to make copies | 50 | * - queue_send_msg and route_message both by API design have to make copies |
70 | * of the payload, and route_message on top of that requires a malloc/free. | 51 | * of the payload, and route_message on top of that requires a malloc/free. |
71 | * Change design to approximate "zero" copy better... | 52 | * Change design to approximate "zero" copy better... |
@@ -130,6 +111,12 @@ | |||
130 | #define IN_PACKET_SIZE_WITHOUT_MTU 128 | 111 | #define IN_PACKET_SIZE_WITHOUT_MTU 128 |
131 | 112 | ||
132 | /** | 113 | /** |
114 | * Number of slots we keep of historic data for computation of | ||
115 | * goodput / message loss ratio. | ||
116 | */ | ||
117 | #define GOODPUT_AGING_SLOTS 4 | ||
118 | |||
119 | /** | ||
133 | * Minimum number of hops we should forward DV learn messages | 120 | * Minimum number of hops we should forward DV learn messages |
134 | * even if they are NOT useful for us in hope of looping | 121 | * even if they are NOT useful for us in hope of looping |
135 | * back to the initiator? | 122 | * back to the initiator? |
@@ -1004,6 +991,49 @@ struct EphemeralCacheEntry | |||
1004 | 991 | ||
1005 | 992 | ||
1006 | /** | 993 | /** |
994 | * Information we keep per #GOODPUT_AGING_SLOTS about historic | ||
995 | * (or current) transmission performance. | ||
996 | */ | ||
997 | struct TransmissionHistoryEntry | ||
998 | { | ||
999 | /** | ||
1000 | * Number of bytes actually sent in the interval. | ||
1001 | */ | ||
1002 | uint64_t bytes_sent; | ||
1003 | |||
1004 | /** | ||
1005 | * Number of bytes received and acknowledged by the other peer in | ||
1006 | * the interval. | ||
1007 | */ | ||
1008 | uint64_t bytes_received; | ||
1009 | }; | ||
1010 | |||
1011 | |||
1012 | /** | ||
1013 | * Performance data for a transmission possibility. | ||
1014 | */ | ||
1015 | struct PerformanceData | ||
1016 | { | ||
1017 | /** | ||
1018 | * Weighted average for the RTT. | ||
1019 | */ | ||
1020 | struct GNUNET_TIME_Relative aged_rtt; | ||
1021 | |||
1022 | /** | ||
1023 | * Historic performance data, using a ring buffer of#GOODPUT_AGING_SLOTS | ||
1024 | * entries. | ||
1025 | */ | ||
1026 | struct TransmissionHistoryEntry the[GOODPUT_AGING_SLOTS]; | ||
1027 | |||
1028 | /** | ||
1029 | * What was the last age when we wrote to @e the? Used to clear | ||
1030 | * old entries when the age advances. | ||
1031 | */ | ||
1032 | unsigned int last_age; | ||
1033 | }; | ||
1034 | |||
1035 | |||
1036 | /** | ||
1007 | * Client connected to the transport service. | 1037 | * Client connected to the transport service. |
1008 | */ | 1038 | */ |
1009 | struct TransportClient; | 1039 | struct TransportClient; |
@@ -1200,6 +1230,11 @@ struct DistanceVectorHop | |||
1200 | struct GNUNET_TIME_Absolute path_valid_until; | 1230 | struct GNUNET_TIME_Absolute path_valid_until; |
1201 | 1231 | ||
1202 | /** | 1232 | /** |
1233 | * Performance data for this transmission possibility. | ||
1234 | */ | ||
1235 | struct PerformanceData pd; | ||
1236 | |||
1237 | /** | ||
1203 | * Number of hops in total to the `target` (excluding @e next_hop and `target` | 1238 | * Number of hops in total to the `target` (excluding @e next_hop and `target` |
1204 | * itself). Thus 0 still means a distance of 2 hops (to @e next_hop and then | 1239 | * itself). Thus 0 still means a distance of 2 hops (to @e next_hop and then |
1205 | * to `target`). | 1240 | * to `target`). |
@@ -1377,11 +1412,6 @@ struct Queue | |||
1377 | struct GNUNET_SCHEDULER_Task *visibility_task; | 1412 | struct GNUNET_SCHEDULER_Task *visibility_task; |
1378 | 1413 | ||
1379 | /** | 1414 | /** |
1380 | * Our current RTT estimate for this queue. | ||
1381 | */ | ||
1382 | struct GNUNET_TIME_Relative rtt; | ||
1383 | |||
1384 | /** | ||
1385 | * How long do *we* consider this @e address to be valid? In the past or | 1415 | * How long do *we* consider this @e address to be valid? In the past or |
1386 | * zero if we have not yet validated it. Can be updated based on | 1416 | * zero if we have not yet validated it. Can be updated based on |
1387 | * challenge-response validations (via address validation logic), or when we | 1417 | * challenge-response validations (via address validation logic), or when we |
@@ -1391,6 +1421,11 @@ struct Queue | |||
1391 | struct GNUNET_TIME_Absolute validated_until; | 1421 | struct GNUNET_TIME_Absolute validated_until; |
1392 | 1422 | ||
1393 | /** | 1423 | /** |
1424 | * Performance data for this queue. | ||
1425 | */ | ||
1426 | struct PerformanceData pd; | ||
1427 | |||
1428 | /** | ||
1394 | * Message ID generator for transmissions on this queue to the | 1429 | * Message ID generator for transmissions on this queue to the |
1395 | * communicator. | 1430 | * communicator. |
1396 | */ | 1431 | */ |
@@ -2380,6 +2415,26 @@ static unsigned int pa_count; | |||
2380 | 2415 | ||
2381 | 2416 | ||
2382 | /** | 2417 | /** |
2418 | * Get an offset into the transmission history buffer for `struct | ||
2419 | * PerformanceData`. Note that the caller must perform the required | ||
2420 | * modulo #GOODPUT_AGING_SLOTS operation before indexing into the | ||
2421 | * array! | ||
2422 | * | ||
2423 | * An 'age' lasts 15 minute slots. | ||
2424 | * | ||
2425 | * @return current age of the world | ||
2426 | */ | ||
2427 | static unsigned int | ||
2428 | get_age () | ||
2429 | { | ||
2430 | struct GNUNET_TIME_Absolute now; | ||
2431 | |||
2432 | now = GNUNET_TIME_absolute_get (); | ||
2433 | return now.abs_value_us / GNUNET_TIME_UNIT_MINUTES.rel_value_us / 15; | ||
2434 | } | ||
2435 | |||
2436 | |||
2437 | /** | ||
2383 | * Release @a pa data structure. | 2438 | * Release @a pa data structure. |
2384 | * | 2439 | * |
2385 | * @param pa data structure to release | 2440 | * @param pa data structure to release |
@@ -3964,7 +4019,12 @@ struct BackchannelKeyState | |||
3964 | 4019 | ||
3965 | 4020 | ||
3966 | /** | 4021 | /** |
3967 | * FIXME: comment! | 4022 | * Given the key material in @a km and the initialization vector |
4023 | * @a iv, setup the key material for the backchannel in @a key. | ||
4024 | * | ||
4025 | * @param km raw master secret | ||
4026 | * @param iv initialization vector | ||
4027 | * @param key[out] symmetric cipher and HMAC state to generate | ||
3968 | */ | 4028 | */ |
3969 | static void | 4029 | static void |
3970 | bc_setup_key_state_from_km (const struct GNUNET_HashCode *km, | 4030 | bc_setup_key_state_from_km (const struct GNUNET_HashCode *km, |
@@ -4794,6 +4854,60 @@ handle_reliability_box (void *cls, | |||
4794 | 4854 | ||
4795 | 4855 | ||
4796 | /** | 4856 | /** |
4857 | * Check if we have advanced to another age since the last time. If | ||
4858 | * so, purge ancient statistics (more than GOODPUT_AGING_SLOTS before | ||
4859 | * the current age) | ||
4860 | * | ||
4861 | * @param pd[in,out] data to update | ||
4862 | * @param age current age | ||
4863 | */ | ||
4864 | static void | ||
4865 | update_pd_age (struct PerformanceData *pd, unsigned int age) | ||
4866 | { | ||
4867 | unsigned int sage; | ||
4868 | |||
4869 | if (age == pd->last_age) | ||
4870 | return; /* nothing to do */ | ||
4871 | sage = GNUNET_MAX (pd->last_age, age - 2 * GOODPUT_AGING_SLOTS); | ||
4872 | for (unsigned int i = sage; i <= age - GOODPUT_AGING_SLOTS; i++) | ||
4873 | { | ||
4874 | struct TransmissionHistoryEntry *the = &pd->the[i % GOODPUT_AGING_SLOTS]; | ||
4875 | |||
4876 | the->bytes_sent = 0; | ||
4877 | the->bytes_received = 0; | ||
4878 | } | ||
4879 | pd->last_age = age; | ||
4880 | } | ||
4881 | |||
4882 | |||
4883 | /** | ||
4884 | * Update @a pd based on the latest @a rtt and the number of bytes | ||
4885 | * that were confirmed to be successfully transmitted. | ||
4886 | * | ||
4887 | * @param pd[in,out] data to update | ||
4888 | * @param rtt latest round-trip time | ||
4889 | * @param bytes_transmitted_ok number of bytes receiver confirmed as received | ||
4890 | */ | ||
4891 | static void | ||
4892 | update_performance_data (struct PerformanceData *pd, | ||
4893 | struct GNUNET_TIME_Relative rtt, | ||
4894 | uint16_t bytes_transmitted_ok) | ||
4895 | { | ||
4896 | uint64_t nval = rtt.rel_value_us; | ||
4897 | uint64_t oval = pd->aged_rtt.rel_value_us; | ||
4898 | unsigned int age = get_age (); | ||
4899 | struct TransmissionHistoryEntry *the = &pd->the[age % GOODPUT_AGING_SLOTS]; | ||
4900 | |||
4901 | if (oval == GNUNET_TIME_UNIT_FOREVER_REL.rel_value_us) | ||
4902 | pd->aged_rtt = rtt; | ||
4903 | else | ||
4904 | pd->aged_rtt.rel_value_us = (nval + 7 * oval) / 8; | ||
4905 | update_pd_age (pd, age); | ||
4906 | the->bytes_received += bytes_transmitted_ok; | ||
4907 | } | ||
4908 | |||
4909 | |||
4910 | /** | ||
4797 | * We have successfully transmitted data via @a q, update metrics. | 4911 | * We have successfully transmitted data via @a q, update metrics. |
4798 | * | 4912 | * |
4799 | * @param q queue to update | 4913 | * @param q queue to update |
@@ -4805,7 +4919,7 @@ update_queue_performance (struct Queue *q, | |||
4805 | struct GNUNET_TIME_Relative rtt, | 4919 | struct GNUNET_TIME_Relative rtt, |
4806 | uint16_t bytes_transmitted_ok) | 4920 | uint16_t bytes_transmitted_ok) |
4807 | { | 4921 | { |
4808 | // FIXME: implement! | 4922 | update_performance_data (&q->pd, rtt, bytes_transmitted_ok); |
4809 | } | 4923 | } |
4810 | 4924 | ||
4811 | 4925 | ||
@@ -4821,7 +4935,7 @@ update_dvh_performance (struct DistanceVectorHop *dvh, | |||
4821 | struct GNUNET_TIME_Relative rtt, | 4935 | struct GNUNET_TIME_Relative rtt, |
4822 | uint16_t bytes_transmitted_ok) | 4936 | uint16_t bytes_transmitted_ok) |
4823 | { | 4937 | { |
4824 | // FIXME: implement! | 4938 | update_performance_data (&dvh->pd, rtt, bytes_transmitted_ok); |
4825 | } | 4939 | } |
4826 | 4940 | ||
4827 | 4941 | ||
@@ -6481,7 +6595,7 @@ handle_validation_response ( | |||
6481 | return; | 6595 | return; |
6482 | } | 6596 | } |
6483 | q->validated_until = vs->validated_until; | 6597 | q->validated_until = vs->validated_until; |
6484 | q->rtt = vs->validation_rtt; | 6598 | q->pd.aged_rtt = vs->validation_rtt; |
6485 | n = q->neighbour; | 6599 | n = q->neighbour; |
6486 | if (GNUNET_NO != n->core_visible) | 6600 | if (GNUNET_NO != n->core_visible) |
6487 | return; /* nothing changed, we are done here */ | 6601 | return; /* nothing changed, we are done here */ |
@@ -7015,7 +7129,8 @@ transmit_on_queue (void *cls) | |||
7015 | message urgency and size when delaying ACKs, etc.) */ | 7129 | message urgency and size when delaying ACKs, etc.) */ |
7016 | update_pm_next_attempt (s, | 7130 | update_pm_next_attempt (s, |
7017 | GNUNET_TIME_relative_to_absolute ( | 7131 | GNUNET_TIME_relative_to_absolute ( |
7018 | GNUNET_TIME_relative_multiply (queue->rtt, 4))); | 7132 | GNUNET_TIME_relative_multiply (queue->pd.aged_rtt, |
7133 | 4))); | ||
7019 | } | 7134 | } |
7020 | 7135 | ||
7021 | /* finally, re-schedule queue transmission task itself */ | 7136 | /* finally, re-schedule queue transmission task itself */ |
@@ -7252,7 +7367,7 @@ notify_client_queues (void *cls, | |||
7252 | for (struct Queue *q = neighbour->queue_head; NULL != q; | 7367 | for (struct Queue *q = neighbour->queue_head; NULL != q; |
7253 | q = q->next_neighbour) | 7368 | q = q->next_neighbour) |
7254 | { | 7369 | { |
7255 | struct MonitorEvent me = {.rtt = q->rtt, | 7370 | struct MonitorEvent me = {.rtt = q->pd.aged_rtt, |
7256 | .cs = q->cs, | 7371 | .cs = q->cs, |
7257 | .num_msg_pending = q->num_msg_pending, | 7372 | .num_msg_pending = q->num_msg_pending, |
7258 | .num_bytes_pending = q->num_bytes_pending}; | 7373 | .num_bytes_pending = q->num_bytes_pending}; |
@@ -7486,7 +7601,7 @@ check_connection_quality (void *cls, | |||
7486 | ctx->q = q; | 7601 | ctx->q = q; |
7487 | /* OPTIMIZE-FIXME: in the future, add reliability / goodput | 7602 | /* OPTIMIZE-FIXME: in the future, add reliability / goodput |
7488 | statistics and consider those as well here? */ | 7603 | statistics and consider those as well here? */ |
7489 | if (q->rtt.rel_value_us < DV_QUALITY_RTT_THRESHOLD.rel_value_us) | 7604 | if (q->pd.aged_rtt.rel_value_us < DV_QUALITY_RTT_THRESHOLD.rel_value_us) |
7490 | do_inc = GNUNET_YES; | 7605 | do_inc = GNUNET_YES; |
7491 | } | 7606 | } |
7492 | if (GNUNET_YES == do_inc) | 7607 | if (GNUNET_YES == do_inc) |
@@ -7669,7 +7784,7 @@ handle_add_queue_message (void *cls, | |||
7669 | queue = GNUNET_malloc (sizeof (struct Queue) + addr_len); | 7784 | queue = GNUNET_malloc (sizeof (struct Queue) + addr_len); |
7670 | queue->tc = tc; | 7785 | queue->tc = tc; |
7671 | queue->address = (const char *) &queue[1]; | 7786 | queue->address = (const char *) &queue[1]; |
7672 | queue->rtt = GNUNET_TIME_UNIT_FOREVER_REL; | 7787 | queue->pd.aged_rtt = GNUNET_TIME_UNIT_FOREVER_REL; |
7673 | queue->qid = aqm->qid; | 7788 | queue->qid = aqm->qid; |
7674 | queue->mtu = ntohl (aqm->mtu); | 7789 | queue->mtu = ntohl (aqm->mtu); |
7675 | queue->nt = (enum GNUNET_NetworkType) ntohl (aqm->nt); | 7790 | queue->nt = (enum GNUNET_NetworkType) ntohl (aqm->nt); |
@@ -7692,7 +7807,7 @@ handle_add_queue_message (void *cls, | |||
7692 | memcpy (&queue[1], addr, addr_len); | 7807 | memcpy (&queue[1], addr, addr_len); |
7693 | /* notify monitors about new queue */ | 7808 | /* notify monitors about new queue */ |
7694 | { | 7809 | { |
7695 | struct MonitorEvent me = {.rtt = queue->rtt, .cs = queue->cs}; | 7810 | struct MonitorEvent me = {.rtt = queue->pd.aged_rtt, .cs = queue->cs}; |
7696 | 7811 | ||
7697 | notify_monitors (&neighbour->pid, queue->address, queue->nt, &me); | 7812 | notify_monitors (&neighbour->pid, queue->address, queue->nt, &me); |
7698 | } | 7813 | } |