I've worked on this for a bit and think it's promising.
I tend to call it the "fairness limiter", because it's actually a map of multiple rate limiters and could use a name 😄
Using a token bucket rate limiting algorithm for repeaters to decide whether they should repeat or not.
I'm looking for feedback from maintainers on whether you would welcome this change to be upstreamed or not.
Happy to work on the PRs, but checking on the idea first 😄
Watching my test firmware with a 2D grid
Goals & motivation
The goal is for a repeater to avoid amplifying problematic levels of traffic, with the limited knowledge it has and minimal coordination.
Because larger meshes, like the NL one I'm part of, already regularly experience congestion problems in spite of attempts to politely ask for slower repeater adverts, removing #test bots and using flooding less for testing.
Particularly rate limiting is for when this is ignorant, accidental or maliciously high traffic. Think repeater adverts on too short intervals, excessive #test messages, or a DOS script forging adverts to draw a face on the ocean.
It aims to be objective and neutral in what traffic is "useful". For example Public and #test are treated equal to any other group. But adverts have much lower limits than group texts.
It's intended as complementary to other means of reducing traffic and keeping the mesh healthy. Especially scopes, because scopes is how a conscious sender can limit their floods voluntarily. And gives meshes something to coordinate and improve their experience. Which is a different angle than rate limiting is going for, providing some relief when faced with uncoordinated high traffic.
My approach is also intended to be used without protocol changes. And therefore has limited options to identify the cause of traffic.
And adding more repeaters to the mesh with these limits should improve overall connectivity, rather than make an already congested mesh worse.
Non-goal is for this to solve scaling meshes on it's own. It's one piece of the puzzle.
Nor does it intend to provide configuration to police the mesh (like block #ai because I can't get any RAM).
Implementation details
Several uint8_t arrays are allocated where each array represents a traffic category. And each index into the array represents one bucket.
Every category and bucket has a max capacity and a refill rate.
Whenever a repeater would normally repeat a packet (so after validating, checking max hops, checking if we've already repeated, etc.) it attempts to "consume" 1 token from the bucket this packet belongs to.
If there are 0 tokens, the packet is not repeated. Otherwise we reduce the remaining tokens by 1.
Category and bucket index
Packet types REQ | RESPONSE | TXT_MSG | PATH | ANON_REQ are considered "Normal priority" and bucket the sender by:
payload[1] & SENDER_NORMAL_MASK (n-bits of it's pubkey first byte).
Packet type ADVERT is considered "Low priority" and bucket the sender by: payload[0] & SENDER_LOW_MASK (n-bits of it's pubkey first byte).
Packet types GRP_TXT | GRP_DATA are considered "Group" and bucket the sender by: payload[0] & GROUP_MASK (n-bits of it's channel hash byte).
Packet types ACK | TRACE | MULTIPART | CONTROL | RAW_CUSTOM are currently not limited as I don't know a reasonable way to identify the sender.
The exact mask for each category can be tuned, and gives the following tradeoff. More bits means less overlap on who affects who when rate limiting kicks in. But increases RAM usage and provides lower protection against malicious scenarios when the sender is forging packets.
The full 8 bits requires a 256 byte array, 7-bit mask requires a 128 byte array, 6-bits 64 byte array, etc.
How many mesh participants overlap for each index depends on the mesh size.
Bucket refill interval and capacity
This is implemented in the main mesh loop, similar to other intervals. next_refill_time, futureMillis(interval), etc.
That pattern is straightforward but important is: this interval is a crucial tuning parameter and should be configurable for each category separately.
Every interval, for each index in the array, the token count is increased by 1 unless it's already at the max.
A way to reason about the interval and capacity for tuning is:
- The refill interval determines the sustained traffic rate we allow.
- The capacity determines how much burst traffic we allow.
The sustained traffic we allow should be data driven, like long term averages collected by the analyzer for particular regions from multiple observers, and whether that level of traffic resulted in congestion or not.
While the burst traffic is more "how the mesh feels" because it is a best effort to accommodate irregular but legitimate traffic. Reducing disruption compared to an algorithm that doesn't use token buckets. Especially when multiple nodes map to the same array index and can consume "each others'" tokens.
Configuration and recommendation
Each of these parameters heavily influence the other. And it's not easy choose a good value by intuition or just trying something.
Hence I think these values should be configured together, and we provide official presets.
By that I mean something like set fairness.groups 6,4,15 as 6-bit mask, 4 minute interval, 15 capacity.
The main point being, it's configured as one command for those 3 values at once.
Currently I recommend this preset as default (once you're comfortable with enabling this by default at all):
| Category |
Index |
Refill interval |
Capacity |
| Groups |
6-bit mask |
4 minutes |
15 tokens |
| Normal |
7-bit mask |
4 minutes |
15 tokens |
| Low |
7-bit mask |
70 minutes |
6 tokens |
From my testing so far, I believe this is a lenient preset that only drops a percentage of traffic when the mesh is actually congested. And I believe can be safely used for any mesh size.
For meshes with more acute congestion problems you probably want a stricter limit. A more relaxed limit I think will be ineffective for it's goals, and it would be better to save your resources / battery and disable it entirely.
I've worked on this for a bit and think it's promising.
I tend to call it the "fairness limiter", because it's actually a map of multiple rate limiters and could use a name 😄
Using a token bucket rate limiting algorithm for repeaters to decide whether they should repeat or not.
I'm looking for feedback from maintainers on whether you would welcome this change to be upstreamed or not.
Happy to work on the PRs, but checking on the idea first 😄
Watching my test firmware with a 2D grid
Goals & motivation
The goal is for a repeater to avoid amplifying problematic levels of traffic, with the limited knowledge it has and minimal coordination.
Because larger meshes, like the NL one I'm part of, already regularly experience congestion problems in spite of attempts to politely ask for slower repeater adverts, removing #test bots and using flooding less for testing.
Particularly rate limiting is for when this is ignorant, accidental or maliciously high traffic. Think repeater adverts on too short intervals, excessive #test messages, or a DOS script forging adverts to draw a face on the ocean.
It aims to be objective and neutral in what traffic is "useful". For example Public and #test are treated equal to any other group. But adverts have much lower limits than group texts.
It's intended as complementary to other means of reducing traffic and keeping the mesh healthy. Especially scopes, because scopes is how a conscious sender can limit their floods voluntarily. And gives meshes something to coordinate and improve their experience. Which is a different angle than rate limiting is going for, providing some relief when faced with uncoordinated high traffic.
My approach is also intended to be used without protocol changes. And therefore has limited options to identify the cause of traffic.
And adding more repeaters to the mesh with these limits should improve overall connectivity, rather than make an already congested mesh worse.
Non-goal is for this to solve scaling meshes on it's own. It's one piece of the puzzle.
Nor does it intend to provide configuration to police the mesh (like block #ai because I can't get any RAM).
Implementation details
Several
uint8_tarrays are allocated where each array represents a traffic category. And each index into the array represents one bucket.Every category and bucket has a max capacity and a refill rate.
Whenever a repeater would normally repeat a packet (so after validating, checking max hops, checking if we've already repeated, etc.) it attempts to "consume" 1 token from the bucket this packet belongs to.
If there are 0 tokens, the packet is not repeated. Otherwise we reduce the remaining tokens by 1.
Category and bucket index
Packet types
REQ|RESPONSE|TXT_MSG|PATH|ANON_REQare considered "Normal priority" and bucket the sender by:payload[1] & SENDER_NORMAL_MASK(n-bits of it's pubkey first byte).Packet type
ADVERTis considered "Low priority" and bucket the sender by:payload[0] & SENDER_LOW_MASK(n-bits of it's pubkey first byte).Packet types
GRP_TXT|GRP_DATAare considered "Group" and bucket the sender by:payload[0] & GROUP_MASK(n-bits of it's channel hash byte).Packet types
ACK|TRACE|MULTIPART|CONTROL|RAW_CUSTOMare currently not limited as I don't know a reasonable way to identify the sender.The exact mask for each category can be tuned, and gives the following tradeoff. More bits means less overlap on who affects who when rate limiting kicks in. But increases RAM usage and provides lower protection against malicious scenarios when the sender is forging packets.
The full 8 bits requires a 256 byte array, 7-bit mask requires a 128 byte array, 6-bits 64 byte array, etc.
How many mesh participants overlap for each index depends on the mesh size.
Bucket refill interval and capacity
This is implemented in the main mesh loop, similar to other intervals.
next_refill_time,futureMillis(interval), etc.That pattern is straightforward but important is: this interval is a crucial tuning parameter and should be configurable for each category separately.
Every interval, for each index in the array, the token count is increased by 1 unless it's already at the max.
A way to reason about the interval and capacity for tuning is:
The sustained traffic we allow should be data driven, like long term averages collected by the analyzer for particular regions from multiple observers, and whether that level of traffic resulted in congestion or not.
While the burst traffic is more "how the mesh feels" because it is a best effort to accommodate irregular but legitimate traffic. Reducing disruption compared to an algorithm that doesn't use token buckets. Especially when multiple nodes map to the same array index and can consume "each others'" tokens.
Configuration and recommendation
Each of these parameters heavily influence the other. And it's not easy choose a good value by intuition or just trying something.
Hence I think these values should be configured together, and we provide official presets.
By that I mean something like
set fairness.groups 6,4,15as 6-bit mask, 4 minute interval, 15 capacity.The main point being, it's configured as one command for those 3 values at once.
Currently I recommend this preset as default (once you're comfortable with enabling this by default at all):
From my testing so far, I believe this is a lenient preset that only drops a percentage of traffic when the mesh is actually congested. And I believe can be safely used for any mesh size.
For meshes with more acute congestion problems you probably want a stricter limit. A more relaxed limit I think will be ineffective for it's goals, and it would be better to save your resources / battery and disable it entirely.