Bugzilla – Bug 2424
RED queueing algorithm never recognizes channel as idle
Last modified: 2016-06-10 05:18:39 EDT
What I am attempting to do: I am modeling an algorithm in NS3 that has very "bursty" communication: there are brief periods where a number of packets are sent, followed by an idle period in the channel. What I expect to happen: I expect the EWMA of the queue size to increase rapidly during the "burst" return to almost zero before the next burst occurs. What I observe: The EWMA does not decrease significantly before the next burst occurs. Additionally, if I enable a small packet stream to keep the channel from idling between bursts, the EWMA decreases. What I believe is happening: In "red-queue.cc" the channel is only marked as idle when the algorithm is initialized, and when DoDequeue() is called on an empty queue. However, in "csma-net-device.cc", (in multiple functions) the queue is checked to see if it is empty before the Dequeue is performed, so a call to DoDequeue() on an empty queue does not occur. What I believe the fix is: The RED queue algorithm needs to check for an empty queue as part of the DoDequeue operation, and mark the channel idle when the last packet is dequeued:
I think that behavior does not apply anymore to ns3.25, due to the traffic control. Anyway, I believe your suggestion could be included, giving the fact that probably these checks aren't done in the traffic-control based version. I checked, and in fact we have a conditional statement that prevents DoDequeue to be called on an empty queue. By the way: why m_idle is 0 or 1? boolean values aren't good? I'm CC'ing also Mohit, which has coded the ARED version, maybe he has some more comments on that.
Stefano, of course feel free to assign it to me if you don't have time to look at it, or maybe Mohit can take it directly..
As Natale said, things have changed quite a lot since ns-3.24. After the introduction of the traffic control, RED is no longer a queue (to install on netdevices) but a queue discipline living in the traffic control module. Stephen, I invite you to upgrade to ns-3.25 (or even better to current ns-3-dev). Your problem might be solved now, because QueueDisc::Dequeue always calls RedQueueDisc::DoDequeue, independently of whether the RED internal queue is empty or not, and RedQueueDisc::DoDequeue sets m_idle to 1 if the RED internal queue is empty. Natale, do you agree?
Stefano, of course feel free to assign it to me if you don't have time to look at it, or maybe Mohit can take it directly..(In reply to Stefano Avallone from comment #3) > As Natale said, things have changed quite a lot since ns-3.24. After the > introduction of the traffic control, RED is no longer a queue (to install on > netdevices) but a queue discipline living in the traffic control module. > > Stephen, I invite you to upgrade to ns-3.25 (or even better to current > ns-3-dev). Your problem might be solved now, because QueueDisc::Dequeue > always calls RedQueueDisc::DoDequeue, independently of whether the RED > internal queue is empty or not, and RedQueueDisc::DoDequeue sets m_idle to 1 > if the RED internal queue is empty. Natale, do you agree? Yes, with traffic control this problem is eliminated; however, it could happen (in the future) that we forgot this detail, and write code that is conceptually similar to what happens now in the csma model: if (m_queue->IsEmpty ()) { return; } else { Ptr<QueueItem> item = m_queue->Dequeue (); NS_ASSERT_MSG (item != 0, "CsmaNetDevice::TransmitReadyEvent(): IsEmpty false but no Packet on queue?"); m_currentPkt = item->GetPacket (); m_snifferTrace (m_currentPkt); m_promiscSnifferTrace (m_currentPkt); TransmitStart (); } In pratice, we need to document that Dequeue has side effects, asking developers to check item != 0 instead of IsEmpty(). Or, more effectively, remove side effects from Dequeue, and inserts the assignment m_idle = 1 before returning true in IsEmpty(). Do you know if there are any others schedulers / AQM with such side effects ? Nat
(In reply to natale.patriciello from comment #4) > Stefano, of course feel free to assign it to me if you don't have time to > look at it, or maybe Mohit can take it directly..(In reply to Stefano > Avallone from comment #3) > > As Natale said, things have changed quite a lot since ns-3.24. After the > > introduction of the traffic control, RED is no longer a queue (to install on > > netdevices) but a queue discipline living in the traffic control module. > > > > Stephen, I invite you to upgrade to ns-3.25 (or even better to current > > ns-3-dev). Your problem might be solved now, because QueueDisc::Dequeue > > always calls RedQueueDisc::DoDequeue, independently of whether the RED > > internal queue is empty or not, and RedQueueDisc::DoDequeue sets m_idle to 1 > > if the RED internal queue is empty. Natale, do you agree? Sorry the delay. Yes, the traffic control takes care of this. > > Yes, with traffic control this problem is eliminated; however, it could > happen (in the future) that we forgot this detail, and write code that is > conceptually similar to what happens now in the csma model: > > if (m_queue->IsEmpty ()) > { > return; > } > else > { > Ptr<QueueItem> item = m_queue->Dequeue (); > NS_ASSERT_MSG (item != 0, "CsmaNetDevice::TransmitReadyEvent(): > IsEmpty false but no Packet on queue?"); > m_currentPkt = item->GetPacket (); > m_snifferTrace (m_currentPkt); > m_promiscSnifferTrace (m_currentPkt); > TransmitStart (); > } > > In pratice, we need to document that Dequeue has side effects, asking > developers to check item != 0 instead of IsEmpty(). Or, more effectively, > remove side effects from Dequeue, and inserts the assignment m_idle = 1 > before returning true in IsEmpty(). Do you know if there are any others > schedulers / AQM with such side effects ? As far as the existing AQMs are concerned, I don't see any of them using m_idle, except RED / ARED. Even PIE (which is under review) doesn't. I agree with Nat on using boolean for m_idle. I shall change it and submit the patch. - Mohit > > Nat
(In reply to Mohit from comment #5) > As far as the existing AQMs are concerned, I don't see any of them using > m_idle, except RED / ARED. Even PIE (which is under review) doesn't. > > I agree with Nat on using boolean for m_idle. I shall change it and submit > the patch. > The patch you've sent for using boolean instead of uint32_t looks fine. Please add it on this bug (so other can review) and in few days we can push it. Anyway, my opinion is that m_idle flag is useless (I will explain why) and dangerous (this bug, even if we have resolved it thanks to other code, is the proof). So, m_idle is used only in DoEnqueue, to basically check that the queue is empty and the packet that we are requested to store is the first. In DoDequeue, we also set idletime as now only when we try to dequeue from an empty queue. But this time is completely random! Idle time starts when the last packet from the queue is removed (more logically). However, with this strategy we are introducing something similar to an histeresis when one packet is enqueued and dequeued continuosly (e.g. the queue size never grows past 1). I don't know the original RED RFC; probably this histeresis is completely fine. What do you think ?
Created attachment 2467 [details] Patch for simplyfyng red queue disc Here's the patch with my idea expressed. I have read the transaction paper, the algorithm is very little compared with what we have here.. I suppose that we can simplify it a lot.