OpenThread behaviour with uncommon node topology

[k.bur...@biotcloud.com]

Hello,

In one of our projects we do plan to use OpenThread network with some special topology - all devices will be in a straight line, trying to get as long line as possible. I understand, that Thread is being primarily focused on home networks, and the line topology isn't the main use case. Still, it should work.

We did some tests, drawn some graphs and strangely we've found few surprising behaviours, which I suspect are result of some errors within the OpenThread implementation. I'm writing this post to cross-check it, maybe our understanding is wrong somewhere.

So, lets start with some basics. What are the theoretical limits for Thread network, when devices are arranged in a line? I'll list all relevant (in my opinion) parameters and their values, as I will refer to them later on:

- Maximum routers: 32

- Max route cost: 16 (awfully low!)

- Router Upgrade Threshold: 16

- Router Downgrade Threshold: 23

In our tests environment we used standard linux PC with a posix implementation, just running a bunch of `ot-cli-ftd` simultaneously (sadly, the limit for such simulations seems to be around 34 devices). We checked a state (child/router/leader) of each device every second and put the matrix on a graph: https://imgur.com/a/5YMXt - I will describe the graph in a moment. Each device was configured to see only 1 neighbour in each side. For simplifications on our end, we actually closed the end of the line together, effectively forming a circle topology (i.e. first node can only communicate with second and last). 

Each node used following scenario:

===

>channel 11

>panid 0x1234

>ifconfig up

>thread start

wait 3 seconds

>macfilter addr whitelist

>macfilter addr clear

>macfilter rss clear

wait 1 second

>routerdowngradethreshold 200

>routerupgradethreshold 16

>macfilter addr add <ext addr of next node in line>

>macfilter addr add <ext addr of prev node in line> 

>macfilter rss add <ext addr of next node in line> -20

>macfilter rss add <ext addr of prev node in line> -20

wait few hours

===

Since each node is seeing only 2 neighbours, and we need to have continuous partitions, each node should become router, we should have 1 leader, and maybe 1 child. (If it would be a proper line, not a circle, we could have 1 child at each end).

In our tests we started with default parameters, but obviously the max route cost is the most limiting factor for us. So, we also tried to increase it to `135` at lines https://github.com/openthread/openthread/blob/992263043b6e33c74bb576200cd7f006b23bc29a/src/core/thread/mle_constants.hpp#L95 and https://github.com/openthread/openthread/blob/992263043b6e33c74bb576200cd7f006b23bc29a/src/core/thread/mle_constants.hpp#L129. Quick analysis of the OpenThread source code suggests that these changes are safe and enough. 

In this post I will describe few problems, we have seen identical problems on default settings, just on a smaller scale.

Now, the graph (https://imgur.com/a/5YMXt - as linked above). Color actually represents role:

0 - black - disabled

1 - violet - detached

2 - red - child

3 - orange - router

4 - yellow - leader

X axis are seconds, Y axis is device number. Devices are in order, so device at Y=N sees only devices N-1 and N+1 (modulo N) devices as its neighbours.

If you look at the graph, you can see that:

- there is more than 1 leader, always - i.e. we have few partitions, which shouldn't be the case

- routers spontaneously downgrade to childs (it shouldn't happen as we have downgrade threshold at 200, and even if we wouldn't, often there is less than 23 routers in a partition when this problem happens)

- you can see partitions being merged by a red diagonal line (e.g. the one starting at X=~32000 Y=11 and going down/right), such wave usually resets other nodes to proper state, e.g. the device at Y=2 was a long standing leader, which got swept by such wave.

- sometimes such propagation stops with no apparent reason - and it gets stuck there. For example the up/right wave starting from X=~32000 Y=11 stops at Y=19, and the node is staying in child mode for >2000 seconds, not even trying to become router, let alone allowing Y=20 device to join its partition

Few conclusions:

- it seems that between each 2 leaders there is at least 1 'stuck' child, which is blocking partition merging

- it seems that the further router is from leader, the more likely it will turn into child without apparent reason (typically 2-3 devices around leader are never having that problem). I do suspect, that it is actually leader timing out particular router, and ordering it to reconfigure.

- top routers on the chart (Y=31, 32) are apparently belonging to leader Y=2, as our line wraps around.

As our POSIX simulator is using UDP for simulating radio transmission, probably a bit of this behavior is related to UDP stuff, and real devices with radios will behave differently (better or worse..).

So, questions:

- why some nodes are stuck on child state?

- why some childs do stop partition merging?

- why routers spontaneously become childs, even if downgrade threshold is not reached?

Any further insights?

[Jonathan Hui]

Thanks for sharing these test results and your observations!  I'll dig into this and get back to you with what I find.

--

Jonathan Hui

--
You received this message because you are subscribed to the Google Groups "openthread-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to openthread-users+unsubscribe@googlegroups.com.
To post to this group, send email to openthread-users@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/openthread-users/314e119e-60bb-4364-bad4-59533b98a366%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jonathan Hui]

Thanks again for sharing these observations.  I have reproduced your observations, found a handful of issues, and submitted a number of PRs that address them.

However, even with the issues fixed, your scenario demonstrates that Thread, as specified, is not designed for deep networks (i.e. many hops) or long-linear networks (i.e. routers having only 1 neighbor in each direction).

1) The primary reason why routers spontaneously transition to other roles is because they are timing out on updates from the leader.  Thread 1.1.1 Section 5.16.1 specifies that routers maintain connectivity with the leader by receiving periodic updates.  Thread specifies a default timeout of 120 seconds.  Updates from the leader are propagated via MLE Advertisement messages that are sent every 32 seconds with random jitter in steady state.  The random jitter causes the propagation to sometimes occur very quickly (<1 second per hop) or very slowly (>30 seconds per hop).  In deep networks, this effect can easily tigger the 120 second timeout.

2) The MLE protocol only allocates 4 bits for communicating route cost (Thread 1.1.1 Section 5.20.1).  As a result, you cannot really grow the maximum depth of the Thread network without changing the MLE Route64 TLV encoding.

Despite the caveats above, you should try your tests again on the latest master branch.  If you want to address point (1) above, you can also modify kAdvertiseIntervalMax to something like 5 seconds to ensure that leader information propagates faster than 5 seconds per hop.

Hope that helps.

--

Jonathan Hui

On Thu, Jan 11, 2018 at 11:39 PM, <k.bur...@biotcloud.com> wrote:

Thanks. Here are some more results: https://imgur.com/a/lbTSu - this time, each node sees 2 neighbours each side (so, in total 4 neighbours for each node). Max route cost: 16. Upgrade threshold: 16. The graph is much cleaner, and in most moments looks as expected. However, the spurious  router->child transitions are there, just on a much smaller rate.

If you would have some specific case to test, let me know and we generally can easily generate graph from it.

--

Jonathan Hui

To unsubscribe from this group and stop receiving emails from it, send an email to openthread-use...@googlegroups.com.
To post to this group, send email to openthre...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/openthread-users/314e119e-60bb-4364-bad4-59533b98a366%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "openthread-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to openthread-users+unsubscribe@googlegroups.com.
To post to this group, send email to openthread-users@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/openthread-users/381e1755-f017-4f2f-95f1-955fd265fb22%40googlegroups.com.

[ka...@tokateam.com]

Thanks for the insight. Indeed, I was watching the Github PRs and we were re-testing after relevant PRs were merged (1 or 2 are still open, right?). The results are much, much better (e.g. like this: https://imgur.com/a/QH1T0), almost perfect now. So, at least the partition merging + spontaneous role changes are not that big deal now. We will, however, try with the kAdvertiseIntervalMax tuning as you suggested, I wasn't familiar with that part of spec, and it indeed could be promising change.

As the deep network topology is quite important for my use case, I'm pretty worried about the 4 bits limitation. I was hoping that increasing the default max cost from 16 to something higher will be enough, but our tests indeed show that it isn't helping. I hand't time to look into it to understand why, but your explanation makes it pretty clear. To make it worse, any Route64 TLV change will make it non-standard, therefore makes no chance to get merged to master, I guess. Not to mention that change from 4 bits to 8 will potentially make TLV longer by 16 bytes. Do you see any way to lift this limitation somehow? 

--

Jonathan Hui

[Jonathan Hui]

Glad to see that you are seeing improved behavior.  All the PRs specific to this use case so far are merged.

Regarding the 4-bit route cost limitation, I do not have a good answer to address the challenges you already identified.  Changing the encoding will not allow interoperability with standard Thread 1.1 FTDs - if you are willing to deploy a proprietary network, this may be fine for you.  We also have to evaluate whether the increase in message size will bump the MLE Advertisement beyond the 6LoWPAN fragmentation threshold and, if so, whether that has significant impact on reliability of communicating MLE Advertisements.

Another avenue to consider is advocating your use case with the Thread Group so that it can be addressed in a future revision of the specification.

--

Jonathan Hui

To unsubscribe from this group and stop receiving emails from it, send an email to openthread-users+unsubscribe@googlegroups.com.
To post to this group, send email to openthread-users@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/openthread-users/6d4edfab-e825-44f3-b284-4e4575f7704d%40googlegroups.com.

[k.bur...@biotcloud.com]

Jonathan,

Sorry for the response delay. Anyway, I would like to push the case to solve the problem somehow, at least as non-standard extension. If it will get 'blessed' by Thread Group some time in future, even better.

So, the problem is that we're using Thread outside household environment - doing it for Smart City projects, especially for street lighting scenarios. Thread works well if all devices are close to each other (relatively), but if you think about street lighting, the lamp posts are usually spread across long line. Even if there is a good connectivity, each lamp will see 3-5 neighbours each side.

Since each mesh will require border router device, it is desirable to extend the mesh as much as possible. Theoretical limits in this 'linear topology' (as I call it internally) are that if each lamp will see up to 5 neighbours each side, then 32 routers can be spread having a router every 5 posts. It will total to roughly about 160 devices. Of course self-healing feature of the mesh will be under big stress - if a router device will go out of order mesh reconfiguration will take a lot of time, and in the edge cases might even not succeed to fully merge both partitions.

Anyway, with current Thread specification, if we will start spreading devices across a line (which will basically guarantee routing cost of each hop to be 4), we can have 3-4 routers at most. Each will have up to 4-5 children, so maybe 20-25 devices per mesh, not more. Even if routers will be elected more densely (and having lower link costs), the max route cost of 16 is awfully limiting.

So, what can we do to make Thread more applicable in this environment?

My core concept here is to bump max route cost to about 127 (7 bits instead of 4). That will of course be coupled with a number of other problems (much slower communication, increased possibility of timeouts, etc.) - though I hope to clear them out more easily once I hit them.

Obviously that will be non-standard. There is a slight chance, that we can do it by extension (so standard implementation will just ignore extra data), though most likely a modification of existing structures will be necessary.

Another problem is that there is 127 bytes per frame limit (and I don't want to go for splitting the MAC Advertisement into 2 messages if it is possible to avoid it). I'm trying to understand how much bytes we can add, though with my limited understanding of mac/mle layers it is extremely confusing. So, here is a Wireshark screenshot from MLE Advertisement message: https://imgur.com/a/GbV9B It was done on posix implementation, with 2 routers in the network. There is 103 bytes on the wire, UDP says there is 79 bytes of payload. 6lowpan says length of 51 bytes. How much can we add to not overflow single packet?

Of course adding 30 more routers will use up 30 bytes. The absolute minimum for extending the route cost from 4 to 7 bits is the extra 3*32 bits = 12 bytes. 14 bytes, if we add extra TLV for it. +4 bytes if we want to keep byte boundaries to not play with bit shifting too much. Do you think this is feasible?

With 32 routers there is max of 31 hops, with 4 link cost each, giving us max route cost of 124, which nicely fits in the 7 bits, the worst case.

If we ignore standard for a moment, some kind of MLE Route64Extended TLV could be introduced which just have more bits per route cost, and that's it. I will try to hack such solution using the current OpenThread, maybe some PR with a config flag for it will get accepted as well ;) So users could enable it at their own discretion.

If, however, there is still extra 16 bytes free after all of the above, we can try to get this change compatible with the existing implementations as much as possible. That will cost the extra 16 bytes, but might be worth it, if feasible. The idea is to keep original MLE Route64 TLV as is, but add MLE Route64Extended constructed such way, that it will contain full 7 bits per router. The full route cost would be a sum of fields from both TLVs. If route cost is <16, extended field would be zero (or even missing), for route costs >= 16, the standard TLV would have 0 (so all standard implementations will know that the route is off limits), but have proper value in the extended TLV. So, standard implementations will reach as many devices as they can today, but augmented implementations could reach all devices.

What do you think?

Jonathan Hui

[k.bur...@biotcloud.com]

So, I did some testing. I used posix implementation from current OpenThread master, running just 1 ot-cli-ftd being leader. I modified the MLE Advertisement sending code to include extra bytes. In this particular setup (only 1 leader in the mesh) I was able to inject 58 more bytes into the message, 59th one caused 6lowpan fragmentation to occur.

In case when all 32 routers would be running, there would be 27 bytes free.

It seems, that if we want to achieve backward compatibility, we would need to add extra TLV (MLE Route64 Extended as I call it), containing 31 * 7 bits of routing cost data. That would equal to 29 bytes and 1 bit. Even if we try to save on TLV header (2 bytes) and squeeze the extra data at the end of the existing MLE Route64 TLV (being arguably compatible with existing implementations), we are still short of 1 bit...

There are few assumptions, which I'm not 100% sure of. For example, I'm afraid that occasionally more than 32 routers might be active at a single moment (old one being removed, new one just being elected) - there are 64 router ids for a reason. Then, I'm not sure if max route cost includes just router-router traffic, or child-router-router-child (i.e. maximum number of hops included in route cost is 31 or 33, with the latter meaning that 7 bits wouldn't be enough for general case). And so on.

Having said all of the above, I think that my proposal boils down to:

Introduce new MLE TLV (MLE Route64 Extended, type 27), containing sequence of bits in groups of 7, zero-padded to full bytes. This TLV should be sent along the MLE Route64 in MLE Advertisements. For each 'Link Quality and Route Data' byte from MLE Route64 TLV the extended TLV could contain an extended route cost, with following remarks:

- if link quality is set to 0 in MLE Route64 TLV (i.e. given byte corresponds to sender's Router ID), extended cost 7-bit field should be skipped (not included)

- if cost advertised in MLE Route64 TLV is non-zero, extended cost field should be skipped (this alone should save us 7-28 bits necessary to avoid 6lowpan fragmentation)

- if all 7 bits of the extended cost field are set to zero, it means no reachability state (identical as the MLE Route64 TLV handles this)

Such approach would give us full compatibility with existing implementations, allowing new ones to benefit from longer routes.

I think that in some edge cases (more than 32 routers, or a singleton router who lost all connectivity to remaining 31 routers and have all costs set to max, etc.) there will be a 6lowpan fragmentation happening. But most (all?) such cases will be temporary, and happening only at meshes with 31+ routers and poor links (if there are less than 31 routers, or link qualities are good, we will save at least 17 bits from the total MLE Advertisement length, avoiding the fragmentation). Existing implementation will cause mesh to fall apart into few partitions in such cases. In my opinion having fragmented 6lowpan MLE Advertisement messages is still better than mesh partitioning.

Sadly, it will make the future extensions slightly harder, as MLE Advertisement message will be extended to its limits, leaving very little (or no at all) room for any new TLVs to be defined. 

Does that sound OK to you? I will try to create such implementation, do you think that PR for this could be accepted into OpenThread? What about chances for including it in the upcoming Thread specification?