<p>I am not sure if scale is the term you are looking for when discussing potential problems with routing. But I will try to focus on scaling when giving the answer. That being said my answer would probably differ quite a lot if the question was asked differently.</p>

<p>The current routing algorithm is onion routing. The onions contain a path from sender to the receiver (decided by the sender - see below for more discussion on that) and are constructed to support as many as 20 hops. This means that we actually can scale to networks with a diameter of 20. (the diameter is the longest shortest path on the friendship network and is a topological property). Already with 21 nodes I could create a lightning network with the topology of a list and be unable to route a payment from the heads of the list to the tail with the current onion format. 
This problem can easily be mitigated though by creating a new payment channel - changing the topology in a a way to decrease the diameter. My autopilot implementation suggests channels that decrease the diameter of the network. </p>

<p>So the problem boils down to how big can a network be to have a diameter less than 20? When looking at the strongly connected component of large networks like the web or the Facebook graph they all seem to have lower diameters which is indicative that the 20 hop limit should not hinder scale. However there is a correlation: the more edges we allow on a network with a fixed set of nodes the lower the diameter. Take a fully connected graph which has diameter 1 by definition in contrast to the "list graph" from above which has diameter <code>n</code>.</p>

<p>That being said the web graph and friendship graph on Facebook are believed too have on average about 150  edges per node (the so called Dunbar number). We already know that without channel factories and with current blocksize limits we would need decades to allow every person in the world to open one payment channel which would most likely result in a graph with a larger Diameter. Allowing people to open 150 channels takes 150 times that much time.</p>

<p>With respect to scale of routing there is not only the 20hops limit of onions. There is also pathfinding and related to that discovery of the network topology (aka the gossip protocol). Path finding boils down to breadth first search or Dijkstra algorithm which is a weighted BFS. Both algorithms have a runtime that makes part finding possible on graphs with billions of nodes on modern hardware in particular when using graph databases like neo4j (currently everything is stored in memory). If the network would grow beyond nodes for humans (e.g with IoT nodes) we might reach the limits of modern hardware to compue those paths. </p>

<p>As for the gossip protocol. Each channel needs to be announced to the peer2peer network. Since channels need to be veryfied / linked to a blockchain tx this should not be a problem. However the gossip protocol seems to be quite noisy. There is currently the million node Challenge run by rusty Russell that tries to stimulate what happens if the network grows.</p>

<p>Also there are potential other issues like the htlc limit of 483 concurrent htlcs per payment channel that might produce traffic jams (though it seems very unlikely and is actually a reason why to avoid these so called centralized hubs and why nodes should work on decreasing the diameter). Also the exact topology of the network is never known (only capacity of channels) </p>

<p>Regarding your second part  (how are the issues mitigated) 
1. The biggest issue seems quick opening of channels. There was research by Christian decker proposing the concept of channel factories showing that we can increase the amount of channels we can open per block by a factor of 10 to 100.
2. As for pathfinding: I currently suggested JIT-routing which is a low level backward compatible improvement for path discovery. This path decovery mechanism mitigates the problem of not knowing the balance of channels when selecting a path. My proposal also included the suggestion to have nodes only store a local view of the network and create an overlay addressing scheme which could be used for routing tables (like it is on the internet) this would also mitigate the problem of storing the entire network.
3. The problems with the gossip protocol currently seem to have the highest focus by developers - look at rustys million channel challenge.</p>

<p>There might be more issues which I am currently not aware of. </p>

CC BY-SA 4.0
2019-04-23T05:23:51.953Z
2019-04-23T05:23:51.953Z
Rene Pickhardt
<p>What are the weaknesses we face with lightning routing currently?</p>

<p>How many nodes do we expect it can handle now?</p>

<p>What is being done to make it scale in the future?</p>

<lightning-routing>
How scalable is the current routing implementation for lightning?
Jc Crown
# How scalable is the current routing implementation for lightning?

(Asked by: username_0 on 2019-04-22)

What are the weaknesses we face with lightning routing currently?

How many nodes do we expect it can handle now?

What is being done to make it scale in the future?

**Tags:** lightning-routing


---

## 1 answers

### Answer by username_1 on 2019-04-23. Score: 5 | Accepted answer

I am not sure if scale is the term you are looking for when discussing potential problems with routing. But I will try to focus on scaling when giving the answer. That being said my answer would probably differ quite a lot if the question was asked differently.

The current routing algorithm is onion routing. The onions contain a path from sender to the receiver (decided by the sender - see below for more discussion on that) and are constructed to support as many as 20 hops. This means that we actually can scale to networks with a diameter of 20. (the diameter is the longest shortest path on the friendship network and is a topological property). Already with 21 nodes I could create a lightning network with the topology of a list and be unable to route a payment from the heads of the list to the tail with the current onion format.
This problem can easily be mitigated though by creating a new payment channel - changing the topology in a a way to decrease the diameter. My autopilot implementation suggests channels that decrease the diameter of the network.

So the problem boils down to how big can a network be to have a diameter less than 20? When looking at the strongly connected component of large networks like the web or the Facebook graph they all seem to have lower diameters which is indicative that the 20 hop limit should not hinder scale. However there is a correlation: the more edges we allow on a network with a fixed set of nodes the lower the diameter. Take a fully connected graph which has diameter 1 by definition in contrast to the "list graph" from above which has diameter `n`.

That being said the web graph and friendship graph on Facebook are believed too have on average about 150 edges per node (the so called Dunbar number). We already know that without channel factories and with current blocksize limits we would need decades to allow every person in the world to open one payment channel which would most likely result in a graph with a larger Diameter. Allowing people to open 150 channels takes 150 times that much time.

With respect to scale of routing there is not only the 20hops limit of onions. There is also pathfinding and related to that discovery of the network topology (aka the gossip protocol). Path finding boils down to breadth first search or Dijkstra algorithm which is a weighted BFS. Both algorithms have a runtime that makes part finding possible on graphs with billions of nodes on modern hardware in particular when using graph databases like neo4j (currently everything is stored in memory). If the network would grow beyond nodes for humans (e.g with IoT nodes) we might reach the limits of modern hardware to compue those paths.

As for the gossip protocol. Each channel needs to be announced to the peer2peer network. Since channels need to be veryfied / linked to a blockchain tx this should not be a problem. However the gossip protocol seems to be quite noisy. There is currently the million node Challenge run by rusty Russell that tries to stimulate what happens if the network grows.

Also there are potential other issues like the htlc limit of 483 concurrent htlcs per payment channel that might produce traffic jams (though it seems very unlikely and is actually a reason why to avoid these so called centralized hubs and why nodes should work on decreasing the diameter). Also the exact topology of the network is never known (only capacity of channels)

Regarding your second part (how are the issues mitigated)
1. The biggest issue seems quick opening of channels. There was research by Christian decker proposing the concept of channel factories showing that we can increase the amount of channels we can open per block by a factor of 10 to 100.
2. As for pathfinding: I currently suggested JIT-routing which is a low level backward compatible improvement for path discovery. This path decovery mechanism mitigates the problem of not knowing the balance of channels when selecting a path. My proposal also included the suggestion to have nodes only store a local view of the network and create an overlay addressing scheme which could be used for routing tables (like it is on the internet) this would also mitigate the problem of storing the entire network.
3. The problems with the gossip protocol currently seem to have the highest focus by developers - look at rustys million channel challenge.

There might be more issues which I am currently not aware of.


---

