通道网络中的再平衡（Rebalancing）算法加速思路

继上一次关于支付网络中路由问题的全面研究之后，热爱研究的 Nervos 小伙伴 Shor 对通道网络中的再平衡（Rebalancing）算法又做了详细的研究。

本文中，我们会介绍通道网络（Channel Network，CN）中的 Rebalance 问题。首先我们将介绍问题的定义和现有的解决算法。之后，我们会针对这一问题，介绍必要的图论基础和建模方法。最后，我们提供一种算法加速思路。（本文默认读者具备对于通道网络的常识。）

我们把一个支付网络看作一个无向图，每个图中的节点代表一个 PID，每条边代表一个支付通道，其中每条边在两端节点各有一个存量。注意：我们默认每个（双向）支付通道内部总存量守恒，即由 A，B 组成的通道中，如果 A 有余额 50，B 有余额 80，B 在向 A 支付 10 元后，A 有余额 60，B 有余额 70。

有时，因为网络拓扑结构等原因，一个支付通道的一个方向总比另一个方向「更受欢迎」，在此情况下，各个通道的有限总存量都被「堆积」到一侧，或者说「受欢迎方向」的流量就此耗尽了。因此，支付网络会频繁出现通道流量耗尽，不得不再次「上链」打开新通道的情况。再平衡（rebalancing）技术通过以下方式试图缓解这一问题。

例如下图中, 我们考虑一个由四条边构成的回路，他们主流方向的10单位余量都已经耗尽。

其中每个箭头  表示一个连接了 A 与 B 的无向通道，其中 A 方存量是 a，B 方存量是 b。值得注意的是，箭头方向代表了主流方向，因而我们画成了一个有向图，不过最新基于 RbR 的支付通道都是双向的。Revive 通过一个来自全局 leader 的协调（本文中，我们不予考虑这个 leader 是如何实现的），完成一个 rebalance 工作。例如，可以协调 B 向 A 转账 5 个单位，协调 A 向 C 转账 5 个单位，协调 C 向 D 转账 5 个单位，协调 D 向 B 转账 5 个单位，使得全图结构如下图所示。其本质上是找到一个「回路」，并在这个回路上让所有通道一起逆着主流方向回流、抵回一些流量。

对于一个有向图，一个强连通分量指一个任意两点之间可以互相由图上有向边访达的子图。一个极大强连通分量是一个增加任何一个其它节点后就不具备强连通分量性质的子图。例如上图中，我们可以用灰色区域勾勒出它的四个极大强连通分量。

我们可以观察到以下方面：