The case for 1.5 byte repeater IDs - get 48 hops while still reducing waste of airtime

[dkriesel]

This was originally posted as short subcomment in @MrAlders0n 's discussion #1613 ("The Case for Expanding Repeater IDs beyond 1 Byte"). I am however doing the full analysis here because I found it worthwile the Idea needs to be discussed (even if turned down) quickly.

Finding/Rationale: We discussed multibyte IDs for the reason of saving air time - but we forgot to optimize.

The whole trigger of the multibyte ID discussion was to ensure that not too many repeaters in an area are activated unneccessarily due to duplicate IDs, thereby consuming the most valuable resource that we have: air time. We found a solution for that, and we paid for it, in the currency of hops. I believe we forgot to optimize, and therefore we paid too much. What did we forget?

For some reason we did not take into account the geospatial density of duplicate IDs, so duplicate IDs per area, despite its major importance as it directly influences wasted air time. Many duplicate IDs concentrated in a small area get us lots of wasted airtime. In this post, I redo the analysis of the original discussion, but with this aspect taken into account.

Two assumptions that are fair to take:

• The vast majority of repeaters have a range of 50km or less. So if double IDs within a circle of 50km radius / 100km diameter / 7854km² area are rare, we'll be well on our way with room to spare (most repeaters don't come even close to that range).
• A new repeater politely chooses an ID that is not taken within a radius of 50km (can easily be achieved by online meshmaps and/or readjusting on neighbourhood).

Analysis: 1-byte IDs -> too few IDs. 2-byte IDs: Too few hops!

We follow and extend @liamcottle's calculation in the original thread.

• 1-byte: ~64 max hops with ~256 unique ids.
  • 7854km²/256 = 30km² per unique id if you want to use all IDs. That means, every ID on average gets the area of a circle with diameter 6km. You can cover our maximum repeater range area with 256 IDs by placing repeaters not closer to each other than 6km. This is very coarse. Verdict: Too few IDs per Area, so too many duplicates, too much wasted air time, which sparked the original discussion in the first place.
• 2-byte: 32 max hops with ~65,535 unique ids.
  • One id for every 7854km²/65535 = 0.12km² area, i.e., circles with a diameter of 390 meters! If you want to do a full closest packing of repeaters within our maximum repeater range, you can place repeaters as close as 390 meters to each other, without getting an ID twice! Verdict: Nice! A solution to the problem for sure.

But is it a strategically efficient solution, that we probably don't have to touch again for a loooong time? And what strategy would even be appropriate given the amazing level of MeshCore success?

I live in central europe, we recently managed to interconnect Germany, Netherlands, Belgium and the UK. I do see messages with >40 hops regularly in the wild. Soon it will be more. Any valid strategy must take meshes of these sizes into account as they already exist. We just paid a whopping 32 hops for wasting less air time! I don't like having to choose between being limited to 32 hops, OR wasting lots of airtime.

Solution / Proposal: Use 1.5byte IDs. You get 48 Hops for the same air-time waste as 2-byte IDs.

• 1.5-byte: 48 (!) Hops, with 4096 unique IDs. Edit, as per addendum: This could be achieved by dropping the 4-byte variant.
  • that would be ~1.9 square kilometers per identifier, circles with a diameter of 1.5km, still very dense (most areas won't need that density anytime soon, and local densities can be even much higher as we assumed the 50km range very generously).

We get back half the hops that we paid for the 2-byte solution, while not wasting additional air time! Way more bang for the buck. I do realize 1.5-byte IDs introduce a bit of nibble handling to ID management which sounds tedious at first glance, but tbh, the code is operating even on bit-level at other places, so it won't be the ugliest thing that ever needed to be done.

(Optional feature for later: Automatic shortening of IDs in Messages when path lenght exceeds boundary, instead of dropping them. Not sure about this however, and it is another topic.)

Too late?

I fully realize that it's probably too late for this thought. Bummer. :-(.

But 1.5 Bytes are so efficient I even would have proposed them as default, if the setting was existent. This is why it felt wrong for me to not at least raise the topic. When, if not now? I don't want to propose something of this magnitude in a year from now or two. Maybe, as this major leap is done now, it is not too late to change the change. Change adaption is right now 0%. But this decision is not mine to make.

What's however for sure is, meshes spanning whole continents are not a matter of the future any more. (Congrats, Liam to the size of what you created! I wonder how you feel with this... :-) ). That means we should take them into account strategically. A big protocol change is the right point in time to do that.

[dkriesel]

Addendum:

While I was unsure on how complex the implementation implications would be, I just got a nice Idea from a 3rd party without a Github account. Reproducing here with permission (Kudos to Matz):

The 1.5 byte path segments could replace the mode with 4 byte path segments, resulting in 1, 1.5, 2 and 3 byte path variants.

[JanMrlth]

That sound super reasonable! Please push