Currently a retraction generally leaves a route with infinite metric, which is not needed

Some things need to be done before we can do a large scale test

• #6
• #7
• #8
• #9
• #10

Do some local testing. The main focus here is system stability and behavior

Currently we use prefixes as intended in the protocol, but these are not properly utilized during the routing phase. Routing matches full IP addresses, which essentially limits us to send data to the specific IP assigned at node start. To fix this:

• Introduce a dedicated "prefix" type (IP address + subnet size)
• Change existing protocol code to take in a prefix and return prefix on reception. Prefix length in the data can then be derived from the prefix (this actually means we will automatically get dynamically sized prefixes instead of hardcoded ones).
• In the routing, use destination IP and look for a subnet where "the destination is part of said subnet". This will require some minor changes in the data structure used for the routing table probably.
• Additionally, we should check and make sure that subnets are unique/nonoverlapping.
• To this end, we should also add some kind of routefilter, which is applied to every incoming update when we learn a route. If the route fails the filter it can be discarded. This way we can limit an update to have a prefix of at most /64, and reject ipv4 routes, for instance.

When executing mycelium in a docker through docker exec, the-t flag has to be passed, don't know if this impacts running it through zinit, systemd or starting it from another process.

Since we consider those peers to be the best path, sending these routes to them makes no sense, as an update for that route would then mean that peer would send a packet for this route to us, we send it back to that peer, and then it magically reaches its destination.

All in all, these updates are redundant and only waste some bandwidth

for some reason I provided a peer which was down, so myceilum was not able to send or receive messages while nothing shown in the logs that says no peers available or so, I think this should be communicated to the user to update the peer address or so

Currently if a peer has a sub 1 ms RTT, it is considered to have a metric cost of 0, essentially causing havoc in the route selection. For instance, if there are 50 peers on the same subnet, it might very well be possible for the node to select a route to a remote destination which first hops over all other 49 peers as this is considered to not cost anything, which is obviously false.

0.9.0 is for project 3.13
1.0.0 is for project 3.14

please make sure the milestones are created and issues are properly assigned

Right now we use TCP, which can lead to things like tcp in tcp. We should look into UDP / SCTP for underlay as well

Currently used because of reqwest. Need to play with the features to avoid this. Either drop SSL/TLS support (only a local API anyway), or switch to rustls

Currently there are 2 routing tables: the selected and the fallback. As the name implies, the selected routing table holds the selected route while the fallback holds any non selected routes which are or were recently viable.

The code needed to manage these multiple routing tables is however very cumbersome. Aside from the fact that we generally have 2 tables, thus using double the amount of memory for simply existing, we also need to do some extra work to ensure the tables are in a good state at all times while managing them. This is most notable in the route selection. While this can be optimized, doing so would require tracking a lot of different states and then making a large decision table. Since everything which influences state essentially doubles the amount of states, it was decided to not do this.

But if there was only 1 table with all the routes, a lot of this complexity would be avoided. It would also be better memory wise for the reason stated above, and we can perfectly mange by changing the routes to be a simple vector instead. This obsoletes #27

Currently the API, when doing a message peek/pop, immediately returns with either a message or no message. This is undesirable since a client thus has to either periodically poll, meaning messages might not be received as they are requested, or busy poll in a tight loop, which essentially burns out a cpu core.

The API needs to be reworked so that a call to these methods can wait for some time before returning if no data is ready. Ideally, the amount of time can be configured. This naturally leads to the use of an optional query parameter defining the amount of time to wait. Other than that, we need to consider if the default behavior is to return immediately or to wait for some default timeout.

Internally there are multiple ways to achieve this. One option would be to rework the VecDequeue of finished messages into a tokio::mpsc::channel::Receiver. Another one would be to work with a Notify (kind of like a semaphore), which is fed when new data comes in.

Currently there way routes are propagated is buggy, leading to strange behavior. While the rfc is somewhat murky about this, we do observe behavior that is for sure not correct. One problem is that we don't increase route seqno, which is obviously not what is intended. This probably causes #40 (in conjunction with the fact that fallback routes are improperly cleared, see #2).

Additionally, we can't rely on info from a peer handshake in the router, see #42.

Currently we assume that if an update has a route entry (which might be a fallback), there must be a selected route. This is not the case as a subnet might have no selected route if they are all unfeasible.

Mostly the protocol headers should be reviewed. Next to this, the data packet needs to be expanded with an intermediate header (inside the encrypted content) which details what kind of data it is. For now we only have raw packets, but this will be expanded in the future. By differentiating between these inside the encrypted content, the actual type of data is transparent for the hops.

Currently there are 2 unwraps when accepting a new peer in the handshake. If a remote exits quickly, this can cause the listening socket to be killed by a panic. Since we already propagate errors up, simply use ? and handle the error in the caller.

The router has 2 main functions: route data packets, and handle control flows. Since these things can happen simultaneously, the router need to arrange how part of its internals are accessed and modified to avoid data races.

The initial implementations uses a RwMutex, which is fine for the general case. For the read only path (i.e. process data packets), this does not seem to have any real impact on performance. The same however can not be said for the write path. Since a write lock also prevents a read lock, and writes seem to take a decent amount of time, we essentially have a "stop the world" kind of situation in the router. This translates to ping spikes running in tens of miliseconds (locally), since the read locks are waiting for the write lock to dissipate.

Considering the write path is infrequently used, it is likely better to look for an alternative concurrency approach which prioritizes read performance, even if it comes at a cost for write performance. A possible approach is to track 2 sets of mutable state and use an atomic pointer to point to a readable version. When we write, we do so on the not pointed to type, and then switch the pointer, and apply the same write. In this scenario, reads would never be blocked

Currently a route is selected when an update arrives, based on the metric. This approach is problematic. Most notably, it does not account for the feasibility condition and thus selectes unfeasible routes, creating routing loops. If a route is advertised by peer A with some metric M, to some node B, it might be that some node C connected to B learns this route from a peer D which is between B and C. This route will have the same seqno, but a higher metric (or the same in case of a local network). If node A now announces it's route with a higher seqno and increased metric, node B might unselect the route to node A, since it has a route to A via C with lower metric. At this point, we created a routing loop.

According to the RFC, route selection must be run after every feasible update is applied. We also need to consider for every route if it is still feasbile. In practice, we can actually simplify this a little bit.

• If the routing table has no route for the prefix, it is installed as the selected route.
• If the routing table has a route for a prefix with seqno S and metric M, we apply the same logic as the feasbility check in the RFC:
  • If the seqno S is higher, install the route from the update as selected route. If the currently selected route is different (i.e. different neighbour), move it to the fallback table.
  • If the seqno S is equal, and the metric M is strictly smaller, install the route as selected, and if the currently selected route has a different neighbour, move it to the fallback table.
  • We should also consider broadcasting this update to our peers. After all, new seqno's should be learned as soon as possible.
• In case the route is already a fallback route, we update it in place using the same feasibility checks.

This approach guarantees that the best route (feasible and lowest metric) is installed for a prefix at any point in time. After all, the metric can only increase if the seqno increases, and increasing the seqno immediately makes all other routes unfeasible.

The only issue left are retraction updates. When a route is retracted, we should apply the update, and then run a full route selection on the prefix.

I tried yesterday with @MarioBassem we both connected to the same peer and tried to reach each other by sending messages but it takes a lot of time and suddenlly it worked
I tried the same today it is taking too many time and giving this

Currently, and MTU sized buffer is allocated, which is then used to read a packet from the tun. Next, (assuming a valid destination), the packet is encrypted, and the nonce is appended. The current implementation does not reuse the allocation of the original data and instead allocates a new vector, of sufficient size for the AES_GCM tag and encrypted data. Then, we extend the vector, possibly growing the allocation but very likely triggering a full reallocation, to append the nonce.

Since we know the max MTU, nonce size, and tag size, we can simply allocate a buffer large enough upfront, provide this to the read method (possibly with some slicing), and encrypt in place. This would remove 2 allocations and deallocations, as wel as a memmove (should not be that expensive) in the hot path of the code.

Should fix #2

This should be send when a node receives an unfeasible update for a selected route, as per https://datatracker.ietf.org/doc/html/rfc8966#section-3.8.2.2. This is needed before we #44 , as #44 by itself might cause routing to break without this (as selected routes would go stale)

Telemetry is needed to gain insight in how the application is behaving. There are 2 kinds we are interested in: traces and metrics. For metrics, we want information regarding the async runtime and system it's running on (to see how changes in the system reflect on changes in the application and vise versa), and general stats such as transmitted packets, dropped packets, etc... For traces, it would be ideal if we can capture traces for entire packet flows (sending, forwarding, receiving), once again to verify how this behaves in various scenarios.

Right now the project is a single bin, it would be better if the majority of the business logic resided in a lib, which is then used by a small wrapper binary project.

Currently the overlay IP is exchanged, which is then also used in the router to generate retractions. This is not how babel works, where there is no handshake. In our case, we could consider keeping the handshake (doing something different like e.g. requesting a random signature to prove the receiver owns the private key), or outright drop it.

• cpu load
• memory allocation

A user needs to have a way to send a message to a peer, and a best effort attempt is done to deliver the message for some time. Status of the message (sent/delivered/other) needs to be queriable as well.

To transport the message (which can be arbitrary size), it can be chunked into small packets (similar to regular data traffic as is), and encrypted as regular data. Then it is forwarded to the destination with the regular flow. Since this requires differentiation between message en regular data traffic, this requires #28 first.

To manage this, another type MessageBox (or similar) is made which takes care of taking in arbitrary messages, chunks them, and injects them into the router. There also needs to be a way to filter data which is spit out by the router. Inside the message protocol, support needs to be added to acknowledge receipt (chunk based), and re transmit after some time.

This is a bit difficult to do, but in general we should be able to send some decent ICMP packets to the tun interface if something goes wrong. This includes no route to host in case we try to send to some unknown address.

Right now a single RoutingTable type is used, both for selected and fallback routing table. However, the selected table will have at most 1 entry for a subnet (the selected route), so the inclusion of a HashSet is not required there. Creating a separate type to express this would offer some minor benefits on the hot path of the code.

Right now any update is accepted, but this should not be the case. Instead, a subnet filter should be created to limit acceptable updates. For now this can be a global filter, but eventually it would be interesting to have these filters configurable per peer.

The current codebase is pretty WIP. While it works, there are some standards which can be applied, and legacy code/comments which can be removed / refactored. This way we can start new development from a clean codebase

Originally printing happened with (e)print(ln)! statements, which is not ideal. This has changed to use the log facade crate, but some more work is needed to verify log lvls and add logs in places where that makes sense.

Currently an update advertises the local metric of a route + the link cost of the destination peer. This is however invalid. Instead, a peer should avertise a link cost of route metric + next hop link cost. This seems similar at first, however the main difference is that the static (i.e. local) subnet is always advertised with metric 0. This means that directly connected peers have this route saved with link cost 0 as well, and advertise this route with a metric equal to the cost of the route source from that node.

This will primarily result in more feasible routes. Feasibility distance is still computed from the advertised metric. This means that it includes the link cost of the final hop, whereas the metric in the advertisements will not, which is what ends up being checked against the feasibility distance.

There needs to be an API which provides some visibility in the internals. Mostly it should be able to expose the routing tables, but it might also be a good idea to add or remove static peers through it

In the RFC, a router id is just 8 bytes random data. In our case, it is 32 bytes, the public key of the private key owned by a system. This means that in our case, router id's are "stable", i.e. a node (and prefix) always have the same router id. Although it is not precisely specified in the RFC, the official babel implementation always generates a random router id on start and you can't force the node to use a specific one.

It turns out that fixed router id's lead to a "fast restart problem". In short, if a node restarts (and thus resets its seqno) with the exact same router id, then it might be that there are still (retracted) routes available on nodes in the network. While the routes themselves are not necessarily a problem, it also means that the source entry will still be present. The source entry is used to determine if an update is feasible. If the seqno in the source entry is not too far ahead of the now 0 seqno, it will cause updates to be unfeasible for an extended period of time. This will in turn prevent routes from being acquired after a restart again, until either the source entry is purged (which requires implementing the timer, we currently also don't have that), or the seqno would be bumped high enough.

As such we need to expand router id to also include some randomness, so restarts change the router ID slowly. For this we will add 8 bytes. The first 2 will be set to 0 to allow us to use these for future purposes. The next 6 will be random. Note that we only need to be random compared with the same publickey (first 32 bytes), so 2^48 bits of randomness should be plenty.

As an added bonus, this also paves the way for anycasting.

Currently if there is an issue in the network a flood of seqno bumps can come in, which will all increment router seqno. it would be best to limit this to 1 every x amount of time

there still is an issue with the population of fallback routing table. When a node joins the network and it first receives and update with the 65534 metric, and later with a lower metric (once the metric has been established through Hello and IHU), the entry with metric 65534 correctly gets placed into the fallback (instead of selected) but the route always stays there. Even when a more appropriate fallback route comes in.

Currently rtnetlink is used to communicate with the linux kernel. This does not work on osx.

The tun code is currently in between other code. It should be isolated to its own module. Also, since tun code and setting routes is generally OS dependent, there should be a top level module exposing a generic tun interface, which also has a Stream and Sink implementation. Then, submodules should be made for specific implementations. Depending on which platform we compile for, the top level implemenation can, at compile time, select the proper submodule.

I got this peers list from @despiegk and only the last one is working

- 185.206.122.77:9651
- 83.231.240.31:9651
- 146.185.93.83:961

can we update the above two?

Source entry updates should be done only if the route is viable. This is an improvement in preparation for #49

Now that we work with prefixes, checks should validate if a destination is part of a prefix instead of an exact match of the base