Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Work-conserving vs.non-work conserving discipline A work-conserving scheduler is idle only when no packet awaiting service Produces lower average delay,higher delay var. Produces high total throughput Examples:GPS,WFQ,VirtualClock A non-work-conserving scheduler may be idle even if it has packets to serve May produce lower worst case end-to-end delay - May produce higher network throughput Reshaping at every hop Examples:Stop Go A non-work-conserving scheduler,by idling away time,makes the traffic arriving at downstream switches more predictable,thus reducing both the buffer size necessary at output queues,and the delay jitter experienced by a connection----Better for multiple hops 2616009:Network Traffic Engineering 6:Packet Scheduling Page.11
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.11 Work-conserving vs. non-work conserving discipline • A work-conserving scheduler is idle only when no packet awaiting service - Produces lower average delay, higher delay var. - Produces high total throughput - Examples: GPS, WFQ, VirtualClock • A non-work-conserving scheduler may be idle even if it has packets to serve - May produce lower worst case end-to-end delay - May produce higher network throughput - Reshaping at every hop - Examples: Stop & Go - A non-work-conserving scheduler, by idling away time, makes the traffic arriving at downstream switches more predictable, thus reducing both the buffer size necessary at output queues, and the delay jitter experienced by a connection----Better for multiple hops
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Work-conserving vs.non-work conserving discipline (cont'd) A A&B S1 S2 An example showing the need for non-work-conserving disciplines: Connection A and B share a common link,so the bustiness of Connection A traffic at S2's output port depends on B's behavior.If B is bursty,and S1 is work-conserving, even if A is smooth when it enters S1,it can be bursty when it enters S2.However,if S1 is non-work-conserving,the traffic entering S2 is smooth,even if B is bursty. 2616009:Network Traffic Engineering 6:Packet Scheduling Page.12
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.12 Work-conserving vs. non-work conserving discipline (cont’d) • An example showing the need for non-work-conserving disciplines: Connection A and B share a common link, so the bustiness of Connection A traffic at S2’s output port depends on B’s behavior. If B is bursty, and S1 is work-conserving, even if A is smooth when it enters S1, it can be bursty when it enters S2. However, if S1 is non-work-conserving, the traffic entering S2 is smooth, even if B is bursty. S1 S2 A B A&B A B
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Degree of Aggregation 。 Some individual connections can be aggregated in deciding their service order 。 Connections within a class share the same service quality The scheduler provides different qualities of service to different classes At one extreme,the scheduler uses a single state variable to describe all connections. At the other extreme,the scheduler maintains per-connection state,and can give different connections different bandwidth and delay bounds. Aggregation trade off smaller scheduler state for a coarser-grained differentiation in QoS More aggregation §less state cheaper:smaller space,less to advertise S BUT:less individualization 2616009:Network Traffic Engineering 6:Packet Scheduling Page.13
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.13 Degree of Aggregation • Some individual connections can be aggregated in deciding their service order • Connections within a class share the same service quality • The scheduler provides different qualities of service to different classes - At one extreme, the scheduler uses a single state variable to describe all connections. - At the other extreme, the scheduler maintains per-connection state, and can give different connections different bandwidth and delay bounds. • Aggregation trade off smaller scheduler state for a coarser-grained differentiation in QoS - More aggregation §less state §cheaper: smaller space, less to advertise §BUT: less individualization
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Service order within a priority level and aggregation class Two fundamental choices serving packets in order they arrive serving packets according to a per-packet service tag 。 For the second choice,the scheduler properties depend heavily on how to compute the tag FCFS discipline does not allow packets that want a lower delay to skip to the head of the queue In order of service tag,packets that want a low delay can be given a lower tag value than others in the queue,and can jump to the head of the queue 2616009:Network Traffic Engineering 6:Packet Scheduling Page.14
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.14 Service order within a priority level and aggregation class • Two fundamental choices serving packets in order they arrive serving packets according to a per-packet service tag • For the second choice, the scheduler properties depend heavily on how to compute the tag • FCFS discipline does not allow packets that want a lower delay to skip to the head of the queue • In order of service tag, packets that want a low delay can be given a lower tag value than others in the queue, and can jump to the head of the queue
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Summary of Mechanism to Create a Scheduling Discipline For the above 4 degrees of freedom in designing scheduling discipline,by appropriately combining elements along each axis,we can come up with new disciplines that provide a trade-off between implementation complexity and desirable features. Each feature comes at some cost. 。 Depending on the situation,a designer must match the need for a feature with its implementation cost. 2616009:Network Traffic Engineering 6:Packet Scheduling Page.15
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.15 Summary of Mechanism to Create a Scheduling Discipline • For the above 4 degrees of freedom in designing scheduling discipline, by appropriately combining elements along each axis, we can come up with new disciplines that provide a trade-off between implementation complexity and desirable features. • Each feature comes at some cost. • Depending on the situation, a designer must match the need for a feature with its implementation cost