Routing, Dijkstra, Bellman-Ford and BFG!

For my first-step towards routing in the c-lightning prototype, I am going to make every node know every route. Easy while the network is small, and simple.

Or so I thought!

The basic routing algorithm I reached for is Dijkstra: you want the cheapest path, and it’s simple and O(#edges + #nodes x log(#nodes)). But there’s a twist: we have a limit of 20 hops. We need some limit since we want a fixed-size onion message, and 20 seemed like enough for anyone. Cheapest path within 20 hops is actually quite a bit harder; I reached out to Andrew Jeffrey (literally, we share an office) and virtually to David Gibson on Freenode’s #ccan for enlightenment.

It was David who asked “can costs be negative?”. Um, yes, they can: Joseph Poon has long suggested that you might pay people to balance your channels, and my protocol supports that. This points to the less-efficient Bellman-Ford algorithm which can handle negative costs, but is O(#edges x #nodes).

It turns out Bellman-Ford also allows you to answer the question “what’s the best path within N hops”. Problem solved?

But even Bellman-Ford can’t handle loops with total negative costs, as Andrew pointed out: it would never terminate as the cost would get cheaper as it went around and around. Of course, we have a hop limit, so we can’t go around forever, but it’d be kind of cool if we could maximize our profit in such an (unlikely!) case.

I coded up a brute-force algorithm, and it works! It loops around as long as it can if costs are negative. Then I wrote a case to show that it’s a horrible idea by creating a malicious 20-node network where would take 5²⁰ iterations. You can find the gist here.

So, where does that leave us? Today I was going simplify the problem to eliminate the negative amounts and use Bellman-Ford, but David saved the day with what I’ll term the “Bellman-Ford-Gibson algorithm” (though I’m sure it’s been invented before).

Instead of a single “best previous” for each node, we keep one for each path length (ie. 21 of them). The core of Bellman-Ford is:

for each edge (u, v) with weight w in edges:
     if distance[u] + w < distance[v]:
          distance[v] := distance[u] + w
          predecessor[v] := u

With Bellman-Ford-Gibson we do that for each hop length:

for each edge (u, v) with weight w in edges:
     for hop in 0..20:
          if distance[u][hop] + w < distance[v][hop+1]:
              distance[v][hop+1] := distance[u][hop] + w
              predecessor[v][hop+1] := u

After doing this whole thing 20 times, we have the answers in the destination node for all possible path lengths up to length 20.

We can then use some heuristics to bias to shorter paths (say, within 1% cost): we do mildly prefer shorter paths, since it means less chance of node failure and shorter timeouts, but longer paths may be better for privacy.

Note that this algorithm will less vital when we move to landmark routing, as is the longer term plan: in that case we’d expect to know only a few routes to each landmark, and we could simply brute-force the cheapest/fastest.

But I did enjoy the collaboration, as well as stretching my brain unexpectedly!