Am Montag, 29. August 2011, 14:32:13 schrieb Ian Clarke: > Yes, small tweaks have worked so well for us for the last decade, leaving us > pretty-much where we were in 2003. No, we don't understand how the current > system works, there is no point in trying to fix something when we don't > even know what is broken.
I’d like to present a clue what is broken in NLM. Before I kill you with the
log, here’s the result:
With NLM the latency of a request is a function of the raw bandwidth
(not so with OLM), and NLM used only half my bandwidth after it had
been deployed for 2 days (at the start much more).
τ ~ bandwidth. q_olm ~ 16s, q_nlm ~ τ! ; with τ: transfer time, q: queue time
(time to find the node), nlm: new load management, olm: old load management.
So first step: make sure all bandwidth gets used - maybe by allocating more
slots till we use all allowed bandwidth. Better having to throttle a transfer
than not using bandwidth.
*NLM should with the current network be slower than OLM by 23%. But in 18
months it should actually be faster by ~8% — given Moores Law holds for upload
bandwidth — because the routes are shorter.*
The main advantage of NLM is, that it should be much more resilient against
attackers (DoS).
Now to the log - it’s math and not cleaned up; you have been warned :)
<ArneBab> SSK-time: σ, CHK-time: ψ, success: Xs, fail: Xf.
<ArneBab> queue-time: q, transfer-time: τ, hops remaining: h, total hops: h₀,
w: success rate
<ArneBab> ψs = τ(h) + q(h)
<ArneBab> ψf = q(h)
<ArneBab> ψ ~ w₁·ψs + (1-w₁)·ψf
<ArneBab> σs = τ(h) + q(h)
<ArneBab> σf = q(h)
<ArneBab> σ ~ w₂·ψs + (1-w₂)·ψf; w₂ ~ 15%
<ArneBab> num(ψ) / num(σ) ~ 1
<ArneBab> → time ~ σ + ψ
<ArneBab> q(h) depends on timeouts, as do w₁ and w₂
<ArneBab> time = w₁·ψs + (1-w₁)·ψf + w₂·ψs + (1-w₂)·ψf
<ArneBab> = w₁ · (τ(h) + q(h)) + (1-w₁)·q(h) + w₂ · (τ(h) + q(h)) + (1-
w₂)·q(h)
<ArneBab> = t(h) · (w₁+w₂) + 2·q(h) · (2-w₁-w₂)
<ArneBab> = τ(h) · (w₁+w₂) + 2·q(h) · (2-w₁-w₂)
<ArneBab> in the congestion case q(h) ~ timeout
<ArneBab> timeout = o
<ArneBab> timeout: o
<ArneBab> w depends on the timeout *somehow*, but inversely
<ArneBab> o=0 → w=0
<ArneBab> assumption: o = ∞ → w₂ ~ 20%, w₁ ~ 100%
<ArneBab> assumption: o = ∞ → w₂ ~ 0.2, w₁ ~ 1
<ArneBab> correction: in the congestion case: q(h) ~ min(timeout, τ(h))
<ArneBab> timeout matters for q(h) only when timeout < τ(h)
<ArneBab> I try to: I still need a dependency of w on timeout
<ArneBab> … lets call it t(w)
<ArneBab> better: w(o) :)
<toad_> well, if there is a timeout, we have a fixed time, but we reduce the
hops ...
<toad_> i thought w was success rate
<ArneBab> ah!
<ArneBab> and the success rates where in the NLM stats
<ArneBab> going mostly smoothly from 60% to 0%
<ArneBab> for the HTL
<toad_> right, success rate peaks at 18 or sometimes 16
<toad_> what are w1 vs w2?
<toad_> chk vs ssk i guess
<ArneBab> yes
-*- toad_ thinks considering both is probably overambitious at this stage?
<ArneBab> should not be too bad: SSKs drop much more rapidly at decreasing
hops
<ArneBab> hops→HTL
<toad_> ψs is time for a successful chk; ψf is time for a failed chk ... in
which case h in the first instance is low, and in the second instance is h0
<ArneBab> yes
<toad_> okay, i don't follow this line: time = w₁·ψs + (1-w₁)·ψf + w₂·ψs +
(1-w₂)·ψf
<toad_> i thought w2 related to SSKs?
<ArneBab> uh, yes…
<ArneBab> time = w₁·ψs + (1-w₁)·ψf + w₂·σs + (1-w₂)·σf
<toad_> you have to appreciate i'm only just getting back into maths and
physics after 12 years ...
<toad_> (retaking a-levels to get a degree)
<ArneBab> no probs, I’m also no expert in this. I try to get a relation
between the time and the timeout, so we can try to find a minimum
<toad_> in any case, there are two different h's for the two uses of q(h) - h0
and h_avg
<toad_> h_avg for success and h0 for failure
<ArneBab> hm, yes
<ArneBab> which makes this harder…
<ArneBab> it’s wrong anyway… the q(h_avg) was missing
<toad_> h_avg is somewhere between 5 and 10 imho
<toad_> at least it is if everything is working well and the input load isn't
all really popular stuff (in which case it's answered quickly and can be
ignored)
<ArneBab> = τ(h) · (w₁+w₂) + q(h) · (2-w₁-w₂) + q(h_avg) · (w₁+w₂)
<ArneBab> would have been too easy :)
<toad_> okay so here q(h) means q(h0) i.e. h = h0, max hops?
<ArneBab> jepp, and max hops sinks with falling timeout
<toad_> hmm?
<ArneBab> the max actual hops
<toad_> on the upside, q() is linear
<-- Torgal ([email protected]) hat das Netzwerk verlassen (Ping timeout: 276
seconds)
<toad_> hopefully
<ArneBab> yes: q(h) = h·o
<ArneBab> (in the congestion case)
<toad_> the problem i have is it looks like q(1) ~= time [ for a full request
], unless load is very low
<ArneBab> so τ « q?
<ArneBab> τ much smaller than q?
<toad_> of course it's bounded by timeouts, but i'd expect a runaway feedback
loop until it reaches heavy timeouts and effectively cuts the htl
<toad_> well, with OLM, success time for a CHK is 1m25s, unsuccessful is
19sec, so transfer time is at least 1 minute
<toad_> and less than 1m25; but with NLM, unsuccessful is 3 min+
<ArneBab> well, for SSKs in OLM the first 6 hops are the most successful, later
ones only contribute 1% success, which piles up to ~ 12%
<toad_> okay...
<ArneBab> (only possible because 85% are unsuccessful)
<ArneBab> (otherwise this would be wrong: the contribution of later ones would
be smaller)
<ArneBab> from the numbers q(h₀) ~ τ(h_avg)
<toad_> well, queueing time on any hop is the time it takes to get a slot to
route to, which is roughly equal to the time it takes for a request to
complete divided by the number of waiters, right?
<toad_> errr multiplied by the number of waiters
<toad_> if the network is homogenous, that's exactly the time it takes for a
request to complete
<toad_> so we expect ridiculous queue times
<toad_> however if there is spare capacity this may be avoidable
-*- toad_ hopes you can establish that NLM isn't totally pointless anyway :)
<ArneBab> actually that fits it quite well, but it leaves out that routes with
NLM should be shorter
<ArneBab> and that for me the point of NLM is not speed but attack-resilience
<ArneBab> that network can’t be spammed efficiently
<ArneBab> simplified: time = (τ + q) · hops ; τ and q as times per hop
<ArneBab> hops for CHK are less with NLM
<ArneBab> hops for SSK are equal
<ArneBab> (most are unsuccessful)
<ArneBab> → time = q(SSK) + τ(CHK) + q(CHK)
<ArneBab> in OLM: “q”(SSK) ~ 16s, “q”(CHK) ~ 18s, τ(CHK) ~ 45s
<ArneBab> (my stats)
<ArneBab> in NLM q(SSK) = τ(CHK)
<ArneBab> or so
<ArneBab> → there we might have the general problem
<ArneBab> toad_: the queue times of SSKs depend on the transfer times of CHKs,
so they have to be higher
<toad_> well, ian thinks there is a fundamental problem with queueing; the
alternative is to allow a larger window between when we start complaining and
when stuff breaks i.e. use less % of the total capacity
<ArneBab> in NLM: q(SSK) ~ q(CHK) ~ τ(CHK), τ(CHK) lower due to better routes?
<toad_> which might be faster in practice
<ArneBab> τ(CHK) depends on the length of the route. with 25% better success
rates per hop, it should be much lower
<ArneBab> …need NLM stats… do you have some handy?
<ArneBab> let’s estimate 60%/50%/50%/50% for HTL 18/17/16/15
<ArneBab> and I currentlo have 45%/50/25%/25% with OLM
<ArneBab> starting with 1000 requests, in NLM 600 have 1 hop, 200 have 2 hops,
100 3 and 50 4, 50 have more → irrelevant.
-*- toad_ not following
<ArneBab> in OLM 450 have 1 hop, 275 have 2 hops, 69 3 and 51 4, 150 have more
<ArneBab> I’m trying to estimate the hops a transfer has to take
<ArneBab> we can’t ignore the 150 with more than 4 hops in OLM
<ArneBab> I’ll just go down to 50, too
<toad_> what are you trying to compute?
<toad_> ian is convinced that queueing always makes the underlying problem
worse
<toad_> i'm inclined to agree with him unless you come up with a persuasive
theoretical argument
<ArneBab> 120 have 5, 96 have 6, 77 have 7, 61 have 8, 50 have more
<ArneBab> so a 95% of the transfers in OLM take on average …
<ArneBab> gah… need to divide the numbers, too
<ArneBab> (I need to generate data to make an argument - that’s what I’m doing
right now)
<ArneBab> average hops for OLM: 450*1 + 275*2 + 69*3 + 51*4 + [now with
correction] 150*0.22*5+120*0.2*6+96*0.2*7+77*0.2*8+61*0.2*9
<ArneBab> → 2087.4
<ArneBab> for NLM 95% of 1000 transfers need 600*1+200*2+100*3+50*4
<ArneBab> = 1500 hops together
<ArneBab> that’s 2.09 hops per transfer for OLM and 1.5 hops for NLM → τ_nlm /
τ_olm ~ 0.71
<toad_> ArneBab: okay, that's plausible
<toad_> ArneBab: however, it should be possible with smart load limiting on
the originator to achieve NLM-level success rates
<ArneBab> but not the resilience
<ArneBab> it still keeps freenet open to a DoS, NLM should help there.
<ArneBab> now back to the queueing: OLM had: “q”(SSK) ~ 16s, “q”(CHK) ~ 18s,
τ(CHK) ~ 45s (my stats)
<toad_> possibly - fair sharing limits our vulnerability to a DoS, possibly
enough as long as we don't have to worry about incentives issues
<ArneBab> that’s about: q = ⅓ · τ (OLM)
<ArneBab> NLM: q ~ τ
<ArneBab> NLM: q ~ τ (NLM)
<ArneBab> time: 2·q + τ
<ArneBab> OLM: time ~ 5/3 τ_olm
<ArneBab> NLM: time = 3 · 0.72 τ_olm = 2.15 τ_olm
<operhiem1> toad_: Alright, it's alive. https://github.com/freenet/fred-
staging/pull/55
<ArneBab> → time_nlm / time_olm ~ 2.15 / (5/3) ~ 1.3
<ArneBab> so the time to transfer should be a bit longer
<ArneBab> (not yet finished: this is the current state)
<ArneBab> now, if we decrease the timeout time, the chance that a given
timeout happens in the first 4 hops should be about 4/20 = 0.2
<ArneBab> …cut that…
<ArneBab> if we decrease the timeout time below the transfer time per hop,
there should be more misrouting → τ goes up, q might go down or up → cut that.
<ArneBab> transfer time per hop in OLM ~ 45s / hops_olm = 45s/2.09 = 21.5s
<ArneBab> …actually, the time in NLM is so dependant on transfer time, that
the most efficient stratigy would likely be to decrease the block size…
<ArneBab> or to get a faster network
<ArneBab> toad_: got it, damnit: NLM is so much slower than OLM, because it
used less bandwidth!
<ArneBab> the time is a function of the raw bandwidth (not so with OLM), and
NLM used only half my bandwidth after it had been deployed for 2 days (at the
start much more)
<ArneBab> when we double the bandwidth (1.8 years?), NLM should be faster than
OLM
<ArneBab> operhiem1: cool!
<ArneBab> toad_: actually I think the slot number calculation is flawed → less
bandwith used than possible
<ArneBab> that’s why it did not break down, but slowed down to 1/5 OLM. From
the math here I’d have guessed 1/2.6
<ArneBab> but adding SSKs with many more hops and time almost pure queue time
it fits
<ArneBab> q_nlm ~ 3·“q”_olm; in the full bandwidth case
<ArneBab> but with half bandwidth we actually are at 6·q_olm
<ArneBab> → more slots should actually make it much better
<ArneBab> toad_: summary: τ ~ bandwidth. q_olm ~ 16s, q_nlm ~ τ! → using only
50% of bandwidth (too little slots) massively slows down NLM.
<ArneBab> the transfer times should actually be dominant
<ArneBab> though they are lower than the queue time.
<ArneBab> and freenet should get faster with faster network or lower chunk
sizes.
<ArneBab> toad_: so first step: make sure all bandwidth gets used - maybe by
allocating more slots till about 2× the current number are transferring
-*- ArneBab is happy
<digger3> cool, lot's of stuff to read tomorrow morning. :)
<ArneBab> NLM should with the current network be slower than OLM by 23%. But
in 18 month it should actually be faster by ~8%, given Moores Law holds for
upload bandwidth.
<ArneBab> :)
<ArneBab> with faster I mean time to complete a request.
<ArneBab> reaction time — latency
<ArneBab> digger3: maybe you can doublecheck the reasoning
--
Konstruktive Kritik:
- http://draketo.de/licht/krude-ideen/konstruktive-kritik
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list [email protected] http://freenetproject.org/cgi-bin/mailman/listinfo/devl
