Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Scheduling Metrics Complexity of enqueue+dequeue processes Fairness:If two flows are backlogged,difference between their weighted throughputs is bounded Complexity of adding and releasing connections Isolation:Delay bounds should not depend upon behavior of other flows,number of other flows,reservations of other flows 2616009:Network Traffic Engineering 6:Packet Scheduling Page.6
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.6 Scheduling Metrics • Complexity of enqueue+dequeue processes • Fairness: If two flows are backlogged, difference between their weighted throughputs is bounded • Complexity of adding and releasing connections • Isolation: Delay bounds should not depend upon behavior of other flows, number of other flows, reservations of other flows
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Requirements of Scheduling Discipline Requirements of a scheduling Disciplines Ease of implementation(for both guaranteed-service and best-effort connections) 。 Farness and protection for best-effort connections) Performance bounds for guaranteed-service connections) Bandwidth,Delay,Delay jitter,Packet loss rate Ease and efficiency of admission control for guaranteed-service connections) 。 Scalability 2616009:Network Traffic Engineering 6:Packet Scheduling Page.7
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.7 Requirements of Scheduling Discipline Requirements of a scheduling Disciplines • Ease of implementation (for both guaranteed-service and best-effort connections) • Farness and protection ( for best-effort connections) • Performance bounds ( for guaranteed-service connections) - Bandwidth, Delay, Delay jitter, Packet loss rate • Ease and efficiency of admission control ( for guaranteed-service connections) • Scalability
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Requirements of Scheduling Discipline(contd) An Example Service rate observed by a particular queue Time Service rate which might be observed by a particular queue 2616009:Network Traffic Engineering 6:Packet Scheduling Page.8
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.8 Requirements of Scheduling Discipline(contd) An Example Time Service Observed Service rate which might be observed by a particular queue : Service rate observed by a particular queue
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Fundamental Choices to Create a Scheduling Discipline Four principal degrees of freedom in designing a scheduling discipline Number of priority levels Whether each level is work-conserving or non-work-conserving The degree of aggregation of connections within a level Service order within a level 2616009:Network Traffic Engineering 6:Packet Scheduling Page.9
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.9 Fundamental Choices to Create a Scheduling Discipline Four principal degrees of freedom in designing a scheduling discipline • Number of priority levels • Whether each level is work-conserving or non-work-conserving • The degree of aggregation of connections within a level • Service order within a level
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Priority Each connection is associated with a priority level. A higher-numbered priority level corresponds to a connection with higher priority Packet is served from a given priority level only if no packets exist at higher levels(multilevel priority with exhaustive service) Highest level gets lowest delay 。 Watch out for starvation! Usually map priority levels to delay classes e.g.low bandwidth urgent messages at highest priority,followed by real-time then non-real-time 2616009:Network Traffic Engineering 6:Packet Scheduling Page.10
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.10 Priority • Each connection is associated with a priority level. • A higher-numbered priority level corresponds to a connection with higher priority • Packet is served from a given priority level only if no packets exist at higher levels (multilevel priority with exhaustive service) • Highest level gets lowest delay • Watch out for starvation! • Usually map priority levels to delay classes - e.g. low bandwidth urgent messages at highest priority, followed by real-time then non-real-time