Scheduling Flashcards
What is a work-conserving scheduler?
A work-conserving scheduler means that a router is never idle when there are packets to be serviced.
What is the work conservation law?
The work conservation law states that reducing the delay of one flow necessarily increases the delay of another.
What is the aim of non-work-conserving schedulers?
Non work-conserving schedulers can be idle even if there are packets waiting. This can reduce jitter, making downstream traffic more predictable. But such systems can be complex to build in practice, as for example each router must maintain a synchronized clock.
What is max-min fair share?
- Flows serviced in order of their requirement
- No flow gets more than their fair share
- Any flows whose demand cannot be satisfied get an equal share.
What is simple priority queuing?
This involves having k queues, with increasing priority levels. Higher priority queues are serviced first. This is simple to implement, but is not max-min fair as low priority queues are liable to starve.
What is generalised processor scheduling?
Generalised Processor Sharing is a work-conserving scheduler which provides max-min fair share, which serves an infinitesimal amount of data from each flow. It is useful as a reference point for other schedulers.
What is the difference between relative and absolute fairnesss bounds?
Relative fairness bound attempts to evaluate the fairness of the scheduler with respect to other flows it is servicing, whilst the absolute fairness bound evaluates the fairness of the scheduler compared to GPS for the same flow.
What is weighted round robin?
Weighted round robin is a simple attempt at emulating GPS. Queues are serviced round-robin, in proportion to a weight that is assigned to each flow/queue, i.e. flows with a greater weight have more service. In each round, each queue is visited once and the weight is normalised by the mean packet length. But unpredictable mean packet lengths may cause unfairness.
What is deficit round robin?
Deficit round robin does not need to know the mean packet size; a deficit counter is maintained for each queue, initially set to zero. The scheduler attempts to serve one quantum of data to each queue each round. Packet at head is served if size <- dc + quantum.
What is weighted fair queuing?
Weighted Fair Queuing attempts to emulate GPS directly by doing bit-by-bit round robin. The Finish Number is the time a packet would have completed service under a bit-by-bit GPS scheduler. Packets are tagged by their finish number and those with the smallest finish number are served first. Queue empty => finish number is number of bits in packet + round number. Queue non-empty => finish number is highest current finish number for queue + number of bits in packet. Can then drop packets in order of decreasing finish-number.
If a queue if full, describe three strategies for packet dropping.
- Drop-from tail is easy to implement, but packets in front may expire.
- Drop-from head is good for real time as older packets get dropped first.
- Random drop is fair if all sources are behaving and if not it penalises misbehaving sources more.
Why might dropping packets be problematic for UDP flows. How can this be addressed?
• Dropping packets works for TCP due to built-in mechanisms to manage flow control. But UDP has no such facility. Explicit congestion notification (ECN) may be required.
What is Random Early Detection (RED)?
Random Early Detection (RED) attempts to spot congestion before it happens and pre-emptively drops packets randomly. Should take exponential average of queue length. Again, assumes that source is adaptive.
