tasklwIP - A Lightweight TCP/IP stack - Tasks: task #14128, Appropriate byte counting/stretch...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

task #14128: Appropriate byte counting/stretch ACK support

Submitter:  Joel Cunningham <jcunningham>
Submitted:  Mon 22 Aug 2016 04:15:28 PM UTC
   
 
Category:  TCP Should Start On:  Mon 22 Aug 2016 12:00:00 AM UTC
Should be Finished on:  Mon 22 Aug 2016 12:00:00 AM UTC Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  jcunningham Percent Complete:  100%
Open/Closed:  Closed Planned Release:  2.1.0
Effort:  0.00

Jump to the original submission

Thu 20 Apr 2017 09:02:17 PM UTC, comment #32: 

Committed in de90d03e483010be770d03d65e34792046b39c6d

Joel Cunningham <jcunningham>
Group Member
Thu 20 Apr 2017 08:54:52 PM UTC, comment #31: 

Oh, right. How could I have missed that ;-)

Simon Goldschmidt <goldsimon>
Group administrator
Thu 20 Apr 2017 08:53:09 PM UTC, comment #30: 

My change adds two variables:

u32_t rto_end
tcpwnd_size_t bytes_acked

So that's 8 bytes when tcpwnd_size_t is a u32_t

Joel Cunningham <jcunningham>
Group Member
Thu 20 Apr 2017 08:49:30 PM UTC, comment #29: 

I don't get why it requires 8 bytes for LWIP_WND_SCALE==1, but I'll check after you pushed.

Simon Goldschmidt <goldsimon>
Group administrator
Thu 20 Apr 2017 08:41:14 PM UTC, comment #28: 

Cool.

Simon Goldschmidt <goldsimon>
Group administrator
Thu 20 Apr 2017 08:36:07 PM UTC, comment #27: 

I did find a 2 byte hole.  unsent_oversize included 2 bytes of padding.  Tests done with MSVC.  So if we are building with LWIP_WND_SCALE set to 0, bytes_acked can go in this hole, otherwise with LWIP_WND_SCALE set to 1, it goes after the hole (and doesn't create any new hole since tcpwnd_size_t is 4 bytes).  Here's my testing:

With LWIP_WND_SCALE set to 0, pcb is 156 bytes before ABC patch and 160 bytes after.  With LWIP_WND_SCALE set to 1, pcb is 212 bytes before ABC patch and 220 bytes after

I'll update my patch to put bytes_acked after unsent_oversize and push it

Joel Cunningham <jcunningham>
Group Member
Thu 20 Apr 2017 07:25:38 PM UTC, comment #26: 

Looks good to me now :-)
Code increasement should be neglibigle.
RAM increasement of tcp_pcb might even be lowered to 4 bytes increasement by putting the new variables in a better place to fix existing alignment holes (if there are any left)?

Simon Goldschmidt <goldsimon>
Group administrator
Wed 19 Apr 2017 09:27:24 PM UTC, comment #25: 

New patched attached that removes options and old cwnd growth code

(file #40445)

Joel Cunningham <jcunningham>
Group Member
Wed 19 Apr 2017 05:36:16 PM UTC, comment #24: 

I think the only valid reason to keep it as an option would be to get a small stack vs. a faster stack. I don't know how much code is added by this patch, but I think TCP has grown quite a but since 1.2.0 (just an example version to compare to).

Simon Goldschmidt <goldsimon>
Group administrator
Wed 19 Apr 2017 04:42:09 PM UTC, comment #23: 

 > Looks good, too. The downside is that this is another option noone will ever change. Since the default is 'enabled', maybe it's better to just use it and dump the old behaviour? All the #if code looks so ugly...

I'm fine with removing the old behavior, which would mean we don't need an LWIP_TCB_ABC option. I suppose I was just being conservative about the changes :)

> Oh, and regarding comment #16: how much sense does it make to configure the limit if we only allow integers? The only possible settings seem to be '1' or '2', reading the RFC.


Someone being more experimental could set the LIMIT to a higher value than 2 to support stretch ACKs spanning more than 2 segments, even though that's against the RFC's guidance.  Maybe having this as an option is over-thinking/engineering it.  We could just use 2 for now and then revisit it as an option if there is desire/feedback from users.  What do you think?

Joel Cunningham <jcunningham>
Group Member
Tue 18 Apr 2017 08:12:40 PM UTC, comment #22: 

Looks good, too. The downside is that this is another option noone will ever change. Since the default is 'enabled', maybe it's better to just use it and dump the old behaviour? All the #if code looks so ugly...

Oh, and regarding comment #16: how much sense does it make to configure the limit if we only allow integers? The only possible settings seem to be '1' or '2', reading the RFC.

Simon Goldschmidt <goldsimon>
Group administrator
Thu 13 Apr 2017 12:43:04 AM UTC, comment #21: 

New patch (0001-tcp-task-14128-Appropriate-Byte-Counting-support.patch) implementing additional RTO tracking requirement and adding a unit test for RTO tracking.

I've also updated the defaults in opt.h to enable ABC and set limit to 2.  This should give best performance by default and I think matches our discussion.

Please review when time permits, thanks!

(file #40384)

Joel Cunningham <jcunningham>
Group Member
Fri 31 Mar 2017 04:38:55 PM UTC, comment #20: 

Just pushing them is fine.

Simon Goldschmidt <goldsimon>
Group administrator
Fri 31 Mar 2017 03:13:23 PM UTC, comment #19: 

Ping!  I've got a couple of de-duplication changes in TCP unit tests.  Want me to post patches here or just push them?  No functional changes, just elimination of bunch of duplicate setup code repeated per test

Joel Cunningham <jcunningham>
Group Member
Thu 23 Mar 2017 06:30:16 PM UTC, comment #18: 

Here's an update on the additional RTO support.  My idea of checking unsent/unacked queue against pcb->snd_nxt isn't 100% full-proof because snd_nxt may be advanced if new segments are sent during the RTO period given the cwnd opens enough.  I can provide some examples if this isn't easily understood

My next idea is to simply record the ending byte of all the segments that are scheduled for RTO, which would be the last seqno on the unacked queue + segment length.  Then check when this is no longer in any of our unsent/unacked queues, we know the RTO is complete.  This should be accurate and perform well.  We will need to add an additional u32_t to the pcb though

I plan on adding a unit test to exercise this RTO tracking to ensure it's correct.  I'd like to do some de-duplication of some of functionality in test_tcp.c.  Should I post those as patches here or just commit them?

Joel Cunningham <jcunningham>
Group Member
Wed 15 Mar 2017 02:40:48 PM UTC, comment #17: 

Simon,

Thanks for catching L=1*SMSS following a RTO.  I'll account for this in an updated patch.  I think we can appropriately detect this scenario by checking the unsent queue for segments where the sequence number is less than pcb->snd_nxt.  This would only happen after an RTO and all unacked segments have been moved back to the unsent queue

In terms of TCP_ABC_LIMIT.  I was thinking of leaving it as an option in order to allow for a port to use L of 1 in cases where they want ABC to protect against ACK division, but not deviate from RFC 5681 (which recommends cwnd += min(acked, 1*SMSS).  Leaving L as configurable also would allow a port to account for a larger number (> 2*SMSS) of stretch ACKs if there is a scenario where this is desirable/valid

Joel Cunningham <jcunningham>
Group Member
Tue 14 Mar 2017 07:14:37 AM UTC, comment #16: 

Hmm, seems to me that it would be good to have this enabled. Code size increasement/slowdown is tiny, the only real downside is the added 'bytes_acked' member. But I'm OK with enabling this: otherwise, probably noone would enable it and noone would get the performance benefits.

As to TCP_ABC_LIMIT: does it really make sense to have this as an option in opt.h? We'd have to limit it to 2 then (see chapter "Choosing the Limit") and prevent 0.

Next, how is the part of "In this situation [RTO], a TCP MUST use L=1*SMSS" handled if we allow configuring the limit to != 1.

Simon Goldschmidt <goldsimon>
Group administrator
Mon 13 Mar 2017 10:11:02 PM UTC, comment #15: 

Any thoughts on the defaults?

Joel Cunningham <jcunningham>
Group Member
Wed 08 Mar 2017 10:22:53 PM UTC, comment #14: 

Simon,

I can add the LWIP_ to TCP_ABC and TCP_ABC_LIMIT.

Did you have any thoughts on the defaults for those settings?  I figure for new features maybe they should be off by default.  There is evidence that other stacks have this particular feature on by default (see netbsd investigation)

Joel Cunningham <jcunningham>
Group Member
Wed 08 Mar 2017 07:47:45 PM UTC, comment #13: 

The implementation looks fine, but pelase add "LWIP_" to new defines to prevent confusion with other libraries (I wish we could enforce this on all defines, but that will break ports or require a huge portiability-define-file...)

Simon Goldschmidt <goldsimon>
Group administrator
Tue 07 Mar 2017 05:40:00 AM UTC, comment #12: 

I did some more investigation of NetBSD and it has two sysctl variables that control ABC, tcp.abc.enable and tcp.abc.aggressive.  With NetBSD 7.0.2, both of these are set to 1, indicating ABC is on by default and is using an L value of 2 * SMSS.  Hopefully this is helpful in evaluating what our defaults for LwIP should be

I have attached a first-round patch of implementing ABC. I've added some options to control ABC functionality and the limit.  I'm doing some performance analysis testing now, but the patch should be functionally correct according to RFC behavior.

I have done a couple of test cases so far, the first is sendmsg test sending 256KB to a Windows 7 receiver.  With ABC, you can see the congestion window is larger by the end of the transfer.  Strangely, we don't get to see the advancement during slow start because LwIP is getting stuck with an super low ssthresh of 8192 when Windows is using receive window auto-tuning.

A second test I've done is run the 'stat' command from the shell which generates a bunch of telnet data, which ends up generating between 1-2 full sized segments and some other runt segments.  You can see ABC appropriately byte counting in this situation

(file #39912, file #39913, file #39914, file #39915)

Joel Cunningham <jcunningham>
Group Member
Sat 04 Mar 2017 12:04:02 AM UTC, comment #11: 

I'm further down the rabbit hole now.

Turns out that Linux also had a previous implementation that was closer to ABC as described in the RFC except for one strange behavior: It only incremented cwnd once a full segment had been received (or two full segments in the L = 2 * SMSS case).  You can see the man page description of the feature here (under tcp_abc):

http://man7.org/linux/man-pages/man7/tcp.7.html

I found posts on the mailing list where the feature was eventually disabled by default because it penalized small application writes and then removed in ca2eb5679f8ddffff60156af42595df44a315ef0.  http://www.spinics.net/lists/netdev/msg122950.html

I also found that NetBSD has an implementation of ABC which matches pretty closely to the RFC and was what I was thinking of for LwIP (see tcp_reno_newack):

http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/netinet/tcp_congctl.c?rev=1.23&content-type=text/x-cvsweb-markup&only_with_tag=MAIN

Joel Cunningham <jcunningham>
Group Member
Fri 03 Mar 2017 08:45:00 PM UTC, comment #10: 

Mailing list post, including patch: http://marc.info/?l=linux-netdev&m=138324287502447&w=2

Unfortunately, there seems to be no discussion of the burstiness tradeoff per RTT by employing ABC with no limit.

I don't have a concrete understanding of how often stretch ACKs (where the span is greater than 2 SMSS) occurrs, but I've observed some instances to suggest it does exist in the wild (though large packet loss could also explain the behavior)

Given that delayed ACKs are very common, including LwIP, I would say we should be supporting stretch ACKs up to 2 SMMS.  In terms of going beyond that, I'm not sure if I have enough data to show it's a good tradeoff

Joel Cunningham <jcunningham>
Group Member
Fri 03 Mar 2017 07:52:24 PM UTC, comment #9: 

Simon,

Thanks for the reminder, my mistake.  I'll just stick to providing links

Ambroz,

From my reading of the code, the Linux implementation specifically chose to not limit how many stretch ACK's it accepts for cwnd adjustment.  The comment even mentions that ABC recommends N 2, while they support N N.  So yes they are not following the guidance in both RFC 5681 and 3465, but it is intentional.  I may do some more digging in the commit history to see if there is more justification for not following the RFCs

Joel Cunningham <jcunningham>
Group Member
Fri 03 Mar 2017 06:56:15 PM UTC, comment #8: 

Seems like Linux does not bound the CWND increase for a single ACK, this seems wrong. RFC 5681 "RECOMMEND"s:

cwnd += min(N, SMSS)
where N is the number of previously unacknowledged bytes acknowledged in the incoming ACK.

I think to accommodate stretch ACK, change SMSS to 2*SMSS here, but I don't see a reason to leave it unbounded like in Linux.

Ambroz Bizjak <abizjak>
Fri 03 Mar 2017 06:44:26 PM UTC, comment #7: 

Please do keep in mind Linux is GPL, we are BSD. We cannot copy from Linux and I don't think posting Linux source code here is a good thing to do.

I'm not saying we can't discuss other OSes behaviour, just not copy&paste from GPL code.

Simon Goldschmidt <goldsimon>
Group administrator
Fri 03 Mar 2017 06:41:20 PM UTC, comment #6: 

Here's what Linux's tcp_cong.c is doing:


/* Slow start is used when congestion window is no greater than the slow start
 * threshold. We base on RFC2581 and also handle stretch ACKs properly.
 * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but
 * something better;) a packet is only considered (s)acked in its entirety to
 * defend the ACK attacks described in the RFC. Slow start processes a stretch
 * ACK of degree N as if N acks of degree 1 are received back to back except
 * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and
 * returns the leftover acks to adjust cwnd in congestion avoidance mode.
 */
u32 tcp_slow_start(struct tcp_sock *tp, u32 acked)
{
        u32 cwnd = min(tp->snd_cwnd + acked, tp->snd_ssthresh);

        acked -= cwnd - tp->snd_cwnd;
        tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp);

        return acked;
}
EXPORT_SYMBOL_GPL(tcp_slow_start);


Joel Cunningham <jcunningham>
Group Member
Fri 03 Mar 2017 06:25:57 PM UTC, comment #5: 

Thanks for the heads up Ambroz.  RFC 5681 references RFC 3465 in "section 3.1.  Slow Start and Congestion Avoidance".  I believe LwIP implements correctly most of slow start/congestion avoidance/fast recovery, but I haven't done a full audit.  I've just noticed the issue with cwnd being susceptible to ACK division and performing sub-optimal when stretch ACKs are used (common case is delayed ACKs)

RFC 5681 appears to only recommend updating cwnd according to cwnd += min (N, SMSS), though it acknowledges that RFC 3465 allows increasing by more.  This covers the ACK division security issue, but not compensating from delayed ACKs.

I don't see any particular issue with compensating for a 2 * MSS stretch ACK, but welcome other thoughts on the matter

Joel Cunningham <jcunningham>
Group Member
Fri 03 Mar 2017 06:13:41 PM UTC, comment #4: 

Hi everyone,

Perhaps RFC 5681 is more relevant here, it is newer and includes specific provisions regarding updates of cwnd and ssthresh. I've looked at the Linux code some time ago and it seems pretty close to the RFC, though I think it's more complex because it tries to be "better".

https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cong.c

Also I have my own implementation of things described in RFC 5681 (Slow Start, Congestion Avoidance, Fast Recovery) and RFC 6582 (NewReno). Perhaps it may be of use to anyone, but it's not extensively tested.

https://github.com/ambrop72/aprinter/blob/ipstack/aipstack/tcp/IpTcpProto_output.h#L440
(and look for other places where cwnd is used)

Ambroz Bizjak <abizjak>
Fri 03 Mar 2017 05:46:26 PM UTC, comment #3: 

I'd like to target this for 2.1.0 and can put together a patch

Specifically I'd like to start by addressing a stretch ACK from TCP's using delayed ACKs, which is a limit of up to 2 * MSS 

The issue of handling spans larger than 2 MSS will require more investigation and study.  I think Linux does accept more than 2 MSS, but RFC 3465 lists this as a MUST NOT

Joel Cunningham <jcunningham>
Group Member
Tue 23 Aug 2016 02:01:55 PM UTC, comment #2: 

Simon,

Yes I plan on working on adding this support, but it could be a little while before I can post some patches.  I wanted to get the issue on everyone's radar and coordinate with anyone else who may be running into this

Joel Cunningham <jcunningham>
Group Member
Tue 23 Aug 2016 11:54:36 AM UTC, comment #1: 

Does the fact that this is assigned to you mean you're working on it? That would be good to know :-)

Simon Goldschmidt <goldsimon>
Group administrator
Mon 22 Aug 2016 04:15:28 PM UTC, original submission:  

LwIP currently doesn't implement appropriate byte counting when making adjustments to the congestion window during slow start.  RFC 3465 outlines both security and performance issues with the initial slow start implementation

I've run into the performance issue when LwIP sends data to clients that use stretch ACKs.  Typically ACK stretching is used with delayed ACKs, which only send 1 ACK per 2 MSS packets, but I've seen empirically both Windows 7 and OS X stretch large number of ACKs (OS X stretched 11 ACKs in one test).

LwIP's slow start implementation increments the congestion window by pcb->mss regardless of how much was actually ACKed.  When stretch ACKs are used the congestion window will grow much slower during slow start.

LwIP is also vulnerable to what the RFC calls "ACK Division":


This scheme involves the receiver sending multiple ACKs
for each incoming data segment, each ACKing only a small portion of
the original TCP data segment.  Since TCP senders have traditionally
used ACK counting to increase cwnd, ACK division causes
inappropriately rapid cwnd growth and, in turn, a potentially
inappropriate sending rate.


Joel Cunningham <jcunningham>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by abizjak (Posted a comment)
  • -email is unavailable- added by goldsimon (Updated the item)
  • -email is unavailable- added by jcunningham (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    Follow 14 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-04-20 jcunningham StatusIn Progress Done
        Percent Complete0% 100%
        Open/ClosedOpen Closed
    2017-04-19 jcunningham Attached File- Added 0001-tcp-task-14128-Appropriate-Byte-Counting-support-NO-OPTIONS.patch, #40445
    2017-04-13 jcunningham Attached File- Added 0001-tcp-task-14128-Appropriate-Byte-Counting-support.patch, #40384
    2017-03-07 jcunningham Attached File- Added 256KB-abc-1-limit-2.txt, #39916
    2017-03-07 jcunningham Attached File- Added 0001-Add-ABC-support.patch, #39912
        Attached File- Added shell-stat-abc-0.txt, #39913
        Attached File- Added shell-stat-abc-1-limit-2.txt, #39914
        Attached File- Added 256KB-abc-0.txt, #39915
    2017-03-03 jcunningham StatusNone In Progress
        Planned ReleaseNone 2.1.0
    2016-08-23 goldsimon SummaryAppropriate btye counting/stretch ACK support Appropriate byte counting/stretch ACK support
    2016-08-22 jcunningham SummaryAppropriate bye counting/stretch ACK support Appropriate btye counting/stretch ACK support

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code