Trade Routing and Execution

In an off-chain network, each user has its direct neighbors, those he shares his payment channels with. In our work, we focus on off-chain network topology selection and user mapping. While network topology describes precisely the connection between nodes, nodes mapping demonstrates users’ assignments to nodes of the topology. We define two fundamental optimization problems for the off-chain network assuming some given routing scheme for payments. In the definitions a function ψ(v1, v2) −→ R denotes the routing cost between two nodes v1, v2 ∈ V in a topology G = (V, E) following some known routing scheme. Along the paper, we refer to a mapping of users to nodes in the topology which is an injective 4 Julia Khamis, Ori Rottenstreich function, namely two users are necessarily mapped to different nodes of the topology. In particular, if the number of nodes in the topology equals the number of users (|V | = N) the mapping is a bijective function.

In both problems the evaluation metrics of a solution take into account the routing cost function ψ(v1, v2) −→ R between two
nodes v1, v2 ∈ V in a topology G = (V, E). Thus solving the problems with different cost functions can lead to different
off-chain networks even for the same demand matrix. Some examples of routing cost functions can be:

Hop count (distance between sender and recipient pairs). Here the function ψ(v1, v2) returns the number of edges in a
shortest path between nodes v1, v2.Transmission fees. Here ψ(v1, v2) returns the amount of fees paid to intermediate nodes along a path between nodes
v1, v2.

one has to dynamically construct an off-chain network topology aiming to minimize the total spent fees. We attain that by adding channels to the network topology that minimizes the fees spent while serving payments off-chain. The general structure of our Algorithm is as follows: Input of (i) Topology (ii) Demand matrix / Pending payment graph. Output of (i) Updated topology, (ii) Routing scheme. We consider constant cost function that reflects the evaluation metric, computing fees for serving demand payments