Talk:Network scheduler

Linux specific

This appears to be a Linux-specific component and term. Recent edits have created links from general topics to this page. Those edits need to be reverted or this article needs to be made and referenced more generally. I'm not sure the latter is possible as I not aware of "network scheduler" having widespread use in describing queue and congestion management topics. Wikipedia is not the place to create new terminology. ~KvnG 13:15, 14 September 2013 (UTC)

The term is not a all specific to Linux. It derives from Process scheduler. I do not think the implementation for the Linux kernel even has some fancy name, so I simply called it Linux network scheduler. ScotXW (talk) 13:27, 14 September 2013 (UTC)

Do you have any citations to support this. All but one of the article's current citations relate to Linux. The one that does not does not contain "network scheduler". ~KvnG 03:14, 15 September 2013 (UTC)

I'm not sure this is a Linux specific term, though I agree its presentation here is skewed towards that aspect. I would also consider setting up a redirect from (or to) transmission scheduling, as this is also an existing term, if not exactly a common coin, on Wikipedia for the subject. However, if there's to be a consensus argument about the terminology, I "vote" for "network schedlung" as the slightly more clear term, but would more strongly support "network transmission scheduling", with redirects from network and transmission scheduling, as the most clear.

I also admit my perception of the subject may be somewhat skewed by my obsession with hard real-time data transfers in avionic systems. In that context, there are two points of interest to me, which are transmission scheduling in the end systems and traffic management in the layer 2 switches; specifically bandwidth management and aspects of resource reservation – which is not a trivial, i.e. bandwidth only, subject for hard real-time systems. Examples of what I would think falls under network / transmission scheduling in an end system are the control of the Bandwidth Allocation Gap (BAG) in an AFDX network interface and scheduling of Time Triggered transfers in TTEthernet. I can probably also provide references to cite for the network / transmission scheduling in these protocols, though they may be a wee while in comming. We also expect to specifically schedule real-time transfers over an Ethernet network in future Integrated Modular Avionic Systems. None of these are specific to an OS. Indeed, the AFDX and TTE solutions are generally implemented in hardware, mostly because doing it in software doesn't work at anything more than very low rates and then only if you dedicate a processor to the task. As an aside, that (bespoke hardware) is such a poor solution to the problem that we're working quite hard to do it much, much better in IMS, i.e. using just IEEE 802.3 NICs; but I digress, again.

I won't comment on network scheduling in routers and switches higher than layer 2 for fear of making a bigger ass of myself than is necessary. In regard to layer 2 switches, our plan is to use per (real-time) connection traffic policing on ingress and an overall limit on egress bandwidth. The thing is, I know that these are not ideas that are specific to us and our applications, as they are provided in the Intel FM4000 switching core chip and are (though mostly optional) in OpenFlow v1.3.0. The overall limit on egress bandwidth could come under this issue of network scheduling, but is not, to my mind, covered in the current network scheduling article. That's the reason I objected to the redirect of bandwidth shaping to here, as it is, in my view, a broader issue than network scheduling, certainly as it is presented on this page. I also don't expect this page to cover much on resource reservation, etc., which I think is very relevant to bandwidth shaping and the possibly bigger subject of bandwidth management. Hence, the bandwidth management article is where I think bandwidth shaping should redirect.

I would also argue with some of the detail in this network scheduler article, e.g. that the buffer is necessarily circular. That, to me, is very much an implementation issue, and I think there's much too much of that sort of thing far too early on in the current article. However, I doubt I will have time or inclination to do more than comment on the subject anytime soon. Though, were it deemed relevant, I might provide a section on BAG control in AFDX, and, just possibly, the cyclicly scheduled transmissions in TTE. But don't expect them to extoll the virtues of AFDX or TTE - I don't see very many.

Slightly off topic, I'd also question the renaming of the "congestion avoidance" section of the network congestion page to "mitigation", but aren't, at this time, prepared to be bold.

Graham.Fountain | Talk 12:11, 17 September 2013 (UTC)

It sounds like you would like to see this article broadened beyond a discussion of network scheduling in Linux. Please go ahead. That would fix the problem of a bunch of new links to this page referencing the general concept but landing here where there's a narrow treatment. The other option is to revert the edits that created all these new links. Those interested in working to improve things in this area should also have a look at Scheduling and Scheduling (computing). ~KvnG 17:47, 18 September 2013 (UTC)

Dubious statement about difference between leaky and token bucket algorithms

My problem is that there is absolutely no effective difference between the leaky and token bucket algorithms : they are exact mirror images of one another. In one, the bucket content is added by a conforming packet/frame/cell if it will not overflow and leaks away over time ; in the other, the bucket content is removed by a conforming packet/frame/cell if it will not underflow and is dripped in over time. Hence, in each case and point, an exactly equal and oposite action is taken. The only reasonably credible place I can find where a distinction is made is in Tanenbaum’s Computer Networks, and I'm afraid that is simply wrong in this instance.

If there’s any confusion over this issue, I suggest looking at the leaky bucket page, specifically at the section on the leaky bucket as a queue, which is all that Tanenbaum describes, despite referencing Turner’s original description of the leaky bucket algorithm, which is clearly of a leaky bucket as a meter. The claim that a traffic policing or shaping function using the leaky bucket algorithm is incapable of passing traffic with a burstiness greater than zero is simply untrue. This is clearly so for the GCRA, which is an implementation of the LBA and used in ATM UPC/NPC in some cases as a dual bucket (where the burstiness of one bucket specifically determins the number of packet/frame/cells in the higher layer message/packet length), and burstiness is specifically mentioned in Turner's original description : “A counter associated with each user transmitting on a connection is incremented whenever the user sends a packet and is decremented periodically. If the counter exceeds a threshold upon being incremented, the network discards the packet. The user specifies the rate at which the counter is decremented (this determines the average bandwidth) and the value of the threshold (a measure of burstiness)”.

There is, obviously, a difference between traffic shaping and traffic policing, and some do seem to apply the token bucket to policing and the leaky bucket to shaping. But I don't know if that is what is meant in the article.

Graham.Fountain | Talk 11:15, 12 September 2014 (UTC)

There've been no arguments that a difference is correctly identified, and the page is actively being edited, so if there were they should have come out. So now I've taken out the statement about the difference between the token and leaky buckets.Graham.Fountain | Talk 10:05, 22 September 2014 (UTC)

Merge from Queuing discipline

user:Dsimic reverted user:Graham.Fountain's merge of Queuing discipline into Network scheduler claiming the proper procedure was not followed. Proper merge procedure allows for WP:BOLD action. Is the objection to these action purely procedural or is there opposition to the merge? My understanding is that Queuing discipline is simply the Linux lingo for different Network scheduler behaviors so a merge is reasonable. ~KvnG 13:50, 16 September 2014 (UTC)

Just a point of order, but 'twas User:Beland that merged Queuing discipline, not I. Not that I have aught again the merge, BTW, just to the assertion that there's a difference between the leaky bucket and the token bucket algorithm. So I shall put the dubious tag back. Graham.Fountain | Talk 16:07, 16 September 2014 (UTC)

Hearing no objection and two supporters, I'll re-do the merge. -- Beland (talk) 22:54, 16 September 2014 (UTC)

Hello! Beland, please don't get me wrong, but as a Wikipedia administrator you should be the one to follow, embrace and promote all of the Wikipedia's rules... I'd say that discussion being the key is one of them. However, not waiting for opinions from other editors isn't a good example; following the rules, I'll revert the merger until there'a a chance to discuss it. According to the "be bold" principle, if someone objects and reverts the changes, a discussion should follow with enough time for everyone to participate. That should also be reasonable as a general approach, if you agree.

Regarding the actual merger, to me Queuing discipline should remain a separate article, and I'll explain why. It is true that "queuing discipline" is pretty much a Linux-specific term, but it is also quite notable on its own. Additionally, mentioning "queuing discipline" immediately points to a specific Linux application area, what puts it into WP:NRV through "significant independent coverage and recognition", while "network scheduler" is pretty much a general term that covers a broad area. As such, having Queuing discipline as a separate article (which has a potential for further expansion) should be beneficial, and should comply with WP:SPINOFF.

Thoughts? — Dsimic (talk | contribs) 03:01, 17 September 2014 (UTC)

WP:SPINOFF begins with "Sometimes, when an article gets long..." That's certainly not the case here. If the material were all in one article from the start, I think you'd have a hard time finding a consensus to WP:SPLIT it. ~KvnG 03:27, 17 September 2014 (UTC)

Please, let's take into account that Queuing discipline as an article could be vastly expanded with Linux-specific content; for example, the availability history of various queuing disciplines could be added, together with Linux-specific relations between different queuing disciplines, performance benchmark summaries etc. Also, content from the Network scheduler § Linux kernel section could be moved there. I'd say all that makes it more fit for having an article on its own. — Dsimic (talk | contribs) 03:40, 17 September 2014 (UTC)

Are you going to undertake that work to expand "Queuing discipline"? Otherwise it's just hand-waving, usually the "could be expanded" argument ends up with nobody doing that work.

And I think going into too much depth about Linux-specific things would actually be detrimental to Wikipedia as an encyclopedia. The subject of scheduling traffic applies to any router, switch or general purpose OS, why would we want to fragment this knowledge? Many of the Linux qdiscs are based on academic papers that are implemented on multiple operating systems.

And that seems to be a general pattern on Wikipedia: even if multiple vendors use different terminology to describe a common concept, there's a just single Wikipedia article with redirects in place. For example, both "swap file" (Linux/Unix terminology) and "page file" (Windows) redirect to the paging article. Folder (computing) [Windows] redirects to directory (computing) [Unix]. There are plenty of examples. -- intgr [talk] 11:56, 17 September 2014 (UTC)

As with this Network Scheduler article, I'm not so sure that Queueing discipline is a purely Linux issue. Specifically, I see both the use of GCRA in ATM NICs for the control of the segmentation in the SAR layer and bandwidth allocation gap control in AFDX NICs (as a simplified copy of ATM SAR functionality) as relating to both. I’d probably have to think about it more, but I suspect that if I did, I’d see transmission scheduling of time triggered transfers in TTEthernet as being the same too. I know the AFDX and TTE stuff relate to the extreme QoS requirements for (firm) real-time data transport, but that’s just my niche (some may say rut, as in "stuck in a...").

However, the reason I see those things as relating to both may be mostly because, other than the terminology, and just possibly the context, I don't see the actual distinction between Network Scheduling and Queueing discipline, and I certainly don't see that distinction being appropriately addressed either here or in the article on Queueing discipline (or in these discussions). Hence, as well as the procedural arguments [yawn], etc., can someone explain what they see this distinction as? Because, if it’s no more than a parochial one, i.e. of its context, I can’t see any argument against merging.

As to the specific point “that Queuing discipline as an article could be vastly expanded with Linux-specific content” : If it were larger and contained this information, then there would be reason not to merge. But it ain’t ; it’s a stub. If you could point to a draught article, as evidence that this stub is not "unlikely to be expanded within a reasonable amount of time" (WP:merging#Reasons for merger #3), that would help. But in the interim, I don’t see why Queuing discipline, as it is, can’t be a merged and replaced with a redirect to the relevant section of Network Scheduler until someone actually sets down and writes this Linux specific content? When they do, the redirect can be overwritten, presupposing that WP:Notability is met (I’d like to include something about being WP:READABLE as well ; but we are all, I assume, engineers here after all), and there can be a link to it as a main article at the start of this section.

So I'm not saying that I think this subject is unsuitable for a stand-alone or anathema in any way. Just that, given the content as it is, and without any evidence that it is likely to be expanded significantly, anytime soon, I believe both that the reader is better served by merging and that sufficient of the requirements for merger are met.

Graham.Fountain | Talk 14:07, 17 September 2014 (UTC)

@Intgr: If we end up concluding that Queuing discipline deserves to remain a separate article, then yes, I am willing to expand it further. Of course, doing that would take some time, but I'd get it done in the end. You're right that going way too deep into Linux-specific stuff wouldn't be inline with the nature of Wikipedia (and it would collide with WP:NOTHOWTO in the first place), but then again, Linux is so widely used that covering it in a bit more detail shouldn't hurt – especially when it's about such a not-so-well documented area as Linux traffic control is. But then again, we're here to discuss the whole thing, and I'm more than willing to contribute new content. — Dsimic (talk | contribs) 20:59, 17 September 2014 (UTC)

@Graham.Fountain: After reading your comments, I've thought once again about the whole thing; what follows is also somehow affecting my reply immediately above, but I was a bit lazy to rewrite it. :) So, with all in mind, maybe it would be better not to have Queuing discipline as a separate article, while instead we'd have a separate article dedicated to Linux traffic control. I'm sure people here are already familiar with it, but Linux Advanced Routing & Traffic Control (LARTC) HOWTO demonstrates very well what could be included in such an article. Sure thing, we don't want to create another howto; however, some form of a summary, at least in my opinion, would increase the value of Wikipedia. Though, I'm not sure what would be the name of that new article, or whether there's already a suitable article that could be expanded further. Regarding what could be included into the Queuing discipline article, if we decide to keep it, LARTC's chapter 9 and chapter 14 demonstrate that as well. Thoughts? — Dsimic (talk | contribs) 20:59, 17 September 2014 (UTC)

Sorry for jumping the gun, Dsimic; I had assumed that if you had any objection on the merits, you would have mentioned when you undid the merger. I agree with the above arguments in favor of the merger; all of these algorithms and any performance metrics are of interest to users of all operating systems. The fact that one OS implements some of them is interesting to have mentioned, but having two lists of algorithms separately is more confusing than helpful for readers. One of the main yardsticks I use is how much the articles overlap. "Queueing discipline" as it stands is nearly 100% contained in "Network scheduler" and certainly if the latter is filled in properly. I agree this article is too short to need splitting along any lines, whether that's by OS or by subtopic. -- Beland (talk) 15:00, 17 September 2014 (UTC)

@Beland: No worries, nothing bad happened, and we're here to discuss it further. As I've described it above, in my last two replies, there's quite a lot of Linux-specific stuff that could be used to expand the Queuing discipline article further, or to create/expand another article. Please, let's just discuss all those possibilities, and if we conclude that such stuff wouldn't be suitable for Wikipedia, I'll have no objections against the merger. — Dsimic (talk | contribs) 21:06, 17 September 2014 (UTC)

@Dsimic: I agree with the comments above; if the material which might potentially be added in the future is not in the encyclopedia now, it's not worth considering with regard to this merge. The best thing to do is to merge now, and then split later once "network scheduler" gets too big, if it ever does. The way in which it is split up might also be different depending on how it grows, and I think in the meantime the content will grow in a less scattered and more informative way. There is a place for additional content to go after a merge - any OS-specific stuff can go in the "Implementations" section, which is currently not big enough for a subarticle. As a reader I find it helpful to have general context before delving into any operating-system-specific details, and having a single article makes that easy. -- Beland (talk) 15:17, 18 September 2014 (UTC)

With regard to the lartc.org links proposed for additional content, Wikipedia is not an instruction manual, and most of the material there is far too detailed for a general-interest encyclopedia. What I would be looking for in an encyclopedia is a general description of what network schedulers do, detail on the logical level of the various algorithms and strategies available (we have articles for many of those, which is good). It's interesting to note that specific implementations exist, and to have external links that point to them - this helps people who are trying to solve a practical problem and not merely get a theoretical background. But the "what options does this thing I'm running support" is not encyclopedic. Some coverage of the pros and cons of various strategies would be interesting, without giving any specific advice. -- Beland (talk) 23:53, 18 September 2014 (UTC)

Ok, then merge it, I see no point in "fighting" any further. At some point in time I'll see to add more content. — Dsimic (talk | contribs) 05:29, 19 September 2014 (UTC)

Just as a reminder, please follow all steps from WP:PROMERGE – you've missed some of them with the initial merger. — Dsimic (talk | contribs) 06:10, 19 September 2014 (UTC)

Merged. -- Beland (talk) 20:46, 29 September 2014 (UTC)

Linux kernel

So, which algorithm does the Linux kernel implement by default? After reading the "Linux kernel" section, I'm still unclear on that. -- Beland (talk) 15:02, 17 September 2014 (UTC)

Currently, the Network scheduler § Linux kernel section is‍—‌I'm sorry to say that‍—‌not so good, and it introduces additional confusion by describing too early those interface-level buffers that are not directly related to qdiscs. That's one of the reasons why I'm proposing that Linux-specific stuff should be explained better. Oh, and the answer to your question is that all network interfaces in Linux have pfifo_fast as their default qdisc, which is basically a three-band FIFO scheduler that uses TOS values to select bands; please see LARTC's section 9.2.1 for more details. — Dsimic (talk | contribs) 21:17, 17 September 2014 (UTC)

Mechanics

I removed this explanation from the article because it is unreferenced and sounds dubious:

The network scheduler logic decides similar to a statistical multiplexer which network packet to forward next from the buffer. The buffer works as a queuing system, where the network packets are stored temporarily until they are transmitted. The buffer space is divided into many queues, each of which is used to hold the packets of one flow, defined for instance by source and destination IP addresses.

The number and purpose of queues depends on the algorithm being implemented. For example, fair queuing has multiple packet flows, but simple FIFO doesn't.

It also seems that the difference between actual queues (removing a packet from the network interface circular receive buffer and add it to a queue data structure on the heap) and virtual queues (some heap structure tracks the ticket numbers or whatever attributes of packets in the circular receive buffer without moving it until its turn to be transmitted) is an implementation detail we can't really generalize about. -- Beland (talk) 23:40, 18 September 2014 (UTC)

Re-organisation of the set of pages describing network scheduling algorithms

After some discussions on the Talk:Fair queuing#Family of Algorithms page, the need arises to re-organise a set of related pages. First, there is a set of related protocols: fair queuing, weighted fair queuing, deficit round robin, Generalized_processor_sharing, and perhaps others. Coarsely, they all implement the same idea, with different trade-offs. Second, there is a set of global principles: traffic shaping, quality of service, Fairness_measure.

My suggestion, following the one of John Nagle would be to use the current Network scheduler as the top page, mentioning the problem of different flows sharing the same queue: how to protect some flows from others? how to handle different requirements (latency vs troughput)? Then, two approaches can be distinguished:

1. drop based: a single queue is used, and packets are dropped before overflow (and something must be said about TCP)
2. separated queues: a queue is dedicated to each flows/class (but does not say how many memory must be given to each queue), and some algorithm must decide which queue has access to output link at a given time, with several variants
   1. priority based: static priority, AVB
   2. fair queuing: use a round-robin-like scheme to share the bandwidth

Any comment? MarcBoyerONERA (talk) 04:59, 22 April 2015 (UTC)

Wikipedia has a large number of article related to this topic, but they're not well organized. There are, at least Traffic shaping, FIFO (computing_and electronics)#Communications and networking, Fair queuing, Weighted Fair Queuing, Random Early Drop, Leaky bucket, Token Bucket, TCP congestion-avoidance algorithm , DOCSIS and Net Neutrality. I'd start by explaining the problem, which is that FIFO, the simplest network scheduling algorithm, behaves badly when faced with several flows with different needs at the same time. A clear explanation of why FIFO is a problem here should be provided. Then go on to discuss the two basic approaches to improving on FIFO - reordering packets, or dropping some of them. Then, since this is a top article, just put all the different approaches under those two headings. (Maybe a third heading for combined approaches.) Mention that network scheduling and transport-level congestion control interact strongly, and provide a wikilink to at least TCP congestion avoidance. Finish up with a mention of net neutrality, which is related to traffic shaping for business/political purposes. That will give readers a way to navigate the subject. John Nagle (talk) 05:11, 22 April 2015 (UTC)

I will try to do some work on this article when I get a chance. In the meantime, I've done some maintenance work on Category:Network scheduling algorithms. Hopefully this gives us better visibility of the set of articles we're dealing with. ~Kvng (talk) 15:46, 22 April 2015 (UTC)

Thanks. Also note bufferbloat, which is what happens when you use FIFO with lots of memory. John Nagle (talk) 17:45, 22 April 2015 (UTC)

Already noted. JimGettys, Dtaht and others have been doing good work drawing attention to this. ~Kvng (talk) 18:07, 22 April 2015 (UTC)

Dave Taht I note that I have been reluctant to directly edit wikipedia, despite being an "expert". But: I have longed to see a re-org of these articles, reworking some phrasing, and citing quite a few things, and adding an entry for fq_codel for sure (based on some work we have not completed here, perhaps: http://snapon.lab.bufferbloat.net/~d/lwn/SFQ2012/FQ-Codel.html (the title and focus on "SFQ on steroids" is wrong, it is more like "DRR on drugs" ) , and maybe the work on cake in progress. ( http://www.bufferbloat.net/projects/codel/wiki/Cake ) I like to think that the debates on the ietf aqm mailing list have come to a bit of consensus finally, and those standards documents (for pie, codel, fq_codel, and the need for aqm) are well along, if you see here: https://tools.ietf.org/wg/aqm/ ~Dave Taht

And there are a metric ton of other papers, documents, and graphs that I would like to see make wikipedia somehow in some form. I have a few rants on the nanog mailing list, we have a few great talks (like steven hemmingers) here: http://www.bufferbloat.net/projects/cerowrt/wiki/Bloat-videos and I am always pointing at the spectacular results we get out of fq_codel-ing all the present edge technologies:

• Cable: [1] (there are also free.fr DSL results off the above url) [2]
• Fiber: [3]
• DSL: [4]
• UBNT: [5]

Then there are the netperf-wrapper RRUL string of tests... ~Dave Taht

CoDel now exists. These are potentially good sources of direct background information but we prefer our citations to be WP:SECONDARY sources. ~Kvng (talk) 16:09, 31 March 2020 (UTC)

---

Being totally unfamiliar with wikipedia and feeling a need to strengthen some terms, I have made a resoluton to learn how. However, I am a primary source, one

of the primary experts, and having a more expert editor of wikipedia along for the ride (topics include fq_codel, flow queuing, "smart queue managment", apple's new "RPM" tests, and a dozen others, would help a lot. ~Dave Taht Dtaht (talk) 01:28, 4 October 2021 (UTC)