Bug 2962

(In reply to Alexander Krotov from comment #0)
> NetDeviceQueueInterface::ConnectQueueTraces accepts only Ptr<Queue<Item>>.
> Queue<Item> implements a drop tail FIFO queue

No, Queue<> is an abstract base class and does not implement any policy. It just provides the methods to enqueue (DoEnqueue), dequeue (DoDequeue), remove (DoRemove) and peek (DoPeek) packets from any position in the queue.

> while DropTailQueue simply
> connects virtual public methods to protected methods, such as Enqueue to
> DoEnqueue etc.

DropTailQueue implements the FIFO policy, as it enqueues packets at the tail and dequeues from the head.

> I propose to move this implementation to DropTailQueue, as it was before
> qdisc implementation. Everyone who wants to build on top of FIFO drop tail
> queue (for example, WifiMacQueue) should inherit from DropTailQueue.

I disagree. Everyone who wants to implement a non-FIFO queue (for example, WifiMacQueue) should inherit from the Queue<> abstract base class, not from DropTailQueue<> (which implements a specific queuing policy).

> Otherwise when I want to implement non-FIFO queue for my network device, I
> have to build on top of Queue<>, which has std::list m_packets and a bunch
> of methods (DoEnqueue, DoDequeue, ...) which I don't need.

Subclasses need to define Enqueue, Dequeue, ... methods (and possibly others) that make use of the DoEnqueue, DoDequeue, ... methods to enqueue, dequeue, ... packets from any position in the queue (head, tail, middle, ...). WifiMacQueue is an example of how a non-FIFO queuing policy can be implemented by using these methods.

> I believe the initial idea was to implement something similar to Linux
> network stack architecture, with Queue<> interface emulating sk_buff between
> the L3 stack and device drivers, but in NS-3 we don't need this ring buffer,
> because we don't have to meet realtime requirements. We need a simple
> "Enqueue" interface, which each NetworkDevice can implement however it wants.

Not really, the current design of Queue<> has been just made to have WifiMacQueue inherit from Queue<>, so that WifiNetDevices can easily support flow control, so that AQM algorithms work on top of WifiNetDevices (you recall that before the introduction of qdiscs, it was not possible to use Red and Codel on WifiNetDevices).

> Implemented architecture works fairly well to emulate "dumb" device drivers,
> which simply pass received packets to hardware queue. In this case m_packets
> structure serves to emulate hardware queue, which is usually a simple FIFO
> queue indeed. But when I want to do additional queueing on the device driver
> level, I have to implement on top of Queue<> but ignore the m_packets
> structure completely.

Again, I think WifiMacQueue is an example of a "complex" queuing policy implemented as a subclass of Queue<>. If you tell us more details about what you want to implement, I can probably better help you.

(In reply to Stefano Avallone from comment #1)
> (In reply to Alexander Krotov from comment #0)
> > NetDeviceQueueInterface::ConnectQueueTraces accepts only Ptr<Queue<Item>>.
> > Queue<Item> implements a drop tail FIFO queue
> 
> No, Queue<> is an abstract base class and does not implement any policy. It
> just provides the methods to enqueue (DoEnqueue), dequeue (DoDequeue),
> remove (DoRemove) and peek (DoPeek) packets from any position in the queue.

Well, it does not implement drop tail FIFO queue, but it has more logic than it should.

Firstly, DoEnqueue drops packets that do not fit the queue.
What if I want to implement infinite queue without any limits instead?

Secondly, Queue<> has std::list structure for m_packets, but I may want to have a non-linear queue.
Even WifiMacQueue can benefit from having std::map<{tid,addr}, std::list<Packet>> instead
of a simple std::list, from the performance point of view.

> > while DropTailQueue simply
> > connects virtual public methods to protected methods, such as Enqueue to
> > DoEnqueue etc.
> 
> DropTailQueue implements the FIFO policy, as it enqueues packets at the tail
> and dequeues from the head.
> 
> > I propose to move this implementation to DropTailQueue, as it was before
> > qdisc implementation. Everyone who wants to build on top of FIFO drop tail
> > queue (for example, WifiMacQueue) should inherit from DropTailQueue.
> 
> I disagree. Everyone who wants to implement a non-FIFO queue (for example,
> WifiMacQueue) should inherit from the Queue<> abstract base class, not from
> DropTailQueue<> (which implements a specific queuing policy).

I agree that anyone who wants a non-FIFO policy should inherit from the Queue<>.
I have said that _FIFO policies_ should inherit from DropTailQueue.

The problem is that Queue<> is not abstract enough, it implies std::list storage,
which is not suitable for some kinds of queueing (for example, implementing FQ on
the MAC layer, like described in this article:
https://www.usenix.org/system/files/conference/atc17/atc17-hoiland-jorgensen.pdf
)

Maybe there should be an intermediate step, between the Queue<> and DropTailQueue<>,
let's say FifoQueue<>. What I propose is not move std::list<> m_packets and
all the functions that manipulate it, somewhere out of the Queue<>.

Or, the other way round, implement a pure virtual QDiskInterface class,
which will serve as a base class for the Queue<>.

> > Otherwise when I want to implement non-FIFO queue for my network device, I
> > have to build on top of Queue<>, which has std::list m_packets and a bunch
> > of methods (DoEnqueue, DoDequeue, ...) which I don't need.
> 
> Subclasses need to define Enqueue, Dequeue, ... methods (and possibly
> others) that make use of the DoEnqueue, DoDequeue, ... methods to enqueue,
> dequeue, ... packets from any position in the queue (head, tail, middle,
> ...). WifiMacQueue is an example of how a non-FIFO queuing policy can be
> implemented by using these methods.

The problem is that I want to implement a queueing policy that is hard to
implement on top of DoEnqueue and DoDequeue. In fact, even WifiMacQueue does
not actually use DoDequeue, because it is not flexible enough.

For example, here m_queue->PeekByTidAndAddress is called, and then the peeked packet is removed via m_queue->Remove:
https://code.nsnam.org/index.cgi/ns-3-dev/file/f868c87528b1/src/wifi/model/qos-txop.cc#l289

Packet is dequeued, but DoDequeue is not called. Instead, WifiMacQueue::Remove goes through
the list again to find a packet that it needs to remove.

> > I believe the initial idea was to implement something similar to Linux
> > network stack architecture, with Queue<> interface emulating sk_buff between
> > the L3 stack and device drivers, but in NS-3 we don't need this ring buffer,
> > because we don't have to meet realtime requirements. We need a simple
> > "Enqueue" interface, which each NetworkDevice can implement however it wants.
> 
> Not really, the current design of Queue<> has been just made to have
> WifiMacQueue inherit from Queue<>, so that WifiNetDevices can easily support
> flow control, so that AQM algorithms work on top of WifiNetDevices (you
> recall that before the introduction of qdiscs, it was not possible to use
> Red and Codel on WifiNetDevices).

qdisc just needs an Enqueue callback and nothing else. In Linux SKBs are used
to pass packets from qdisc to device drivers, but in NS-3 a simple callback
is enough. 

> > Implemented architecture works fairly well to emulate "dumb" device drivers,
> > which simply pass received packets to hardware queue. In this case m_packets
> > structure serves to emulate hardware queue, which is usually a simple FIFO
> > queue indeed. But when I want to do additional queueing on the device driver
> > level, I have to implement on top of Queue<> but ignore the m_packets
> > structure completely.
> 
> Again, I think WifiMacQueue is an example of a "complex" queuing policy
> implemented as a subclass of Queue<>. If you tell us more details about what
> you want to implement, I can probably better help you.

I want to implement a policy that serves STAs in round-robin fashion, non FIFO.
For that, I need to store packets not in the std::list, but in multiple queues,
one per destination.

Now I have replaced WifiMacQueue with a WifiMacScheduler class, which implements Queue<>,
but ignores the m_packets and all those functions. It is a virtual class.
There is one WifiMacScheduler per AC, just like there was one WifiMacQueue per AC before.

On top of that I have WifiMacFifoScheduler, which has one WifiMacQueue inside.
It simply passes all the calls (Enqueue, PeekFirstAvailable etc.) to this WifiMacQueue and backwards.

Also I have WifiMacRrScheduler, which has multiple WifiMacQueues inside, one per TID+destination pair.

I hope to share the code when I finish it, but you can see the problem from the description.
Abstract class WifiMacScheduler has m_packets list inside which is simply ignored.
That is because it has to implement Queue<> to interface with qdisk.
But I do not need any of the Queue<> and QueueBase implementations at this layer.

In other words, Queue<> serves both as an interface from qdisk to device driver (NetDevice in NS-3) and as a hardware queue. I think Queue<> should be just a queue, which one may use or may not use (it is in /utils/ after all) to implement hardware queues, qdisk<->device interface should instead be replaced with a pure abstract class, that probably has only one "Enqueue" method.

Well, the idea of the current design is to make the Queue<> class as simple as possible, because it should just be a means to store a collection of packets. More or less complex queuing policies should be implemented via qdiscs. You are correct that Queue<>::DoEnqueue checks whether the queue size is exceeded: this is the result of some discussions with Natale, according to whom it makes no sense to consider an infinite queue (I am open to re-discussing this point). Concerning the choice of std::list, I think a list is flexible enough to implement simple queuing policies and it is aligned with the design of Queue<> as a means to just store a collection of packets. Currently, qdiscs can implement complex queuing policies, but packets are ultimately stored within Queues.

I am aware of Toke's work and I can think of other situations (the OFSwitch13 and LTE modules) where a Queue<> is currently used but more complex queuing policies are desirable. I don't think that implementing complex Queue<> subclasses is the way to go here, because we may have a duplicate implementation of many queuing policies (think of FQ-CoDel...), both as QueueDisc subclasses and Queue subclasses.

What I am planning for ns-3.30 (and to work on in the next weeks) is to find a proper solution for the above situations. One solution may be to convert the involved NetDevices to using Ptr<QueueDisc> instead of Ptr<Queue> to store packets. In fact, the FifoQueueDisc is basically nothing more than a DropTail queue. But more complex strategies could be achieved by reusing (or implementing new) QueueDiscs. However, this would probably require to have templated QueueDiscs as well, if we want them to be used in different context. Some other changes may also be required in the QueueDisc class and in the NetDeviceQueueInterface class as well.

(In reply to Stefano Avallone from comment #4)
> Well, the idea of the current design is to make the Queue<> class as simple
> as possible, because it should just be a means to store a collection of
> packets. More or less complex queuing policies should be implemented via
> qdiscs. You are correct that Queue<>::DoEnqueue checks whether the queue
> size is exceeded: this is the result of some discussions with Natale,
> according to whom it makes no sense to consider an infinite queue (I am open
> to re-discussing this point). Concerning the choice of std::list, I think a
> list is flexible enough to implement simple queuing policies and it is
> aligned with the design of Queue<> as a means to just store a collection of
> packets. Currently, qdiscs can implement complex queuing policies, but
> packets are ultimately stored within Queues.
> 
> I am aware of Toke's work and I can think of other situations (the
> OFSwitch13 and LTE modules) where a Queue<> is currently used but more
> complex queuing policies are desirable. I don't think that implementing
> complex Queue<> subclasses is the way to go here, because we may have a
> duplicate implementation of many queuing policies (think of FQ-CoDel...),
> both as QueueDisc subclasses and Queue subclasses.
> 
> What I am planning for ns-3.30 (and to work on in the next weeks) is to find
> a proper solution for the above situations. One solution may be to convert
> the involved NetDevices to using Ptr<QueueDisc> instead of Ptr<Queue> to
> store packets. In fact, the FifoQueueDisc is basically nothing more than a
> DropTail queue. But more complex strategies could be achieved by reusing (or
> implementing new) QueueDiscs. However, this would probably require to have
> templated QueueDiscs as well, if we want them to be used in different
> context. Some other changes may also be required in the QueueDisc class and
> in the NetDeviceQueueInterface class as well.

I am ok with the implementation of the Queue<>, std::list is the right choice for queue implementation.
I just don't like that it is used for qdisc<->NetDevice interface.

NetDevice represents a hardware and its driver. No need to enforce using Queue or QueueDisc
inside the driver implementation.
Just standardize the qdisc<->NetDevice interface, and let the NetDevice store
packets however it wants, as long as it implements this interface.

Then it is possible to store packets in Queue<> or QueueDisc inside the Wi-Fi or LTE MAC implementation,
or not store them at all and just count some statistics, for example.

(In reply to Alexander Krotov from comment #5)
> I am ok with the implementation of the Queue<>, std::list is the right
> choice for queue implementation.
> I just don't like that it is used for qdisc<->NetDevice interface.
> 
> NetDevice represents a hardware and its driver. No need to enforce using
> Queue or QueueDisc
> inside the driver implementation.
> Just standardize the qdisc<->NetDevice interface, and let the NetDevice store
> packets however it wants, as long as it implements this interface.
> 
> Then it is possible to store packets in Queue<> or QueueDisc inside the
> Wi-Fi or LTE MAC implementation,
> or not store them at all and just count some statistics, for example.

There is a fundamental aspect of the interactions between qdiscs and netdevices: flow control. A netdevice has to tell the qdisc that its queue is full or there is room again. Additionally, techniques like BQL rely on notifications about the amount of bytes enqueued into and dequeued from the device queue. Using the Queue<> class is very convenient here thanks to the traces (enqueue, dequeue) it provides. Of course, we do not necessarily need to use Queue<>, but then the NetDevice has to implement the support for flow control and BQL in an alternative manner.

Anyway, since I am about to start re-thinking some aspects in this area, I will take into account your suggestion of having a standardized interface between qdiscs and netdevices.