ELEC3506

Topics

Quality of ServiceLecture 10 PDF15 min

Scheduling

How a router chooses which queued packet to send next on a link, covering FIFO with its discard policies, priority scheduling, round robin and weighted fair queuing with the lecture's weight examples.

By the end of this page you should be able to

  • State what a scheduling mechanism does and list the four the lecture covers
  • Describe FIFO and its three discard policies
  • Work out the departure order for priority and round robin using the lecture's examples
  • Apply the WFQ rate formula and explain the lecture's two weight examples

The idea

A router can only put one packet on a link at a time, and several may be waiting. Which goes next? That choice is scheduling, and it decides whether a phone call gets through ahead of a file transfer or both crawl along together. The four mechanisms in this topic are four different answers, from “whoever arrived first” to “each class gets a guaranteed share”.

How it works

Scheduling mechanisms

Scheduling means choosing the next packet to send on the link. The lecture lists four mechanisms: FIFO, priority scheduling, round robin scheduling and WFQ. Scheduling sits beside flow control, congestion control and call admission control (CAC) under the lecture’s heading of traffic management.

How it works

FIFO

First in first out sends packets in the order of arrival to the queue. When a packet arrives to a full queue the router has to decide who to discard. The lecture gives three policies:

  • Tail drop, drop the arriving packet.
  • Priority, drop or remove on a priority basis.
  • Random, drop or remove at random.

How it works

Priority scheduling

Priority scheduling transmits the highest-priority queued packet. There are multiple classes with different priorities. A packet’s class may depend on its marking or on header information such as IP source or destination and port numbers.

The lecture’s example has high-priority packets 1, 3 and 4 and low-priority packets 2 and 5. The figure shows the departure order 1 3 2 4 5. The arrival timeline behind that order is a diagram that does not survive text extraction, so the reason packet 2 departs before packet 4 is not given here.

How it works

Round robin

Packets are sorted into classes but there is no priority class. The scheduler cycles through the class queues, serving one packet from each class if one is available.

The lecture’s example has class 1 holding packets 1, 2 and 4, and class 2 holding packets 3 and 5. The service order is 1 3 2 4 5.

How it works

Weighted fair queuing (WFQ)

WFQ is a generalised round robin. Each class i has a weight w_i and gets a weighted amount of service in each cycle. For a link rate R, class i receives the rate in the formula.

WFQ service rate
R
Link rate in bps
w_i
Weight of class i
\sum_j w_j
Sum of the weights of all classes

The lecture gives two weight examples:

  • w1 = w2 = w3 = 1/3 gives the service order 1 2 3 1 2 3 ..., which is plain round robin.
  • w1 = 2/3, w2 = 1/6, w3 = 1/6 gives 1 1 2 3 1 1 repeating, or equally 1 1 1 1 2 3 repeating.

Worked example

Rates under the lecture's second WFQ example

  1. Weights: w1 = 2/3, w2 = 1/6, w3 = 1/6.

  2. Sum: 2/3 + 1/6 + 1/6 = 4/6 + 1/6 + 1/6 = 6/6 = 1.

  3. Class 1: R x (2/3) / 1 = 2R/3.

  4. Classes 2 and 3: R x (1/6) / 1 = R/6 each.

  5. Check against the pattern: in 1 1 2 3 1 1, class 1 is served 4 times out of 6, which is 4/6 = 2/3. Classes 2 and 3 are served once each, 1/6.

  6. Numbers for illustration (not from the lecture): on a 6 Mbps link the rates are 4 Mbps, 1 Mbps and 1 Mbps.

AnswerClass 1 gets 2R/3, classes 2 and 3 get R/6 each.

FIFOPriorityRound robinWFQ
RuleOrder of arrivalHighest-priority packet firstOne packet from each class in turnWeighted share of each cycle
ClassesNoneSeveral, with prioritiesSeveral, no prioritySeveral, each with a weight
Lecture exampleDiscard policiesOrder 1 3 2 4 5Order 1 3 2 4 5Weights 1/3 each, or 2/3, 1/6, 1/6
Equal weights make WFQ identical to round robin.

Where marks get lost

Do not force strict priority into the example

The lecture’s priority figure shows departures 1 3 2 4 5. Sorting all high-priority packets ahead of all low-priority ones would give 1 3 4 2 5. The departures depend on when each packet arrives, and that timeline does not survive text extraction, so check the slide if you need to explain why packet 2 goes before 4.

In the exam

  • List the four mechanisms and give each rule in one line.
  • FIFO needs a discard policy: tail drop, priority, random.
  • WFQ is generalised round robin. Know the rate formula and that equal weights reduce to round robin.
  • Work the two weight examples: 1/3 each, and 2/3, 1/6, 1/6.

Check yourself

  • Scheduling picks the next packet on the link: FIFO, priority, round robin, WFQ.
  • FIFO needs a discard policy when the queue fills.
  • Priority sends the highest class first, round robin takes turns, WFQ takes weighted turns.
  • WFQ rate for class i is R times w_i over the sum of weights.

Check yourself

  1. With FIFO and a full queue, which discard policy drops the packet that has just arrived?
  2. In the lecture's priority example, packets 1, 3 and 4 are high priority and 2 and 5 are low. What is the departure order?
  3. Three classes have weights 1/3 each on a link of rate R. What does each class get?
  4. With w1 = 2/3, w2 = 1/6, w3 = 1/6, what fraction of the link rate does class 1 receive?