fred
fred copied to clipboard
freenet
No path folding at high HTL
For consideration. This would improve security (e.g. no possibility of attacker data source getting directly connected to request originator just by path folding), but it may have negative performance impacts, especially on new nodes who mostly get their peers from doing local requests.
This may also have an impact on the number of long links, and it was originally proposed to deal with that. However, we have code to deal with that directly, enforcing 30% of the routing table to be long and 70% short. With this patch, path folding will probably produce fewer long link candidates.
Unfortunately I am not yet in a position to test opennet in multi-node simulations. Maybe I will be in coming months.
returning less long link candidates is likely a good thing. The 30/70 thing is a brute force method, this one should make it work smoother (since the links returned from path folding will be a better match for what the node requires).
It might. Or there might be too few. Either way, newbie nodes are likely to take longer to bootstrap, unless we take other measures such as announcing through any peer (I think there's a pull request for this?). Agree we should probably try it at some point, but we need some systematic stats first.
Matthew Toseland writes:
It might. Or there might be too few. Either way, newbie nodes are likely to take longer to bootstrap, unless we take other measures such as announcing through any peer (I think there's a pull request for this?). Agree we should probably try it at some point, but we need some systematic stats first.
There isn’t yet a pull request, I think, but there is a bug report. And I don’t think we need additional stats to know that it would be useful to announrce through any peer, since the seednodes are a single point of failure.
Best wishes,
Arne
Unpolitisch sein heißt politisch sein ohne es zu merken
So in conclusion, this is longer term ... #491 should be considered for 1472...
Why should there be too few nodes? We route with HTL 18, so we only lose about 10% of the possible folding options — mostly the long ones (of which we get too many anyway) — which means that bootstrap should become a bit slower, but not seriously slower. And the link length distribution could improve seriously.
We will need to test this, but conceptually it’s sound.
Maybe. I'd want to simulate it first, and have much better stats gathering (digger3's stats are down).
Bootstrapping would be dramatically slower because new nodes would get no nodes from path folding from successful local requests - they'd have to wait until they have successful relayed requests. However, the opennet-changes branch may offset this.
We could test this without a full blown opennet simulation. The necessary changes will work fine on their own on the end-node. E.g. bootstrap a new node with this branch, which will cause it to not path fold on local requests.
This looks good, except for formatting. I agree with @ArneBab that this is conceptually sound, but haven't looked at your alternative #491 yet.
I’m testing this right now, and it fails to connect for two nodes here. One got one working connection, the other got none. After half an hour, both don’t have any connection.
Time to find out why the concept doesn’t work…
I guess @toad is right that it’s because local requests don’t give new nodes anymore: As long as a node has few connections, few requests will get routed to the node (due to FOAF routing, others have more than 100 times higher chance to be selected as a routing target), and it can only get new connections through announcement or from requests it forwards.
With only a single connection, nothing can be forwarded.
Next test: I’ll switch back to a regular version and test whether this gets connections. If it does, this patch is the culprit.
For my test I merged this pull request into 1471-stable.
now I merged into build 1470, one node without folding at high HTL (Freenet1), one regular (Freenet2). Both nodes got 3 connections, but the one without folding at high HTL only reports 16 rejections, the regular one reports 36 rejections.
I’ll keep both running for a while.
Bear in mind that there is IP-address-based limiting on the seednodes, and announcement is rather hit-and-miss anyway. So bootstrapping more than one node on the same IP in the same day may work poorly regardless.
Also, this patch should have no effect on announcements - except to make new nodes more dependent on them.
Status: 5 connections with this pull-request, 12 without it. At least the no-high-HTL-folding node has now 86 rejections. Both try to get 18 connections.
I’ll check it again in an hour.
Now both have 15-17 connections (of 18 needed). As next test I’ll reduce the upload bandwidth to 6KiB/s, wait till the connections drop and then increase it again (to more than what it has now) and see how the peer distance distribution looks. I expect that the no-high-HTL node would have less long distance connections.
The no-high-HTL node currently has a cluster of 4 nodes at distance 0.2 and one at distance 0.4, the regular node has 3 long distance nodes at distances 0.05, 0.1 and 0.25.
canWriteDatastoreRequest is HTL <= maxHTL - 2, so it’s 16 or less. Given that the success rate is highest at HTL 17, this means most requests cannot fold, which looks excessive to me.
Does this mean that it only starts folding after the first 2.5 hops? Or is it 1.5 hops (just skipping direct neighbors)?
If it is 2.5 hops, HTL 17 might suffice.
CHK SSK
18 31,505% (1032,75121,241721) (,0006) 1,342% (597,3075,273704) (,0043)
17 34,155% (1227,69383,206735) (,0003) 1,763% (549,2371,165639) (,0012)
16 30,653% (1469,112647,372288) (,0002) 0,775% (699,1167,240673) (,0004)
15 26,292% (1111,109847,422017) (,0001) 0,335% (378,491,259291) (,0002)
14 15,796% (168,40717,258836) (,0002) 0,084% (71,109,213087) (,0003)
45% of requests reach HTL16, 31% HTL15, 68% HTL17. We might need at least 2 steps, though, to avoid the first two longrange hops due to FOAF routing.
status: just increased upload bandwidth to 60 == 27 peers.
Now 18 vs. 25. However the no high HTL peers are all connected while the regular peer has a quarter to half its peers busy.
For analysis:
Node locations no high HTL:
0.16986777257793562
0.17901946183666562
0.5052537534294653
0.5086700871359677
0.6390555069251317
0.6822584345099271
0.8980318688923236
0.9450003036258698
0.9472578481300644
0.9475679196733452
0.9505918714537117
0.9512505057035953
0.9512848146581615
0.951332629568245
0.953138735932966
0.9534703560289312
0.9537457741318474
0.9612296077880356
0.18339809750763603
0.9517140598028574
0.9521872029906774
0.9531178654323221
Node locations, regular:
0.1683899971760181
0.5462565170155342
0.6584651359671296
0.6669163773467959
0.6752661195055957
0.8012936926640807
0.8020591962695599
0.8066928956581909
0.8081615954443561
0.8094734715697488
0.8100868389013971
0.8121570853807678
0.8136131131663924
0.8150852508230284
0.8164318649800096
0.9073881084564737
0.7200454861860763
0.8031756611247909
0.8047278039539334
0.8095277095841826
0.8103247800000128
0.8118534916279835
0.813718338962537
0.8137287779436605
0.8139409096231633
0.8184079088556605
0.7194572283696072
now 23 vs. 27.
Peer distribution no high HTL:
0.17901946183666562
0.5052537534294653
0.8980318688923236
0.9008688888658157
0.9450003036258698
0.9472578481300644
0.9504251829525352
0.9505918714537117
0.9512505057035953
0.9512848146581615
0.951332629568245
0.953138735932966
0.9534703560289312
0.9537457741318474
0.9543209138274216
0.9553451901226157
0.9562020585339739
0.9564390915303991
0.9612296077880356
0.14636055660556124
0.8935836794924024
0.9509168180104608
0.9530186614237126
0.5086700871359677
0.9475679196733452
0.9502900387595263
0.9615630709874536
regular:
0.1683899971760181
0.40145412492581534
0.5462565170155342
0.6669163773467959
0.7200454861860763
0.7993934278340358
0.8003752187303285
0.8012936926640807
0.8018909930668665
0.8066928956581909
0.8081615954443561
0.8100868389013971
0.8118534916279835
0.8134545396525108
0.8136131131663924
0.8137287779436605
0.8139409096231633
0.8150852508230284
0.8164318649800096
0.8184079088556605
0.9073881084564737
0.9076888086179288
0.8031756611247909
0.8095277095841826
0.8103247800000128
0.813718338962537
0.8094734715697488
26/27 — so the no high HTL folding took roughly 3x longer to get a full set of connections (3 hours) — I would estimate that it needs 9 hours to get a good distribution of peers. Given that our median uptime is rather around 2 hours, that’s too long.
For security: can’t the HTL be faked?
I’m shutting down the regular node. The no-high-HTL one will run a bit longer to see whether it settles.
7 hours later:
0.0161567010603062
0.14977241274358533
0.2535342406046017
0.6398256029475275
0.7907590894018743
0.8991295287193819
0.9450003036258698
0.9472578481300644
0.9474802650784804
0.9477809820924051
0.9504251829525352
0.9505918714537117
0.9512848146581615
0.9517140598028574
0.9521872029906774
0.9530186614237126
0.9534703560289312
0.9535672941936432
0.9553451901226157
0.9579391787964676
0.959033783035655
0.9469400351870869
0.9482952331226397
0.9514408501738144
0.9543209138274216
0.686718197657147
So, after 9 hours the quality of the link length distribution looks similar as the regular one after 3 hours. It does not give significantly more short distance connections.
For comparing:
import pylab as pl
def plotfromtext(a, label):
b = [float(i) for i in a.splitlines() if i]
c = [(i - pl.median(b))%0.5 for i in b]
pl.plot(sorted(c), label=label)
pl.xscale('log')
a = """0.0161567010603062
0.14977241274358533
0.2535342406046017
0.6398256029475275
0.7907590894018743
0.8991295287193819
0.9450003036258698
0.9472578481300644
0.9474802650784804
0.9477809820924051
0.9504251829525352
0.9505918714537117
0.9512848146581615
0.9517140598028574
0.9521872029906774
0.9530186614237126
0.9534703560289312
0.9535672941936432
0.9553451901226157
0.9579391787964676
0.959033783035655
0.9469400351870869
0.9482952331226397
0.9514408501738144
0.9543209138274216
0.686718197657147
"""
plotfromtext(a, "no high HTL")
a = """0.1683899971760181
0.40145412492581534
0.5462565170155342
0.6669163773467959
0.7200454861860763
0.7993934278340358
0.8003752187303285
0.8012936926640807
0.8018909930668665
0.8066928956581909
0.8081615954443561
0.8100868389013971
0.8118534916279835
0.8134545396525108
0.8136131131663924
0.8137287779436605
0.8139409096231633
0.8150852508230284
0.8164318649800096
0.8184079088556605
0.9073881084564737
0.9076888086179288
0.8031756611247909
0.8095277095841826
0.8103247800000128
0.813718338962537
0.8094734715697488
"""
plotfromtext(a, "regular")
pl.legend()
pl.show()
Ok so you've confirmed that it works but it takes longer to bootstrap, which is pretty much what we expected???
Re hops taken, you can't deduce much from success rates... But you were looking at request counts?
Could such a bias be a good thing? If something is found quickly then presumably it's very close? Does that mean we'd tend to get more longer links from path folding??