On Wednesday 08 August 2007 16:45, Matthew Toseland wrote:
> On Wednesday 08 August 2007 16:42, Matthew Toseland wrote:
> > On Wednesday 08 August 2007 16:26, Matthew Toseland wrote:
> > > On Wednesday 08 August 2007 16:25, Matthew Toseland wrote:
> > > > On Wednesday 08 August 2007 16:23, Matthew Toseland wrote:
> > > > > On Wednesday 08 August 2007 16:22, Matthew Toseland wrote:
> > > > > > On Wednesday 08 August 2007 16:20, Matthew Toseland wrote:
> > > > > > > On Wednesday 08 August 2007 16:19, Matthew Toseland wrote:
> > > > > > > > On Wednesday 08 August 2007 16:17, Matthew Toseland wrote:
> > > > > > > > > On Wednesday 08 August 2007 16:05, Matthew Toseland wrote:
> > > > > > > > > > Continued at end to minimise confusion!
> > > > > > > > > >
> > > > > > > > > > On Wednesday 08 August 2007 15:59, Matthew Toseland wrote:
> > > > > > > > > > > Unfortunately this thread is rather rambling, it
> > > > > > > > > > > includes lots of discussion on token passing as well as
> > > > > > > > > > > the original premise.
> > > > > > > > > > >
> > > > > > > > > > > ----- Anonymous at o9_0DTuZniSf_+oDmRsonByWxsI -----
> > > > > > > > > > > 2007.04.25 - 20:18:36GMT -----
> > > > > > > > > > >
> > > > > > > > > > > I made some measurements on how freenet node behaves if
> > > > > > > > > > > bandwidth limit is set low: 10KBps and downto 6KBps
> > > > > > > > > > > (specificially, input bandwidth limit; output bandwidth
> > > > > > > > > > > limit was set to at least 15KBps but as expected
> > > > > > > > > > > factually used output bandwidth is comparable (just
> > > > > > > > > > > slightly above) with factually used input bandwidth).
> > > > > > > > > > > The node itself was running frost but no
> > > > > > > > > > > uploads/downloads, so absolute majority of network
> > > > > > > > > > > traffic was forwarded CHK/SSK
> > > > > > > > > > > requests/inserts.
> > > > > > > > > > >
> > > > > > > > > > > Results are interesting enough: CHK traffic becomes as
> > > > > > > > > > > low as 5% (in packets) of CHK+SSK, while at least 92%
> > > > > > > > > > > of SSK requests were not satisfied for assorted
> > > > > > > > > > > failures (plus quite some more certainly resulted in
> > > > > > > > > > > NotFound response due to missing the key in whole
> > > > > > > > > > > network, but I don't have the number). This makes low
> > > > > > > > > > > traffic node working highly inefficient and
> > > > > > > > > > > improportionally slow; this also slows down its peers
> > > > > > > > > > > with all the extra reject traffic. Worse, input
> > > > > > > > > > > bandwidth sometimes goes over set limit, suggesting
> > > > > > > > > > > that on hardware 33600/56000 Kbps modem and even ISDN
> > > > > > > > > > > things will just get worse due to increased delays.
> > > > > > > > > > >
> > > > > > > > > > > Another thing to note: low bandwidth node (LBN) almost
> > > > > > > > > > > exclusively reject requests with "input bandwidth
> > > > > > > > > > > liability" reason, and extremely rarely other reasons.
> > > > > > > > > > >
> > > > > > > > > > > Speculating a bit, the same picture will likely be
> > > > > > > > > > > observed for peers of fast node (1Mbps or more) with
> > > > > > > > > > > many peers having typical home connection of 256Kbps or
> > > > > > > > > > > less.
> > > > > > > > > > >
> > > > > > > > > > > Not sure if simulations ever showed anything like this,
> > > > > > > > > > > but contributing to network mostly SSK service (and
> > > > > > > > > > > absolute majority of SSK requests fail!) is rather
> > > > > > > > > > > useless: optimally working network is supposed to
> > > > > > > > > > > transfer at least one CHK block for each SSK key, and
> > > > > > > > > > > typically much much more (single 10MB file consists of
> > > > > > > > > > > 481 CHK blocks!), and even if you found SSK but not CHK
> > > > > > > > > > > the SSK points to, then you failed to find information
> > > > > > > > > > > you requested.
> > > > > > > > > > >
> > > > > > > > > > > OK to make the long story short[er], at the end of this
> > > > > > > > > > > message you will find a small patch that noticably
> > > > > > > > > > > improves LBN situation. Idea is to reserve some
> > > > > > > > > > > bandwidth for CHK transfers (and SSK inserts, as those
> > > > > > > > > > > are too rare to penalize, and more valuable than
> > > > > > > > > > > requests). The line directly before the inserted one
> > > > > > > > > > > implicitly penalizes CHK transfers (as much smaller SSK
> > > > > > > > > > > requests tend to rereserve bandwidth the next moment it
> > > > > > > > > > > got released after CHK transfer finish, while much
> > > > > > > > > > > larger CHK requests do not have such good chance), so
> > > > > > > > > > > bandwidth should be reserved for 2 CHKs at least (and
> > > > > > > > > > > tests show that's enough to make a difference).
> > > > > > > > > > >
> > > > > > > > > > > Another thing I tried was increasing the 90 seconds
> > > > > > > > > > > period up to 120. That had some (no numbers here; just
> > > > > > > > > > > "noticeable but small") positive effect on making
> > > > > > > > > > > traffic smoother and staying closer to set limit,
> > > > > > > > > > > without jumping up and down too much. Where the 90
> > > > > > > > > > > seconds number came from anyway, and how dangerous 120
> > > > > > > > > > > could be?
> > > > > > > > > > >
> > > > > > > > > > > Some pros observed and/or thought out during tests of
> > > > > > > > > > > the patch: - I observe increase of output payload by
> > > > > > > > > > > approx. 15% (of total traffic), making LBN more useful
> > > > > > > > > > > for its peers. - the change is negligibly small for
> > > > > > > > > > > faster nodes so should not break anything globally.
> > > > > > > > > > > - entire network SSK flood traffic will be toned down a
> > > > > > > > > > > little bit (at temporary overloaded nodes only),
> > > > > > > > > > > additionally simplifying life for LBNs: after all,
> > > > > > > > > > > requesting the same SSK every 15 seconds for 35 hours,
> > > > > > > > > > > total 8100 times (factual numbers from one of the test
> > > > > > > > > > > before this patch applied; there are over 60 other SSKs
> > > > > > > > > > > that were requested more than 1000 times during the
> > > > > > > > > > > same period) is just way too much, SSKs are not
> > > > > > > > > > > inserted into network THAT fast. [does it worth to
> > > > > > > > > > > remember recently seen SSK requests, and do not forward
> > > > > > > > > > > them if same request was already forwarded within last
> > > > > > > > > > > 10 minutes and resulted in DNF/RNF? Table of recently
> > > > > > > > > > > requested SSKs that are closest to the node location
> > > > > > > > > > > should not be too big?].
> > > > > > > > > > >
> > > > > > > > > > > And contras:
> > > > > > > > > > > - in exceptional conditions (specificially, with less
> > > > > > > > > > > than 2 incoming CHK requests per 90 seconds; factually
> > > > > > > > > > > I observe 2-7 CHK requests per seconds, that's 180-630
> > > > > > > > > > > per 90 seconds) notwithstanding node bandwidth speed,
> > > > > > > > > > > up to 800 Bps might end being unused. For high
> > > > > > > > > > > bandwidth node that's just way too small to notice, for
> > > > > > > > > > > LBN that's still acceptable (10% of 56Kbps) and will
> > > > > > > > > > > decrease roundtrip delays a bit which is always a good
> > > > > > > > > > > thing for so slow links.
> > > > > > > > > > >
> > > > > > > > > > > Other notes:
> > > > > > > > > > > - distribution of location closeness/number of SSK
> > > > > > > > > > > requests is very nice: only SSK requests with location
> > > > > > > > > > > very close to node location get repeated frequently;
> > > > > > > > > > > farther SSK location is, less requests the node sees,
> > > > > > > > > > > with those SSKs seen only once or two times per 1-2
> > > > > > > > > > > days period are distributed evenly among location
> > > > > > > > > > > space. This suggests that routing is working fine. - As
> > > > > > > > > > > far as I understand, if input bandwidth limit/liability
> > > > > > > > > > > exceeded (but a packet already received anyway),
> > > > > > > > > > > CHK/SSK request gets instantly rejected (thus throwing
> > > > > > > > > > > out received bytes while input bandwidth has no spare
> > > > > > > > > > > volume!); only otherwise node checks if the requested
> > > > > > > > > > > key exists in the storage. Heh? This feels like a
> > > > > > > > > > > serious bug hurting overall network performance: better
> > > > > > > > > > > query storage and hopefully send back result (or still
> > > > > > > > > > > reject if the key not found locally) rather than wait
> > > > > > > > > > > for retry request to waste more input bandwidth. At
> > > > > > > > > > > least for SSK reject and reply are comparable in output
> > > > > > > > > > > bandwidth usage, so worth a little delay in response.
> > > > > > > > > > > Or do I miss something?
> > > > > > > > > > >
> > > > > > > > > > > ===
> > > > > > > > > > > diff --git a/freenet/src/freenet/node/NodeStats.java
> > > > > > > > > > > b/freenet/src/freenet/node/NodeStats.java
> > > > > > > > > > > index 3b091b4..fb9f8b9 100644
> > > > > > > > > > > --- a/freenet/src/freenet/node/NodeStats.java
> > > > > > > > > > > +++ b/freenet/src/freenet/node/NodeStats.java
> > > > > > > > > > > @@ -414,6 +414,7 @@ public class NodeStats implements
> > > > > > > > > > > Persistable {
> > > > > > > > > > >
> > > > > > > > > > > successfulChkInsertBytesReceivedAverage.currentValue()
> > > > > > > > > > > * node.getNumCHKInserts() +
> > > > > > > > > > >
> > > > > > > > > > > successfulSskInsertBytesReceivedAverage.currentValue()
> > > > > > > > > > > * node.getNumSSKInserts();
> > > > > > > > > > > bandwidthLiabilityInput +=
> > > > > > > > > > > getSuccessfulBytes(isSSK, isInsert,
> > > > > > > > > > > true).currentValue(); + if (isSSK &&
> > > > > > > > > > > !isInsert)
> > > > > > > > > > > bandwidthLiabilityInput+=successfulChkFetchBytesReceive
> > > > > > > > > > >dA ve ra ge .c ur re nt Va lu
> > > > > > > > > > > e()+successfulChkInsertBytesReceivedAverage.currentValu
> > > > > > > > > > >e( ); // slightly penalize SSK requests by reserving
> > > > > > > > > > > bandwidth for 2 additional CHK transfers (or SSK
> > > > > > > > > > > inserts if any) double bandwidthAvailableInput =
> > > > > > > > > > > node.getInputBandwidthLimit() *
> > > > > > > > > > > 90; // 90 seconds at full power
> > > > > > > > > > > if(bandwidthLiabilityInput >
> > > > > > > > > > > bandwidthAvailableInput) { ===
> > > > > > > > > > >
> > > > > > > > > > > ----- toad at zceUWxlSaHLmvEMnbr4RHnVfehA ----- 2007.04.26
> > > > > > > > > > > - 16:56:59GMT -----
> > > > > > > > > > >
> > > > > > > > > > > Most SSK requests fail. They DNF. The reason for this
> > > > > > > > > > > is most SSK requests are polling for data that has not
> > > > > > > > > > > yet been inserted.
> > > > > > > > > > >
> > > > > > > > > > > Bandwidth liability is usually the main reason for
> > > > > > > > > > > rejection. If we reach most of the other reasons, there
> > > > > > > > > > > is a problem - usually a cyclical problem. The main
> > > > > > > > > > > reason for it is to ensure that we don't accept so many
> > > > > > > > > > > requests that some of them needlessly timeout even
> > > > > > > > > > > though they succeeded. The timeout is 120 seconds, so
> > > > > > > > > > > we need the actual transfer to take less than this; on
> > > > > > > > > > > a request, 30 seconds seems a reasonable upper bound
> > > > > > > > > > > for the search time. We don't throw out many bytes when
> > > > > > > > > > > we reject a request/insert because the bulk of it
> > > > > > > > > > > hasn't been sent yet, except with SSKs where typically
> > > > > > > > > > > a little under half of the total bytes will have been
> > > > > > > > > > > moved. Ideally we wouldn't send requests until we have
> > > > > > > > > > > a good idea that they will be accepted, but token
> > > > > > > > > > > passing load balancing is a long way off, not likely to
> > > > > > > > > > > happen for 0.7.0.
> > > > > > > > > > >
> > > > > > > > > > > We cannot control input bandwidth usage precisely.
> > > > > > > > > > >
> > > > > > > > > > > Any more info on SSK flooding? Is it simply Frost?
> > > > > > > > > > >
> > > > > > > > > > > We can add a failure table, we had one before, however
> > > > > > > > > > > a failure table which results in actually blocking keys
> > > > > > > > > > > can be extremely dangerous; what I had envisaged was
> > > > > > > > > > > "per node failure tables" i.e. reroute requests which
> > > > > > > > > > > have recently failed to a different node since we know
> > > > > > > > > > > it isn't where it's supposed to be.
> > > > > > > > > > >
> > > > > > > > > > > On what do you base the assertion about key closeness?
> > > > > > > > > > > It would be nice to have a histogram or circle on the
> > > > > > > > > > > stats pages showing recent keys on the keyspace - can
> > > > > > > > > > > you write a patch?
> > > > > > > > > > >
> > > > > > > > > > > As far as your patch goes, surely rejecting more SSK
> > > > > > > > > > > requests would be counterproductive as it wastes
> > > > > > > > > > > bandwidth? Shouldn't a slow node accept those requests
> > > > > > > > > > > it's likely to be able to handle?
> > > > > > > > > > >
> > > > > > > > > > > I can see an argument that we shouldn't prefer SSKs,
> > > > > > > > > > > and that on slow nodes we do prefer SSKs... I'm not
> > > > > > > > > > > sure the above is the right way to deal with it though.
> > > > > > > > > > > The effect of the patch would be to never accept any
> > > > > > > > > > > SSKs unless we have plenty of spare bandwidth, correct?
> > > > > > > > > > >
> > > > > > > > > > > ----- Anonymous at o9_0DTuZniSf_+oDmRsonByWxsI -----
> > > > > > > > > > > 2007.04.26 - 18:41:32GMT -----
> > > > > > > > > > >
> > > > > > > > > > > > Ideally we wouldn't send requests until we have a
> > > > > > > > > > > > good idea that they will
> > > > > > > > > > >
> > > > > > > > > > > be accepted, but token passing load balancing is a long
> > > > > > > > > > > way off, not likely to happen for 0.7.0.
> > > > > > > > > > >
> > > > > > > > > > > Well, even current algorithm implementation has certain
> > > > > > > > > > > room for improvement. Here is the typical numbers I
> > > > > > > > > > > observe:
> > > > > > > > > > >
> > > > > > > > > > > ===
> > > > > > > > > > > unclaimedFIFO Message Counts
> > > > > > > > > > > * FNPRejectOverload: 89 (45.2%)
> > > > > > > > > > > * FNPInsertTransfersCompleted: 59 (29.9%)
> > > > > > > > > > > * FNPDataNotFound: 15 (7.6%)
> > > > > > > > > > > * packetTransmit: 12 (6.1%)
> > > > > > > > > > > * FNPRejectLoop: 7 (3.6%)
> > > > > > > > > > > * FNPAccepted: 6 (3.0%)
> > > > > > > > > > > * FNPSwapRejected: 4 (2.0%)
> > > > > > > > > > > * FNPDataInsertRejected: 4 (2.0%)
> > > > > > > > > > > * FNPRouteNotFound: 1 (0.5%)
> > > > > > > > > > > * Unclaimed Messages Considered: 197
> > > > > > > > > > > ===
> > > > > > > > > > >
> > > > > > > > > > > FNPRejectOverload always stays at top sometimes with
> > > > > > > > > > > hundreds messages (for the last hour before unclaimed
> > > > > > > > > > > messages expire, that's alot), and so indicates that
> > > > > > > > > > > there is some bug (or bugs) with bandwidth limiting
> > > > > > > > > > > obeying.
> > > > > > > > > > >
> > > > > > > > > > > > Any more info on SSK flooding? Is it simply Frost?
> > > > > > > > > > >
> > > > > > > > > > > Not local frost for sure, it generates just several SSK
> > > > > > > > > > > simultaneous requests (by default max 8: 6 for boards
> > > > > > > > > > > plus 2 for filesharing, AFAIR; practically 2-4
> > > > > > > > > > > simutaneous requests most of the time). Other 100 SSK
> > > > > > > > > > > requests (without proposed patch) are forwarded ones.
> > > > > > > > > > >
> > > > > > > > > > > >We can add a failure table, we had one before, however
> > > > > > > > > > > > a failure table which
> > > > > > > > > > >
> > > > > > > > > > > results in actually blocking keys can be extremely
> > > > > > > > > > > dangerous;
> > > > > > > > > > >
> > > > > > > > > > > Is it, having timeout of max few minutes (i.e. at least
> > > > > > > > > > > few times less than SSK propagation time visible with
> > > > > > > > > > > frost messages)? Is it more dangerous than current
> > > > > > > > > > > wastage of bandwith for same SSK key requests several
> > > > > > > > > > > times per minute? Had some simulations been done on
> > > > > > > > > > > that in the past?
> > > > > > > > > > >
> > > > > > > > > > > BTW, isn't the observed very low store hit rate results
> > > > > > > > > > > from prioritising the likely-to-fail SSKs?
> > > > > > > > > > >
> > > > > > > > > > > BTW2 the failure table could also act as a targetted
> > > > > > > > > > > content propagation mechanism: if a node sees SSK
> > > > > > > > > > > insert for a temporary blacklisted (non-existing) SSK,
> > > > > > > > > > > then forwarding the insert (more likely insert copy,
> > > > > > > > > > > for security reasons and routing sake) to the original
> > > > > > > > > > > requestor should speed up propagaton of new SSKs toward
> > > > > > > > > > > the nodes that already anticipate/await for them.
> > > > > > > > > > >
> > > > > > > > > > > >what I had envisaged was "per node failure tables"
> > > > > > > > > > > > i.e. reroute requests
> > > > > > > > > > >
> > > > > > > > > > > which have recently failed to a different node since we
> > > > > > > > > > > know it isn't where it's supposed to be.
> > > > > > > > > > >
> > > > > > > > > > > At a glance, very nice idea. But LBNs typically answer
> > > > > > > > > > > with reject, not DFN... even with current code.
> > > > > > > > > > > Probably such rerouting will even further increase SSK
> > > > > > > > > > > traffic toward LBNs, and get sharply increased volume
> > > > > > > > > > > of SSK rejects as result. Hmm, some testing/simulation
> > > > > > > > > > > seems really needed here.
> > > > > > > > > > >
> > > > > > > > > > > >On what do you base the assertion about key closeness?
> > > > > > > > > > > > It would be nice to
> > > > > > > > > > >
> > > > > > > > > > > have a histogram or circle on the stats pages showing
> > > > > > > > > > > recent keys on the keyspace - can you write a patch?
> > > > > > > > > > >
> > > > > > > > > > > Mmmm... in fact I just added custom logging, then a
> > > > > > > > > > > wild combination of grep/sed/sort/uniq to analyze the
> > > > > > > > > > > logs. But let me think, maybe visualizing a couple of
> > > > > > > > > > > stats files I operate with will be rather trivial...
> > > > > > > > > > >
> > > > > > > > > > > But I would rather stay away from stats page graphics
> > > > > > > > > > > at this time, as the stats files I operate
> > > > > > > > > > > (filtered+sorted+uniqued) with are rather large,
> > > > > > > > > > > 20-50Mb each - too much memory for the toy. Unless your
> > > > > > > > > > > 'recent' means just 10-15 minutes at most?
> > > > > > > > > > >
> > > > > > > > > > > >As far as your patch goes, surely rejecting more SSK
> > > > > > > > > > > > requests would be
> > > > > > > > > > >
> > > > > > > > > > > counterproductive as it wastes bandwidth?
> > > > > > > > > > >
> > > > > > > > > > > Tests show the opposite: without the patch payload
> > > > > > > > > > > output at stats page never exceeded 38%, with patch it
> > > > > > > > > > > becomes 53% or little more after several minutes upon
> > > > > > > > > > > node restart. So, with the patch SSK/CHK forwarding
> > > > > > > > > > > behaviour 'feels' logical:
> > > > > > > > > > >
> > > > > > > > > > > without patch:
> > > > > > > > > > > - just several CHKs, and over over 100 SSKs very
> > > > > > > > > > > typical.
> > > > > > > > > > >
> > > > > > > > > > > with patch:
> > > > > > > > > > > - most of the time (say, 75%) number of currently
> > > > > > > > > > > forwarded CHK requests+inserts approximately equals to
> > > > > > > > > > > the number of SSK requests+inserts (i.e. 10-25 each,
> > > > > > > > > > > depending on set bandwidth limit); - sometimes (say,
> > > > > > > > > > > 10%) CHK requests start to prevail, but current SSK
> > > > > > > > > > > requests+inserts seems never go below the amount which
> > > > > > > > > > > CHK get at max without patch (i.e. 6-10). This is very
> > > > > > > > > > > typical when number of CHK inserts gets several times
> > > > > > > > > > > higher than CHK requests (close fast peer inserts
> > > > > > > > > > > something really large?). - other times (say, 15%) CHK
> > > > > > > > > > > requests+inserts flow does not saturate bandwidth, and
> > > > > > > > > > > number of SSK requests quickly climbs to 50 or even
> > > > > > > > > > > over 100+ as it typically gets without the patch.
> > > > > > > > > > >
> > > > > > > > > > > That's for LBN. Raising input bandwidth allotment,
> > > > > > > > > > > number of SSKs quickly grows resembling the situation
> > > > > > > > > > > without the patch.
> > > > > > > > > > >
> > > > > > > > > > > So that's why I suggest reserving bandwidth for 2 CHK
> > > > > > > > > > > transfers; 3 would kill SSKs, 1 still makes SSKs to
> > > > > > > > > > > seriously prevail over CHKs (but nonetheless gives
> > > > > > > > > > > quite better ratio, so is a legal value to try if the
> > > > > > > > > > > value of 2 alarms you too much). Just, in case of
> > > > > > > > > > > reserving bandwidth for 1 extra CHK the proposed patch
> > > > > > > > > > > is not really needed: simply comment out the line
> > > > > > > > > > > starting with "bandwidthLiabilityInput +=" and decrease
> > > > > > > > > > > 90 seconds constant to 80 (10 seconds is roughly how
> > > > > > > > > > > much 33.6Kbod modem takes to transmit a single CHK -
> > > > > > > > > > > using anything noticeably slower than 28800/33600bod
> > > > > > > > > > > for freenet will not ever work well anyway).
> > > > > > > > > > >
> > > > > > > > > > > >Shouldn't a slow node accept those requests it's
> > > > > > > > > > > > likely to be able to handle?
> > > > > > > > > > >
> > > > > > > > > > > Considering the very high chance of SSK request
> > > > > > > > > > > failures (at lest 92%), I would say the answer is no.
> > > > > > > > > > > But with sane SSK failure rate (say 75% or below) SSK
> > > > > > > > > > > requests would likely not waste the limited thus
> > > > > > > > > > > precious LBN bandwidth so fruitlessly.
> > > > > > > > > > >
> > > > > > > > > > > The problem, in my belief, is too small size of UDP
> > > > > > > > > > > packets if SSK requests prevail: PPP(oE)/TCP/FNP
> > > > > > > > > > > overhead becomes too large while LBNs, unlike faster
> > > > > > > > > > > link nodes, almost never coalesce packets, obviously.
> > > > > > > > > > >
> > > > > > > > > > > ----- toad at zceUWxlSaHLmvEMnbr4RHnVfehA ----- 2007.04.27
> > > > > > > > > > > - 17:19:24GMT -----
> > > > > > > > > > >
> > > > > > > > > > > The current algorithm is working, on most nodes, far
> > > > > > > > > > > better than it has in *ages*. I'm at 62% of a 700MB
> > > > > > > > > > > ISO, I started inserting it yesterday morning, and only
> > > > > > > > > > > a few of my peers are backed off - frequently none are
> > > > > > > > > > > backed off, right now it's 11 connected, 6 backed off,
> > > > > > > > > > > which is more backed off than I've seen for quite a
> > > > > > > > > > > while.
> > > > > > > > > > >
> > > > > > > > > > > Re failure tables: Yes it is extremely dangerous. It
> > > > > > > > > > > can result in self-reinforcing key censorship, either
> > > > > > > > > > > as an attack or just occurring naturally. This happened
> > > > > > > > > > > on 0.5. And the hit ratio is only for CHKs iirc.
> > > > > > > > > > >
> > > > > > > > > > > Even LBNs don't often send local RejectedOverload's on
> > > > > > > > > > > SSKs *once they have accepted them*. They may relay
> > > > > > > > > > > downstream RO's but that is not fatal. And if they
> > > > > > > > > > > reject some requests, so what, it's a slow node, it's
> > > > > > > > > > > bound to reject some requests with the current load
> > > > > > > > > > > balancing system.
> > > > > > > > > > >
> > > > > > > > > > > 10-15 minutes would be interesting. We already show a
> > > > > > > > > > > circle and histogram of nearby nodes from swapping and
> > > > > > > > > > > of our peers, you'd just have to add another one. It
> > > > > > > > > > > would be good to have a visual proof that routing is
> > > > > > > > > > > working on the level of adhering to node
> > > > > > > > > > > specialisations. I didn't expect it to be working given
> > > > > > > > > > > the load: I'm surprised that it does, it's an
> > > > > > > > > > > interesting result.
> > > > > > > > > > >
> > > > > > > > > > > Packet size has nothing to do with it, ethernet has a
> > > > > > > > > > > 1472 byte maximum. Dial-up has 576 bytes max, but we
> > > > > > > > > > > ignore it, and use fragmented packets (this sucks,
> > > > > > > > > > > obviously, as it greatly increases the chance of losing
> > > > > > > > > > > a packet and having to retransmit it).
> > > > > > > > > > >
> > > > > > > > > > > Please explain why the patch doesn't result in never
> > > > > > > > > > > accepting a single SSK?
> > > > > > > > > > >
> > > > > > > > > > > ----- Anonymous at o9_0DTuZniSf_+oDmRsonByWxsI -----
> > > > > > > > > > > 2007.04.27 - 19:31:14GMT -----
> > > > > > > > > > >
> > > > > > > > > > > >Packet size has nothing to do with it, ethernet has a
> > > > > > > > > > > > 1472 byte maximum.
> > > > > > > > > > >
> > > > > > > > > > > Dial-up has 576 bytes max, but we ignore it, and use
> > > > > > > > > > > fragmented packets (this sucks, obviously, as it
> > > > > > > > > > > greatly increases the chance of losing a packet and
> > > > > > > > > > > having to retransmit it).
> > > > > > > > > > >
> > > > > > > > > > > I am talking about typical/average packet size, not
> > > > > > > > > > > MTU. LBNs, unlike faster nodes, rarely have a chance to
> > > > > > > > > > > coalesce reject responses (over max 100ms), and thus
> > > > > > > > > > > send improportionally more tiny packets resulting in
> > > > > > > > > > > much higher protocols overhead. Thus having LBNs to
> > > > > > > > > > > mostly cater SSKs not CHKs results in lowest imaginable
> > > > > > > > > > > usefulness of LBNs for network as a whole.
> > > > > > > > > > >
> > > > > > > > > > > BTW in my experience typical/default dialup/PPP MTU is
> > > > > > > > > > > 1500 minus link level headers, like ethernet. 576 is a
> > > > > > > > > > > reasonable adjustment for interactive traffic like ssh
> > > > > > > > > > > but I fail to remember if it was used as default since
> > > > > > > > > > > the time the super fast 28800 bod modems became common.
> > > > > > > > > > >
> > > > > > > > > > > :) 1400+ is the typical size of GPRS PPP packets too,
> > > > > > > > > > > : and the same
> > > > > > > > > > >
> > > > > > > > > > > holds true for other popular wireless mediae like
> > > > > > > > > > > BlueTooth or WiFi; so I have no concerns regarding IP
> > > > > > > > > > > fragmentation.
> > > > > > > > > > >
> > > > > > > > > > > > Please explain why the patch doesn't result in never
> > > > > > > > > > > > accepting a single SSK?
> > > > > > > > > > >
> > > > > > > > > > > I can not. :) Can you explain why the current code that
> > > > > > > > > > > penalizes CHKs still gives 5% for them, even if CHKs
> > > > > > > > > > > are 25 times larger and similarly less frequent so have
> > > > > > > > > > > really hard time to arrive at the exact moment when
> > > > > > > > > > > bandwidth liability is not maxed out?
> > > > > > > > > > >
> > > > > > > > > > > Seriously, I believe that goes with 2 facts:
> > > > > > > > > > >
> > > > > > > > > > > - SSK requests are much more frequent, so any temporary
> > > > > > > > > > > drop of CHK requests level enables node to quickly get
> > > > > > > > > > > a bunch of new SSKs accepted for processing;
> > > > > > > > > > > - the large CHK requests (at times while they prevail
> > > > > > > > > > > over SSKs) tend to hit other limits too, like "output
> > > > > > > > > > > bandwidth liability", "Insufficient input/output
> > > > > > > > > > > bandwidth" throttles. Then the small SSK requests
> > > > > > > > > > > quickly pick up all the remaining bandwidth bits.
> > > > > > > > > > >
> > > > > > > > > > > But currently I do not have relevant statistics to
> > > > > > > > > > > prove that.
> > > > > > > > > > >
> > > > > > > > > > > Anyway, please commit the following patch - it should
> > > > > > > > > > > equal out bandwidth rights for CHKs and SSKs at least
> > > > > > > > > > > half way toward fair/expected distribution (and the
> > > > > > > > > > > change will make any difference for high-/over-loaded
> > > > > > > > > > > nodes only). Once most of my peers (and their peers)
> > > > > > > > > > > update, I will study the new node traffic forwarding
> > > > > > > > > > > efficiency and behavior at different bandwidth limits
> > > > > > > > > > > and with different penalization levels again - and then
> > > > > > > > > > > will be in better position to prove the original
> > > > > > > > > > > proposal of reserving bandwidth for 2 CHKs is optimal
> > > > > > > > > > > (or maybe withdraw it).
> > > > > > > > > > >
> > > > > > > > > > > ===
> > > > > > > > > > > diff --git a/freenet/src/freenet/node/NodeStats.java
> > > > > > > > > > > b/freenet/src/freenet/node/NodeStats.java
> > > > > > > > > > > index 3b091b4..98c82c3 100644
> > > > > > > > > > > --- a/freenet/src/freenet/node/NodeStats.java
> > > > > > > > > > > +++ b/freenet/src/freenet/node/NodeStats.java
> > > > > > > > > > > @@ -399,9 +399,8 @@ public class NodeStats implements
> > > > > > > > > > > Persistable {
> > > > > > > > > > >
> > > > > > > > > > > successfulSskFetchBytesSentAverage.currentValue() *
> > > > > > > > > > > node.getNumSSKRequests() +
> > > > > > > > > > >
> > > > > > > > > > > successfulChkInsertBytesSentAverage.currentValue() *
> > > > > > > > > > > node.getNumCHKInserts() +
> > > > > > > > > > >
> > > > > > > > > > > successfulSskInsertBytesSentAverage.currentValue() *
> > > > > > > > > > > node.getNumSSKInserts();
> > > > > > > > > > > - bandwidthLiabilityOutput +=
> > > > > > > > > > > getSuccessfulBytes(isSSK, isInsert,
> > > > > > > > > > > false).currentValue(); double bandwidthAvailableOutput
> > > > > > > > > > > = -
> > > > > > > > > > > node.getOutputBandwidthLimit() * 90; // 90 seconds at
> > > > > > > > > > > full power; we have to leave some time for the search
> > > > > > > > > > > as well +
> > > > > > > > > > > node.getOutputBandwidthLimit() * 80; // 80 seconds at
> > > > > > > > > > > full power; we have to leave some time for the search
> > > > > > > > > > > as well bandwidthAvailableOutput *=
> > > > > > > > > > > NodeStats.FRACTION_OF_BANDWIDTH_USED_BY_REQUESTS;
> > > > > > > > > > > if(bandwidthLiabilityOutput >
> > > > > > > > > > > bandwidthAvailableOutput) {
> > > > > > > > > > > preemptiveRejectReasons.inc("Output bandwidth
> > > > > > > > > > > liability"); @@ -413,9 +412,8 @@ public class NodeStats
> > > > > > > > > > > implements Persistable {
> > > > > > > > > > >
> > > > > > > > > > > successfulSskFetchBytesReceivedAverage.currentValue() *
> > > > > > > > > > > node.getNumSSKRequests() +
> > > > > > > > > > >
> > > > > > > > > > > successfulChkInsertBytesReceivedAverage.currentValue()
> > > > > > > > > > > * node.getNumCHKInserts() +
> > > > > > > > > > >
> > > > > > > > > > > successfulSskInsertBytesReceivedAverage.currentValue()
> > > > > > > > > > > * node.getNumSSKInserts();
> > > > > > > > > > > - bandwidthLiabilityInput +=
> > > > > > > > > > > getSuccessfulBytes(isSSK, isInsert,
> > > > > > > > > > > true).currentValue(); double bandwidthAvailableInput =
> > > > > > > > > > > - node.getInputBandwidthLimit() *
> > > > > > > > > > > 90; // 90 seconds at full power
> > > > > > > > > > > + node.getInputBandwidthLimit() *
> > > > > > > > > > > 80; // 80 seconds at full power
> > > > > > > > > > > if(bandwidthLiabilityInput >
> > > > > > > > > > > bandwidthAvailableInput) {
> > > > > > > > > > > preemptiveRejectReasons.inc("Input bandwidth
> > > > > > > > > > > liability"); return "Input bandwidth liability"; ===
> > > > > > > > > > >
> > > > > > > > > > > ----- toad at zceUWxlSaHLmvEMnbr4RHnVfehA ----- 2007.04.28
> > > > > > > > > > > - 17:05:53GMT -----
> > > > > > > > > > >
> > > > > > > > > > > Why does assuming 80 seconds instead of 90 help? I
> > > > > > > > > > > would have expected it to make the situation worse.
> > > > > > > > > > >
> > > > > > > > > > > Isn't what you want to increment the value you are
> > > > > > > > > > > multiplying the CHK byte counters by if the request is
> > > > > > > > > > > an SSK? In any case I'm not convinced - we accept 32x
> > > > > > > > > > > as many SSKs as CHKs precisely because they use 32x
> > > > > > > > > > > less bandwidth. As far as I can see incrementing the
> > > > > > > > > > > CHK counts but only on a CHK would just result in us
> > > > > > > > > > > never accepting an SSK...
> > > > > > > > > > >
> > > > > > > > > > > But by all means continue to investigate.
> > > > > > > > > > >
> > > > > > > > > > > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 -----
> > > > > > > > > > > 2007.04.30 - 19:36:36GMT -----
> > > > > > > > > > >
> > > > > > > > > > > > we accept 32x as many SSKs as CHKs precisely because
> > > > > > > > > > > > they use 32x less
> > > > > > > > > > >
> > > > > > > > > > > bandwidth.
> > > > > > > > > > >
> > > > > > > > > > > Sorry but I don't understand the rationale behind this.
> > > > > > > > > > > It seems to be based on the assumption that equal
> > > > > > > > > > > resources should be allocated to SSKs and CHKs,
> > > > > > > > > > > regardless of whether there's equal demand for
> > > > > > > > > > > resources. If we're only getting, say, 16 times as many
> > > > > > > > > > > SSK requests as CHK requests, would we reject CHK
> > > > > > > > > > > requests to keep things "fair"?
> > > > > > > > > > >
> > > > > > > > > > > ----- toad at zceUWxlSaHLmvEMnbr4RHnVfehA ----- 2007.05.02
> > > > > > > > > > > - 16:13:52GMT -----
> > > > > > > > > > >
> > > > > > > > > > > Why should CHKs be prioritised over SSKs?
> > > > > > > > > > >
> > > > > > > > > > > What do you think of the patch I committed anyway?
> > > > > > > > > >
> > > > > > > > > > ----- Anonymous at o9_0DTuZniSf_+oDmRsonByWxsI -----
> > > > > > > > > > 2007.05.02 - 17:03:52GMT -----
> > > > > > > > > >
> > > > > > > > > > > Why should CHKs be prioritised over SSKs?
> > > > > > > > > >
> > > > > > > > > > Because SSK success ratio is extremely low (remember the
> > > > > > > > > > example I gave within initial message in the thread: 8100
> > > > > > > > > > rejected requests for the same SSK key within 35 hours,
> > > > > > > > > > and uncounted amount of the same key requests resulted in
> > > > > > > > > > DNF - and such key is nowhere near being alone); linear
> > > > > > > > > > programming would certainly suggest that SSK requests
> > > > > > > > > > like they currently are should be totally disabled. I do
> > > > > > > > > > not propose anything as drastic; but as SSKs currently
> > > > > > > > > > use bandwidth very
> > > > > > > > > > inefficiently I propose to tone them down heuristically
> > > > > > > > > > to approximately CHK level while node is short on
> > > > > > > > > > bandwidth (but let SSKs go as much as sending node needs
> > > > > > > > > > if spare bandwidth available).
> > > > > > > > > >
> > > > > > > > > > [not that I meant to speak instead of mrogers]
> > > > > > > > > >
> > > > > > > > > > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 -----
> > > > > > > > > > 2007.05.03 - 13:54:38GMT -----
> > > > > > > > > >
> > > > > > > > > > >> Why should CHKs be prioritised over SSKs?
> > > > > > > > > > >
> > > > > > > > > > > Because SSK success ratio is extremely low
> > > > > > > > > >
> > > > > > > > > > That doesn't make sense for two reasons:
> > > > > > > > > >
> > > > > > > > > > 1) rejecting SSKs will make the SSK success ratio worse,
> > > > > > > > > > not better 2) "SSK not found" is useful information - for
> > > > > > > > > > example, that's how you discover the current version of a
> > > > > > > > > > USK - but "SSK rejected for not being a CHK" is not
> > > > > > > > > > useful to anyone
> > > > > > > > > >
> > > > > > > > > > Let me use an analogy: you're designing a Cisco router.
> > > > > > > > > > Some of the packets it gets asked to forward will be
> > > > > > > > > > small SSH packets, others will be large HTTP packets. Do
> > > > > > > > > > you say "half our resources should go to SSH because we
> > > > > > > > > > don't want to prioritise HTTP, so we'll only forward one
> > > > > > > > > > HTTP packet for every 32 SSH packets"? If you answered
> > > > > > > > > > yes, you just lost your job at Cisco. The router's job is
> > > > > > > > > > to deliver packets to the best of its ability, not to
> > > > > > > > > > decide what kind of packets the end hosts "should" be
> > > > > > > > > > sending.
> > > > > > > > >
> > > > > > > > > ----- Anonymous ----- 2007.05.03 - 18:37:00GMT -----
> > > > > > > > >
> > > > > > > > > lets build an extreme case:
> > > > > > > > > There is a packet type which is 1 MB in size and one which
> > > > > > > > > is 1 byte in size. Both get constantly send to a router at
> > > > > > > > > a higher rate then the routers bandwidth quota allows it to
> > > > > > > > > forward the packets. If the following rules apply not a
> > > > > > > > > single 1 MB packet will get served: 1. the router doesn't
> > > > > > > > > care for the size of the packet or penalises any kind of
> > > > > > > > > packet, all are considered equal 2. if a packet arrives and
> > > > > > > > > the remaining bandwidth quota doesn't allow to forward it,
> > > > > > > > > it gets instantly rejected 3. no queueing of incomming
> > > > > > > > > packets is done (with
> > > > > > > > > part-allocation of available bandwidth if packet size
> > > > > > > > > exceed the free quota)
> > > > > > > > >
> > > > > > > > > Afaik this is a possible situation for freenet, correct me
> > > > > > > > > if I am wrong.
> > > > > > > >
> > > > > > > > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.05.04 -
> > > > > > > > 11:15:09GMT -----
> > > > > > > >
> > > > > > > > You're right, that pretty much describes the problem. I'm
> > > > > > > > suggesting that we should fix it by modifying step 2:
> > > > > > > >
> > > > > > > > 2. if a packet arrives and the remaining bandwidth quota
> > > > > > > > doesn't allow to forward *an average packet*, it gets
> > > > > > > > instantly rejected
> > > > > > > >
> > > > > > > > The average is calculated over all packets, large and small.
> > > > > > > > In other words we ask:
> > > > > > > >
> > > > > > > > a) how much bandwidth does a packet use, on average?
> > > > > > > > b) is there enough bandwidth for another average packet?
> > > > > > > >
> > > > > > > > Let's say 75% of packets are 1 byte in size and 25% are 1 MB
> > > > > > > > in size, so the average is 262,144.75 bytes. We accept
> > > > > > > > packets (large or small) if we have at least 262,144.75 bytes
> > > > > > > > of bandwidth left in the quota, and reject them otherwise. If
> > > > > > > > there's a long stream of 1 byte packets followed by a 1 MB
> > > > > > > > packet we might go over quota temporarily, but we'll match
> > > > > > > > the quota in the long term.
> > > > > > > >
> > > > > > > > ----- Anonymous at o9_0DTuZniSf_+oDmRsonByWxsI ----- 2007.05.10
> > > > > > > > - 21:01:58GMT -----
> > > > > > > >
> > > > > > > > Oh no, getting stuff instantly rejected is most often not
> > > > > > > > good (an exception would be certain kinds of realtime
> > > > > > > > traffic, but that is not applicable for freenet at all). I
> > > > > > > > have some experience with independant/competing ISPs and
> > > > > > > > their broken traffic shaping routers that were always
> > > > > > > > dropping packets not fitting current shaping limits; TCP
> > > > > > > > performance was
> > > > > > > > experiencing major hit there, and several TCP connections
> > > > > > > > running under the same shaping were always taking seriously
> > > > > > > > unfair bandwidth share (unless you get quite long intervals
> > > > > > > > for stats, like 10+ minutes). Changing shaping processing by
> > > > > > > > queueing an over-quota packet (even a single packet queue!)
> > > > > > > > till the calculated average bandwidth allows to send the
> > > > > > > > packet (thus in the end increasing roundtrip slightly) was
> > > > > > > > always sufficient for TCP flow to work at 100% of the shaped
> > > > > > > > level, and having simultaneous TCP streams to very equally
> > > > > > > > share available bandwidth even for sub-second stats
> > > > > > > > intervals, and there were no other working solution found
> > > > > > > > (aside raising the shaping limit above the maximum speed of
> > > > > > > > TCP peers).
> > > > > > > >
> > > > > > > > I am not sure that can be directly applied to the current
> > > > > > > > freenet networking code; honestly, the mechanism of first
> > > > > > > > quickly accepting packets and then slowly picking them using
> > > > > > > > some kind of filters looks unneccessary complicated and
> > > > > > > > performance inoptimal, to say least: I have another bright
> > > > > > > > example why - the mechanism quite resembles the traditional
> > > > > > > > O/S network packets handling (with received packets extracted
> > > > > > > > from NIC at highest priority - during hardware interrupt, and
> > > > > > > > then having CPU/server business logic failing to process all
> > > > > > > > received packets leading to internal queues overflow), and
> > > > > > > > after years and decades it is generally agreed that such
> > > > > > > > approach does not work well for server applications; instead,
> > > > > > > > linux for several years already has mechanism named NAPI
> > > > > > > > (which is optional for some NIC drivers - check kernel
> > > > > > > > config, but default and mandatory for most server-grade
> > > > > > > > and/or 1Gb NIC drivers): hardware interrupt just sets a
> > > > > > > > flag/semaphore that NIC has received something, and instantly
> > > > > > > > quits leaving the particular NIC interrupt line disabled
> > > > > > > > (actual algorithm is a little bit more complex, allowing
> > > > > > > > hardware interrupt to perform extraction of a very limited
> > > > > > > > number of packets if the host is very idle). Then there is a
> > > > > > > > lowest priority kernel thread ("software interrupt") woken up
> > > > > > > > by the flag/semaphore starts reading packets from NIC into
> > > > > > > > O/S queues (where user-level read()s get satisfied from),
> > > > > > > > extracting only limited number of packets at a time (then
> > > > > > > > yielding CPU for other runnable processes), and reenabling
> > > > > > > > the NIC interrupts only when it managed to empty the hardware
> > > > > > > > queue - with TCP flow control, and with the modern ethernet
> > > > > > > > hardware flow control that works exceptionally well. Thus
> > > > > > > > server business logic (i.e. useful work) running at priority
> > > > > > > > much higher than software interrupt thread is never starved
> > > > > > > > from CPU by hardware interrupts that first pull in packets
> > > > > > > > which then result in CPU wasted to drop them from overflown
> > > > > > > > system queue - resulting in smooth behaviour and best
> > > > > > > > sustained performance.
> > > > > > > >
> > > > > > > > Or in short - on overload, delaying input packets
> > > > > > > > reading/processing is better than dropping or rejecting them
> > > > > > > > instantly.
> > > > > > > >
> > > > > > > > Toad - if you know a simple way to delay freenet reads from
> > > > > > > > UDP socket in order to enforce configured input bandwidth
> > > > > > > > limit, please do so. (And with that UDP read delay, I would
> > > > > > > > be very interested to test freenet node without other input
> > > > > > > > bandwidth limiters aside input bandwidth liability used -
> > > > > > > > chances that the UDP socket read delay will be sufficient for
> > > > > > > > quality shaping, with the valuable help of sending node
> > > > > > > > tracking the roundtrip - an already well implemented
> > > > > > > > feature).
> > > > > > > >
> > > > > > > > If the delay can not be done easily with the current
> > > > > > > > codebase, I will consider doing major rewrite of the traffic
> > > > > > > > accepting code part. Not of highest priority tho, due to
> > > > > > > > anticipated large amount of work - but those high fruits look
> > > > > > > > big and tasty.
> > > > > > >
> > > > > > > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.05.11 -
> > > > > > > 14:56:37GMT -----
> > > > > > >
> > > > > > > > I am not sure that can be directly applied to the current
> > > > > > > > freenet networking
> > > > > > >
> > > > > > > code;
> > > > > > >
> > > > > > > We're working on an idea called token-passing that's supposed
> > > > > > > to address this: you can only send a search (request/insert) to
> > > > > > > a peer if you have a flow control token from that peer. If you
> > > > > > > don't have a token you either keep the search in a queue until
> > > > > > > you receive a token, or send it to the next-best peer if the
> > > > > > > queue is full.
> > > > > > >
> > > > > > > > the mechanism quite resembles the traditional O/S network
> > > > > > > > packets handling
> > > > > > >
> > > > > > > (with received packets extracted from NIC at highest priority -
> > > > > > > during hardware interrupt, and then having CPU/server business
> > > > > > > logic failing to process all received packets leading to
> > > > > > > internal queues overflow)
> > > > > > >
> > > > > > > Interesting point - in the new congestion control layer, maybe
> > > > > > > the UDP reader shouldn't advance the receiver window until the
> > > > > > > internal queues have dropped below a certain size... but it
> > > > > > > might be tricky to implement because the internal queues all
> > > > > > > belong to different threads...
> > > > > > >
> > > > > > > > If the delay can not be done easily with the current
> > > > > > > > codebase, I will
> > > > > > >
> > > > > > > consider doing major rewrite of the traffic accepting code
> > > > > > > part.
> > > > > > >
> > > > > > > This is due to be rewritten soon anyway, so now's probably a
> > > > > > > good time to make suggestions.
> > > > > > >
> > > > > > > ----- Anonymous at o9_0DTuZniSf_+oDmRsonByWxsI ----- 2007.05.14 -
> > > > > > > 16:46:24GMT -----
> > > > > > >
> > > > > > > While token passing would indeed smooth the traffic out, it
> > > > > > > feels excessive:
> > > > > > >
> > > > > > > - it adds extra traffic;
> > > > > > > - it creates additional traffic patterns, that quite simplify
> > > > > > > attacks (like those aiming at reliably proving that a
> > > > > > > particular request originates from attacked node) against a
> > > > > > > node which all connections are monitored (by ISP), and some of
> > > > > > > them are fast but compromised (compromised peers).
> > > > > > > - it requires to pull a multidimensional set of heurictics on
> > > > > > > whom to send new token out of a thin air, and those heuristics
> > > > > > > will tend to disagree for different connection types.
> > > > > > >
> > > > > > > The method of delaying network reads (thats important - and
> > > > > > > AFAIK the only major missing thing to get shaping rolling
> > > > > > > smoothly already) should work similarly well (might be even
> > > > > > > better): just consider the metric 'the current peer roundtrip
> > > > > > > time is lower than the [peer] average roundtrip time' as
> > > > > > > equivalence of 'the peer gave us few tokens', and enjoy the
> > > > > > > bandwidth/crypt(CPU) free virtual token passing which obeys
> > > > > > > both hardware/ISP traffic shaping imposed limits, as well as
> > > > > > > software configured limits - whichever is stricter.
> > > > > > >
> > > > > > > So I currently discorage implementing explicit token passing,
> > > > > > > in favor of lower, equially tasty fruit.
> > > > > >
> > > > > > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.05.17 -
> > > > > > 21:40:27GMT -----
> > > > > >
> > > > > > > - it adds extra traffic
> > > > > >
> > > > > > Um, right. "Here are n tokens" takes about 6 bytes: two for the
> > > > > > message type, two for the message size, and two for the number of
> > > > > > tokens (we're never going to hand out more than 65535 tokens in
> > > > > > one go). It uses less traffic than "Can I send you a request?"
> > > > > > "Yes" "Here's the request", and it avoids a round-trip. It also
> > > > > > uses less traffic than "Can I send you a request?" "No", because
> > > > > > if you don't have a token, you don't need to ask!
> > > > > >
> > > > > > > - it creates additional traffic patterns, that quite simplify
> > > > > > > attacks (like
> > > > > >
> > > > > > those aiming at reliably proving that a particular request
> > > > > > originates from attacked node) against a node which all
> > > > > > connections are monitored (by ISP), and some of them are fast but
> > > > > > compromised (compromised peers).
> > > > > >
> > > > > > Please explain how handing my peer some tokens reveals anything
> > > > > > about traffic patterns that wasn't already visible to traffic
> > > > > > analysis. If they can see the requests and results going back and
> > > > > > forth, who cares if they can also see the tokens?
> > > > > >
> > > > > > > - it requires to pull a multidimensional set of heurictics on
> > > > > > > whom to send
> > > > > >
> > > > > > new token out of a thin air, and those heuristics will tend to
> > > > > > disagree for different connection types.
> > > > > >
> > > > > > No magical heuristics are needed - we hand out tokens as long as
> > > > > > we're not overloaded (measured by total queueing delay, including
> > > > > > the bandwidth limiter). That alone should be enough to outperform
> > > > > > the current system, because we'll avoid wasting traffic on
> > > > > > rejected searches. Then we can start thinking about clever token
> > > > > > allocation policies to enforce fairness when the network's busy,
> > > > > > without imposing unnecessary limits when the network's idle, etc
> > > > > > etc. But token passing doesn't depend on any such policy - it's
> > > > > > just a lower-bandwidth alternative to pre-emptive rejection.
> > > > >
> > > > > ----- toad at zceUWxlSaHLmvEMnbr4RHnVfehA ----- 2007.05.19 -
> > > > > 17:38:09GMT -----
> > > > >
> > > > > We hand out tokens when we're not overloaded? What if later on we
> > > > > get overloaded? How exactly do we determine the total appropriate
> > > > > number of tokens in the system?
> > > > >
> > > > > Token passing would be really nice, it would solve the flooding
> > > > > problem and remove a lot of alchemy...
> > > >
> > > > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.05.20 -
> > > > 11:19:36GMT -----
> > > >
> > > > We determine the appropriate number of tokens by experimentation: as
> > > > we approach overload we produce tokens more and more slowly, until at
> > > > the overload point we don't produce tokens at all. For example, delay
> > > > between producing tokens = MAX_DELAY/(MAX_DELAY - currentDelay)
> > > > seconds, or something similar.
> > > >
> > > > We stop producing tokens when all the buckets are full. To limit the
> > > > number of tokens in circulation, we adjust the bucket sizes. Each
> > > > peer's bucket starts at size 0, and is reset to 0 whenever the peer
> > > > reconnects. Whenever we add a token to an empty bucket, we increase
> > > > its size by 1. Thus if a peer doesn't use the tokens we give it (ie
> > > > doesn't empty its bucket), its bucket stays small. If it uses the
> > > > tokens we give it (ie empties its bucket), we increase the size of
> > > > its bucket as long as we're not overloaded (the bucket size is only
> > > > increased when a token is handed out, which doesn't happen when we're
> > > > overloaded).
> > >
> > > ----- Anonymous at o9_0DTuZniSf_+oDmRsonByWxsI ----- 2007.05.25 -
> > > 11:45:36GMT -----
> > >
> > > Even this brief description proposes 3 heuristics already:
> > >
> > > - "more slowly or something similar"
> > > - "adjust bucket sizes"
> > > - "stays small"
> > >
> > > No doubts complete practical implementation will involve quite more,
> > > and I see no way to ensure they will all work smoothly for all the wide
> > > variety of connection types.
> > >
> > > This also totally silences the burst problems, as well as decreasing
> > > buckets during the bursts/overload periods. Kinda extreme case: if you
> > > gave a node 5 tokens, and it decided to use them 3 minutes later when
> > > the node got overloaded, what did you gain with the tokens? That is a
> > > true Pandora box.
> > >
> > > In the end it is timing that matters, while tokens represent data
> > > amount (and if you think of a formula time*bandwidth=data, then
> > > bandwidth, generally speaking, is not constant due to highly irregular
> > > traffic from different peers and other apps sharing the same internet
> > > connection). Purely controlling the latter will always be just a rough
> > > approximation of controlling the former, alas.
> >
> > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.05.25 - 17:20:00GMT
> > -----
> >
> > > I see no way to ensure they will all work smoothly for all the wide
> > > variety
> >
> > of connection types
> >
> > That may be true, but can you ensure that with the current mechanism?
> >
> > > if you gave a node 5 tokens, and it decided to use them 3 minutes later
> > > when
> >
> > the node got overloaded, what did you gain with the tokens?
> >
> > It shouldn't ever reach that point, because when you give out 4 tokens
> > and get a burst that nearly overloads the node, you'll stop increasing
> > the size of the buckets.
> >
> > > Purely controlling the latter will always be just a rough approximation
> > > of
> >
> > controlling the former, alas.
> >
> > True, it's only a rough approximation and traffic is bursty and we can't
> > predict the future, but all those things also apply to the current
> > system.
>
> ----- Anonymous at o9_0DTuZniSf_+oDmRsonByWxsI ----- 2007.05.25 -
> 20:35:30GMT -----
>
> - I gave 4 tokens to peer A, and 4 tokens for peer B;
> - peer A used up the token in one burst, causing local bandwidth overage
> already.
> - now if peer B decides to use up the tokens, my bandwidth is already
> flooded badly.
>
> - I gave 2 tokens (generally: very small amount) to peer A, and 2 tokens to
> peer B at this time;
> - the peer A used up both of them, but peer B does not have anything to
> request for now.
> - as result, the available bandwidth is only half-loaded until peer A
> explicitly given another few tokens; but giving away small amounts of
> tokens puts traffic overhead (often in form of small sized packets with
> highest overhead), and speed of feeding small packs of tokens is seriously
> limited by roundtrip delays.
>
> Thus nothing is really gained with tokens, and fighting that situation
> sounds fruitless, and the only reasonable approach is to control the
> roundtrip delay instead of fighting it, by delaying network reads as needed
> to shape incoming traffic. This gives sending node not just boolen flag
> can/cannot send immediatelly, but certain number to estimate optimal
> outgoing interpacket delay toward a particular peer.
>
> ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.05.26 - 19:31:25GMT
> -----
>
> You're making the jump from 0 to 4 tokens as if there are no intermediate
> stages. If 4 searches are enough to overload the node, then after you give
> 2 tokens each to A and B, you'll get a burst and stop increasing the size
> of the buckets. You should never reach a situation where there are more
> tokens in circulation than you can handle simultaneously.
>
> You're also confusing the number of tokens with the size of the buckets
> (probably my fault for not explaining it properly). If you give 2 tokens
> each to A and B, and A uses its tokens but B doesn't, you're free to give 2
> more tokens to A; there's no reason for A to starve just because B is
> holding tokens. The only effect of B holding tokens is to limit the size of
> the bursts you can get from A to a level that will be safe even if you
> simultaneously get a burst from B. To avoid making these limits too strict,
> we start with small buckets and only increase the size of a bucket when
> it's empty, so idle peers are limited to smaller bursts than active peers,
> but the total burst size is still limited to what we can handle.
>
> Obviously we should also have TCP-style congestion control between peers,
> but that's not sufficient for network-wide load limiting in my opinion (eg
> look at the original Gnutella, which used TCP between peers but still had
> massive load limiting problems).
----- toad at zceUWxlSaHLmvEMnbr4RHnVfehA ----- 2007.05.26 - 23:07:42GMT -----
How do we determine the maximum bucket size?
Gnutella's load problems were architectural because of it broadcasting - but
they do illustrate an important point, which is that you must throttle at the
request stage, not just on bytes in general.
----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.05.27 - 14:56:13GMT
-----
We slowly increase the bucket sizes until we get close to overload (measured
using the total delay between deciding to forward a search and the search
actually leaving the node). Then we have two choices:
1) Assume that capacity is fairly constant: don't increase the bucket sizes
again unless there's a major change in circumstances (eg the user increases
the bandwidth limit).
2) Ongoing adjustment: occasionally increase the size of a bucket, possibly
provoking a timeout, to discover unused capacity; return to the previous
level if a timeout occurs.
The first approach is more conservative and requires less alchemy. The second
might get bettter performance.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL:
<https://emu.freenetproject.org/pipermail/tech/attachments/20070808/7d45f2c5/attachment.pgp>
