Routemap scaling (was: Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0)

Summary:

The proposal suggests a way to maintain determinism in network maps while encouraging a diverse distribution. The solution involves treating it as a spatial indexing problem, using the lexicographical space of node ids (or hashes of), similar to DHTs. A quadtree could be used, where nodes are put into one of four buckets based on the two most significant bits of their public key hash. Nodes would advertise a feature bit indicating that they are committed to keeping the entire routemap of the bucket matching their own public key hash. The amount of information held by each node could be reduced to around 40% of that of the parent node in the quadtree. Nodes can also decide their bucket capacities and go several layers deep.Payments within a bucket can be made without querying, and payments to another bucket can rely on local routemaps, with JIT routing for the second half if required. A convention could be created where each bucket represents an approximate physical location, and the globe can be spatially-indexed as a quadtree using a tetrahedral map projection. This method may improve routing for local trade, but privacy concerns need to be addressed.To overcome the issue of unbalanced trees due to population density, an equal-population-per-area projection can be used. Autopilot implementations may also need adjusting to consider distance, with a suggested geometric distribution where half of opened channels should be within the same bucket, a quarter to sibling buckets, and an eight to cousin buckets, etc.Privacy considerations arise if nodes indicate their approximate locations, which needs to be discussed. The proposed method does not need to be the exclusive way in which gossip is communicated between nodes, and it can be combined with other methods such as ZmnSCPxj's suggestion for gossiping about highest capacity nodes or sharing information about the highest capacity channels in a bucket.

Updated on: 2023-06-02T18:14:38.805463+00:00