电子科技大学：《先进计算机网络技术》课程教学资源（课件讲稿）Unit 6 Packet Scheduling

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