Packet Scheduling · Computer Networking Interactive

Several packets are waiting on one link, and something has to choose which goes next — a choice that decides whose traffic is fast, and whose is not.

Words you will meet

FCFS (First-Come-First-Served) , also called FIFO (First-In-First-Out) — packets leave in the order they arrived.
Priority queueing — classes, and the highest non-empty one always wins.
Non-preemptive — a packet already being transmitted is never interrupted.
Round robin — classes served in turn, one each.
Work-conserving — the link never sits idle while any packet is queued.
Weighted fair queueing ( WFQ (Weighted Fair Queueing) ) — round robin where each class gets a guaranteed fraction of the link.
Net neutrality — the policy question of what an ISP (Internet Service Provider) is allowed to do with all of the above.

Why this matters

Section 4.2.3 left one job unfinished. Packets are queued at an output port, the link becomes free, and something must pick one. This section is that pick.

It is the shortest mechanism in the chapter and the one with the largest consequences outside it. Every scheduling discipline here is a way of deciding whose traffic goes first, and once a router can do that, the question stops being technical. The book puts a sidebar on net neutrality in the middle of this section for exactly that reason, and it belongs there: the mechanisms are the argument’s premise.

Four disciplines, one queue

The book introduces them by analogy to queueing for service, which is fair enough — everyone has stood in one.

First-come-first-served. The British queue at a bus stop. “Oh, are you queueing?”
Priority. Some class of customer is served ahead of others.
Round robin. Customers are divided into classes as with priority, but each class is served in turn.

Here are the book’s own worked examples — Figures 4.12, 4.14 and 4.15 — with identical arrivals, so that only the scheduler changes.

Figures 4.12, 4.14 and 4.15 — the same five packets, four schedulers

FIFO / FCFS. First-in-first-out, also called first-come-first-served. Packets leave in exactly the order they arrived. No classes, no choices — the queue is the decision.

Departure order: 1, 2, 3, 4, 5. The link is idle from t = 12 to t = 13 — not because the scheduler chose badly, but because nothing had arrived to send.

Identical arrivals every time; only the choosing changes. Switch between the four and watch the departure order. Two of them agree — for completely different reasons.

Read the three the book draws

Five packets. Each takes three time units to transmit. Packet 1 arrives to an idle link; 2 and 3 arrive while 1 is being sent; 4 arrives later; 5 arrives much later.

FIFO (Figure 4.12) — order 1, 2, 3, 4, 5. Packets leave in the order they arrived, and after packet 4 departs the link goes idle until packet 5 turns up. That idle stretch is not a scheduling failure. There was simply nothing to send.

Priority (Figure 4.14) — packets 1, 3, 4 are high priority; 2 and 5 are low. Order 1, 3, 2, 4, 5. Packet 1 finds the link idle and goes. While it transmits, 2 (low) and 3 (high) queue. At the end of packet 1 the scheduler picks 3 over 2 — even though 2 arrived first, because 2 is low priority. Then 2 goes. Packet 4 (high) arrives during packet 2’s transmission and must wait, because the discipline is non-preemptive.

Round robin (Figure 4.15) — packets 1, 2, 4 are class 1; 3 and 5 are class 2. Order 1, 3, 2, 4, 5. After packet 1, the scheduler looks for a class 2 packet and finds 3. After 3, it looks for class 1 and finds 2. After 2, only packet 4 remains, so it goes immediately.

Priority and round robin give the same answer here. Do not read anything into it.

Both produce 1, 3, 2, 4, 5, and that is a coincidence of the book’s chosen class assignments. The two figures use different groupings that happen to land on the same order.

Under priority, packet 3 beats packet 2 because 3 is more important. Under round robin, packet 3 beats packet 2 because it is class 2’s turn. Those are entirely different reasons, and they come apart the moment traffic keeps arriving: priority queueing will starve the low class indefinitely, and round robin never will.

Switch between the two in the widget and read the class labels under the arrivals. They are not the same packets.

Non-preemptive, and why

Packet 4 is high priority. It arrives while packet 2 — a low priority packet — is being transmitted. And it waits.

Under a non-preemptive discipline, the transmission of a packet is not interrupted once it has begun. Packet 4 queues, and starts only when packet 2 finishes.

In plain words

This looks like a flaw and is not. A partly transmitted packet is not a packet — it is a fragment that the receiver’s link layer will discard, so abandoning it wastes everything already sent.

The cost is bounded and small: a high-priority packet waits at most one packet transmission time. The book quantified that budget in section 4.2.1 — a 1,500-byte frame on a 100 Gbps link takes about 120 nanoseconds. Preemption would buy back a fraction of that and throw away a whole packet to get it.

Work-conserving

A work-conserving discipline never lets the link sit idle while packets of any class are queued.

For round robin that means something specific. A scheduler that looks for a packet of a given class and finds none immediately checks the next class, rather than waiting its turn out. All four disciplines here are work-conserving.

Look again at the idle stretch in the FIFO run. The link idles because the queue is genuinely empty, not because a scheduler is holding a slot open. That is the distinction the word draws.

Weighted fair queueing

Round robin is fair in the blunt sense: every class gets one turn each. But it gives you no way to say that one class deserves more than another.

Weighted fair queueing generalises it. Each class i carries a weight wᵢ, and the scheduler still serves classes in a circular manner. But during any interval in which class i has packets to send, it is guaranteed a fraction of service equal to

wᵢ / Σ wⱼ

where the sum runs over the classes that also have packets queued. So on a link of rate R, class i always achieves a throughput of at least

$\text{throughput}_i \geq R \cdot \frac{w_i}{\sum_j w_j}$

What weighted fair queueing guarantees

What each symbol means

w_i — the weight given to class i (—)
Σ w_j — sum over the classes that currently have packets queued (—)
R — transmission rate of the link (bits/s)

Read aloud: A class always gets at least its share of the link, and its share is its weight divided by the weights of everyone competing right now.

this class’s weight wᵢweights of the other busy classeslink rate RMbps

guaranteed throughput for this class50.0 Mbps

share = w_i / sum(w_j) = 3 / (3 + 3) = 0.500
guaranteed throughput = R x share = 100 Mbps x 0.500 = 50.0 Mbps
and this is the WORST case: if the other busy classes go quiet, the denominator shrinks and this class gets more
the guarantee is a floor, never a cap

Change any number above and the arithmetic re-runs, carrying the units through.

Three classes weighted 3 : 2 : 1 on a 100 Mbps link. Set the "classes currently busy" control to 3 for the worst case, then to 1 to see what a class gets when it has the link to itself.

Why the denominator is the interesting part

The sum is over classes that currently have something to send, not over all classes that exist.

That is what makes the guarantee useful rather than pessimistic. A class weighted 3 among three classes weighted 3 : 2 : 1 gets half the link when all three are busy. When the other two fall silent, its denominator shrinks to 3 and it gets the whole link. WFQ is work-conserving, and will not hold capacity back for a class that is not asking.

The worst case is the guarantee: even if every class is busy, the sum in the denominator is over all of them, and class i still gets its share. That hard floor is why WFQ, of the four, is the one that has been widely implemented in routers [Demers 1990; Parekh 1993].

The book’s own caveat: this description is idealised

The book says so explicitly, and it matters.

The formula above treats service as something that can be divided infinitely finely. It cannot. Packets are discrete, and a packet’s transmission will not be interrupted to begin another — the non-preemption above.

So a real WFQ scheduler cannot hit its weighted shares exactly at every instant. It approximates them, and the error is on the order of one packet transmission time per class. [Demers 1990; Parekh 1993] deal with this packetisation issue, and it is the difference between the clean formula and a working router.

The four disciplines

	FIFO / FCFS	Priority	Round robin	WFQ
Classifies packets?
How the next packet is chosen
Can a class be starved?
What a class is promised
Work-conserving?

Cells marked ⓘ have a reason behind them — click to read it.

Two questions separate them: does the scheduler classify packets, and can a class be starved? Click any cell for the reasoning.

Net neutrality

The book places a sidebar here, and its logic is worth following: everything above is a mechanism for giving different classes of traffic different levels of service. What counts as a “class” is up to an ISP (Internet Service Provider) , and could be based on any set of fields in the IP (Internet Protocol) datagram header.

Three examples the book gives, escalating:

By service. The port field could mark network management traffic ( SNMP (Simple Network Management Protocol) , port 161) as higher priority than e-mail ( IMAP (Internet Mail Access Protocol) , ports 143 or 993). Uncontroversial.
By who is paying. The source IP address could give priority to datagrams from companies that have paid the ISP for the privilege, over companies that have not.
By blocking. An ISP could block traffic from a given company, or a given country, outright.

The mechanisms allow all three equally. The real question is what policies and laws determine what an ISP can actually do — and those vary by country.

The three bright-line rules

The term has no precise definition, but the US Federal Communications Commission’s March 2015 Order on Protecting and Promoting an Open Internet gave three rules now often associated with it:

No blocking. A broadband provider shall not block lawful content, applications, services, or non-harmful devices — subject to reasonable network management.
No throttling. It shall not impair or degrade lawful Internet traffic on the basis of content, application, service, or use of a non-harmful device — subject to reasonable network management.
No paid prioritization. It shall not manage its network to directly or indirectly favour some traffic over other traffic in exchange for payment, including by traffic shaping, prioritization or resource reservation.

Note the phrase subject to reasonable network management in the first two. The rules do not ban the mechanisms in this section. They ban particular uses of them, and leave “reasonable” to be argued.

It had already happened, twice

The book notes that before the Order, behaviour violating the first two rules had been observed [Faulhaber 2012].

2005 — blocking. An ISP (Internet Service Provider) in North Carolina agreed to stop blocking its customers from using Vonage, a voice-over-IP service that competed with the ISP’s own telephone business.

2007 — throttling. Comcast was judged to be interfering with BitTorrent peer-to-peer traffic by creating and sending TCP (Transmission Control Protocol) RST (reset) packets to BitTorrent senders and receivers, causing them to close their connections [FCC 2008].

The second one is worth dwelling on, because you can now read it precisely. A RST is the reset flag from section 3.5.2’s segment header. Forging one, from a middlebox, with the source address of the other end, makes both sides believe their peer has torn the connection down. Section 4.5 returns to what middleboxes can do; this is what they can do when nobody is watching.

Where the policy stands

The 2015 Order was superseded by the 2017 FCC Restoring Internet Freedom Order, which rolled back these prohibitions and focused instead on ISP transparency.

The book’s own assessment, given so much interest and so many changes:

“it’s probably safe to say we aren’t close to having seen the final chapter written on net neutrality in the United States, or elsewhere.”

Both sides have been argued strenuously, mostly over how far net neutrality benefits customers while promoting innovation [Peha 2006, Faulhaber 2012, Economides 2017, Madhyastha 2017].

Check yourself

0 of 7 answered

1.predictPriority and round robin both give the departure order 1, 3, 2, 4, 5 in the book's examples. What should you conclude?
2.A high-priority packet arrives while a low-priority packet is being transmitted. What happens, and why?
3.What is priority queueing's biggest weakness?
4.predictThree WFQ classes are weighted 3 : 2 : 1 on a 100 Mbps link. The two other classes fall silent. What does the class weighted 3 get?
5.The book calls its description of WFQ "idealised". What is idealised about it?
6.In 2007 Comcast was judged to be interfering with BitTorrent traffic. How?
7.predictDo the FCC's three bright-line rules forbid the scheduling mechanisms in this section?

What to remember

Scheduling is the choice of which queued packet goes next, and it is the last thing an output port does before transmitting.
FIFO has no classes and no choices. Priority always serves the highest non-empty class, and can starve the lower ones indefinitely. Round robin serves classes in turn so nothing starves. WFQ is round robin with weights, guaranteeing class i at least R · wᵢ / Σwⱼ, and it is the one widely implemented.
These mechanisms are the premise of the net-neutrality debate. A router that can prioritise by port can prioritise by who paid, and the difference is policy, not engineering.