I could not find this discussion on the frost board any longer. Did it continue? Then I'd be happy if someone could post it to the list or send me a copy. :-)
Also regarding the blocking-sockets method to let a node delay requests. This seems to have some sideeffects to me that may be unwanted later on. If Freenet would need a QoS mechanism or OOB data (some sort of control messages with higher priority) -- wouldnt blocking socket reads entirely for limiting requests also block these out? But I still find the idea interesting to delay traffic when the load is high rather than preemptively rejecting it. This would simplify adapting greedy routing to take delays into account (e.g. only having to consider delays as the extra factor when making routing decisions at a node will simplify things a lot by incorporating both the effect from link delay and node load). This is what I'm currently working on.. regards, Vilhelm On Mon, Jun 18, 2007 at 04:40:16PM +0100, Matthew Toseland wrote: > MRogers and Anonymous have been arguing that we should limit load only on the > immediate bandwidth level. Some of the thread is below, and my response > including a proposal for a bandwidth limiting mechanism: > > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.06.14 - 21:32:43GMT > ----- > > No, what I've been arguing is that we don't need to *explicitly* take the > lifetime overhead into account, because the feedback loop should be slow > enough that it will *implicitly* take it into account anyway. If the feedback > loop takes a few minutes to adapt (which it must if we don't want to > over-adapt to short-term conditions) then we're implicitly measuring the > lifetime overhead of a search, and we don't need to make an additional > explicit estimate of the lifetime overhead. > > ----- toad at zceUWxlSaHLmvEMnbr4RHnVfehA ----- 2007.06.15 - 17:12:52GMT ----- > > What makes you think it would work at all? It seems to me that it would > simply > oscillate - we accept too many requests, most of them time out, the we accept > too many requests again, and most of them timeout again. KISS is one thing, > but not slitting your own throat with occam's razor is another! > > ----- mrogers at UU62+3E1vKT1k+7fR0Gx7ZN2IB0 ----- 2007.06.15 - 21:44:34GMT > ----- > > :) If the feedback loop is slow enough it shouldn't oscillate - that applies > equally to bandwidth liability estimation, token passing or any other > mechanism - we musn't get into the situation of saying "I accepted 100 > requests in the last 10 seconds and nothing bad has happened yet, therefore I > can accept another 100". As far as I can see, the only way to avoid that > situation is by adapting very slowly, ie on the order of the longest timeout. > Luckily we expect the connections to be relatively long-lived (minutes or > hours) so we can afford to take a few minutes to get up to speed. > > Assuming that we have a suitably slow feedback loop in place, the next > question is how to tell our peers when we're ready to accept another search. > We could use tokens, preemptive rejection or blocking sockets. I don't have > any religious opinions on this issue, but I thought Anonymous made a fairly > good case for handling it in the same way as any other network app: don't > read from the socket until you're ready to process more data. I realise > there's a highly variable relationship between bytes in and bytes out, but > regardless of which mechanism we use we'll have to rely on the slow feedback > loop to smooth that out, because so far nobody's suggested a way of dealing > with it that doesn't involve favouring some kinds of traffic over others. (I > hope we agree that we don't want the whole network to end up favouring SSK > traffic over CHK traffic just because it happens to come in smaller quanta. > Maybe there are reasons for giving SSK traffic priority, but that isn't one > of them.) > > ----- toad at zceUWxlSaHLmvEMnbr4RHnVfehA ----- 2007.06.18 - 14:25:49GMT ----- > > It's not possible using the mechanism you propose *on its own*, while it *is* > interesting. Here's why: I have 48kB/sec output. With your proposed > mechanism, the fact that I have 1MB/sec input won't matter. So a leaf node > requests a splitfile through me, which is all in the network, but is not in > my datastore. I route his requests. It takes 5 seconds for enough of the > requests to start transferring to make a difference. Over that 5 seconds, > he's sent me 240kB of requests. That's around 240k/50 = 4,915 requests. Which > will yield 160MB of data. Unfortunately it will take me 160M/48k = nearly an > hour to transfer all the data. > > This is not acceptable, because we want Freenet requests to complete in a > reasonable amount of time - if only for fproxy support, which IMHO is an > important application. And I don't like the idea of having different request > priorities either; it gives away information on the traffic and allows for > Bad Things. > > Imposing an arbitrary limit on the number of requests running is not the > solution either. A limit may be imposed because of threads/memory usage, but > this is likely to be heavily architecture dependant. The solution IMHO is to > take into account likely future bandwidth usage. If we want to guarantee that > there are no timeouts, this means bandwidth liability limiting. The current > code will accept an SSK request only if it could also accept a CHK request, > and vice versa, so I don't see any reason to think it is excessively biased > in favour of CHKs. However if you like I will add code to collect the > probability of rejection for SSKs and CHKs individually. > > For data blocks, clearly we cannot send one if there is no available space in > the congestion window to the peer in question. However we may want the data > for ourself, or for multiple peers, in which case the slowest peer should not > necessarily dictate the transfer rate; AFAICS we must accept the data as fast > as we can manage within memory/cpu/etc limits, and limit the incoming > bandwidth at a higher level. > > So given that we must limit traffic on the request level (as well as the > congestion control level), how can we do this? We can either: > > A) Wait for a request, and then either accept it or reject it, based on e.g. > how many requests are running already. > PRO: > - Simple > CON: > - Wasteful of time and bandwidth when we have to ask multiple peers before > one > accepts > - Difficult to adapt to propagate load back to source > > Queueing doesn't help much here because we still have to complete the > request - including queueing it - in a reasonable time. > > or > > B) Tell our peers when they can send us a request. The obvious way to do this > is to compute our overall quota of requests (or request-success-bytes), and > allocate it to our peers (and tell them on every packet/response/etc), > initially equally, but progressively allowing more to busier nodes and less > to nodes that don't use their quota (but with diminishing returns: a node > with a low quota that suddenly starts using more will take quota away from an > established heavy requestor). Thus, initially, if most nodes aren't busy we > won't run many requests, but as we identify those nodes which need a bigger > quota, more requests run overall. Note that running fewer requests than we > could isn't necessarily a problem anyway unless they complete really slowly. > > How to avoid excessive misrouting? > Options: > 1: We don't need to queue requests, as they are queued on the next node for > us > (running requests can be regarded as queued requests). When we get a request, > we identify the set of nodes that we are willing to route it to, and if none > of them have any free request slots, we reject it. > 2: Queueing requests helps, because we can match requests with nodes. When we > get a request, (if it's allowable by the node's current quota), we queue it. > When we have a slot in an outgoing node's quota, we send the request which is > closest to the node's location (which hasn't already been to that node), > regardless of the time it's been queued for (if multiple nodes have space, we > find the best request/node pair until they don't or we run out of requests). > If after a certain period a request hasn't been sent, we reject it. This > avoids excessive misrouting without requiring arbitrary parameters (as the > first option does), and sends more specialised requests to slower nodes. > 3: Simulated queueing: remember the locations of recent requests we could > have > sent to a node, and calculate a threshold, which decays over time if we don't > accept a request (obviously this will result in fewer requests being sent, > but lower latency). > > Does this prevent flooding? Yes: we only accept, and offer, as many requests > as we can handle, and with the right fairness algorithms, a flood will be > limited to what the other peers don't need, although if our overall quota > calculation is too generous flooding may still be an effective attack. > Obviously on opennet, connecting to several hundred peers and flooding to > each of them will be fairly effective; opennet sucks, we all know this, it's > a transition phase. > > Does this propagate load back to the originator? Not explicitly, as it's not > an originator-throttles scheme (such schemes don't prevent flooding and may > make it easier to identify the originator). However, the rate at which a node > can send requests is quite clearly limited by the rate at which the rest of > the network can handle them: > > O - A - B - C > > If B is a bottleneck, then O will only send requests at the rate that can be > funneled through it (or satisfied on A). > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 187 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20070808/bb7ae98c/attachment.pgp>
