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

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 only these 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 the normal text message is sent successfully 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
515aa	5x5 km
515a	20x20 km

Companions and repeaters only set a 5 character geohash.

---

4. Geohash Routing Table

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

Geohash	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 geohash route advert interval hours a companion sends a geohash route advert after a successful text message to a companion with a geohash with the messages since the 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 messages since last advert count.
• A new entry starts with a initial hotness score.
• Every decay time interval the hotness score is multiplied by a 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 a max table size.

Mechanism:

1. Every hour, routing table entries are removed if their age exceeds the route expiration time.
2. When the max table size is exceeded, a fixed percentage of the routes is removed, where routes with the lowest hotness are removed first.
3. When a new route is added for a geohash, and three routes already exist, the route with the lowest hotness is replaced.

This way geohash routes that are used a lot are kept.

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.

---

5. 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.

---

6. Hierarchical Matching

When a destination is further away then a minimal coarse routing distance from a repeater, then the lookup of routes may be done by matching the first four characters of the 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.

Example

A repeater knows:

u15aa → A
u15aa → D
u15af → E
u15ga → C

For a destination u15a1 that is not found in the table, the repeater may forward to A, D and E if the distance of the repeater to a15a is bigger then the minimal the minimal coarse routing distance.

---

7. 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.

---

8. Privacy

A companion and router can only set a geohash of 5 characters, this represents an area of about 5x5 km which in most cases is not specific enough to find the location.

A companion can also choose not to advertise a geohash.

---

9. 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.

---

10. Implementation

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

Messages

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_MAX_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 = MAX_LOCAL_HOPS
                                +-- set message designated_repeaters = empty
                                +-- repeat