Networks Scheduling, Isolation, and Fairness

6.829 Computer Networks Lecture 5: Scheduling, Isolation, and Fairness Mohammad Alizadeh Fall 2016 Some slides based on lectures by: Nick McKeown (nickm@cs.stanford.edu), and Ion Stoica (istoica@cs.berkeley.edu) 1

Recap of last time Buffer management When and which packet to drop? Drop-tail: large delays, synchronization RED: Early probabilistic dropping PI: Decouple queue length & number of flows Explicit congestion control ECN: slow down! (binary feedback) XCP: increase/decrease by (multi-bit feedback)

Max-Min Fairness A common way to allocate flows 1. Allocate in order of increasing demand 2. No flow gets more than demand 3. The excess, if any, is equally shared = Rate Demanded/Allocated min( , ) r f C 8 10 i 4 i 4 2 10 2 10 8 f = 4: min(8, 4) = 4 min(10, 4) = 4 min(2, 4) = 2 Total = 10 Total = 6 2 2 4 4 2 2 Flows sorted by demand 3

XCP: An eXplicit Control Protocol 1. Efficiency Controller 2.Fairness Controller Credit: Dina Katabi (MIT)

How Does an XCP Router Compute the Feedback? Efficiency Controller Fairness Controller Goal: Matches input traffic to link capacity & drains the queue Goal: Divides between flows to converge to fairness Looks at a flow s state in Congestion Header Looks at aggregate traffic & queue Algorithm: Aggregate traffic changes by ~ Spare Bandwidth ~ - Queue Size So, = davg Spare - Queue Algorithm: If > 0 Divide equally between flows If < 0 Divide between flows proportionally to their current rates Credit: Dina Katabi (MIT)

Packet Scheduling In what order are packets sent Work-conserving e.g., FCFS, priorities, weighted fair-queueing At what time are packets sent Non-work-conserving e.g., Token bucket shaping 6

Weighted Fair Queueing A schedulingalgorithm for (weighted) max-min fairness Decides which flow s packet to send next Link 1, ingress Link 1, egress Link 2, ingress Link 2, egress flow 1 Classifier flow 2 Scheduler Link 3, ingress Link 3, egress flow n 7 Credit: Nick McKeown (Stanford)

Properties of WFQ Work conserving Link is busy if there are packets to send Max-min fair allocation of bandwidth Provides isolation Behavior of one sender does not impact another Traffic hogs cannot overrun others End-to-end delay bounds for guaranteed service 8

Bandwidth vs Delay Guarantees 0.1Mb/s A Voice call 1Mb/s C 1Mb/s B 1/7 Mb/s Time-scale of bw guarantee critical for delay Mon Tue Wed Thu Fri Sat Sun Mon 9

Classic Papers Thousands of citations; several best paper awards; on nearly every must-read networking papers list 10

Outline for Rest of Today Bit-by-bit Fair Queuing ( fluid system) Packet-by-packet Fair Queuing (aka. WFQ) Implementing WFQ 11

Bit-by-Bit Fair Queueing 1. Packets belonging to a flow are placed in a FIFO. This is called per-flow queueing . 2. FIFOs are scheduled one bit at a time, in a round-robin fashion. Question: How can we give weights? Question: What is a flow ? Flow 1 Bit-by-bit round robin Classification Flow N * Slide by Nick Mckeown nickm@cs.stanford.edu 12

Bit-by-Bit Weighted Fair Queueing Flows can be allocated different rates by servicing a different number of bits for each flow during each round. w1 = 0.1 w2 = 0.3 1 C R1 w3 = 0.3 w4 = 0.3 Order of service for the four queues: f1, f2, f2, f2, f3, f3, f3, f4, f4, f4, f1, Generalized Processor Sharing (GPS): infinitesimal amount of flow instead of bits 13 * Slide by Nick Mckeown (nickm@cs.stanford.edu)

GPS Example Red flow backlogged between time 0 and 10 Question: Is this max-min fair? link Other flows continuously backlogged flows 5 1 1 1 1 1 0 2 4 6 8 10 15 * Slide by Ion Stoica istoica@cs.berkeley.edu 14

Outline Bit-by-bit Fair Queuing ( fluid system) Packet-by-packet Fair Queuing (aka. WFQ) Implementing WFQ 15

Packet vs. Fluid System Bit-by-bit FQ is not implementable [why?] Multiple queues/packets can be serviced simultaneously In real packet-based systems One queue is served at any given time Packet transmission cannot be preempted Goal: A packet scheme close to fluid system Bound performance w.r.t fluid system 16

First Cut: Simple Round Robin Serve a packet from non-empty queues in turn Lets assume all flows have equal weight [Is this fair?] Variable packet length can get more service by sending bigger packets Unfair instantaneous service rate (esp. with variable weights) E.g. 500 flows: 250 with weight 1, 250 with weight 10 Each round takes 2,750 packet times What if a packet arrives right after its turn ? 17

Packet-by-packet Fair Queuing (Weighted Fair Queuing) Deals better with variable size packets and weights Key Idea: 1. Determine the finish time of packets in bit-by-bit system (GPS), assuming no more arrivals 2. Serve packets in order of finish times GPS+Lmax Theorem: WFQ Fp Fp r 18

Intuition for Bound Finishing order of packets currently in fluid system is independent of future arrivals [why?] A packet is delayed more in packet system only if when it arrives, a packet that finishes later in the fluid system is already being transmitted There can be at most one such packet 19

Outline GPS ( fluid system) Packet-by-packet GPS (aka. WFQ) Implementing WFQ 20

Implementing WFQ Challenge: Determining finish time for GPS is hard [Why?] Idea: Don t need finish time. Need finish order. The finish order is a lot easier to calculate. 21

Finish order Increasing Li/wi In what order do the packets finish? L1 w1 = 0.1 1 L2 w2 = 0.3 C R1 w3 = 0.3 w4 = 0.3 L3 Order of service for the four queues: f1, f2, f2, f2, f3, f3, f3, f4, f4, f4, f1, L4 Does not change with future packet arrivals! 22

Bit-by-bit System Round L1 w1 = 0.1 w1 = 1 1 L2 w2 = 0.3 w2 = 3 C R1 w3 = 3 w3 = 0.3 w4 = 0.3 w4 = 3 L3 Order of service for the four queues: f1, f2, f2, f2, f3, f3, f3, f4, f4, f4, f1, L4 Round One complete cycle through all the queues sending wibits per qeueue R(t) = # of rounds at time t C = link rate B(t) = set of backlogged flows dR dt Question: How long does a round take? C = wj j B(t) 23

Bit-by-bit System Round L1 w1 = 0.1 w1 = 1 1 L2 w2 = 0.3 w2 = 3 C R1 w3 = 3 w3 = 0.3 w4 = 0.3 w4 = 3 L3 Order of service for the four queues: f1, f2, f2, f2, f3, f3, f3, f4, f4, f4, f1, L4 Round One complete cycle through all the queues sending wibits per qeueue Question: How many rounds does it take to Packet of length L takes L/wi rounds to serve serve a packet of length L from flow i? 24

Round vs Time 1/2 1/8 1/8 1/8 1/8 R(t) 2*C C 2*C 0 4 8 12 16 * Based on slide by Ion Stoica istoica@cs.berkeley.edu 25

Round (aka. Virtual Time) Implementation of WFQ Assign a start/finish round to each packet at arrival serve packets in order of finish rounds Question: What is finish round of kth packet Fik? Suppose kth packet of flow i arrives at time a Finish round of (k-1)th packet Start round of kth packet k-1 k k-1 Fi (Flow i backlogged) k= Si R(a) k Round number at time a (Flow i empty) 26

Putting it All Together For kth packet of flow i arriving at time a: k-1,R(a)) k=max(Fi Si k k+Li i w k= Si Fi Question: How to compute R(a)? Simple approximation: Set R(a) to start or finish round of packet currently in service dR dt C = wj j B(t) 27

Summary of WFQ Pros Excellent approximation of GPS Preserves good properties of GPS: isolation, rate and delay guarantees Gives users incentive to use intelligent flow control Cons Needs per-flow queues (potentially millions) Requires sorting packets by virtual finish time Virtual time hard to implement exactly 28

29