XRPLF / rippled

Decentralized cryptocurrency blockchain daemon implementing the XRP Ledger protocol in C++
https://xrpl.org
ISC License
4.64k stars 1.48k forks source link

Filtering paths could return a better aggregate quality set of paths. #206

Closed owenkellogg closed 6 years ago

owenkellogg commented 11 years ago

In the function Pathfinder::filterPaths the algorithm sorts by highest Quality and then begins to select by quality until the total amount is fulfilled by the entire set. However if the highest quality paths contribute a small proportion of the total amount then it is possible to skip several paths that could result in a better total quality.

Example: Given a set of paths with decreasing quality I want to match a set of four paths whose values sum to 1200.

Given the following set of paths:

10, 10, 10, 500, 500, 500, 1500

The current algorithm would choose the first three 10, 10, 10 and then skip down to take 1500, which has the lowest quality.

If the algorithm instead chose 10, 500, 500, 500 it could return a higher total quality, but it skips these because the first three paths have already been set to 10, 10, 10.

JoelKatz commented 11 years ago

Taking 10, 500, 500, 500 is extremely dangerous. If those three 500 paths consume the same liquidity, then the payment won't work at all. You want to take 500, 500, 500, 1200. This gets almost the best quality you can and ensures the payment will work because the 1200 path definitely can complete the payment.

You're welcome to experiment with different algorithms and heuristics, but it is not feasible to try to get the best possible set of filtered paths every time. The current algorithm actually will actually not take those first three 10's because they are considered too small (this was a recent change):

    STAmount saMinDstAmount = STAmount::divide(mDstAmount, STAmount(iMaxPaths + 2), mDstAmount);
...
        else if (saDstAmountAct < saMinDstAmount)
        {
            WriteLog (lsDEBUG, Pathfinder)
                    << boost::str (boost::format ("findPaths: dropping: outputs %s: %s")
                                   % saDstAmountAct

        }
vinniefalco commented 11 years ago

I'd like to see a formal exposition (English language write-up) of the exact algorithm used by the pathfinding engine.