[Lightning-dev] Reproducing Flare routing results

[Shruti Hiray]

Hi everyone,

I am a final year undergraduate student at IIT Bombay, working on initial
steps of exploring routing in Lightning Network.
The following repository aims to reproduce results of the Flare Routing
Paper
<https://bitfury.com/content/downloads/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf>
[1] using
Haskell: Github repository <https://github.com/shrutihiray/lightning-flare>
 [2]

The results for Reachability in LN graph after varying number of beacons
(B) and number of queried nodes (Q)  for Graph order = 2000 and Seed for
Random Generator = 212, are as follows:

==========================================
                            Reachability in Graph
==========================================
                   Q = 0         Q = 1          Q > 1         Total
==========================================
    B = 2      0.95%       10.19%      41.02%      52.17%
==========================================
    B = 4      3.31%        64.56%      31.21%     99.16%
==========================================



In Figure 6 (a) of Flare Routing Paper
<https://bitfury.com/content/downloads/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf>
[1]
the results for Graph order = 2000 are (the numbers are estimated
approximately from the figure):

==========================================
                            Reachability in Graph
==========================================
                  Q = 0        Q = 1            Q > 1         Total
==========================================
    B = 2       0%             4%              56%           60%
==========================================
    B = 4       1%            79%             18%           98%
==========================================

As we can see the reachability with zero queried nodes is more than
expected.
The reachability with one queried node is more than expected for 2 beacons
and lesser than expected for 4 beacons.
The reachability with more than one queried nodes is lesser than expected
for 2 beacons and is more than expected for 4 beacons.
As a result, the total reachability is lesser by around 8% for 2 beacons
and is almost equal for 4 beacons.

Please help by providing suggestions to overcome the discrepancies in
reproducing the results.
Also, suggestions are welcome to help improve the design of algorithm.

[1]
https://bitfury.com/content/downloads/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf
[2] https://github.com/shrutihiray/lightning-flare

Thanks and Regards,
Shruti
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180919/ed4250f4/attachment.html>