Bug 2751 - QueueDisc::Enqueue() order of operations
QueueDisc::Enqueue() order of operations
Status: RESOLVED FIXED
Product: ns-3
Classification: Unclassified
Component: traffic-control
unspecified
All All
: P3 normal
Assigned To: Stefano Avallone
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2017-06-05 09:06 EDT by Tom Henderson
Modified: 2017-09-16 22:45 EDT (History)
3 users (show)

See Also:


Attachments
Use lambdas to make the MacOS linker happy (6.18 KB, patch)
2017-09-16 12:11 EDT, Stefano Avallone
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Tom Henderson 2017-06-05 09:06:01 EDT
The current QueueDisc::Enqueue() is:

bool
QueueDisc::Enqueue (Ptr<QueueDiscItem> item)
{
  NS_LOG_FUNCTION (this << item);

  m_nPackets++;
  m_nBytes += item->GetSize ();
  m_nTotalReceivedPackets++;
  m_nTotalReceivedBytes += item->GetSize ();

  NS_LOG_LOGIC ("m_traceEnqueue (p)");
  m_traceEnqueue (item);

  return DoEnqueue (item);
}

This results in the following behavior:
- counters are incremented even if the subclass decides to drop the packet.  This may lead to unexpected behavior, such as DoEnqueue() never seeing the queue empty with zero packets, and clients observing queues to grow beyond their limits temporarily (e.g. PacketsInQueue, a traced value, may exceed the capacity of the queue by one packet in the short time interval between start of Enqueue() and the result of a failed DoEnqueue())
- subclasses are forced to call Drop() themselves to correct the counters if they decide to drop

I suggest to instead only increment counters if DoEnqueue() returns true, and to have this method call Drop() upon DoEnqueue () returning false.  If a subclass decides to accept this item and drop another instead (e.g. DropHead policy), it must instead call Drop()).
Comment 1 Stefano Avallone 2017-06-23 10:24:04 EDT
I prepared a patch to fix this issue. While at it, I added some other useful features. Code is here:

https://github.com/stavallo/ns-3-dev-git/commits/tc-next

traffic-control: (fixes #2751) Ensure queue discs keep correct statistics
---------------------------------------------------------------------------
This commit fixes this bug. Also, a distinction is made between packets dropped before enqueue and packets dropped after dequeue. A QueueDisc::Stats struct is introduced to keep detailed statistics for all the queue discs. Also fixed by this commit is an issue arising with fq-codel, whereby packets dropped from the internal queue are not correctly reported. This issue is now fixed by connecting the DropBeforeEnqueue and DropAfterDequeue methods to the drop traces of internal queues and child queue discs.

traffic-control: Trace sojourn times within queue discs
---------------------------------------------------------------------------
This commit adds a new trace source which provides the sojourn time of all the packets dequeued from the queue disc.

traffic-control: CoDel uses the QueueDiscItem timestamp
---------------------------------------------------------------------------
This commit makes CoDel use the newly introduced timestamp field of QueueDiscItem and get rid of the TimeStamp tag.

traffic-control: Be more restrictive on internal queue size
---------------------------------------------------------------------------
Queue discs having a single internal queue should check that their limit matches the size of the internal queue.

traffic-control: Record reasons for dropping and marking packets
---------------------------------------------------------------------------
This commit allows to record the number of packets/bytes dropped for each of the possible reasons. These counters are included in the queue disc stats.
Comment 2 Mohit 2017-06-26 15:46:40 EDT
Hi Stefano,

I glanced through the series of commits and they look fine to me. 

I have left some minor suggestions in the latest github commit (traffic-control: Record reasons for dropping and marking packets).

Thanks,
Mohit P. Tahiliani
Comment 3 Stefano Avallone 2017-06-26 17:28:54 EDT
Thanks a lot, Mohit!
Comment 4 Tom Henderson 2017-08-11 12:05:17 EDT
(In reply to Stefano Avallone from comment #1)
> I prepared a patch to fix this issue. While at it, I added some other useful
> features. Code is here:
> 
> https://github.com/stavallo/ns-3-dev-git/commits/tc-next

Here are some comments on this set of commits.

1) the additions to CHANGES.html are a good start but there are also some changes to existing API and changed behavior to document.  Also edit RELEASE_NOTES to mark the bug as fixed.

I found these changes to existing API patterns and behavior:

1.1) no longer use of RedQueueDisc::Stats:

-  RedQueueDisc::Stats st = StaticCast<RedQueueDisc> (queueDiscs.Get (0))->GetStats ();
+  QueueDisc::Stats st = queueDiscs.Get (0)->GetStats ();

1.2) the stats are accessed through methods rather than raw members

-  if (st.qLimDrop != 0)
+  if (st.GetDroppedPackets (QueueDisc::internalQueueDrop) != 0)

1.3) QueueItem objects now have a settable timestamp

1.4) CodelQueueDisc no longer has a DropCount trace source or getter method, and its SojournTime trace was moved to QueueDisc 

1.5) CodelTimestampTag is removed

1.6) PieQueueDisc Stats struct and GetStats() have been removed

1.7) the API usage pattern around packet marking is changed (QueueDisc::Mark() should be called instead of the lower-level QueueDiscItem::Mark())

Are those all of the main changes?
Comment 5 Tom Henderson 2017-08-11 12:17:43 EDT
continuing with comments.

2) the Drop/Mark reason strings

currently they are named such as follows
RedQueueDisc::unforcedDrop
QueueDisc::internalQueueDrop

and declared such as:
static constexpr auto unforcedDrop = "Unforced drop";  //!< Early probability drops: proactive

according to our naming conventions (written before C++11 and constexpr) these kind of compile time constants would be named in all caps:

Defined constants (such as static const class members, or enum constants) will be all uppercase letters or numeric digits, with an underscore character separating words

I am not sure why these are declared as 'static constexpr auto' instead of 'static const std::string'; what properties of constexpr and auto are being exploited?

In summary, I think that at least we should capitalize the first letter so that it reads e.g. QueueDisc::InternalQueueDrop, or consider to name according to existing convention for enums and integers, e.g. QueueDisc::INTERNAL_QUEUE_DROP.
Comment 6 Tom Henderson 2017-08-11 13:14:45 EDT
3) please clarify in documentation whether Sojourn time includes requeuing time.  Perhaps clarify in documentation how requeue relates to dequeue; if packet is dequeued and then requeued, but dequeued later without requeue, at what time is the dequeue count incremented, and how does it relate to sojourn time?

4) for this method:

+uint32_t
+QueueDisc::Stats::GetDroppedPackets (std::string reason) const
+{
+  auto it = nDroppedPacketsBeforeEnqueue.find (reason);
+
+  if (it != nDroppedPacketsBeforeEnqueue.end ())
+    {
+      return it->second;
+    }
+
+  it = nDroppedPacketsAfterDequeue.find (reason);
+
+  if (it != nDroppedPacketsAfterDequeue.end ())
+    {
+      return it->second;
+    }
+
+  return 0;


will the above cause the drop count to not include drops after dequeue if drops before dequeue is non-zero?  (same comment for QueueDisc::Stats::GetDroppedBytes())

I suppose that you are exploiting the current case that each 'reason' maps exclusively to either 'before enqueue' or 'after dequeue' cases, but is that guaranteed in the future?  

5) related to the above comment, it is not clear how a drop that occurs while 'in queue' is counted; is it dequeued and dropped, or just dropped?  For instance, if the drop policy is not tail drop but 'oldest in the queue' dropped, upon packet arrival to a full queue, what counters are incremented?
Comment 7 Stefano Avallone 2017-08-21 10:07:39 EDT
(In reply to Tom Henderson from comment #4)
> Here are some comments on this set of commits.
> 
> 1) the additions to CHANGES.html are a good start but there are also some
> changes to existing API and changed behavior to document.  Also edit
> RELEASE_NOTES to mark the bug as fixed.
> 
> I found these changes to existing API patterns and behavior:
> 
> 1.1) no longer use of RedQueueDisc::Stats:
> 
> -  RedQueueDisc::Stats st = StaticCast<RedQueueDisc> (queueDiscs.Get
> (0))->GetStats ();
> +  QueueDisc::Stats st = queueDiscs.Get (0)->GetStats ();
> 
> 1.2) the stats are accessed through methods rather than raw members
> 
> -  if (st.qLimDrop != 0)
> +  if (st.GetDroppedPackets (QueueDisc::internalQueueDrop) != 0)
> 
> 1.3) QueueItem objects now have a settable timestamp
> 
> 1.4) CodelQueueDisc no longer has a DropCount trace source or getter method,
> and its SojournTime trace was moved to QueueDisc 
> 
> 1.5) CodelTimestampTag is removed
> 
> 1.6) PieQueueDisc Stats struct and GetStats() have been removed
> 
> 1.7) the API usage pattern around packet marking is changed
> (QueueDisc::Mark() should be called instead of the lower-level
> QueueDiscItem::Mark())
> 
> Are those all of the main changes?

I uploaded a new version of the patch series on github. The file CHANGES.html and queue-disc.rst have been updated to reflect all the changes introduced by these commits.
Comment 8 Stefano Avallone 2017-08-21 10:12:06 EDT
(In reply to Tom Henderson from comment #5)
> continuing with comments.
> 
> 2) the Drop/Mark reason strings
> 
> currently they are named such as follows
> RedQueueDisc::unforcedDrop
> QueueDisc::internalQueueDrop
> 
> and declared such as:
> static constexpr auto unforcedDrop = "Unforced drop";  //!< Early
> probability drops: proactive
> 
> according to our naming conventions (written before C++11 and constexpr)
> these kind of compile time constants would be named in all caps:
> 
> Defined constants (such as static const class members, or enum constants)
> will be all uppercase letters or numeric digits, with an underscore
> character separating words
> 
> I am not sure why these are declared as 'static constexpr auto' instead of
> 'static const std::string'; what properties of constexpr and auto are being
> exploited?

I replaced auto with const char* (string cannot be used because it is a non-literal type). constexpr is necessary because const char* is a non-integral type.

> In summary, I think that at least we should capitalize the first letter so
> that it reads e.g. QueueDisc::InternalQueueDrop, or consider to name
> according to existing convention for enums and integers, e.g.
> QueueDisc::INTERNAL_QUEUE_DROP.

I renamed all the constants according to the ns-3 naming conventions (all uppercase letters and underscores).
Comment 9 Stefano Avallone 2017-08-21 10:20:10 EDT
(In reply to Tom Henderson from comment #6)
> 3) please clarify in documentation whether Sojourn time includes requeuing
> time.  Perhaps clarify in documentation how requeue relates to dequeue; if
> packet is dequeued and then requeued, but dequeued later without requeue, at
> what time is the dequeue count incremented, and how does it relate to
> sojourn time?

The documentation (both QueueDisc class doxygen and queue-disc.rst) should now clarify this:

 * [...] Also, it is assumed that every packet (including requeued
 * packets) is dequeued just once.
[...]
 * The QueueDisc base class provides the SojournTime trace source, which provides
 * the sojourn time of every packet dequeued from a queue disc, including packets
 * that are dropped or requeued after being dequeued. The sojourn time is taken
 * when the packet is dequeued from the queue disc, hence it does not account for
 * the additional time the packet is retained within the queue disc in case it is
 * requeued.

> 4) for this method:
> 
> +uint32_t
> +QueueDisc::Stats::GetDroppedPackets (std::string reason) const
> +{
> +  auto it = nDroppedPacketsBeforeEnqueue.find (reason);
> +
> +  if (it != nDroppedPacketsBeforeEnqueue.end ())
> +    {
> +      return it->second;
> +    }
> +
> +  it = nDroppedPacketsAfterDequeue.find (reason);
> +
> +  if (it != nDroppedPacketsAfterDequeue.end ())
> +    {
> +      return it->second;
> +    }
> +
> +  return 0;
> 
> 
> will the above cause the drop count to not include drops after dequeue if
> drops before dequeue is non-zero?  (same comment for
> QueueDisc::Stats::GetDroppedBytes())
> 
> I suppose that you are exploiting the current case that each 'reason' maps
> exclusively to either 'before enqueue' or 'after dequeue' cases, but is that
> guaranteed in the future?  

I changed the above methods so that the drop count includes both drops before enqueue and drops after dequeue, in case the same reason applies to both cases.
 
> 5) related to the above comment, it is not clear how a drop that occurs
> while 'in queue' is counted; is it dequeued and dropped, or just dropped? 

The packet is first dequeued and then dropped. In fact, I added a call to m_traceDequeue in Queue::Remove (which is the only way to remove a packet while in queue)

> For instance, if the drop policy is not tail drop but 'oldest in the queue'
> dropped, upon packet arrival to a full queue, what counters are incremented?

dequeued++, dropped++, enqueued++
Comment 10 Stefano Avallone 2017-08-21 10:34:37 EDT
Thanks for your comments, Tom. Besides addressing your comments, I made a couple of more changes:

- the QueueDisc base class provide a "Mark" trace, which outputs all the items that have been marked and the reason why they have been marked

- the "DropBeforeEnqueue" and "DropAfterDequeue" traces now provide both the dropped items and the reason why they were dropped (it is straightforward to add the drop reason to the "Drop" trace as well, but I did not do so for compatibility reasons).

- in order to notify parent queue discs about packet dropped, the "DropBeforeEnqueue" and "DropAfterDequeue" traces of the child queue discs and of the internal queues are connected to a callback provided by the parent queue disc. Instead of introducing 4 methods to the QueueDisc class (for each drop before enqueue/after dequeue and internal queue/child queue disc combination), I used 4 standard function objects, whose operator() is then connected to the traces.

Please let me know if it is ok to push the new version of the commits to ns-3-dev, thanks.
Comment 11 Tom Henderson 2017-08-31 12:04:05 EDT
(In reply to Stefano Avallone from comment #9)
> (In reply to Tom Henderson from comment #6)
> > 3) please clarify in documentation whether Sojourn time includes requeuing
> > time.  Perhaps clarify in documentation how requeue relates to dequeue; if
> > packet is dequeued and then requeued, but dequeued later without requeue, at
> > what time is the dequeue count incremented, and how does it relate to
> > sojourn time?
> 
> The documentation (both QueueDisc class doxygen and queue-disc.rst) should
> now clarify this:
> 
>  * [...] Also, it is assumed that every packet (including requeued
>  * packets) is dequeued just once.
> [...]
>  * The QueueDisc base class provides the SojournTime trace source, which
> provides
>  * the sojourn time of every packet dequeued from a queue disc, including
> packets
>  * that are dropped or requeued after being dequeued. The sojourn time is
> taken
>  * when the packet is dequeued from the queue disc, hence it does not
> account for
>  * the additional time the packet is retained within the queue disc in case
> it is
>  * requeued.

Is it the case that requeued packets are in a limbo state from the perception of the external user monitoring the trace sources, since it has been dequeued but (silently) requeued and may be dequeued (without dequeue count incrementing) at a future time?

I'm wondering whether we can delete requeue from this traffic control model, for simplicity.  Will it ever apply to ns-3 use cases?  Of these cases listed here:
http://qos.ittc.ku.edu/howto/node11.html
what would apply in an ns-3 use case?

Could requeue function be removed and added in at a later date if the need arises, or is the need already there?
Comment 12 Stefano Avallone 2017-09-01 09:35:20 EDT
(In reply to Tom Henderson from comment #11)
> Is it the case that requeued packets are in a limbo state from the
> perception of the external user monitoring the trace sources, since it has
> been dequeued but (silently) requeued and may be dequeued (without dequeue
> count incrementing) at a future time?

I think confusion is generated by the fact that Linux counts a requeued packet as a packet that is still part of the queue disc:

- when a packet is dequeued, the counter of packets in the queue disc is decremented
- if a dequeued packet is requeued (because the device tx queue the packet is destined to is stopped), the counter of packets in the queue disc is incremented
- when a requeued packet is sent to the device, the counter of packets in the queue disc is decremented again.

However, a requeued packet is not really re-enqueued in the queue disc, but is rather retained by the traffic control infrastructure. When TC is requested to send a packet to the device, TC sends the requeued packet (if any) instead of asking the queue disc to dequeue a packet. Hence, queue discs never handle packets after they have been dequeued.

The current patch for ns-3 follows such approach. Probably, it would be less confusing not to consider a requeued packet as part of the queue disc and not to increment the counter of packets in the queue disc if a packet is requeued. Thus, the number of packets in the queue disc would be simply computed as:

queued = enqueued - dequeued

instead of:

queued = enqueued - dequeued (+ 1 if there is a requeued packet)

as it is currently. This should make it clear that a packet is dequeued just once from a queue disc and a requeued packet is simply retained by the traffic-control module until the netdevice tx queue is restarted.

Concerning traces, when a packet is dequeued, the "Dequeue" trace is fired. Then, if it is requeued, the "Requeue" trace is fired (thus, it is not silently requeued). The traces of the netdevice can be used to be notified about when the packet (either dequeued or requeued) is sent to the netdevice.

Shall I update this patch by assuming that a requeued patch is not part of the queue disc?
 
> I'm wondering whether we can delete requeue from this traffic control model,
> for simplicity.  Will it ever apply to ns-3 use cases?  Of these cases
> listed here:
> http://qos.ittc.ku.edu/howto/node11.html
> what would apply in an ns-3 use case?
> 
> Could requeue function be removed and added in at a later date if the need
> arises, or is the need already there?

The requeued mechanism is relevant for multi-queue devices (like wifi) when a non multi-queue-aware queue disc is used (all but mq). In such a case, the queue disc may be required to dequeue a packet even if some of the tx queues are stopped. If the dequeued packet happens to be destined to one of the stopped tx queues, the packet is requeued. Without the requeue mechanism, such packet would be lost.
Comment 13 Tom Henderson 2017-09-06 15:36:49 EDT
.
> 
> Shall I update this patch by assuming that a requeued patch is not part of
> the queue disc?

Yes, please; that seems more clear to me.
Comment 14 Stefano Avallone 2017-09-13 17:36:45 EDT
(In reply to Tom Henderson from comment #13)
> .
> > 
> > Shall I update this patch by assuming that a requeued patch is not part of
> > the queue disc?
> 
> Yes, please; that seems more clear to me.

Patch series updated. Please let me know if you want me to push it to ns-3-dev.
Comment 15 Tom Henderson 2017-09-13 17:53:38 EDT
(In reply to Stefano Avallone from comment #14)
> (In reply to Tom Henderson from comment #13)
> > .
> > > 
> > > Shall I update this patch by assuming that a requeued patch is not part of
> > > the queue disc?
> > 
> > Yes, please; that seems more clear to me.
> 
> Patch series updated. Please let me know if you want me to push it to
> ns-3-dev.

I have reviewed and believe it is ready.
Comment 16 Stefano Avallone 2017-09-14 12:15:19 EDT
Patch series pushed, thanks.
Comment 17 Tom Henderson 2017-09-14 18:02:30 EDT
Patch series is causing a linker error on MacOS:

Undefined symbols for architecture x86_64:
 "std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::data() const", referenced from:
     ns3::QueueDisc::QueueDisc() in queue-disc.cc.1.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

We are working on it.
Comment 18 Stefano Avallone 2017-09-16 12:11:16 EDT
Created attachment 2918 [details]
Use lambdas to make the MacOS linker happy

This error may be a bug of the MacOS linker:

https://stackoverflow.com/questions/27680418/clang-trouble-using-bind-or-mem-fn-with-stringc-str-and-transform

Anyway, I used lambdas to avoid incurring this issue. Also, the code looks cleaner now.

Could you please test the attached patch?
Comment 19 Tommaso Pecorella 2017-09-16 19:21:42 EDT
(In reply to Stefano Avallone from comment #18)
> Created attachment 2918 [details]
> Use lambdas to make the MacOS linker happy
> 
> This error may be a bug of the MacOS linker:
> 
> https://stackoverflow.com/questions/27680418/clang-trouble-using-bind-or-mem-
> fn-with-stringc-str-and-transform
> 
> Anyway, I used lambdas to avoid incurring this issue. Also, the code looks
> cleaner now.
> 
> Could you please test the attached patch?

It's working.
Thanks.
Comment 20 Tom Henderson 2017-09-16 22:45:30 EDT
latest patch pushed in changeset 13066:ba822822d15e