Implementing Index Server multi route searching

[realcr]

Summary

When paying using an Offst node, a route to the destination node is required. Offst nodes obtain routes by sending a request to an index server. Currently the algorithm used at the index server is very naive, and might fail in some cases. We want to improve this algorithm.

Note: This issue continues issue #195.

Multi routes

A multi route between B and E is a set of routes (must be disjoint?) between B and E. For example:

B -- C -- E
B -- D -- F -- E
B -- G -- H --E

is a multi route between B and E.

To be a suitable multi route, the multi route between B and E should allow pushing enough credits from B to E. The index server's search algorithm must also take into consideration the fees B has to pay mediator nodes along the way.

Rates and Fees

Every node can specify a rate for forwarding payments for any of his immediate friends. We denote Rate{B,C} to be the rate the node B set for the node C. (Only B controls this value).
Rates are of the form Rate {add: u32, mul: u32}. Using a Rate, one can calculate the fee for sending x credits as rate.calc_fee(x) == (mul * x / 2**32) + add

Example: Consider the following network topology:

B -- C -- D -- E
      \-- F

1. If B sends C x credits along the route B -- C, no fees will be paid.
2. If B sends D x credits along the route B -- C -- D, C will be paid Rate{C,B}.calc_fee(x)
3. If B sends F x credits along the route B -- C -- F, C will be paid Rate{C,B}.calc_fee(x)
4. If B sends E x credits along the route B -- C -- D -- E, C will be paid Rate{C,B}.calc_fee(x), and D will be paid Rate{D,C}.calc_fee(x).

Available information for searching

The index server maintains capacity edges of the form:

pub struct CapacityEdge<C, T> {
    pub capacity: CapacityPair<C>, // send and receive capacity pair.
    pub rate: T,
}

For each pair of friend nodes. These edges are directed. This means that for two nodes B -- C, the index server will keep a CapacityEdge for the edge (B,C) and another one for the edge (C,B). Each edge represents the point of view of one of the nodes.

To get the "actual" send and receive capacity, one should take, for example, the minimum of send capacity of one side together with the receive capacity of the other side. This method should protect against one node reporting an inflated capacity to the index server.

Exclude edge option

The algorithm should allow searching the whole graph with one excluded edge. This is useful to be able to search for cycles. An example use case would be letting a node rebalance his debts. The way to do this is to find a cyclic route from a node to himself, and let him push credits along this route.

For example, consider the network layout:

 /--...--\
B -- C -- D

Where the following pairs of nodes are friends: (B,C), (C,D). We also know that there is some route between B and D that doesn't include the edge (C,D).

Assume that C wants to move his debt with D to the node B. This can be done by letting C pay to himself along the route: C --> D --> ... -> B --> C.

Without the edge excluding feature, if C naively asked for a route that goes from D to C, he would have gotten the route D -- C, which is not suitable for debt rebalancing. However, if C uses the edge exclusion feature, he can ask to get a route from D to C that doesn't go through the directed (D,C) edge. This forces the index server to come up with a route that will allow C to rebalance his debts.

Thumb rules for expected results

1. The search algorithm should find reasonably cheap multi-routes between pairs of nodes, reasonable quickly.

2. Single routes (Multi routes with only one route) are preferred over multi routes, unless (3).

3. It is preferred that every route in the multi route is not "saturated". For example: If we want to push 20 credits, and the index server returns two routes that have capacity of 10 credits each, we get a very tight situation (Every small change in the two routes might shut our opportunity to send funds). However, if we get three routes, each having 10 free credits, we have more space for changes. I have no idea how to put this into the algorithm. If it turns out difficult, it is not required.

In the current implementation of stctrl, when a multi-route is obtained, we try to take some capacity from each of the routes while staying as far as possible from saturation (Using the metric of max(distance from saturation)). You can check it here

There are some things I'm not sure about here, this is why I named it "thumb rules" and not "rules":

• How to get multiple multi-route results?
• How to make sure we get safe to use multi routes, (where non of the routes is saturated, as described in (2)).
• Should routes in a multi-route always be disjoint?

The most minimal solution should be able to return one multi-route whenever a valid one can be found.

Relevant code

I think that this has became a pretty self contained task. The code that should be changed is at:
components/index_server/graph. bfs.rs probably needs to change into some kind of advanced dijkstra, and in simple_capacity_graph.rs we should change get_multi_routes() and get_multi_route().