Convert Queue into a template class

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Convert Queue into a template class

Stefano Avallone
Hi all,

as the subject says, I worked on converting the Queue class into a template class. There are two main reasons behind this work:

1) all the queue discs perform ugly static casts when dequeuing packets from their internal queue: the Queue::Dequeue methods returns a Ptr<QueueItem> but we know (and need) that the returned item is a Ptr<QueueDiscItem>

2) adding support for flow control and BQL to netdevices requires to perform some actions in all the places where a packet is enqueued into or dequeued from the device queue. The current approach to adding such support leads to redundant code and is error-prone (we might miss some places where a packet is enqueued and dequeued). The latter especially holds for devices such as wifi where enqueue and dequeue operations are scattered throughout the whole module. Hence, I had the idea to add a few methods to the NetDeviceQueueInterface class that perform the actions required when enqueuing or dequeuing packets to support flow control and BQL. All the netdevices need to do is to connect the traced callbacks (enqueue, dequeue and drop) of their queue(s) to such methods through bound callbacks.

Making Queue a template class solves 1) and enables to adopt the approach in 2) for wifi.

I opened two code reviews (for the moment). The first one converts Queue into a template class:

https://codereview.appspot.com/316080043/ <https://codereview.appspot.com/316080043/>

This involved a number of changes:

- a non-template base class, QueueBase, is introduced which includes all the methods that are independent of the type of items in the queue. This required to change Queue::QUEUE_MODE_PACKET into QueueBase::QUEUE_MODE_PACKET (many files are touched just to make this change)

- the class Queue becomes a template class, Queue<Item>. The typeid of each instance is “ns3::QueueOf”+Item, e.g. “ns3::QueueOfPacket” or “ns3::DropTailQueueOfQueueDiscItem”. This is done with the help of two macros, NS_OBJECT_TCLASS_DECLARE and NS_OBJECT_TCLASS_DEFINE (which I added to object-base.h because they could be used for every template object class). The latter also register an instance of the Queue class with the TypeId system. The former shall be included in an header file and defines a convenient alias for the type of a specific instance (e.g., QueueOfPacket or DropTailQueueOfQueueDiscItem). The latter shall be included in the .cc file (just like NS_OBJECT_ENSURE_REGISTERED).

- The only requirement on the type parameter of Queue is that it must provide a GetSize () method which returns the size of the packet. Hence, the (unmodified) Packet class can be used as type parameter of Queue. Thus, net devices queue can store Ptr<Packet> again, instead of Ptr<QueueItem>. Internal queues of queue discs store instead Ptr<QueueDiscItem> and no static casts are needed anymore. This required to change QueueItem::GetPacketSize () into QueueItem::GetSize () (many files are touched just to make this change)

- The only requirement on subclasses of Queue is that they have to declare a static const std::string TypeParamName; (which is then defined by the NS_OBJECT_TCLASS_DEFINE class)

- Currently, queue.cc <http://queue.cc/> instantiates and registers QueueOfPacket, drop-tail.cc registers DropTailQueueOfPacket, queue-disc.cc <http://queue-disc.cc/> registers QueueOfQueueDiscItem and DropTailQueueOfQueueDiscItem

- Given that the implementation of the template methods must reside in the header file, I introduced an alternative method to perform logging based on a method of the non-template QueueBase class. Instead of calling NS_LOG_xxx (a << b << c), the Queue class and its subclasses have to call NsLog (LOG_LEVEL_xxx, a, b, c). For C++11 fans, this exploits variadic templates :-) The logging is enabled by enabling the Queue log component

- Another (optional) change I made is to move QueueItem to separate queue-item.{h,cc} files (in network/utils) and QueueDiscItem to separate queue-disc-item.{h,cc} files in traffic-control/model. This is to avoid that modules requiring QueueDiscItem (such as ipvX-flow-probe) have to include the whole queue.h and queue-disc.h. Actually, QueueItem is no longer needed. If you think that it could be useful to derive other subclasses in the future, we can leave it. Otherwise, we can just leave QueueDiscItem (in network/utils — currently, it is used by wifi-net-device for the select queue callback)

- Another change included in this patch is the addition of two traced callbacks to the Queue class: DropBeforeEnqueue and DropAfterDequeue (as discussed with Tom and Natale a while ago). This is required by the new flow control approach because different actions must be performed when a packet is dropped before enqueue (the queue is full) or after dequeue

The second code review implements the new approach for the support of flow control and BQL:

https://codereview.appspot.com/313270043 <https://codereview.appspot.com/313270043>

This is rather straightforward and show how easy it is to add support for flow control and BQL to net devices.

Future work includes:

- making Queue hold a std::list<Item> instead of having subclasses use their own queue. DoEnqueue, DoDequeue and DoPeek will get a new argument, a std::list<Item>::iterator, to allow operations in different places of the queue (needed by wifi)

- making wifi use Queue<WifiMacQueueItem> and remove the Cleanup () method

- add support for flow control and BQL to wifi

I hope to get this done by the end of next week. In the meantime, any feedback/comment would be much appreciated.

Thanks,
Stefano





Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Convert Queue into a template class

Tom Henderson-2
On 01/03/2017 04:21 AM, Stefano Avallone wrote:

> Hi all,
>
> as the subject says, I worked on converting the Queue class into a
> template class. There are two main reasons behind this work:
>
> 1) all the queue discs perform ugly static casts when dequeuing
> packets from their internal queue: the Queue::Dequeue methods returns
> a Ptr<QueueItem> but we know (and need) that the returned item is a
> Ptr<QueueDiscItem>
>
> 2) adding support for flow control and BQL to netdevices requires to
> perform some actions in all the places where a packet is enqueued
> into or dequeued from the device queue. The current approach to
> adding such support leads to redundant code and is error-prone (we
> might miss some places where a packet is enqueued and dequeued). The
> latter especially holds for devices such as wifi where enqueue and
> dequeue operations are scattered throughout the whole module. Hence,
> I had the idea to add a few methods to the NetDeviceQueueInterface
> class that perform the actions required when enqueuing or dequeuing
> packets to support flow control and BQL. All the netdevices need to
> do is to connect the traced callbacks (enqueue, dequeue and drop) of
> their queue(s) to such methods through bound callbacks.
>
> Making Queue a template class solves 1) and enables to adopt the
> approach in 2) for wifi.
>
> I opened two code reviews (for the moment). The first one converts
> Queue into a template class:
>
> https://codereview.appspot.com/316080043/
> <https://codereview.appspot.com/316080043/>

Stefano, I had a look at the reviews and your overall design proposals
and implementation look reasonable to me to solve the issues above
(templates may be a better fit than inheritance to generalize the
objects in held in queue structures).  I'd like to encourage other
maintainers to review since this proposes at the core level to open the
ns3::Object system to templated classes, and for queue-related code,
would result in some API changes of the related class names, such as:

-  Ptr<Queue> queue = ptpnd->GetQueue ();
+  Ptr<QueueOfPacket> queue = ptpnd->GetQueue ();

and some new conventions for how to perform logging for such classes.

- Tom
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Convert Queue into a template class

Stefano Avallone
In reply to this post by Stefano Avallone
Hi all,

> On 3 Jan 2017, at 13:21, Stefano Avallone <[hidden email]> wrote:
>
> Future work includes:
>
> - making Queue hold a std::list<Item> instead of having subclasses use their own queue. DoEnqueue, DoDequeue and DoPeek will get a new argument, a std::list<Item>::iterator, to allow operations in different places of the queue (needed by wifi)
>
> - making wifi use Queue<WifiMacQueueItem> and remove the Cleanup () method
>
> - add support for flow control and BQL to wifi
>

just to let you know that I completed the work outlined above. I have to say that I am rather satisfied with the result. I opened bug #2633 to keep track of the various code reviews this work consists of.

Thanks,
Stefano


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Convert Queue into a template class

Stefano Avallone
In reply to this post by Tom Henderson-2
Hello all,

> On 16 Jan 2017, at 00:39, Tom Henderson <[hidden email]> wrote:
>
> On 01/03/2017 04:21 AM, Stefano Avallone wrote:
>> Hi all,
>>
>> as the subject says, I worked on converting the Queue class into a
>> template class. There are two main reasons behind this work:
>>
>> 1) all the queue discs perform ugly static casts when dequeuing
>> packets from their internal queue: the Queue::Dequeue methods returns
>> a Ptr<QueueItem> but we know (and need) that the returned item is a
>> Ptr<QueueDiscItem>
>>
>> 2) adding support for flow control and BQL to netdevices requires to
>> perform some actions in all the places where a packet is enqueued
>> into or dequeued from the device queue. The current approach to
>> adding such support leads to redundant code and is error-prone (we
>> might miss some places where a packet is enqueued and dequeued). The
>> latter especially holds for devices such as wifi where enqueue and
>> dequeue operations are scattered throughout the whole module. Hence,
>> I had the idea to add a few methods to the NetDeviceQueueInterface
>> class that perform the actions required when enqueuing or dequeuing
>> packets to support flow control and BQL. All the netdevices need to
>> do is to connect the traced callbacks (enqueue, dequeue and drop) of
>> their queue(s) to such methods through bound callbacks.
>>
>> Making Queue a template class solves 1) and enables to adopt the
>> approach in 2) for wifi.
>>

I recently updated the code reviews [1][2][3] that make Queue a class template and add support for flow control and BQL to CsmaNetDevice and SimpleNetDevice according to the new design. As usual, the most updated version of this work can be found on GitHub [4]. I believe this work is now ready to merge. Changes with respect to the previous version:

- as suggested by Tom, I removed the introduction of aliases for Queue specifications. Now, we need to use Queue<Packet> or DropTailQueue<Packet>

- I changed the way GetTypeID methods obtain the type name of the stored items to fix runtime errors with g++-4.9. Together with the removal of aliases, this now allows us to introduce a single new macro in object-base.h (instead of two)

- I tried to optimize build performance and remove unneeded inclusions of header files. This is much required now, since queue.h includes the implementation of the template methods. This work involved:
  + forward declaring the Queue template class where possible (almost everywhere)
  + using explicit template instantiation declarations to suppress implicit instantiations where possible
  + moving QueueItem and QueueDiscItem classes to a new module (queue-item.{h,cc} in network/utils)
  + moving NetDeviceQueue and NetDeviceQueueInterface classes to a new module (net-device-queue-interface.{h,cc} in network/utils)
  + introducing a new QueueDiscMode enum in queue discs (red, pie and codel) that can work either in packet mode or byte mode. This is to avoid including queue.h because of the QueueMode enum

Important remark: [3] introduces a ConstIterator type (std::list<Ptr<Item> >::const_iterator) to allow subclasses of Queue to specify the position where the insertion/removal of elements should take place. This is fine because, since C++11, std::list::insert and std::list::erase accepts a const iterator. However, this feature seems to be unimplemented in the standard library shipped with g++-4.8, which produces a build error (an iterator is required). So, either we raise the minimum g++ version required to 4.9 or I have to revert to an Iterator (until the minimum requirement is raised to g++-4.9). The minimum requirement for ns-3.26 was g++-4.8.

Regarding API changes, (I may miss something now, but I believe) two only changes were made:
- QueueItem::GetPacketSize () has been replaced by QueueItem::GetSize ()
- Queue::DequeueAll () has been replaced by Queue::Flush () (gives better the idea that packets are removed instead of being dequeued)

User visible changes:
- Queue<Packet> and DropTailQueue>Packet> must be used instead of Queue and DropTailQueue. However, the SetQueue method of the p2p and csma helpers still allows to specify “ns3::DropTailQueue”
- Parameter independent methods and members (e.g., QueueMode enum, GetNPackets (), etc) have been moved to the QueueBase base class

Thanks,
Stefano


[1] https://codereview.appspot.com/316080043/ <https://codereview.appspot.com/316080043/>
[2] https://codereview.appspot.com/313270043/ <https://codereview.appspot.com/313270043/>
[3] https://codereview.appspot.com/313370043/ <https://codereview.appspot.com/313370043/>
[4] https://github.com/stavallo/ns-3-dev-git/commits/tc-next <https://github.com/stavallo/ns-3-dev-git/commits/tc-next>

Loading...