Queue rework

Queue rework. From RELEASE_NOTES:

(network) The queue subsystem has been refactored for the following improvements: 1) Unified interface for proper queue sizing, through attributes and trace sources shared by all Queue subclasses. 2) An indicator on the number of packets dropped due to full queue, has been added.

Check queue.rst and CHANGES.html to see a list of changed things.

[n.p, 2015-11-06 16:01:48]

This is my attempt to rewrite queue subsystem to offer a sound API to users.

[Tom Henderson, 2015-12-19 02:05:17]

I'm in favor of improving the Queue class along these lines; two main
comments/questions:

- is the idea to keep internet-aware queues like CoDel and RED inheriting from
this, or migrate them to another base class as a second step?  I've been
assuming the latter since I think that more than a Packet will be enqueued (like
a pair of Packet and Header).  What do you think?

- it would be nice to write a small test with DropTail that hooked every trace
source and checked boundary conditions on which trace fired for different
conditions.  Do you think you could add such a test also?

https://codereview.appspot.com/270540044/diff/60001/CHANGES.html
File CHANGES.html (right):

https://codereview.appspot.com/270540044/diff/60001/CHANGES.html#newcode65
CHANGES.html:65: (<em>{Get,Set}{Mode,MaxBytes,MaxPackets}</em>).</li>
mention new trace sources here

https://codereview.appspot.com/270540044/diff/60001/CHANGES.html#newcode86
CHANGES.html:86: mutuated from CoDelQueue and DropTailQueue.</li>
s/mutuated/migrated

https://codereview.appspot.com/270540044/diff/60001/CHANGES.html#newcode114
CHANGES.html:114: <li>Queue sizing unified through attributes and trace sources
in class Queue.</li>
is there some behavioral change due to how Drop() is handled?  Will all traces
fire the same way?

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.cc
File src/network/utils/queue.cc (right):

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:33: #define MAXBYTES_DEFAULT MAXPACKETS_DEFAULT *
1500
minor style nit:  use static const uint32_t MAXPACKETS_DEFAULT = 100;

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:70: .AddTraceSource ("Drop", "A stored packet is
dropped",
should it be named DropInside?

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:73: .AddTraceSource ("Drop", "A packet is dropped due
to queue overflow",
should it be named DropOverflow?

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:117: "Cannot change queue mode dynamically.");
dynamically, or on an active queue?

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:139: m_maxBytes = maxBytes;
if lowered on a full queue, do packets need to be dropped?

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:153: m_maxPackets = maxPackets;
if lowered on a full queue, do packets need to be dropped?

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:175: if (m_mode == QUEUE_MODE_PACKETS && GetNPackets
() >= m_maxPackets)
when can GetNPackets () be > m_maxPackets?

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:292: * Enqueue (p) will fail, because it would exceed
the queue size.
wouldn't a uint32_t GetSpace() const work better here?  If GetSpace () == 0,
queue is full (packet mode).  If GetSpace () is small in byte mode, user can
decide what threshold he or she wants to declare it to be full.

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:376: m_traceDequeue (packet);
why are you tracing a dequeue?  I would expect this not to be called here.

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.h
File src/network/utils/queue.h (right):

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.h...
src/network/utils/queue.h:40: * This class defines the base APIs for packet
queues in the ns-3 system.
add "for queues that need no special header processing and can operate purely on
Packet objects as opaque objects (i.e., no header peeking).  There exist other
types of queues in ns-3 that are more specialized for particular protocol
handling."

[n.p, 2015-12-20 13:55:55]

On 2015/12/19 02:05:17, Tom Henderson wrote:
> I'm in favor of improving the Queue class along these lines; two main
> comments/questions:
> 
> - is the idea to keep internet-aware queues like CoDel and RED inheriting from
> this, or migrate them to another base class as a second step?  I've been
> assuming the latter since I think that more than a Packet will be enqueued
(like
> a pair of Packet and Header).  What do you think?

This is a question that involves more than Queue.. because of QueueDisc :)
I will reply for this in a mail. For now, I'm assuming to maintain the old API,
and so inherit from Queue.

> - it would be nice to write a small test with DropTail that hooked every trace
> source and checked boundary conditions on which trace fired for different
> conditions.  Do you think you could add such a test also?

Of course, this is a must! I'll add as soon as possible.

[n.p, 2016-01-02 14:49:13]

Updated the submission; replies to comments inside.

https://codereview.appspot.com/270540044/diff/60001/CHANGES.html
File CHANGES.html (right):

https://codereview.appspot.com/270540044/diff/60001/CHANGES.html#newcode114
CHANGES.html:114: <li>Queue sizing unified through attributes and trace sources
in class Queue.</li>
The Drop trace source will behave as the old one; it catches all types of drop.
Then, OverflowDrop and InsideDrop are added to specialized the search of "what"
type of drop happened. InsideDrop is more typical for AQM like CoDel, while
OverflowDrop is the Drop we all know from DropTail.

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.cc
File src/network/utils/queue.cc (right):

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:153: m_maxPackets = maxPackets;
On 2015/12/19 02:05:16, Tom Henderson wrote:
> if lowered on a full queue, do packets need to be dropped?

I inserted a conditional check to abort Set* operations if packets are stored in
queue, because I fear that this will confuse users when attribute set/get comes
inside a simulation. If users want this feature, I would like that they
explicitly disable this checking through a subclass.

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:292: * Enqueue (p) will fail, because it would exceed
the queue size.
On 2015/12/19 02:05:17, Tom Henderson wrote:
> wouldn't a uint32_t GetSpace() const work better here?  If GetSpace () == 0,
> queue is full (packet mode).  If GetSpace () is small in byte mode, user can
> decide what threshold he or she wants to declare it to be full.

I'm not sure if I understood what you're saying: GetSpace would return the bytes
inside the queue? Or the available space until MaxBytes is achieved? I think the
latter... anyway, I would like to avoid to depends on another attribute, that
can vary from simulation to simulation.. through the average size of packets
inside the queue, I think we are resolving the problem cleanly, since usually
our applications are generating fixed-size packets.

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:376: m_traceDequeue (packet);
On 2015/12/19 02:05:16, Tom Henderson wrote:
> why are you tracing a dequeue?  I would expect this not to be called here

traceEnqueue is not called if the packet is dropped due to overflow; then, if
the packet is enqueued, and then is dropped inside the queue, without calling
traceDequeue we will have # traceEnqueue != from # traceDequeue, even if the
packet count is 0, while with this approach we have:

if GetPackets() == 0 ==> # traceEnqueue == # traceDequeue

which is a bit more intuitive for me. After all, packet is dequeued and then
dropped.

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.h
File src/network/utils/queue.h (right):

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.h...
src/network/utils/queue.h:40: * This class defines the base APIs for packet
queues in the ns-3 system.
On 2015/12/19 02:05:17, Tom Henderson wrote:
> There exist other
> types of queues in ns-3 that are more specialized for particular protocol
> handling."

This could be added when the other types hit the mainline, with links to them,
to avoid misunderstanding by users. For the first part, ok.

[n.p, 2016-01-02 14:51:09]

Little note: I cannot run any test under src/network.

$ ./test.py -s packet
The test suite was not run because an unknown test suite name was requested.

$ ./test.py -l
test.py error:  test-runner return code returned -6
To debug, try running './waf --run "test-runner --print-test-name-list"'

[Stefano Avallone, 2016-01-03 22:31:46]

I have looked at the proposed changes to queue.{h,cc} and left some comments.

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.cc
File src/network/utils/queue.cc (right):

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.c...
src/network/utils/queue.cc:104: Queue::~Queue ()
Remove trailing whitespace

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.c...
src/network/utils/queue.cc:142: NS_ABORT_MSG_UNLESS (m_nBytes.Get () <=
maxBytes,
This condition does not match the message. Maybe you meant m_nBytes.Get () == 0
?

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.c...
src/network/utils/queue.cc:163: NS_ABORT_MSG_UNLESS (m_nPackets.Get () <=
maxPackets,
This condition does not match the message. Maybe you meant m_nPackets.Get () ==
0 ?

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.c...
src/network/utils/queue.cc:295: Queue::IsFull (void) const
I would get rid of this tricky IsFull and (as Tom suggested) replace it by a
GetSpace method, which returns m_maxPackets - m_nPackets.Get () in packet mode
and m_maxBytes - m_nBytes.Get () in byte mode.

Thus, a queue in packet mode can enqueue another packet if GetSpace () > 0,
while a queue in byte mode can enqueue another packet p if GetSpace () >
p.GetSize (). The object which is trying to enqueue a packet knows the mode of
the queue and can therefore use the correct condition.

Also note that a network device might stop its transmission queue before it is
actually full (as part of its flow control strategy; something like this is done
by many Linux drivers). Thus, if we want to stop the transmission queue when it
is more than 90% full, it is sufficient to check whether GetN[Bytes|Packets] ()
/ GetMax[Bytes|Packets] > 0.9 (Queue might even provide a GetOccupancy () method
that returns such a ratio). Thus, IsFull () is not really necessary.

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.c...
src/network/utils/queue.cc:390: m_traceDequeue (packet);
I agree with Tom here. I think that it is more intuitive that:

- # traceEnqueue = # traceDequeue + # traceDropInside

- # traceDequeue is the number of packets actually dequeued (thus, not counting
the packets dropped inside)

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.h
File src/network/utils/queue.h (right):

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.h...
src/network/utils/queue.h:98: * \brief Default constructor
s/constructor/destructor

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.h...
src/network/utils/queue.h:153: * Set the operating mode of this device.
s/device/queue

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.h...
src/network/utils/queue.h:155: * \param mode The operating mode of this device.
s/device/queue

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.h...
src/network/utils/queue.h:161: * Get the encapsulation mode of this device.
s/device/queue

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.h...
src/network/utils/queue.h:163: * \return The encapsulation mode of this device.
s/device/queue

https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.h...
src/network/utils/queue.h:168: * \brief Set the maximum amount of bytes
storeable in this queue
storable? I would prefer "that can be stored", but a native English speaker
might give a better advice

[Tom Henderson, 2016-01-04 04:07:54]

On 2016/01/02 14:51:09, n.p wrote:
> Little note: I cannot run any test under src/network.
> 
> $ ./test.py -s packet
> The test suite was not run because an unknown test suite name was requested.
> 
> $ ./test.py -l
> test.py error:  test-runner return code returned -6
> To debug, try running './waf --run "test-runner --print-test-name-list"'

Check that you enabled tests in your configuration.
grep ^ENABLE_TESTS build/c4che/_cache.py

[Tom Henderson, 2016-01-04 04:08:32]

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.cc
File src/network/utils/queue.cc (right):

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:292: * Enqueue (p) will fail, because it would exceed
the queue size.
On 2016/01/02 14:49:13, n.p wrote:
> On 2015/12/19 02:05:17, Tom Henderson wrote:
> > wouldn't a uint32_t GetSpace() const work better here?  If GetSpace () == 0,
> > queue is full (packet mode).  If GetSpace () is small in byte mode, user can
> > decide what threshold he or she wants to declare it to be full.
> 
> I'm not sure if I understood what you're saying: GetSpace would return the
bytes
> inside the queue? Or the available space until MaxBytes is achieved? I think
the
> latter... 

Yes, the latter.  Depending on the mode, the units of the integer returned are
bytes or packets (amount of space left that an enqueue should succeed).

anyway, I would like to avoid to depends on another attribute, that
> can vary from simulation to simulation.. through the average size of packets
> inside the queue, I think we are resolving the problem cleanly, since usually
> our applications are generating fixed-size packets.

I don't think it is a realistic model that packets are all the same size even if
many ns-3 simulations are that simplified.

I think it may be considered a bug if IsFull () returns false but the queue
overflows on the next packet; better to give the caller more state information
to make its own "full" determination.

https://codereview.appspot.com/270540044/diff/60001/src/network/utils/queue.c...
src/network/utils/queue.cc:376: m_traceDequeue (packet);
On 2016/01/02 14:49:13, n.p wrote:
> On 2015/12/19 02:05:16, Tom Henderson wrote:
> > why are you tracing a dequeue?  I would expect this not to be called here
> 
> traceEnqueue is not called if the packet is dropped due to overflow; then, if
> the packet is enqueued, and then is dropped inside the queue, without calling
> traceDequeue we will have # traceEnqueue != from # traceDequeue, even if the
> packet count is 0, while with this approach we have:
> 
> if GetPackets() == 0 ==> # traceEnqueue == # traceDequeue
> 
> which is a bit more intuitive for me. After all, packet is dequeued and then
> dropped.

OK, I think it is a matter of definition, as long as we are consistent and
documentation is clear, I would be fine with your definition.

I found this internet-draft to be useful when I searched just now for the
conventional terminology:

https://tools.ietf.org/html/draft-ietf-aqm-fq-implementation-03

The above draft conforms to definitions in which all enqueues are followed by
dequeues, and drops either occur before the enqueue occurs (in RED/PIE cases, or
if queue resources are overrun), or after the dequeue occurs (in CoDel
approaches).

[Tom Henderson, 2016-01-04 04:17:55]

On 2016/01/03 22:31:46, Stefano Avallone wrote:

> 
>
https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.c...
> src/network/utils/queue.cc:390: m_traceDequeue (packet);
> I agree with Tom here. I think that it is more intuitive that:
> 
> - # traceEnqueue = # traceDequeue + # traceDropInside
> 
> - # traceDequeue is the number of packets actually dequeued (thus, not
counting
> the packets dropped inside)
> 

Hmm, I agree that with a trace named DropInside, it seems counter-intuitive that
such a packet is also dequeued.

I do not have a strong opinion about which way to go other than that we are
consistent and document it well.  If we follow that internet-draft that I cited,
there are seemingly no "inside" drops; a drop either occurs before Enqueue or
after Dequeue.  So if we follow that convention, it seems that the finer
granularity trace sources may need to be named something like
"DropBeforeEnqueue" and "DropAfterDequeue".  If we keep the trace sources named
"InsideDrop" and "OverflowDrop", then I think that we should probably not
dequeue also on an inside drop.

> 
>
https://codereview.appspot.com/270540044/diff/80001/src/network/utils/queue.h...
> src/network/utils/queue.h:168: * \brief Set the maximum amount of bytes
> storeable in this queue
> storable? I would prefer "that can be stored", but a native English speaker
> might give a better advice

I'd go with "that can be stored"

[n.p, 2016-01-11 09:38:33]

On 2016/01/04 04:17:55, Tom Henderson wrote:
> I do not have a strong opinion about which way to go other than that we are
> consistent and document it well.  If we follow that internet-draft that I
cited,
> there are seemingly no "inside" drops; a drop either occurs before Enqueue or
> after Dequeue.  So if we follow that convention, it seems that the finer
> granularity trace sources may need to be named something like
> "DropBeforeEnqueue" and "DropAfterDequeue".  If we keep the trace sources
named
> "InsideDrop" and "OverflowDrop", then I think that we should probably not
> dequeue also on an inside drop.

Thank you all for the suggestion. I've replaced IsFull with 

uint32_t Available (void) const (used also in Tcp{Tx,Rx}Buffer) which tells the
available space inside the queue.

I renamed the traces in DropBeforeEnqueue and DropAfterEnqueue, to stay
"compatible" with both the RFC and what you said. In particular, the following
conditions apply now:

 - # Enqueue = # Dequeue + # DropAfterEnqueue
 - # Drop    = # DropBeforeEnqueue + # DropAfterEnqueue

And so, after calling "DropAfterEnqueue" (the previous DropInQueue) I don't call
m_traceDequeue anymore.

I corrected the english, and added a bit of documentation on these new traces.
Should they added to RELEASE_NOTES or CHANGES.html?

Thank you again