Deadline scheduler merged for 3.14

[Posted January 21, 2014 by corbet]

After years of development, the deadline scheduling class has finally been merged for the 3.14 kernel. This class allows processes to declare an amount of work needing to be done and a deadline by which it must happen; with care, it can guarantee that all processes will meet their deadlines. It has applications in the realtime world, in streaming media processing, and elsewhere.

(Log in to post comments)

Deadline scheduler for network

Posted Jan 21, 2014 17:12 UTC (Tue) by proski (subscriber, #104) [Link]

Is there a deadline scheduler for network? That is, it the packet is not sent before the deadline, it's not sent at all. The only scheduler under net/sched that mentions deadlines is sch_hfsc.c, but it doesn't appear I can set deadlines for specific packets.

Deadline scheduler for network

Posted Jan 21, 2014 18:17 UTC (Tue) by johill (subscriber, #25196) [Link]

Realistically, that needs hardware support, as the packet will spend some time on a hardware queue. Some hardware supports this (I know the Intel wireless hardware does, for example) but setting it up requires having code to synchronise the NIC time domain with the CPU time domain first. It's probably not terribly difficult down to some reasonable error margin though, but the use cases haven't really come up yet. It'd probably be good for voice/video streaming though.

Deadline scheduler for network

Posted Jan 21, 2014 18:38 UTC (Tue) by proski (subscriber, #104) [Link]

Exactly. Voice and video. It things get delayed, commands should go through and the rest should be discarded.

Deadline scheduler for network

Posted Jan 21, 2014 18:43 UTC (Tue) by johill (subscriber, #25196) [Link]

The problem really comes into managing it. You kinda have to tag each packet with a deadline, but how should that deadline be calculated, and when should it be tagged? Should it be a socket option for the video/voice application to set? Realistically, is any application going to call setsockopt() then?

As with any infrastructure project, it's a bit of a chicken-and-egg problem, and I guess it needs somebody willing to invest into both ends. From my point of view (as maintainer of a big chunk of the wireless subsystem) there's little incentive to work on it right now as application support will probably never happen. Think of the PM-QoS parameters the kernel has, e.g. for network latency, nobody ever uses those either.

Deadline scheduler for network

Posted Jan 22, 2014 1:44 UTC (Wed) by Cyberax (✭ supporter ✭, #52523) [Link]

You can do this with the HTB (hierarchical token bucket) queuing discipline. It guarantees a certain bandwidth for each connection, which in reality is quite close to the maximum delay.

In my past experience as a network engineer in a cell phone network it's simply not worth it.

First, you can't make any guarantees for return traffic and for intermediate relays.

Second, complicated QoS is simply not necessary in networks that are adequately provisioned.

Third, even VoIP traffic is quite tolerant to delays. A couple of milliseconds spent during packet dispatch on the sender are not a problem.

We simply used "red/green" traffic separation in our networks - "red" traffic was sensitive control or voice traffic and "green" was everything else. All the routers were configured to give all possible preference to "red" traffic.

Deadline scheduler for network

Posted Jan 22, 2014 9:22 UTC (Wed) by dgm (subscriber, #49227) [Link]

This somehow reminds me of the trick of priority-boosting interactive vs. batch processes. There has been a lot of discussion over the years about the best way to automatically label such processes.

And this makes me think if something like this would be any good for the block subsystem. Partitioning (using cgroups) has been shown to help keep the system responsible under heavy disk load.

But maybe It's too early and I need some coffee.

Deadline scheduler for network

Posted Jan 21, 2014 18:44 UTC (Tue) by kaber (guest, #18366) [Link]

With HFSC you can set deadlines for classes using realtime ("rt") curves with the parameters "umax <max pkt size> dmax <max delay> rate <bps>". If you don't oversubscribe, the packets *will* be sent before the deadline, so there's no support for dropping them. Assuming a well paced flow, you could probably achieve that using a child queue length of 1 or a policer.

Deadline scheduler for network

Posted Jan 21, 2014 20:05 UTC (Tue) by heijo (guest, #88363) [Link]

This seems to be of dubious use, since packets can be arbitrarily delayed while in transit and so the only reliable time to drop delayed packets is after they are received.

So to make it work well, you'd need to add a time deadline option to IP packets, and have all routers respect it.

Even then, if packets get dropped often due to delay, the communication system is going to be unusable anyway, and if they are only dropped rarely, this optimization doesn't provide much of an advantage.

Deadline scheduler for network

Posted Jan 21, 2014 20:23 UTC (Tue) by johill (subscriber, #25196) [Link]

Yes, that's true. However, the immediate use case for Wi-Fi that I had in mind was "Miracast(TM)" streaming, or similar, which is pretty much only a local link.

Deadline scheduler for network

Posted Jan 22, 2014 1:14 UTC (Wed) by droundy (subscriber, #4559) [Link]

I would think this could be useful even if it doesn't *guarantee* that no late packets will be sent, as it could reduce the number of packets that are sent when they are already late. Of course, that would only happen if the first link is slow... but I expect that's not an uncommon scenario. It is, however, hard to imagine it being a huge win, or worth programming into a network client.

Deadline scheduler for network

Posted Jan 22, 2014 14:27 UTC (Wed) by farnz (subscriber, #17727) [Link]

I suspect that in many scenarios, it's the second hop that's slow. You have wired Ethernet or WiFi at high speeds to a router, which then dispatches over a much slower ADSL, VDSL or DOCSIS link to the general Internet.

IOW, my home isn't atypical - 2MBit/s upload to the Internet is more than beaten by even 802.11b WiFi (let alone the 802.11n I actually use). The highest upload I can get for an affordable monthly payment is 30MBit/s - pushing it on 802.11g or 10BASE-T, but on the 802.11n and 100BASE-TX/1000BASE-T I actually use, it's still the bottleneck link.

At work, the upload is much higher, but it's got more contention - there are more people sharing it, and it's still slower than my 1000BASE-T first hop link.

Deadline scheduler for network

Posted Jan 22, 2014 21:30 UTC (Wed) by adiknoth (guest, #95133) [Link]

It's called Ethernet/AVB (audio-video bridging) and requires special NICs with PTP and multi-tx-rings plus AVB-capable switches. You can then set a deadline for a packet, and the NIC's HW scheduler (yes, the magic happens in the NIC, not in software) will pick the packet from the corresponding rings.

Of course, the whole concept requires guaranteed bandwidth across all switches and hence includes a stream reservation protocol. The switches feature a specifically crafted traffic shaper to prioritize AVB traffic.

See https://github.com/intel-ethernet/Open-AVB for the current implementation.

Cheers