Linux 2.6.22 Packet Scheduler now accurate?



1 Background

In the 2.6.20 and earlier releases of the Linux kernel, there have problems with the DCCP packet scheduler, some documented here. One of the most remarkable results was that the actual send speed was up to three times higher than the value derived for the idealised throughput

    idealized_throughput(t_ipi)  =  1/t_ipi * 1492 * 8        [in bits/sec]

This lead to a lot of reasoning and discussion. One outgrowth of this was the `avoid accumulation of large send credits' patch, which caused  some controversy.

Below is now experimental evidence that this patch does not seem to be required and in fact degrades performance towards higher speeds.

2 Experimental setup

The experiments used the same experimental setup as earlier, based on using fixed values for t_ipi which are passed to the kernel via sysctls. This bypasses the receiver-sender feedback loop and is useful for isolating problems that pertain to the packet scheduler.

The DCCP Test tree (which contained this patch) based on the netdev 2.6.22 Linux subtree as of 20/7/2007 was used for comparisons.

3 Architectural comparisons

The problem was first detected by comparing the performance of a `naked' 2.6.22 netdev tree to the performance of applying the DCCP test tree patches. On the DCCP test tree the performance was worse. Bisecting among the patches lead to the  send-credit patch as potential culprit. As shown below, applying the patch noticeably degrades performance towards higher link speeds (which will play a role even at lower transmission rates, since DCCP auto-probes for the path capacity). To make sure that this is not just an i386 phenomenon, the following architectures were tested:
The comparisons were simple `before/after' tests.

3.1 Pentium 4

The following figure shows the impact of disabling the send-credit patch on the i386 (data before and after):

3.2 Xeon 3Ghz dual core

The same trend was observed on the dual core SMP box (before and after):


3.3 Sparc64 Ultra80

On the sparc64 the trend is less drastic than on the i386, but still noticeable (before and after):


4. Experiments with different values of HZ

In addition to the above experiments (which were all run at HZ=1000), a throughput comparison was performed with a Pentium M tickless system (DYNTICKS) and a value of HZ=250, since this challenges the accuracy of the scheduling. The results were:

5. rfc3448bis suggestions

The current wisdom in rfc3448bis is to allow accumulation of send credits of up to one RTT. It was tried to implement this `blindly', i.e. as the draft suggests. The performance was as `bad' as with the send-credits patch (which limits accumulation of up to 1 t_ipi instead of 1 RTT). It therefore seems that it is a bad idea to use such throttling with the current implementation of the DCCP packet scheduler.

6. Conclusion

The experiments all agree in that using the send-credits patch is a bad idea with the current 2.6.22 kernel. As a result, it is proposed to remove it from the DCCP test tree, and to encourage further experimentation to find out why the scheduler now works so accurately and didn't in 2.6.20.