Bug 1850

Summary: TCP NewReno loss behavior
Product: ns-3 Reporter: Tom Henderson <tomh>
Component: internetAssignee: George Riley <riley>
Status: RESOLVED FIXED    
Severity: normal CC: bswenson3, m.kheirkhah, mory83, ns-bugs
Priority: P5    
Version: pre-release   
Hardware: PC   
OS: All   
Attachments: Result from TCP NewReno
Modified TcpNewReno
Patch for tcp-newreno.cc loss recovery
slightly modified patch to tcp-newreno.cc to fix

Description Tom Henderson 2014-02-04 09:14:46 EST
This was reported on ns-3-users list on 2/4/14 and needs confirmed:

> I was looking at implementation of TCP NewReno (tcp-newreno.cc) and I 
> notice, when the partial ACK being received, the sender sends a assumed 
> lost segment after sending new data into pipe since 
> TcpSocketBase::NewAck (seq) method would be called first (this is not 
> what rfc 3782 is suggested). I was wondering does this could be hurtful 
> in some scenarios since new data would be arrived sooner 
> than retransmitted segment and so generate unnecessary dupACK for 
> retransmitted segment instead of cumulative ACK??
>
Comment 1 Morteza 2014-02-04 10:13:31 EST
Created attachment 1778 [details]
Result from TCP NewReno

Partial ACK for the segment 28 is received, segment 29 is retransmitted after sent of segment 35. Thus 35 would generate dupACK for segment 28...
Comment 2 Morteza 2014-02-04 10:24:00 EST
Created attachment 1779 [details]
Modified TcpNewReno

Retransmit the segment 29 after receiving partial ACK for segment 28. The result would be quite similar to Figure 3 of Simulation-based Comparison of Tahoe, Reno and SACK TCP by Kevin Fall and Sally Floyd.
Comment 3 Morteza Kheirkhah 2014-02-19 13:16:28 EST
Created attachment 1783 [details]
Patch for tcp-newreno.cc loss recovery

I called DiscardUp(seq) first in order to achieve right sequence number when HeadSequence() is called from Tx buffer. DoRetrasnmit() function uses HeadSequence() to get the first byte of lost segment. Following that we can safely call TcpSocketBase::NewAck (seq) and send new data. 

Note that DiscardUp(seq) would be called again inside NewACK() but this would not be hurtful at all.

This patch helps TCP exit from fast recovery much faster and in turn decrease flow completion time, i.e., number of partial ACKs that TCP need to sends would be significantly decreased. I will upload some simulation results to show this more clearly.

I made the patch from ns-3-dev version with Eclipse IDE on Mac OS X 10.8.5. I tested the patch on ns-3.19 as well.
Comment 4 Tom Henderson 2014-02-26 13:19:19 EST
(In reply to Morteza Kheirkhah from comment #3)
> Created attachment 1783 [details]
> Patch for tcp-newreno.cc loss recovery
> 
> I called DiscardUp(seq) first in order to achieve right sequence number when
> HeadSequence() is called from Tx buffer. DoRetrasnmit() function uses
> HeadSequence() to get the first byte of lost segment. Following that we can
> safely call TcpSocketBase::NewAck (seq) and send new data. 
> 
> Note that DiscardUp(seq) would be called again inside NewACK() but this
> would not be hurtful at all.
> 
> This patch helps TCP exit from fast recovery much faster and in turn
> decrease flow completion time, i.e., number of partial ACKs that TCP need to
> sends would be significantly decreased. I will upload some simulation
> results to show this more clearly.
> 
> I made the patch from ns-3-dev version with Eclipse IDE on Mac OS X 10.8.5.
> I tested the patch on ns-3.19 as well.

I've reviewed this patch and it looks fine technically.  However, we prefer to avoid leaving comments in the code with names and personal web page references, so if you agree, I would like to instead apply the modified patch (see my new attachment) and commit it with this message and userstring on your behalf:

user:  Morteza Kheirkhah <m.kheirkhah@sussex.ac.uk>
description:  bug 1850:  Tcp NewReno retransmit before sending new data
Comment 5 Tom Henderson 2014-02-26 13:20:03 EST
Created attachment 1788 [details]
slightly modified patch to tcp-newreno.cc to fix
Comment 6 Tom Henderson 2014-02-26 13:38:17 EST
Morteza,
How can we incorporate your several plots and examples demonstrating this bug, for future NewReno users?  If you are willing to help with this, I see an opportunity to contribute the example scripts and plots that you have generated and sent on the ns-3-users list.

We don't have any test code coverage of NewReno.  Ideally, it would be nice to write regression tests that produce validated response vectors, perhaps along the lines of Sally Floyd's research papers.

However, if this is too much work, I suggest that perhaps you could contribute a (already mostly written?) example that demonstrates the correct behavior of the model, and perhaps automatically produces a nice plot of different events, such as you circulated.  I don't know whether you have that automated or wrote it by hand.  We could do a basic sanity check of the example output and put that example script into our regression tests, and put some documentation of the example into the model library documentation for TCP.

Please let us know if you would like to provide any of your examples or write any other tests.
Comment 7 Morteza 2014-02-27 12:18:48 EST
> I've reviewed this patch and it looks fine technically.  However, we prefer
> to avoid leaving comments in the code with names and personal web page
> references, so if you agree, I would like to instead apply the modified
> patch (see my new attachment) and commit it with this message and userstring
> on your behalf:
> 
> user:  Morteza Kheirkhah <m.kheirkhah@sussex.ac.uk>
> description:  bug 1850:  Tcp NewReno retransmit before sending new data

No problem at all. Please go ahead with it.
Comment 8 Morteza 2014-02-27 12:43:07 EST
Hi Tom, I hope you are ok.

> Morteza,
> How can we incorporate your several plots and examples demonstrating this
> bug, for future NewReno users?  If you are willing to help with this, I see
> an opportunity to contribute the example scripts and plots that you have
> generated and sent on the ns-3-users list.

Yes, I like to.

> We don't have any test code coverage of NewReno.  Ideally, it would be nice
> to write regression tests that produce validated response vectors, perhaps
> along the lines of Sally Floyd's research papers.

This has been part of my agenda for sometimes, in fact I need to do similar testing for the transport protocol that I have written in NS3.

> However, if this is too much work, I suggest that perhaps you could
> contribute a (already mostly written?) example that demonstrates the correct
> behavior of the model, and perhaps automatically produces a nice plot of
> different events, such as you circulated.  I don't know whether you have
> that automated or wrote it by hand.  We could do a basic sanity check of the
> example output and put that example script into our regression tests, and
> put some documentation of the example into the model library documentation
> for TCP.
>
> Please let us know if you would like to provide any of your examples or
> write any other tests.

All of my plots being generated automatically after completion of any simulation scenario (I have designed a few scenarios similar to some test that Sally Floyd did in the past), but some modifications are needed in TcpSocketBase for gathering all statistics. I will send them in mailing list as soon as I can and I'll let you know.
Comment 9 Brian Swenson 2014-04-22 14:20:12 EDT
10696:2b5f35631d76 updated code and response vectors