[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] [gnunet] branch master updated: design for DV routing data
From: |
gnunet |
Subject: |
[GNUnet-SVN] [gnunet] branch master updated: design for DV routing data structure |
Date: |
Sat, 26 Jan 2019 17:59:18 +0100 |
This is an automated email from the git hooks/post-receive script.
grothoff pushed a commit to branch master
in repository gnunet.
The following commit(s) were added to refs/heads/master by this push:
new 9b41c00ea design for DV routing data structure
9b41c00ea is described below
commit 9b41c00eabf04e7f24fb540aa205acc8ecc61f94
Author: Christian Grothoff <address@hidden>
AuthorDate: Sat Jan 26 17:59:13 2019 +0100
design for DV routing data structure
---
src/transport/gnunet-service-tng.c | 203 ++++++++++++++++++++++++++++++++++++-
1 file changed, 199 insertions(+), 4 deletions(-)
diff --git a/src/transport/gnunet-service-tng.c
b/src/transport/gnunet-service-tng.c
index 5a8bf5bc1..707fe49a7 100644
--- a/src/transport/gnunet-service-tng.c
+++ b/src/transport/gnunet-service-tng.c
@@ -33,9 +33,7 @@
* transport-to-transport traffic)
*
* Implement:
- * - data structures for defragmentation
- * - manage defragmentation
- * - ACK handling / retransmission
+ * - ACK handling / retransmission
* - track RTT, distance, loss, etc.
* - DV data structures, learning, forgetting & using them!
*
@@ -609,6 +607,98 @@ struct TransportClient;
struct Neighbour;
+/**
+ * Entry in our #dv_routes table, representing a (set of) distance
+ * vector routes to a particular peer.
+ */
+struct DistanceVector;
+
+/**
+ * One possible hop towards a DV target.
+ */
+struct DistanceVectorHop
+{
+
+ /**
+ * Kept in a MDLL, sorted by @e timeout.
+ */
+ struct DistanceVectorHop *next_dv;
+
+ /**
+ * Kept in a MDLL, sorted by @e timeout.
+ */
+ struct DistanceVectorHop *prev_dv;
+
+ /**
+ * Kept in a MDLL.
+ */
+ struct DistanceVectorHop *next_neighbour;
+
+ /**
+ * Kept in a MDLL.
+ */
+ struct DistanceVectorHop *prev_neighbour;
+
+ /**
+ * What would be the next hop to @e target?
+ */
+ struct Neighbour *next_hop;
+
+ /**
+ * Distance vector entry this hop belongs with.
+ */
+ struct DistanceVector *dv;
+
+ /**
+ * Array of @e distance hops to the target, excluding @e next_hop.
+ * NULL if the entire path is us to @e next_hop to `target`. Allocated
+ * at the end of this struct.
+ */
+ const struct GNUNET_PeerIdentity *path;
+
+ /**
+ * At what time do we forget about this path unless we see it again
+ * while learning?
+ */
+ struct GNUNET_TIME_Absolute timeout;
+
+ /**
+ * How many hops in total to the `target` (excluding @e next_hop and
`target` itself),
+ * thus 0 still means a distance of 2 hops (to @e next_hop and then to
`target`)?
+ */
+ unsigned int distance;
+};
+
+
+/**
+ * Entry in our #dv_routes table, representing a (set of) distance
+ * vector routes to a particular peer.
+ */
+struct DistanceVector
+{
+
+ /**
+ * To which peer is this a route?
+ */
+ struct GNUNET_PeerIdentity target;
+
+ /**
+ * Known paths to @e target.
+ */
+ struct DistanceVectorHop *dv_head;
+
+ /**
+ * Known paths to @e target.
+ */
+ struct DistanceVectorHop *dv_tail;
+
+ /**
+ * Task scheduled to purge expired paths from @e dv_head MDLL.
+ */
+ struct GNUNET_SCHEDULER_Task *timeout_task;
+};
+
+
/**
* Entry identifying transmission in one of our `struct
* GNUNET_ATS_Sessions` which still awaits an ACK. This is used to
@@ -897,6 +987,18 @@ struct Neighbour
*/
struct PendingMessage *pending_msg_tail;
+ /**
+ * Head of MDLL of DV hops that have this neighbour as next hop. Must be
+ * purged if this neighbour goes down.
+ */
+ struct DistanceVectorHop *dv_head;
+
+ /**
+ * Tail of MDLL of DV hops that have this neighbour as next hop. Must be
+ * purged if this neighbour goes down.
+ */
+ struct DistanceVectorHop *dv_tail;
+
/**
* Head of DLL of ATS sessions to this peer.
*/
@@ -1307,6 +1409,12 @@ static struct GNUNET_CRYPTO_EddsaPrivateKey
*GST_my_private_key;
*/
static struct GNUNET_CONTAINER_MultiPeerMap *neighbours;
+/**
+ * Map from PIDs to `struct DistanceVector` entries describing
+ * known paths to the peer.
+ */
+static struct GNUNET_CONTAINER_MultiPeerMap *dv_routes;
+
/**
* Database for peer's HELLOs.
*/
@@ -1404,6 +1512,56 @@ struct MonitorEvent
};
+/**
+ * Free a @dvh, and if it is the last path to the `target`,also
+ * free the associated DV entry in #dv_routes.
+ *
+ * @param dvh hop to free
+ */
+static void
+free_distance_vector_hop (struct DistanceVectorHop *dvh)
+{
+ struct Neighbour *n = dvh->next_hop;
+ struct DistanceVector *dv = dvh->dv;
+
+ GNUNET_CONTAINER_MDLL_remove (neighbour,
+ n->dv_head,
+ n->dv_tail,
+ dvh);
+ GNUNET_CONTAINER_MDLL_remove (dv,
+ dv->dv_head,
+ dv->dv_tail,
+ dvh);
+ GNUNET_free (dvh);
+ if (NULL == dv->dv_head)
+ {
+ GNUNET_assert (GNUNET_YES ==
+ GNUNET_CONTAINER_multipeermap_remove (dv_routes,
+ &dv->target,
+ dv));
+ if (NULL != dv->timeout_task)
+ GNUNET_SCHEDULER_cancel (dv->timeout_task);
+ GNUNET_free (dv);
+ }
+}
+
+
+/**
+ * Free entry in #dv_routes. First frees all hops to the target, and
+ * the last target will implicitly free @a dv as well.
+ *
+ * @param dv route to free
+ */
+static void
+free_dv_route (struct DistanceVector *dv)
+{
+ struct DistanceVectorHop *dvh;
+
+ while (NULL != (dvh = dv->dv_head))
+ free_distance_vector_hop (dvh);
+}
+
+
/**
* Notify monitor @a tc about an event. That @a tc
* cares about the event has already been checked.
@@ -1596,6 +1754,8 @@ free_reassembly_cb (void *cls,
static void
free_neighbour (struct Neighbour *neighbour)
{
+ struct DistanceVectorHop *dvh;
+
GNUNET_assert (NULL == neighbour->session_head);
GNUNET_assert (GNUNET_YES ==
GNUNET_CONTAINER_multipeermap_remove (neighbours,
@@ -1613,6 +1773,8 @@ free_neighbour (struct Neighbour *neighbour)
GNUNET_CONTAINER_heap_destroy (neighbour->reassembly_heap);
neighbour->reassembly_heap = NULL;
}
+ while (NULL != (dvh = neighbour->dv_head))
+ free_distance_vector_hop (dvh);
if (NULL != neighbour->reassembly_timeout_task)
GNUNET_SCHEDULER_cancel (neighbour->reassembly_timeout_task);
GNUNET_free (neighbour);
@@ -3019,7 +3181,10 @@ handle_fragment_ack (void *cls,
{
struct CommunicatorMessageContext *cmc = cls;
- // FIXME: do work!
+ // FIXME: do work: identify original message; then identify fragments being
acked;
+ // remove those from the tree to prevent retransmission;
+ // compute RTT
+ // if entire message is ACKed, handle that as well.
finish_cmc_handling (cmc);
}
@@ -4371,6 +4536,29 @@ free_neighbour_cb (void *cls,
}
+/**
+ * Free DV route entry.
+ *
+ * @param cls NULL
+ * @param pid unused
+ * @param value a `struct DistanceVector`
+ * @return #GNUNET_OK (always)
+ */
+static int
+free_dv_routes_cb (void *cls,
+ const struct GNUNET_PeerIdentity *pid,
+ void *value)
+{
+ struct DistanceVector *dv = value;
+
+ (void) cls;
+ (void) pid;
+ free_dv_route (dv);
+
+ return GNUNET_OK;
+}
+
+
/**
* Free ephemeral entry.
*
@@ -4436,6 +4624,11 @@ do_shutdown (void *cls)
}
GNUNET_CONTAINER_multipeermap_destroy (neighbours);
neighbours = NULL;
+ GNUNET_CONTAINER_multipeermap_iterate (dv_routes,
+ &free_dv_routes_cb,
+ NULL);
+ GNUNET_CONTAINER_multipeermap_destroy (dv_routes);
+ dv_routes = NULL;
GNUNET_CONTAINER_multipeermap_iterate (ephemeral_map,
&free_ephemeral_cb,
NULL);
@@ -4463,6 +4656,8 @@ run (void *cls,
GST_cfg = c;
neighbours = GNUNET_CONTAINER_multipeermap_create (1024,
GNUNET_YES);
+ dv_routes = GNUNET_CONTAINER_multipeermap_create (1024,
+ GNUNET_YES);
ephemeral_map = GNUNET_CONTAINER_multipeermap_create (32,
GNUNET_YES);
ephemeral_heap = GNUNET_CONTAINER_heap_create
(GNUNET_CONTAINER_HEAP_ORDER_MIN);
--
To stop receiving notification emails like this one, please contact
address@hidden
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] [gnunet] branch master updated: design for DV routing data structure,
gnunet <=