TCP LEDBAT implementation in ns-3.26

This patch provides an implementation of TCP LEDBAT [1] in ns-3.26.

Patch contains:
- Implementation of TCP LEDBAT in ns-3.26
- Documentation
- Test suite
- Extended examples/tcp/tcp-variants-compare.cc to provide an option to simulate TCP LEDBAT

This patch is aligned with the Linux kernel code [2] of TCP LEDBAT.

Thanks,
Ankit Deepak

[1] RFC 6817: https://tools.ietf.org/html/rfc6817

[2] M. Kuehlewind's Linux code: http://mirja.kuehlewind.net/src/tcp_ledbat.c

[Tom Henderson, 2016-10-30 16:31:58]

https://codereview.appspot.com/307530043/diff/1/src/internet/doc/tcp.rst
File src/internet/doc/tcp.rst (right):

https://codereview.appspot.com/307530043/diff/1/src/internet/doc/tcp.rst#newc...
src/internet/doc/tcp.rst:699: More information (RFC): 
https://tools.ietf.org/html/rfc6817
Please comment in the documentation about these points:

1) is RFC6817 fully implemented?  If not, what parts are missing?

2) how may a user observe the effects of LEDBAT with an existing ns-3 example
program?  (provide example command syntax for a program that uses LEDBAT vs not
using LEDBAT)

3) How did you verify that LEDBAT is correctly implemented (what tests have been
performed)?

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat.cc
File src/internet/model/tcp-ledbat.cc (right):

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat...
src/internet/model/tcp-ledbat.cc:42: MakeUintegerChecker<uint32_t> ())
General question on this implementation-- why are time values being maintained
as integers?  Have you considered to use the ns3::Time class?  IMO it is better
choice unless there is a problem with doing so.

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat...
src/internet/model/tcp-ledbat.cc:241: cb.buffer.push_back (owd);
have you thought about implementing a circular buffer object (instead of a
struct exposing a vector) so that you can just encapsulate the details rather
than implementing circular buffer management in this method?

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat.h
File src/internet/model/tcp-ledbat.h (right):

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat...
src/internet/model/tcp-ledbat.h:130: void LedbatInitCircbuf (struct OwdCircBuf
&buffer);
InitCircBuff

https://codereview.appspot.com/307530043/diff/1/src/internet/test/tcp-ledbat-...
File src/internet/test/tcp-ledbat-test.cc (right):

https://codereview.appspot.com/307530043/diff/1/src/internet/test/tcp-ledbat-...
src/internet/test/tcp-ledbat-test.cc:33: * \brief Testing the congestion
avoidance increment on TcpLedbat
Please say more about what is being tested by this test suite.  I see that there
is one test macro being used:

NS_TEST_ASSERT_MSG_EQ (m_state->m_cWnd.Get (), m_cWnd, "CWnd has not updated
correctly");

It also seems to me that you have copied TcpLedbat::CongestionAvoidance() into a
test method IncreaseWindow(), and you are merely testing that you copied the
code correctly into this test suite (i.e. not testing that Ledbat gives the
expected value according to the algorithm).

[adadeepak8, 2016-11-15 13:19:27]

Dear Sir,

Thank you reviewing and providing suggestions.

I have incorporated all the suggested changes and uploaded the revised patch,
except the query related to circular buffer object. I would be glad if you can
provide some pointers related to circular buffer object implementation.

Sincerely,
Ankit Deepak

https://codereview.appspot.com/307530043/diff/1/src/internet/doc/tcp.rst
File src/internet/doc/tcp.rst (right):

https://codereview.appspot.com/307530043/diff/1/src/internet/doc/tcp.rst#newc...
src/internet/doc/tcp.rst:699: More information (RFC): 
https://tools.ietf.org/html/rfc6817
On 2016/10/30 16:31:57, Tom Henderson wrote:
> Please comment in the documentation about these points:
> 
> 1) is RFC6817 fully implemented?  If not, what parts are missing?
> 
> 2) how may a user observe the effects of LEDBAT with an existing ns-3 example
> program?  (provide example command syntax for a program that uses LEDBAT vs
not
> using LEDBAT)
> 
> 3) How did you verify that LEDBAT is correctly implemented (what tests have
been
> performed)?

Done.

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat.cc
File src/internet/model/tcp-ledbat.cc (right):

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat...
src/internet/model/tcp-ledbat.cc:42: MakeUintegerChecker<uint32_t> ())
On 2016/10/30 16:31:58, Tom Henderson wrote:
> General question on this implementation-- why are time values being maintained
> as integers?  Have you considered to use the ns3::Time class?  IMO it is
better
> choice unless there is a problem with doing so.

Done.

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat...
src/internet/model/tcp-ledbat.cc:241: cb.buffer.push_back (owd);
On 2016/10/30 16:31:57, Tom Henderson wrote:
> have you thought about implementing a circular buffer object (instead of a
> struct exposing a vector) so that you can just encapsulate the details rather
> than implementing circular buffer management in this method?

I haven't thought about that. Can you please give some suggestions on how to do
this?

Currently, the struct has (i) a vector which works as a circular queue and (ii)
an index to the minimum value found in the vector.

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat.h
File src/internet/model/tcp-ledbat.h (right):

https://codereview.appspot.com/307530043/diff/1/src/internet/model/tcp-ledbat...
src/internet/model/tcp-ledbat.h:130: void LedbatInitCircbuf (struct OwdCircBuf
&buffer);
On 2016/10/30 16:31:58, Tom Henderson wrote:
> InitCircBuff

Done.

https://codereview.appspot.com/307530043/diff/1/src/internet/test/tcp-ledbat-...
File src/internet/test/tcp-ledbat-test.cc (right):

https://codereview.appspot.com/307530043/diff/1/src/internet/test/tcp-ledbat-...
src/internet/test/tcp-ledbat-test.cc:33: * \brief Testing the congestion
avoidance increment on TcpLedbat
Modified the Test Suite to test different phases of Ledbat

[n.p, 2017-02-03 14:28:17]

Done, please solve the circular buffer issue and some small thing here and here.
Thank you!

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.cc (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:69: m_doSs = doSS;
please add NS_LOG_FUNCTION at the beginning of every function

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:266: {
Be sure there is no overflow there

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.h (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:38: };
This structure should be inserted in the class TcpLedbat to not pollute the
namespace. Or, as Tom said, implement a CircularBuffer.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:132: typedef uint32_t (*FilterFunction)(struct
OwdCircBuf &);
Please document also the typedef

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:184: {
the name should be SlowStartType, in order to be called as
TcpLedbat::SlowStartType

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:193: {
The TcpLedbat in the name is not necessary, but is necessary a descriptive name
of what state is.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.cc (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.cc:1545: }
Please move these statements inside the piece of code in which we test for
m_timestampEnabled to avoid another comparison.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.h (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.h:165: 
As I have said in another review, please use ns-3 compliant names (such as
m_rcvTsVal)

[adadeepak8, 2017-02-04 07:53:37]

Hi Natale,

Thanks for taking out time to review this patch. I have uploaded a new one with
your suggestions incorporated. Please let me know if this looks correct.

Thanks,
Ankit

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.cc (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:69: m_doSs = doSS;
On 2017/02/03 14:28:16, n.p wrote:
> please add NS_LOG_FUNCTION at the beginning of every function

Done.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:266: {
Unsigned subtraction might not be affected by a single wraparound, which is
possible at timestamp > 2^64 and m_lastRollover < 2^64

Please let me know what do you think about it.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.h (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:38: };
On 2017/02/03 14:28:16, n.p wrote:
> This structure should be inserted in the class TcpLedbat to not pollute the
> namespace. Or, as Tom said, implement a CircularBuffer.

Done.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:132: typedef uint32_t (*FilterFunction)(struct
OwdCircBuf &);
On 2017/02/03 14:28:16, n.p wrote:
> Please document also the typedef

Done.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:184: {
On 2017/02/03 14:28:16, n.p wrote:
> the name should be SlowStartType, in order to be called as
> TcpLedbat::SlowStartType

Done.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:193: {
On 2017/02/03 14:28:16, n.p wrote:
> The TcpLedbat in the name is not necessary, but is necessary a descriptive
name
> of what state is.

Done.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.cc (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.cc:1545: }
On 2017/02/03 14:28:16, n.p wrote:
> Please move these statements inside the piece of code in which we test for
> m_timestampEnabled to avoid another comparison.

Done.

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.h (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.h:165: 
On 2017/02/03 14:28:16, n.p wrote:
> As I have said in another review, please use ns-3 compliant names (such as
> m_rcvTsVal)

Done.

[n.p, 2017-02-04 19:22:35]

Good work, I've pointed out some other thing that I've missed in the first
review.

Now, if you want to be perfect, you could setup a git repo, create a branch
based on the master, and prepare a commit with the code that answers all the
questions. I will then pull it and push into the ns-3-dev mainline as soon as
possible. If you don't know or if you don't have time, I will do it myself,
don't worry :)

Thank you again and great job!

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.cc (right):

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:252: {
This function seems useless, it just wastes stack space ... Please remove it

https://codereview.appspot.com/307530043/diff/20001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:266: {
On 2017/02/04 07:53:36, adadeepak8 wrote:
> Unsigned subtraction might not be affected by a single wraparound, which is
> possible at timestamp > 2^64 and m_lastRollover < 2^64
> 
> Please let me know what do you think about it.

Overall I don't like the C-style casting (we are in C++, reinterpret_cast is
more appropriate) but, even doing that, this thing is unsafe. I mean, why don't
storing directly a double? In this way, all the problem are solved.

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.cc (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:62: MakeUintegerChecker<uint32_t> ())
We have EnumChecker, which control if the values of the Attribute are inside the
bounds. Here, the user could insert "2" and the code will not fail.

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:205: base_delay = (int64_t)BaseDelay ();
Please avoid doing C-style casts. In general, I don't like working with uint and
then converting to int, because it is possible to lose precision. I would like
to keep working with uint, preventing the case of overflow by using conditional
statements. So, it would be:

uint64_t current_delay = CurrentDelay (&TcpLedbat::MinCircBuf);
uint64_t base_delay = BaseDelay ();

if (current_delay > base_delay)
{
  uint64_t queue_delay = current_delay - base_delay;
  offset = m_Target.GetMilliSeconds () - queue_delay;
}
else
{
  uint64_t queue_delay = base_delay - current_delay;
  offset = m_Target.GetMilliSeconds () + queue_delay;
}

Probably, the else branch will never be taken, but in a simulator who knows what
kind of technologies will be employed? So, it's better to stay safe.
Another thing is, can offset be negative? Because in this case there will be a
problem in the following line. Again, don't assume too much in a simulator... 


If you think that these things will not appear, simply use uint64_t and add an
ASSERT (current_delay >= base_delay).

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:211: cwnd += (inc * tcb->m_segmentSize);
inc could be negative if m_sndCwndCnt is negative.

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:245: for (uint32_t i = 1; i < maxlen - 1; i++)
Is it normal having a cycle from 1 to maxlen-1? Don't we miss the first element?

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:259: }
This just waste stack space. Please remove this function (UpdateCurrentDelay)
and replace directly with AddDelay (...)

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.h (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:201: Time m_Target;                     //!<
Target Queue Delay
ns-3 naming style here is missing, it should be m_target

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:207: int32_t m_sndCwndCnt;              //!< The
congestion window addition parameter
Remember this int32_t ... we will need it later :)

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.cc (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.cc:3678: 
Good :)

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.h (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.h:169: 
Now these are ok, please move them near the Timestamp member variables.

[n.p, 2017-02-04 19:48:53]

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.cc (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.cc:3678: 
On 2017/02/04 19:22:35, n.p wrote:
> Good :)

No, actually this is not good, I'm sorry. Please, add this statements inside
ProcessOptionTs. Thank you!

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.h (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.h:169: 
On 2017/02/04 19:22:35, n.p wrote:
> Now these are ok, please move them near the Timestamp member variables.

No, the position is fine (this is TCB, not TcpSocketBase)

[adadeepak8, 2017-02-06 11:25:27]

Hi Natale,

I have pushed the changed LEDBAT files at
https://github.com/adeepkit01/TCP-Ledbat, as you instructed. 

Thank you for reviewing and will be looking forward to further suggestions.

-Ankit

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.cc (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:62: MakeUintegerChecker<uint32_t> ())
On 2017/02/04 19:22:35, n.p wrote:
> We have EnumChecker, which control if the values of the Attribute are inside
the
> bounds. Here, the user could insert "2" and the code will not fail.

Done.

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:205: base_delay = (int64_t)BaseDelay ();
On 2017/02/04 19:22:34, n.p wrote:
> Please avoid doing C-style casts. In general, I don't like working with uint
and
> then converting to int, because it is possible to lose precision. I would like
> to keep working with uint, preventing the case of overflow by using
conditional
> statements. So, it would be:
> 
> uint64_t current_delay = CurrentDelay (&TcpLedbat::MinCircBuf);
> uint64_t base_delay = BaseDelay ();
> 
> if (current_delay > base_delay)
> {
>   uint64_t queue_delay = current_delay - base_delay;
>   offset = m_Target.GetMilliSeconds () - queue_delay;
> }
> else
> {
>   uint64_t queue_delay = base_delay - current_delay;
>   offset = m_Target.GetMilliSeconds () + queue_delay;
> }
> 
> Probably, the else branch will never be taken, but in a simulator who knows
what
> kind of technologies will be employed? So, it's better to stay safe.
> Another thing is, can offset be negative? Because in this case there will be a
> problem in the following line. Again, don't assume too much in a simulator... 
> 
> 
> If you think that these things will not appear, simply use uint64_t and add an
> ASSERT (current_delay >= base_delay).

Done.

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:211: cwnd += (inc * tcb->m_segmentSize);
I feel that is an expected behaviour, as the congestion window should reduce
when the queue_delay is more than the target delay.

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:245: for (uint32_t i = 1; i < maxlen - 1; i++)
We assume that the minimum element is at 0 initially (i.e., cb.min = 0), hence
we compare the rest of array with it, to find the index of minimum element

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.cc:259: }
On 2017/02/04 19:22:35, n.p wrote:
> This just waste stack space. Please remove this function (UpdateCurrentDelay)
> and replace directly with AddDelay (...)

Done.

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
File src/internet/model/tcp-ledbat.h (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-le...
src/internet/model/tcp-ledbat.h:201: Time m_Target;                     //!<
Target Queue Delay
On 2017/02/04 19:22:35, n.p wrote:
> ns-3 naming style here is missing, it should be m_target

Done.

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
File src/internet/model/tcp-socket-base.cc (right):

https://codereview.appspot.com/307530043/diff/40001/src/internet/model/tcp-so...
src/internet/model/tcp-socket-base.cc:3678: 
I am unable to find the function "ProcessOptionTs", please let me know where can
I find it or else did you mean any other function?