RFC: Geohash Routing for MeshCore

[ttadegraaff]

RFC: Geohash Path Discovery Optimization for MeshCore

1. Summary

This RFC proposes an optional extension to MeshCore that allows repeaters to learn and reuse successful path information to geographic areas using geohash-defined regions.

The goal is to reduce flooding for path discovery while maintaining multiple alternative routes for geographic areas.

The idea is that when one path to a specific area is learned, path discovery messages from other companions directed to that area can use this information instead of triggering a flood discovery. When a message reaches the destination area, hop limited flooding is used to learn the last bit of the path. This has the potential to reduce the discovery load on connections between distinct geographic areas.

How it works

Three new message types are introduced:

Message type
1. Geohash discovery message	Uses geohash routing for path discovery
2. Geohash discovery return path	Uses geohash routing to return path information
3. Geohash route advert	Adverts geohash destination information to repeaters along found path

When a companion want to send a text message to a contact that has a geohash but no known path, it first sends a geohash discovery message. Hop limited local flooding is used to send the message. When a repeater receives such a message and has one or more designated neighbour id's for the geohash in it's routing table, the local scope is removed and only these designated repeaters will forward the message. The message now travels via one or more known paths through the mesh using geohash routing information from earlier discoveries until it reaches the destination area. At the destination area the scope local is set, and hop limited local flooding is used to reach the end destination.

For example a geohash discovery message that goes from companion A to companion F in geohash area u15aa. Repeater B, C and D have geohash information for a15aa in their routing table and repeater E is located in the geohash area of the endpoint.

    (A) (u12ee)         -
   / | \                | Local flood
  /  |  \               |
 J   K   B              -
         |              |
         C              | Geohash routing
         |              |
         D              |
         |              |
         E (u15aa)      -
       / | \            | Local flood
      /  |  \           |
     M   L  (F) (u15aa)  -

The destination companion now responds with a geohash discovery returned path message. This response contains the successful path and is returned in the exact same way using geohash routing as the geohash path discovery message.

For example geohash path discovery response from companion F to companion A.

 J   B  (A) (u12ee)     -
  \  |  /               | Local flood
   \ | /                |
     K (u12ee)          -
     |                  |
     Q                  | Geohash routing
     |                  |
     P                  |
     |                  |
 M   O   L              -
  \  |  /               | Local flood
   \ | /                |
    (F)                 -

When the geohash path discovery response arrives at the original sender, a known path is added to the contact information of the destination companion. Then the text message is send using the known path as meshcore would normally.

When no geohash path discovery arrives at the original sender, a second geohash discovery is sent with a bigger local flooding hop limit. If that also fails a normal message is sent, triggering normal flood discovery without geohash.

When a successful path is discovered using geohash routing then a normal text message is sent. When that message is acknowledged a successful path has been learned, and the user can continue sending messages using this path.

When the route advert interval time has passed, and after sending a text message to the destination the user receives a acknowledge received message, then a geohash route advert is sent to the destination using the learned path. This advert contains the geohash of the destination and the return path. While this advert travels along the path the repeaters update their geohash routing table using the path and the geohash.

For example a geohash route advert containing the geohash of F and the now confirmed return path for F to A traveling from A to F.

(A)
 |
 B -> learns or updates u15aa - C
 |
 C -> learns or updates u15aa - D
 |
 D -> learns or updates u15aa - E
 |
 E
 |
(F) -> learns path F -> O -> P -> Q -> K -> A

When the advert reaches the destination, the destination adds the now confirmed return path to the sender contact.

Discovery order

1. Geohash discovery with default local flood hop limit
2. Geohash discovery with increased local flood hop limit (increased_hop_limit is flagged)
3. Normal flood discovery

---

2. Current MeshCore compared with this proposal

Consider two people who have never communicated before.

With current MeshCore, a message path needs to be discovered through flooding. If a returned path message is received, the sender learned a succesfull path to the destination. A message to another person in the same area, or to the same person by a different sender, requires another flood discovery.

With this proposal, repeaters store designated neighbour information based on the destination's geohash.

For example, a first successful message from Person A to Person E in geohash area u15aa triggers a geohash route advert from Person A to person E:

Geohash route advert with known path:

Person A
   ↓
Repeater B
   ↓
Repeater C
   ↓
Repeater D
   ↓
Person E geohash u15aa

This cuases repeater B to learn valid neighbour C for geohash u15aa:

u15aa → C

And repeater C to learn:

u15aa → D

When repeater B receives a geohash discovery message for another companion in geohash u15aa it will flow via C and D instead of flooding.

When repeater C receives a geohash discovery message from another repeater then B, it also flows via known route D.

---

3. Geohash usage

A geohash defines a square area where the size depends on the number of geohash characters.

Geohash size	Geohash	Area size
5	515aa	5x5 km
4	515a	20x20 km
3	515	120x120 km

Companions and repeaters only set a 5 character geohash.

---

4. Geohash Routing Table

Repeaters have a geohash routing table that stores geohash routing information.

When a geohash route advert passes through the mesh network, the repeaters being passed store or update information of the form:

Geohash	Designated neighbour	Last confirmed time	Hotness
u15aa	A	496812	20
u15aa	B	496814	5
b55ea	A	496816	12

Last confirmed time: epoch time in hours

Hotness: usage count with decay

Mechanism:

• Every fixed route_advert_interval hours a companion sends a geohash route advert after a successful text message to a companion containing a destination geohash value and the messages_since_last_advert count.
• When a geohash route advert passes that matches a exiting route, the last_confirmed_time is updated and the hotness is increased with the number of messages that were send since the last advert.
• A new entry starts with a initial hotness score.
• Every hotness_decay_interval hours the hotness score is multiplied by the hotness_decay_factor.

---

5. Limited Memory Usage

The routing table is stored in memory. For this reason the size of the routing table is restricted to the max_route_table_size.

Mechanism:

1. Every hour, routing table entries are removed if their age calculated from the last_confirmed_time exceeds the route_expiration_time.
2. When a new route is added for a geohash, and max_routes_per_geohash routes already exist, the route with the lowest hotness is replaced.
3. If adding a new entry to the routing table would make the table size exceed the max_route_table_size, remove the existing entry with lowest hotness first.

This way geohash routes that are used a lot survive while little used routes perish.

Using Dutch land-use data:

• The Netherlands is covered by roughly 1,400 5-character geohashes.
• Let's assume 20% is densely populated.

That gives about 280 densely populated geohashes.

Asuming a average geohash route has 1.5 designated repeaters then the memory usage for an average geohash is 1.5 x 11 = 16.5 bytes. For the Netherlands this would mean that routes for all densely populated areas would consume about 16.5 x 280 = 4.6Kb of memory.

---

6. Geohash Route Recovery

If a geohash route is broken in the middle, hop limited local flooding is triggered where the route ends. If within this local scope a geohash repeater with a geohash route for the destination is found, this path is picked up from there and as such a new path is formed. The broken geohash path will be automatically removed after some time because of route decay and max age.

If this fails a second attempt of geohash route discovery is triggered with increased_hop_limit flagged resulting in a higher hop limit increasing recovery chance.

If that too fails, a normal flood text message discovery is triggered to find a new route.

Consider a message from A to G at geohash u15aa.

     A
   / | \
  J  K  B (has route for u15aa)
        |
        C --- D ---- E ---- F (u15aa)
                            |
                          / | \
                         F  P  G (u15aa)

The route breaks at C. The repeater at C has no designated neighbours for u15aa and triggers local discovery. Repeater H receives the geohash discovery message and has a route to I for u15aa.

     A
   / | \
  J  K  B
        |
        C --- X  (broken geohash route)
        |
      / | \
     Y  Z  H (has route for u15aa)
           |
           |                 
           |            P   Q   G (u15aa)
           |             \  |  /
           |              \ | /
           I ------- J ---- K (u15aa)

Now a new geohash route from A to G will be added in the mesh.

---

7. Hierarchical Matching

There will not always be a exact match for the geohash in the table.

For example

A repeater knows:

u15aa → A
u15af → B
u15ga → C

A message with geohash u15a1 is will not find a exact geohash match.

But there is a destination area that is really close to the destination area: u15aa. If the message is still far away from the endpoint, then using the path from u15aa would a very good guess to get closer.

Both u15a1 and u15aa are subareas of u15a.

To make it possible to use routing information from a geohash area near the destination area we allow the lookup of a partial geohash match of 4 or even 3 characters in the routing table when there is a minimal distance between repeater and destination geohash.

This way a discovery can use coarse geohash route information from a destination that is close to the message destination if no exact geohash route match is found.

The two coarse routing distances for geohash size 3 and 4 are stored in protocol constants.

Parameter	Geohash area size	Value	Description
COARSE_ROUTING_DISTANCE_GEOHASH_LENGTH_4	20x20 km	100 km	Minimal coarse routing distance for geohash size 4
COARSE_ROUTING_DISTANCE_GEOHASH_LENGTH_3	120x120 km	600 km	Minimal coarse routing distance for geohash size 3

Destination u15a1 is not found in the table. If this destination is more then 100 km away from the repeater, then the repeater will lookup u15a. This will make it forward to A and B.

Destination u15b1 is not found in the table. if the destination is more then 100 km away, then the repeater will lookup u15b. No result found. If the destination is more then 600km away then it will look for u15 and find A, B and C to forward to.

---

8. Companions Without Geohashes

Geohash advertisement is optional.

A companion without a geohash remains reachable through the existing MeshCore routing mechanisms.

Geohash routing is therefore an optimization rather than a requirement for communication.

---

9. Privacy

Setting geohash is optional for a companion and router.

The geohash size is 5 characters. This represents an area of about 5x5 km which in most cases is not specific enough to find the location.

---

10. Backward Compatibility

Nodes that do not support geohash routing continue to use existing discovery through flooding.

Geohash-aware fixed location repeaters provide an additional routing mechanism and can coexist with existing MeshCore nodes.

---

11. Implementation

Messages

Three new geohash messages are introduced:

• Geohash discovery message
• Geohash discovery return path
• Geohash route advert

Two new control types are introduced.

• CONTROL_TYPE_GEOHASH_DISCOVERY
• CONTROL_TYPE_GEOHASH_ADVERT

Geohash discovery message

ROUTE_TYPE_FLOOD
PAYLOAD_TYPE_CONTROL
CONTROL_TYPE_GEOHASH_DISCOVERY (new)

Payload:
  tag
  flags (increased_hop_limit, ...)
  destination_hash
  destination_geohash
  designated_repeaters
  hop_limit
  source_geohash (optional)

Payload fields:

Field	Description
tag	Matches a geohash discovery message with its corresponding geohash returned path.
flags	When increased_hop_limit flag is set, the local flooding starts with higher hop limit.
destination_hash	The destination companion ID.
destination_geohash	The destination companion geohash.
designated_repeaters	The designated repeaters that should forward the message.
hop_limit	Initialized with the local flooding hop limit. When > 0 then local flood discovery
source_geohash (optional)	The geohash area where the sender is located.

Geohash discovery returned path

ROUTE_TYPE_FLOOD
PAYLOAD_TYPE_PATH

containing:

path=[]

extra_type=PAYLOAD_TYPE_CONTROL
CONTROL_TYPE_GEOHASH_DISCOVERY (new)

Payload:
  tag
  flags (increased_hop_limit, ...)
  destination_hash
  destination_geohash
  designated repeaters
  hop_limit
  source_geohash (optional)

Geohash route advert

ROUTE_TYPE_DIRECT
PAYLOAD_TYPE_CONTROL
CONTROL_TYPE_GEOHASH_ADVERT (new)

Payload:
  destination_hash
  destination_geohash
  return_path
  messages_since_last_advert (optional)

Repeater decision making

How does a repeater decide to forward a geohash discovery message or a geohash discovery return path or not?

A geohash message is initialized with a destination_geohash and hop_limit initialized to LOCAL_DISCOVERY_HOPS or INCREASED_LOCAL_DISCOVERY_HOPS depending on message increased_hop_limit flag.

Message
|
+-- hop_limit > 0 ?
    |
    +-- YES -> local discovery
    |   |
    |   +-- geohash route exists in routing table?
    |       |
    |       +-- YES -> geohash routing starts
    |       |   |
    |       |   +-- set message hop_limit = 0
    |       |   +-- set message designated_repeaters = found routes 
    |       |   +-- repeat
    |       |
    |       +-- NO
    |           |
    |           +-- decrease message hop_limit with 1
    |           +-- repeat
    |
    +-- NO -> geohash routing
        |
        +-- repeater in message designated_repeaters?
            |
            +-- NO
            |   |
            |   +-- drop
            |
            +-- YES
                |
                +-- repeater geohash == destination geohash?
                    |
                    +-- YES -> destination geohash region reached -> local flooding
                    |   |
                    |   +-- set message hop_limit = LOCAL_DISCOVRY_HOPS / INCREASED_LOCAL_DISCOVERY_HOPS
                    |   +-- set message designated_repeaters = empty
                    |   +-- repeat
                    |
                    +-- NO
                        |
                        +-- geohash route exists?
                            |
                            +-- YES -> continue geohash routing
                            |   |
                            |   +-- set message designated_repeaters = routes
                            |   +-- repeat
                            |
                            +-- NO -> local flooding
                                |
                                +-- set message hop_limit = LOCAL_DISCOVRY_HOPS / INCREASED_LOCAL_DISCOVERY_HOPS
                                +-- set message designated_repeaters = empty
                                +-- repeat

Companion decision making

Sending a text message

User sends message
|
+-- known path to destination?
    |
    +-- YES
    |   |
    |   +-- send direct text message
    |
    +-- NO
        |
        +-- destination advertises geohash?
            |
            +-- NO
            |   |
            |   +-- send flood text message
            |
            +-- YES
                |
                +-- send geohash discovery message
                |       hop_limit = LOCAL_DISCOVERY_HOPS
                |
                +-- geohash discovery returned path received?
                    |
                    +-- YES
                    |   |
                    |   +-- store learned path
                    |   +-- send direct text message
                    |
                    +-- NO
                        |
                        +-- send geohash discovery message
                        |       hop_limit = INCREASED_LOCAL_DISCOVERY_HOPS
                        |
                        +-- geohash discovery returned path received?
                            |
                            +-- YES
                            |   |
                            |   +-- store learned path
                            |   +-- send direct text message
                            |
                            +-- NO
                                |
                                +-- send flood text message

Receiving a message received acknowledgement from destination

Direct text message acknowledge is received
|
+-- Does message destination advert geohash?
   |
   +-- YES
   |    |
   |     +-- Is geohash route advert time passed for this destination?
   |     |
   |     +-- YES
   |     |   |
   |     |   +-- -> Send geohash route advert
   |     |   +-- -> Add `route_advert_interval` time to `route_advert_time` for this destination
   |     |
   |     +-- NO -> Do nothing
   |
   +-- NO
       |
       +-- Do nothing

Protocol constants, Configuration parameters and variables

The following parameters control geohash routing behaviour.

In the future some configurable options may become protocol constants when sane values have been found.

Protocol constants:

Parameter	Value	Description
GEOHASH_LENGTH	5	Length of geohash that may be set on companions or repeaters
LOCAL_DISCOVERY_HOPS	?	Hop limit used for initial geohash discovery
INCREASED_LOCAL_DISCOVERY_HOPS	?	Hop limit used for second discovery attempt
COARSE_ROUTING_DISTANCE_GEOHASH_LENGTH_4	?	Minimal coarse routing distance for geohash size 4
COARSE_ROUTING_DISTANCE_GEOHASH_LENGTH_3	?	Minimal coarse routing distance for geohash size 3
INITIAL_HOTNESS_SCORE	?	Starting hotness for new routes
MINIMAL_ROUTE_ADVERT_INTERVAL	?	The minimal time between geohash route adverts.

Repeater configuration:

Parameter	Default	Description
route_expiration_time	?	Maximum route age before removal in hours
hotness_decay_factor	?	Multiplier applied during decay
hotness_decay_interval	?	Interval between decay operations in hours
max_routes_per_geohash	?	Maximum stored designated neighbours per geohash
max_route_table_size	?	Maximum routing table entries
geohash	?	The repeater geohash

Companion configuration:

Parameter	Default	Description
route_advert_interval	?	Minimum time between route adverts
geohash	?	The companion geohash

Companion state:

Variable	Purpose
contact.route_advert_time	Next advert timestamp stored on contact
contact.messages_since_last_advert	Message counter stored on contact
contact.geohash	Contact geohash
contact.out_path	Contact learned path (already exists)

Repeater state:

Variable	Purpose
routing_table	The geohash routing table
routing_table_entry.geohash	The geohash (5)
routing_table_entry.designated_neighbour	Id of designated neighbour extracted from path
routing_table_entry.last_confirmed_time	Last time the geohash was confirmed by geohash route advert
routing_table_entry.hotness	Upped with usages by geohash route advert

12. Scheme

1. Implement geohash config for companion and repeater
2. Implement new geohash message types
3. Implement sending of geohash messages by companion
4. Implement repeater routing of geohash messages

---