I'll answer this on Frost to avoid breaking the thread (unless Anonymous is on the mailing list).
The short answer is "argh". ;-) Cheers, Michael 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
