Unexpected properties of contention windows for rebroadcasting

[korbinianbauer]

I'm currently looking deeper into how the rebroadcast timing works in the firmware. There's plenty of proposals about changing the Role's behaviour, so I wanted to make sure my assumptions about the current behaviour are right to begin with... Turns out they're not.

There's multiple surprises (to me), I'll go through them step by step.

This plot shows the range of possible delays a node randomly chooses from to wait before rebroadcasting a packet in units of "slots".
The range depends on the SNR measured at reception and the role:
ROUTER-like (green)
CLIENT-like (blue)
ROUTER_LATE (red)

First, the expectations that got confirmed:

• Routers (green shaded area) always rebroadcast earlier than Clients
• Clients (blue shaded area) tend to wait longer at higher SNR

Now here's what I'm surprised about. It's multiple things, I'll try to explain and visualize as clearly as I can, please bear with me.
I'll always provide one plot on the left that shows the "issue" and one plot on the right that shows what I expected it to be like.

1. A Client with vastly higher SNR still has a significant chance of preempting a Client with much lower SNR
That's because the lower bound of the Clients delay window is independent of SNR. (left plot).
I would have expected the lower bound of the range to increase with SNR, too, so a node with vastly higher SNR (1) doesn't preempt another one (2), even when it chooses a pretty small delay from their allowed range by chance (right plot).

---

2. Within major ranges, a Client that received with multiple dB lower SNR has zero (!) preference over another Client
There's only a small number of discrete steps here. In this example - despite significantly different SNR (here -14.5 dB vs. -9.5 dB) both Clients choose their delay randomly from the exact same range of possible values. Which of these Clients rebroadcasts is a 50/50 chance within a whole range of SNR values.
I would have expected the ranges to smoothly scale with SNR, so even though the ranges of nodes with similar SNR overlap, the lower SNR node (4) is more likely to rebroadcast and preempt (3) than the other way around.

There's so few different ranges because RadioInterface::getCWsize(float snr) returns a uint8_t in the range 3...8

If getCWsize() returned a float 3.0...8.0 instead and the rounding to an Integer amount of timeslots was only done later in RadioInterface::getTxDelayMsecWeighted() we would get the expected rebroadcasting preference that scales smoothly with SNR.

---

3. Routers consider SNR, too
I'm not sure why that is, given that they are not able to silence each other anyways.
I would expect them to always choose from the full range of delays up to where the Client window starts, to make collisions as unlikely as possible:

---

4. Router_Late considers SNR, too
Again, I'm not sure why that is. My impression was that the whole selling point of Router_Late is to not preempt Client-Rebroadcasts.
But according to this, it's actually very likely that a low-SNR Router_Late somewhere will preempt most Clients.
I would have expected the "Late" window to always be later than the whole Client-window, independent of SNR.

---

5. There's just a single slot for Router_Late
Apparently, the "Late window" that is used by Router_Late isn't actually a window, it's a deterministic delay based on SNR. And since there's just a small handful of bins that all SNRs are grouped into right now, the risk of collision between multiple Router_Late seems pretty high.

[GUVWAF]

First of all, SNR is just a heuristic; it was not designed to be a one-to-one relationship with rebroadcasting delay. There’s all kind of hardware and environmental differences that makes it not suited to follow precisely.

1. When increasing the lower bound to increase with SNR too, the window to choose a random number from gets very small, which increases the chance that nodes with similar SNR transmit at the same time (your point from 3 and 5).

2. Yeah, could be done, if it’s not too computationally expensive. But still, it’s just a heuristic ;)

3. I think that's a fair point, although multiple ROUTERs in each other's range is not advised in general. Furthermore, it determines which nodes are trying to rebroadcast first after they hear one of the ROUTERs rebroadcast. Two ROUTERs in each other's range does not mean every node can hear both.

4. No, ROUTER_LATE was designed to be acting as client first, and only when it receives a duplicate, it will move to the late rebroadcast window.

5. No, add_delay is still random:
   

   firmware/src/mesh/RadioLibInterface.cpp

   Lines 318 to 320 in 07d354f

   	unsigned long add_delay = p->rx_rssi ? getTxDelayMsecWeighted(p) : getTxDelayMsec();
   	unsigned long now = millis();
   	p->tx_after = min(max(p->tx_after + add_delay, now + add_delay), now + 2 * getTxDelayMsecWeightedWorst(p->rx_snr));

[korbinianbauer]

First of all, SNR is just a heuristic; it was not designed to be a one-to-one relationship with rebroadcasting delay. There’s all kind of hardware and environmental differences that makes it not suited to follow precisely.

I think the SNR heuristic (and the whole managed flooding idea) deserves more credit people make it out to be though. SNR may not be a great indicator of physical, spacial, euclidian distance, but it is a good indicator of distance in the "RF space". That space has weird properties and is not as intuitive to imagine, but it does matter.

Even though SNR isn't a perfectly precise indicator for the optimal order of rebroadcasts, following SNR strictly wouldn't result in a worse order than following SNR+randomness IMO.

I do agree there has to be some added randomness to reduce collisions on average, yes, but I think the amount of randomness deserves some scrutiny.

1. When increasing the lower bound to increase with SNR too, the window to choose a random number from gets very small, which increases the chance that nodes with similar SNR transmit at the same time (your point from 3 and 5).

Currently, the low-SNR nodes (< -15 dB) have the narrowest window. That wouldn't get any narrower. It's only the (much larger) windows of the higher-SNR regions that would have to get a little bit smaller to preserve the rough order of rebroadcasting that the SNR would suggest, but they'd still stay much larger than the low-SNR window is now.

The total Client window across the whole SNR-range wouldn't get smaller at all. I'd just like to constrain the order of which Clients use what part of the total window to align with the heuristic better.

A high-SNR Client being allowed to randomly choose to rebroadcast first is equal to terribly placed Routers popping in and out of existence randomly.

In fact, if high-SNR Clients wouldn't be allowed to rebroadcast super early by chance, the low-SNR Clients wouldn't need to hurry up as much to get ahead of them. The window for low-SNR Clients could actually be larger then, e.g.:

2. Yeah, could be done, if it’s not too computationally expensive.

Certainly can be implemented efficiently, it doesn't have to be actual float exponentiation to be smooth-ish.

3. I think that's a fair point, although multiple ROUTERs in each other's range is not advised in general.

..well, they have to be to transport a packet across multiple Routers though.

Furthermore, it determines which nodes are trying to rebroadcast first after they hear one of the ROUTERs rebroadcast. Two ROUTERs in each other's range does not mean every node can hear both.

Not every node, but for the whole area (gray) between two Routers that can talk to each other, only large obstacles will shield Clients from one of them.

For real meshes with multiple Routers that can hear each other, almost everything is between some two Routers. So I'd argue multiple Routers hearing a transmission at the same time and fighting over the same, small contention window is the rule, rather than the exception.

4. No, ROUTER_LATE was designed to be acting as client first, and only when it receives a duplicate, it will move to the late rebroadcast window.
5. No, add_delay is still random:

I see, I missed that it acts like a Client at first and that setTransmitDelay() is applied again after the non-randomized clampToLateRebroadcastWindow()

[GUVWAF]

 following SNR strictly wouldn't result in a worse order than following SNR+randomness IMO

Here I disagree on. Following it strictly may result into that consistently the wrong nodes rebroadcast, rather than having an equal chance (when CW size is the same), or at least a chance to win (when the lower bound doesn’t change). Managed flooding is also used to assign next-hops for direct messages. It needs only one successful delivery for that to work, but retrying the same failed route over and over will not get you further.
Yes, it would be nice if it would be more consistently right, but SNR just isn’t the perfect metric for reaching the most nodes. Besides, we’re using an unreliable medium on a shared spectrum anyway, so any external influences like interference or even collisions caused by our own transmissions (due to e.g. the hidden node problem) will cause inconsistent results.

If you want to make it more deterministic, we’d definitely need things like #8189 to make sure we’re not consistently wrong. Basically you need to calibrate each device based on their receiver sensitivity and transmit power in order to be able to use SNR as good approximation for “reach”.
Furthermore, you’ll need to calibrate for processing time between packet reception and the time you start the rebroadcast delay. This is not only determined by hardware (e.g. a Linux host PC versus nRF52), but also e.g. whether you have the channel key to decrypt the packet, such that more logic is triggered, and which Modules the node has enabled. Modules are handled first, because it might be they change the packet content or trigger other packets, but they might take a long time to process (can be >200ms when it’s saving to flash, for example).

Currently, the low-SNR nodes (< -15 dB) have the narrowest window. That wouldn't get any narrower.

OK, good, but it was in your original graph.

The window for low-SNR Clients could actually be larger then

When taking my initial concerns into account, I’m not totally against fine-tuning this, but you’re now increasing the average delay quite a lot. Nodes close to each other will always have a fixed delay, rather than having at least a chance to transmit early. We’d also need to avoid wasting airtime and make sure the overall latency remains within limits such that packets will not be dropped and people are not retrying too quickly when there’s no ACK/reply yet.

..well, they have to be to transport a packet across multiple Routers though.

We were talking about multiple Routers competing for rebroadcasting. Routers in a chain are not competing, they transmit hop by hop after each other.
However, if it’s really currently the case that meshes have often multiple Routers in each other’s range, I agree it would be better to use a fixed CW size for them.