Multiqueue support

Multiqueue support

[Pasquale Imputato, 2015-06-22 14:48:41]

This is our attempt at adding support for multiqueue netdevices (such as WiFi)
in ns-3, following the same strategy as Linux. The starting point is Tom’s work
to introduce priority queues (the equivalent of Linux qdiscs), reported here as
patch set #1.

In Linux, packets dequeued by the queueing discipline are enqueued again in the
hardware queue of the device. More and more devices today support multiple
hardware queues to increase performance. WiFi, for instance, supports 4 hardware
queues to handle traffic with different priorities. The idea is to have the
qdisc create as many queues as the number of hardware queues and have each
packet carry the number of the queue it has to be enqueued into (both at the
qdisc level and at the hardware level). This is achieved by using a field
(queue_mapping) of the skbuff structure to carry such queue number. Such a field
is set before the packet is enqueued by the qdisc by calling the select_queue
method registered by the device (if any, otherwise some fallback mechanisms -
among which a simple hashing - are employed). A few qdiscs, such as multiq and
mqprio, support multiqueue devices through this technique. mac8011 registers a
select_queue method to classify packets according to the ToS byte (for IPv4).
Some notes we took while looking at the kernel code are available here [1].

Patch set #2 just adds a m_numTxQueues field to a NetDevice (this is the
equivalent of the num_tx_queues field in the Linux struct net_device) and a
virtual uint8_t GetNumTxQueues() method to the NetDevice base class. The
m_numTxQueues field is actually implemented only in WifiNetDevice. For the other
devices (where it is not currently used) the GetNumTxQueues() method simply
returns 1. For WifiNetDevices, m_numTxQueues is set when installing the MAC (in
WifiNetDevice::SetMac), given that the number of queues is 4 if the MAC supports
QoS and 1 otherwise.

Patch set #3 implements the equivalent of skb->queue_mapping by means of a
QueueTag and the equivalent of the select_queue method by means of a virtual
uint8_t GetSelectedQueue(Ptr<Packet>) method in the NetDevice base class. The
latter returns zero for all the devices, except for WifiNetDevices, where the
queue is identified based on the Access Category (this is done by a newly
introduced QosUtilsGetQueueForAc function). For each packet, the
Ipv4Interface::DeviceQueueTransmit function calls the device GetSelectedQueue
function and adds a QueueTag with the returned value to the packet before
passing the packet to the priority queue. The value of this tag will be used by
multiqueue-aware qdiscs and multiqueue devices.

In the Wifi area, one of the things that could be done to make the ns-3 behavior
more similar to that of Linux is to review the selection of the Tid for a
packet. In ns-3, this is currently based on a QoS tag. In Linux (mac80211), it
is done based on the ToS byte for IPv4.

More patch sets to come shortly....

Looking forward to feedbacks and comments, thanks for your attention.

[1]
https://docs.google.com/document/d/13ZPco990UKFW8Ox59P9IiLbAIc51Z9m1QU3k-Sf0z...

[Pasquale Imputato, 2015-11-24 09:02:38]

Hi,
our updated approach is in [1].
Any comment/review of the code would be much appreciated.

[1] https://github.com/stavallo/ns-3-dev-git/commits/traffic-control

[tomh_tomh.org, 2015-11-24 18:02:33]

On 11/24/2015 01:02 AM, p.imputato@gmail.com wrote:
> Hi,
> our updated approach is in [1].
> Any comment/review of the code would be much appreciated.
>
> [1] https://github.com/stavallo/ns-3-dev-git/commits/traffic-control
>
> https://codereview.appspot.com/244440043/

Hi, can you provide a bit more background?

- should the codereview be disregarded at this time?  (the github code 
is newer)

- are there any open issues or things you wish to call out to people 
regarding the code?  Is there a good example program that we can try it 
out with?

Thanks,
Tom

[Pasquale Imputato, 2015-11-25 22:32:23]

2015-11-24 19:02 GMT+01:00 Tom Henderson <tomh@tomh.org>:

> On 11/24/2015 01:02 AM, p.imputato@gmail.com wrote:
>
>> Hi,
>> our updated approach is in [1].
>> Any comment/review of the code would be much appreciated.
>>
>> [1] https://github.com/stavallo/ns-3-dev-git/commits/traffic-control
>>
>> https://codereview.appspot.com/244440043/
>>
>
> Hi, can you provide a bit more background?
>
> - should the codereview be disregarded at this time?  (the github code is
> newer)
>

Hi Tom,

this work has been announced on the ns-developers mailing list by Stefano
Avallone.
The codereview can be disregarded; the github code provides a refinement of
the design of traffic-control and queue disc in ns-3.


>
> - are there any open issues or things you wish to call out to people
> regarding the code?


We ask a general comment/review about the work in order to define future
directions.

Open issue are:

- how to render qdisc_reschedule in ns-3. When dequeue operations are
stopped, Linux reschedules the qdisc (i.e., a qdisc_run will be invoked as
soon as the cpu can schedule it). For the moment, we do nothing in place of
a reschedule call. A possibility would be to schedule a QueueDisc::Run
after a predefined amount of time, but we are not sure yet how to set such
amount of time

- we would like the NetDevice base class to allocate the array used to
track the status of each transmission queue. However, each derived class
has to specify the number of physical tx queues at construction time. Can
we use the DoInitialize method to achieve this goal? For instance, the
NetDevice base class has a protected member m_numTxQueues;
WifiNetDevice::DoInitialize sets m_numTxQueues to 4; then
NetDevice::DoInitialize allocates, e.g., a vector of 4 boolean value


> Is there a good example program that we can try it out with?
>

A simple example that show how use TrafficContorlHelper has been added to
the branch and is in examples/traffic-control.


>
> Thanks,
> Tom
>

Thanks,

-- 
Pasquale Imputato