On Sun, 07 Feb 2021 17:07:24 +0300 Greg Minshall <[email protected]> wrote:
Dear Greg, > just a comment from the outside. > > if i read get_connection_to_drop_candidate() correctly, your algorithm > selects the first, in terms of location in 'connection' array, "best" > (lowest state) candidate to drop. > > you might think of, when finding an *equally* "best" candidate, > flipping some (weighted, by?) coin, and either taking your current > candidate, or taking the newly discovered "best". as someone's > e-mail tag says, "when in doubt, randomize" :). > > (as a *research* experiment, in some other life, i might flip a coin > for *every* element in the array, based maybe on the relative states?) thanks for your input! I may have been imprecise with the description of my algorithm: Of all connection slots (where every one of them is occupied), it first finds out which in-address takes up the most (e.g. 20 connections from 127.217.17.131). Among those 20, it finds the (first) one with the smallest progression (i.e. state in this case). Indeed, this "minimizer" is not unique and we can have more than one connection from this client in the "minimal" state (e.g. 10 of those connections might be in the state C_RECV_HEADER, so not even finished with sending the request header). One could refine the algorithm to also minimize e.g. over the number of bytes received (for C_RECV_HEADER) or how much data has already been sent (for C_SEND_HEADER, C_SEND_BODY) and then find an even "better" candidate among those connections from this one greedy client, but maybe that goes too far. Your randomness approach might give a little peace of mind to select from multiple candidates, as mentioned before, but the placement in the connection-array itself is non-deterministic if a non-trivial number of clients access the server, especially near saturation, where any slot at any point in the connection-array might become free at any time. If I wanted a more refined behaviour, I'd probably just reduce my drop-candidate set further (with the previously mentioned further criteria). With this reduction, we'd be talking about 1-2 minimizers (how likely is it that we have matching byte-progresses?) which would not need a randomized approach anyway. If we still have a large set of candidates despite the refined criteria, one can reasonably assume that the client is just spamming the server with connections, and then it doesn't really matter which one of the connections we drop. Maybe I'll further refine it in the future. Thanks for reaching out and raising this very interesting point about randomization! With best regards for a nice Sunday Laslo
