On Wednesday 03 Jul 2013 02:09:22 Vladislav Sterzhanov wrote: > Greetings once again, I suddenly realised (thanks, toad), that the last > report was ages ago, so will make up for it. > _______________________________________________________________ > Quick outline: > Proposals: > - Current Congestion Window Validation (RFC 2861) problems and > solutions for them > - Cummulative acknowledgements > - Appropriate_Byte_Counting-oriented congestion window adjustements > (RFC 3465) > - Fast retransmission and loss recovery (RFC 5681) > - Slow start and congestion avoidance (RFC 5681) > Discussion: > - Packet vs Byte size of congestion window and packets in flight > - Forward RTO-Recovery (RFC 5682) > _______________________________________________________________ > > | Concerning CWV: Original RFC promotes two crucial ideas: > 1) If we received ack for a packet, but we didn't utilize the full window > when we actually sent it to the node (we were application-limited rather > than network-limited) - we should not increase the window size, but instead > shrink it since we can't be sure, could the link hold such window or not. > This shrink should be done immideately after sending the last packet that > doesn't fill up the window. > 2) If the application was idle for N RTO periods - the window should be > shrinked for each of those N - the previous window size can't be trusted as > relevant anymore.
The RFC says to shrink it by half for each RTT. (Subject to the usual arbitrary minimum etc). > Two major problems here: > Current implementation of CWV (PacketThrottle.notifyOfPacketAcknowledged()) > checks the size of a window *after* receiving an ack for packet, when it > should check for the state of the window *when the packet was sent* - could > be solved simply by adding a bitflag to SentPacket. I don't follow, above you talk about when we receive an ack. > Since it only makes this check on receiving an ack - it does not handle the > second principle - PacketThrottle simply is not notified about idle > periouds, but it should be. Ugh, the code is hideous. I've just removed the _packetSeqWindowFullChecked/_packetSeq stuff; the old packet format is gone, so this should not be used... Which leaves: // If we didn't use the whole window, shrink the window a bit. // This is similar but not identical to RFC2861 // See [freenet-dev] Major weakness in our current link-level congestion control int windowSize = (int)getWindowSize(); ... // Ensure that we the window size does not grow dramatically larger than the largest window // that has actually been in flight at one time. if(_windowSize > maxWindowSize) _windowSize = (float) maxWindowSize; This is what you were thinking of? Which isn't exactly what RFC 2861 says, partly because we don't explicitly track individual RTT windows; it wasn't obvious how to directly implement RFC 2861. But yes it looks like this should be implemented at send time from the RFC, and needs some changes... > > | Cummulative acks: > The main principle holds the same as in the previous report, just to > formalize it a bit: > - Make range acknowledgement the default one. We can leave a bitflag for > individual acks and decide which will be more efficient for each packet. > - Save the delta compression, but provide the possibility to ack wide > ranges also - I see it as [[B|range1-begin][B|range1-end] > [B|range2-begin][B|range2-end]], where B signifies the size of the next > value (far / near). > - Include already acked packets in the ack-range if it reduces the total > cost. Yes, this is all fine. I suppose it's okay to include a later ack in the ack timings, if the first ack was lost, rather than resending the packet? > - Possibly include duplicate acks even if it increases the overall cost, > depending on the per-link stats. (This one feels foggy - too much of a > strange heuristic) > > | ABC - the main message is that we should increase the window size not by > some constant multiple every time we receive an ack, but instead depend on > the amount of new data that it acknowledges (the behaviour varies depending > on whether we are in slow-start on in congestion avoidance phase). But we > need to decide about the units that window size is measured in (see below) > - otherwise there will not be much sence in it. Okay, I haven't read the RFC yet. > > | Fast retransmission. I was a bit confused with it: This freenet-wiki > page<https://wiki.freenetproject.org/Transport_Layer>states that fred > implements the fast retransmission logic, but I didn't > manage to find any.. Nothing in NPFCK, which is responsible for everything > concerning message ids. Is it really unimplemented or I am just looking in > the wrong direction? Yes, IIRC we don't do fast recovery. Fast recovery = when we receive an ack for packet 2 and 4 we assume packet 3 is lost and resend it immediately? > | Fast recovery: also nothing for this part of TCP congestion control. Need > to be implemented. > | Slow-start -- Congestion avoidance: as soon as we leave slow-start, we > never return to it again in context of a single link - we should, at least > for the purposes of fast recovery. Yes, I think this is a known bug. :( > > So now for the points that I'd like to discuss: > > | Packet vs Byte size: not sure about current status of this discussion, > the last description of it that I've seen was in the comments to > NPFCK.countSentPackets() - if there was something more recent - please, let > me know. *IMHO*, changing it to bytes will give *much* more precise control > over the link. In any case, there is *very* significant difference from the > point of the already implemented algos and the ones outlined here whether > there are currently N max-sized packets in flight, or just N left-overs or > ack-only packets, much shorter than maxPacketSize. Thoughts? But of course > it will create some difficulties, e.g. what to consider a "full" window? I > propose considering the window full if it utilizes > (window - > window%maxPacketSize bytes) - quite natural. Yes, I started to try to implement byte-based congestion control some years ago. It got awfully complicated, and the code was quite different then. IMHO it's not worth looking at the old attempt. A closely related issue: Small packets cause efficiency problems, because we have largish headers. We may want to allow congestion control to make us send small packets, but there has to be a lower bound ... > > | F-RTO algo: not very trivial logic to outline here, but it allows to > detect the cases where the retransmission timeout was spurious - we could > wait a while more and the ack would arrive. Could possibly help especially > over high-latency and high-bandwith links. Have someone looked through it - > could it be usefull for us? This is a more sophisticated form of fast retransmission? Sounds interesting. > > You are welcome to ask if something is not clear for you - I'm falling > asleep, so sorry in advance. I'll try to read the RFCs soon. Got lots of stuff to catch up on still...
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list [email protected] https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
