Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Unit 6 Packet Scheduling 2616009:Network Traffic Engineering 6:Packet Scheduling Page.1
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.1 Unit 6 Packet Scheduling
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Roadmap Why Scheduling? Problem Definition 。 Metrics and Requirements of Scheduling Discipline 。 Mechanisms to Create a Scheduling Discipline Scheduling Disciplines for Best Effort Connections 。 Scheduling Disciplines for Guaranteed-service Connections QoS Service curve model 2616009:Network Traffic Engineering 6:Packet Scheduling Page.2
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.2 Roadmap • Why Scheduling? • Problem Definition • Metrics and Requirements of Scheduling Discipline • Mechanisms to Create a Scheduling Discipline • Scheduling Disciplines for Best Effort Connections • Scheduling Disciplines for Guaranteed-service Connections • QoS Service curve model
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Why a Scheduling Discipline? Because applications need it - Sharing bandwidth Sharing bandwidth fairly Scheduling disciplines can allocate bandwidth,delay,loss>QoS 。 Best-effort (adaptive,non-real time),e.g.email,ftp Guaranteed service (non-adaptive,real time),e.g.interactive voice,video, stock quotes Meeting bandwidth guarantees(min and max) Meeting loss guarantees(multiple levels) Meeting delay guarantees(multiple levels) Reducing delay variation 2616009:Network Traffic Engineering 6:Packet Scheduling Page.3
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.3 Why a Scheduling Discipline? • Because applications need it - Sharing bandwidth - Sharing bandwidth fairly - Scheduling disciplines can allocate bandwidth, delay, loss QoS • Best-effort (adaptive, non-real time), e.g. email, ftp • Guaranteed service (non-adaptive, real time), e.g. interactive voice, video, stock quotes - Meeting bandwidth guarantees (min and max) - Meeting loss guarantees (multiple levels) - Meeting delay guarantees (multiple levels) - Reducing delay variation
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Why a Scheduling Discipline?(cont'd) QoS Guarantees require a number of mechanisms working together call admission control,traffic shaping,drop policies,buffer allocation,traffic scheduling,etc. These issues are related. - For example,zero-loss can be obtained by allocating PCR(but no multiplexing gain). Scheduling disciplines are the key to providing QoS guarantee for performance-critical applications 2616009:Network Traffic Engineering 6:Packet Scheduling Page.4
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.4 Why a Scheduling Discipline?(cont’d) • QoS Guarantees require a number of mechanisms working together - call admission control, traffic shaping, drop policies, buffer allocation, traffic scheduling, etc. - These issues are related. - For example, zero-loss can be obtained by allocating PCR (but no multiplexing gain). • Scheduling disciplines are the key to providing QoS guarantee for performance-critical applications
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Problem Definition Class 1 Class 2 Link Sever Class 3 Multiplexer.switch. router,... Scheduling Discipline handles the "contention"by deciding the order in which requests are serviced manages the service queue of requests awaiting service 2616009:Network Traffic Engineering 6:Packet Scheduling Page.5
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.5 Problem Definition Sever Link Class 1 Class 2 Class 3 Multiplexer, switch, router,... Scheduling Discipline handles the “contention” by • deciding the order in which requests are serviced • manages the service queue of requests awaiting service
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