Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 What is actually out there? So far,the range of choices available in commercial switches routers,multiplexers)is limited:most schedulers are FIFO,with single level priority: 。 Some products of routers and switches begin to provide alternatives, such as WFQ,Weighted round-robin,etc. Example:CISCO routers provide FIFO,Priority Queuing,Custom Queuing and Weighted Fair Queuing Manufacturers are slowly beginning to realize the need to for good scheduling discipline,and this has resulted in some excellent research in this area - Motivated by the requirement of supporting QoS application; We can expect the results of this research appear in switches and routers over the next decade. 2616009:Network Traffic Engineering 6:Packet Scheduling Page.16
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.16 What is actually out there? • So far, the range of choices available in commercial switches ( routers, multiplexers) is limited: most schedulers are FIFO, with single level priority; • Some products of routers and switches begin to provide alternatives, such as WFQ, Weighted round-robin, etc. - Example: CISCO routers provide : FIFO, Priority Queuing, Custom Queuing and Weighted Fair Queuing • Manufacturers are slowly beginning to realize the need to for good scheduling discipline, and this has resulted in some excellent research in this area - Motivated by the requirement of supporting QoS application; • We can expect the results of this research appear in switches and routers over the next decade
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Scheduling:Methods FCFS Round Robin 。 Priority Queueing 。 Priority Queueing with Windows 。 Generalized Processor Sharing (GPS) Weighted Round Robin (WRR) 。 Deficit Round-Robin(DRR) VirtualClock Weighted Fair Queueing(WFQ),WF2Q,WF2Q+ 。 Self-Clocked Fair Queueing (SCFQ) Stop and Go Rate Controlled Service Descipline(RCSD) 2616009:Network Traffic Engineering 6:Packet Scheduling Page.17
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.17 Scheduling: Methods • FCFS • Round Robin • Priority Queueing • Priority Queueing with Windows • Generalized Processor Sharing (GPS) • Weighted Round Robin (WRR) • Deficit Round-Robin(DRR) • VirtualClock • Weighted Fair Queueing (WFQ), WF2Q, WF2Q+ • Self-Clocked Fair Queueing (SCFQ) • Stop and Go • Rate Controlled Service Descipline (RCSD)
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 The Conservation Law--FCFS Simplest scheduling:first-come-first-served(FCFS) The scheduler transmit incoming packets in the order they arrive at the output queue,and drop packets that arrive at a full queue. FCFS scheduling cannot differentiate among connections Conservation law states that if the scheduler is work-conserving (i.e., it is idle only if its queue is empty: -constant where p:mean utilization of a link due to connection i 9, connection i's mean waiting time at the scheduler Unfair No isolation among users 2616009:Network Traffic Engineering 6:Packet Scheduling Page.18
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.18 The Conservation Law--FCFS • Simplest scheduling: first-come-first-served (FCFS) • The scheduler transmit incoming packets in the order they arrive at the output queue, and drop packets that arrive at a full queue. • FCFS scheduling cannot differentiate among connections • Conservation law states that if the scheduler is work-conserving (i.e., it is idle only if its queue is empty: where : mean utilization of a link due to connection i : connection i’s mean waiting time at the scheduler N i i i q 1 r constant ri qi Unfair No isolation among users
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Priority Queuing Also known as head of line (HOL) Priority O through n-1 Priority 0 is always serviced first. Priority i is serviced only if O through i-1 are empty Highest priority has the lowest delay,highest throughput, lowest loss Lower priority classes may be starved if higher priority are overloaded 2616009:Network Traffic Engineering 6:Packet Scheduling Page.19
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.19 Priority Queuing • Also known as head of line (HOL) • Priority 0 through n-1 • Priority 0 is always serviced first. • Priority i is serviced only if 0 through i-1 are empty • Highest priority has the lowest delay, highest throughput, lowest loss • Lower priority classes may be starved if higher priority are overloaded
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Priority Queueing(cont'd) Example of implementation in a Router: Priority queuing defines four priorities of traffic-high,normal,medium,and low Router Backbone network Traffic Priority UDP High Bridged LAT- priority Traffic sent to router DECnet Traffic sent to Medium backbone in without any priority VINES priority TCP order of priority Other bridged- Normal All other traffic priority Low AppleTalk priority 2616009:Network Traffic Engineering 6:Packet Scheduling Page.20
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 6: Packet Scheduling Page.20 Priority Queueing(cont’d) Router Traffic sent to router without any priority Traffic Priority UDP Bridged LAT DECnet VINES TCP Other bridged All other traffic AppleTalk High priority Medium priority Normal priority Low priority Backbone network Traffic sent to backbone in order of priority • Example of implementation in a Router: Priority queuing defines four priorities of traffic—high, normal, medium, and low