Decides Server order
- Why do we need one?
- What can scheduling disciplines do?
- Requirements of a scheduling discipline
- Ease of implementation
Fairness is global, scheduling(congestion avoidance) is local.
- Notion of Fairness
- Fundamental choices
Work-conserving and non-work-conserving
Degree of aggregation
- Scheduling disciplines
FIFO & other disciplines(SPT, SRPT), the performance among them
(SRPT process the remaining time, which means if I’m processing a package which still needs 5 min, then comes a package which only need 1 min, then I go to process the new package)
- The Conservation Law
scheduling is independent of the packet service time\(\sum ρ_iq_i=constant\) \(ρ_i\) mean utilization of connection i and \(q_i\) mean waiting time of connection i
The average delay with FIFO is a tight lower bound for
work conserving and service time independent scheduling
Jain’s index use equal share as the
- Max-Min Fairness
- General Process Sharing (GPS)
Conceptually, GPS serves packets as if they are
in separate logical queues, visiting each nonempty
queues in turn.
How to emulate GPS as fair as possible, also efficient
- (Weighted) round robin
Different weights, fixed packet size
Different weights, variable size packets：normalize weights by mean packet size
- With variable size packets and different weights,
need to know mean packet size in advance
- Can be unfair for long periods of time