Re: [PATCH RFC] pkt_sched: QFQ Plus: fair-queueing service at DRR cost

[Paolo Valente]

Il giorno 01/ott/2012, alle ore 19:52, Stephen Hemminger ha scritto:

> On Mon, 01 Oct 2012 19:46:41 +0200
> Paolo Valente <paolo.valente@xxxxxxxxxx> wrote:
> 
>> Il 01/10/2012 17:31, Stephen Hemminger ha scritto:
>>> On Sun, 30 Sep 2012 19:40:49 +0200
>>> Paolo Valente <paolo.valente@xxxxxxxxxx> wrote:
>>> 
>>>> Hi,
>>>> this patch turns QFQ into QFQ+, a faster variant of QFQ that groups
>>>> classes into aggregates, and uses the original QFQ scheduling
>>>> algorithm to schedule aggregates instead of single classes. An
>>>> aggregate is made of at most M classes, all with the same weight and
>>>> maximum packet size.  M is equal to the minimum between tx_queue_len+1
>>>> and 8 (value chosen to get a good trade-off between execution time and
>>>> service guarantees). QFQ+ associates each aggregate with a budget
>>>> equal to the maximum packet size for the classes in the aggregate,
>>>> multiplied by the number of classes of the aggregate. Once selected an
>>>> aggregate for service, QFQ+ dequeues only the packets of its classes,
>>>> until the aggregate finishes its budget. Finally, within an aggregate,
>>>> classes are scheduled with DRR. In my tests, described below, the
>>>> execution time of QFQ+ with M=8 was from 16% to 31% lower than that of
>>>> QFQ, and close to that of DRR.
>>>> 
>>>> QFQ+ does not use packet lengths for computing aggregate timestamps,
>>>> but budgets. Hence it does not need to modify any timestamp if the
>>>> head packet of a class changes. As a consequence, differently from
>>>> QFQ, which uses head-packet lengths to compute class timestamps, QFQ+
>>>> does not need further modifications to correctly schedule also
>>>> non-leaf classes and classes with non-FIFO qdiscs. Finally, QFQ+ is
>>>> more robust than QFQ against corruption of the data structures
>>>> implementing the bucket lists. A detailed description of QFQ+ can be
>>>> found in [1].
>>>> 
>>>> As for service guarantees, thanks to the way how M is computed, the
>>>> service of QFQ+ is close to the one of QFQ. For example, as proved in
>>>> [1], under QFQ+ every packet of a given class is guaranteed the same
>>>> worst-case completion time as under QFQ, plus an additional delay
>>>> equal to the transmission time, at the rate reserved to the class, of
>>>> three maximum-size packet. See [1, Section 7.1] for a numerical
>>>> comparison among the packet delays guaranteed by QFQ+, QFQ and DRR.
>>>> 
>>>> I measured the execution time of QFQ+, DRR and QFQ using the testing
>>>> environment [2]. In particular, for each scheduler I measured the
>>>> average total execution time of a packet enqueue plus a packet
>>>> dequeue.  For practical reasons, in this testing environment each
>>>> enqueue&dequeue is also charged for the cost of generating and
>>>> discarding an empty, fixed-size packet (using a free list). The
>>>> following table reports the results with an i7-2760QM, against four
>>>> different class sets. Time is measured in nanoseconds, while each set
>>>> or subset of classes is denoted as <num_classes>-w<weight>, where
>>>> <num_classes> and <weight> are, respectively, the number of classes
>>>> and the weight of every class in the set/subset (for example, 250-w1
>>>> stands for 250 classes with weight 1). For QFQ+, the table shows the
>>>> results for the two extremes for M: 1 and 8 (see [1, Section 7.2] for
>>>> results with other values of M and for more information).
>>>> 
>>>>  -----------------------------------------------
>>>> | Set of  |      QFQ+ (M)     |   DRR      QFQ  |
>>>> | classes |    1          8   |                 |
>>>> |-----------------------------------------------|
>>>> | 1k-w1   |   89         63   |    56       81  |
>>>> |-----------------------------------------------|
>>>> | 500-w1, |                   |                 |
>>>> | 250-w2, |  102         71   |    87      103  |
>>>> | 250-w4  |                   |                 |
>>>> |-----------------------------------------------|
>>>> | 32k-w1  |  267        225   |   173      257  |
>>>> |-----------------------------------------------|
>>>> | 16k-w1, |                   |                 |
>>>> | 8k-w2,  |  253        187   |   252      257  |
>>>> | 8k-w4   |                   |                 |
>>>>  -----------------------------------------------
>>>> 
>>>> About DRR, it achieves its best performance when all the classes have
>>>> the same weight. This is fortunate, because in such scenarios it is
>>>> actually pointless to use a fair-queueing scheduler, as the latter
>>>> would provide the same quality of service as DRR. In contrast, when
>>>> classes have differentiated weights and the better service properties
>>>> of QFQ+ make a difference, QFQ+ has better performance than DRR. It
>>>> happens mainly because QFQ+ dequeues packets in an order that causes
>>>> about 8% less cache misses than DRR. As for the number of
>>>> instructions, QFQ+ executes instead about 7% more instructions than
>>>> DRR, whereas QFQ executes from 25% to 34% more instructions than DRR.
>>>> 
>>>> Paolo
>>>> 
>>>> [1] P. Valente, "Reducing the Execution Time of Fair-Queueing Schedulers"
>>>> http://algo.ing.unimo.it/people/paolo/agg-sched/agg-sched.pdf
>>>> 
>>>> [2] http://algo.ing.unimo.it/people/paolo/agg-sched/test-env.tgz
>>>> 
>>>> Signed-off-by: Paolo Valente <paolo.valente@xxxxxxxxxx>
>>> I like the improvement and the performance improvement.
>>> Is there some concern that changing the implementation this much might
>>> upset some people already using QFQ?
>> If you mean people upset for the degradation of the service quality 
>> (which should however be hard to perceive in most practical 
>> applications), then the following solution could address this issue. It 
>> was the my first idea, before I decided not to change the interface at all.
>> 
>> 1. Add an additional parameter M to the tc interface, with two types of 
>> values:
>> 0        -> automatically compute the max number of classes in an 
>> aggregate using the current formula
>>> 0     -> use the value provided by the user as max number of classes
>> 
>> 2. Set M to 1 as default value, which would let QFQ+ behave as QFQ by 
>> default.
>> 
>> tc should however be modified, and people using QFQ should probably move 
>> to the new version (which is the main reason why I opted for the other 
>> solution).
>> 
>> Paolo
>>> What happens if an existing working QFQ config is used in QFQ+?
>>> 
>>> 
>>> 
>> 
>> 
> 
> In order for the transistion to be seamless all possible upgrades
> have to work. As in:
>  * old iproute2 utilities with new kernel with QFQ+
>  * new iproute2 utilities with old kernel with QFQ
> 
> It is okay to force users to give new parameters to get full performance,
> but just don't want to break existing users.

I am sorry for asking again, but I did not clearly understand what you think about the current solution, with no interface change, no need to give new parameters, and no compatibility issues between new and old versions of iproute2 and kernel. But of course with less control over the small service deviation between QFQ+ and QFQ.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/