11Quality of Service (QoS)EE 122: Intro to Communication NetworksFall 2006 (MW 4-5:30 in Donner 155)Vern PaxsonTAs: Dilip Antony Joseph and Sukun Kimhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Homework #3 solutions now available• Reminder, phase 1 of Project #3 due this Thursevening with no slip days23Goals of Today’s Lecture• How can we get some sort of reliable performancefrom the network?– If we need it• QoS mechanisms from fine-grained to large-scale:– Queuing algorithms beyond FIFO (isolation, fairness)– End-to-end network “reservations” (Integrated Services)– First Class vs. Coach (Differentiated Services)• Why none of this actually works– At least, not end-to-end• The struggle over “network neutrality”4Scheduling• Decide when and what packet to send on output link• Classifier partitions incoming traffic into flows eachwith their own FIFO queue12Schedulerflow 1flow 2flow nClassifierBuffermanagement35Link Scheduling: FIFO• What if scheduler uses one first-in first-out queue?– Simple to implement– But, restrictive in providing guarantees• Example: two kinds of traffic– Video conferencing needs high bandwidth and low delay E.g., 1 Mbps and 100 msec delay– E-mail transfers not very sensitive to delay• Cannot admit much e-mail traffic– Since it will interfere with the video conference traffic6Link Scheduling: Strict Priority• Strict priority– Multiple levels of priority– Always transmit high-priority traffic, when present– .. and force the lower priority traffic to wait• Isolation for the high-priority traffic– Almost like it has a dedicated link– Except for the (small) delay for packet transmission High-priority packet arrives during transmission of low-priority Router completes sending the low-priority traffic first47Link Scheduling: Weighted Fairness• Limitations of strict priority– Lower priority queues may starve for long periods– … even if the high-priority traffic can afford to wait– Traffic still competes inside each priority queue• Weighted fair scheduling– Assign each queue a fraction of the link bandwidth– Rotate across the queues on a small time scale– Send extra traffic from one queue if others are idle50% red, 25% blue, 25% green8Max-Min Fairness• Denote– C – link capacity– N – number of flows– ri – arrival rate• Max-min fair rate computation:1. compute C/N2. if there are flows i such that ri ≤ C/N, update C and N3. if no, f = C/N; terminate4. go to 1• Flows receive at most the fair rate, i.e., min(f, ri)! C = C " rii s.t ri#C / N$; N = N " k (for k such flows)59Example• C = 10; r1 = 8, r2 = 6, r3 = 2; N = 3• C/3 = 3.33 – Can service all of r3– Remove r3 from the accounting: C = C – r3 = 8; N = 2• C/2 = 4 – Can’t service all of r1 or r2– So hold them to the remaining fair share: f = 4862442f = 4: min(8, 4) = 4 min(6, 4) = 4 min(2, 4) = 2 1010Fair Queuing (FQ) [DKS’89]• Conceptually, computes when each bit in thequeue should be transmitted to attain max-minfairness (a “fluid flow system” approach)• Then serve packets in the order of thetransmission time of their last bits611Example1 2 3 4 51 2 3 41 231 243 455 61 2 1 3 2 3 4 45 655 6Flow 1(arrival traffic)Flow 2(arrival traffic)Servicein fluid flow systemPacketsystemtimetimetimetime12Fair Queuing (FQ) [DKS’89]• Conceptually, computes when each bit in thequeue should be transmitted to attain max-minfairness (a “fluid flow system” approach)• Then serve packets in the order of thetransmission time of their last bits• Provides isolation: misbehaving flow can’t impairothers• Doesn’t “solve” congestion: still need to deal withindividual queues filling up• Generalized to Weighted Fair Queuing (WFQ)713Reserving Resources End-to-End• Source sends a reservation message– E.g., “this flow needs 5 Mbps”• Each router along the path– Keeps track of the reserved resources E.g., “the link has 6 Mbps left”– Checks if enough resources remain E.g., “6 Mbps > 5 Mbps, so circuit can be accepted”– Creates state for flow and reserves resources E.g., “now only 1 Mbps is available”14Specifying Bursty Traffic• Option #1: Specify the maximum bit rate– Maximum bit rate may be much higher average– Reserving for the worst case is wasteful• Option #2: Specify the average bit rate– Average bit rate is not sufficient– Network will not be able to carry all of the packets– Reserving for average case leads to bad performance• Option #3: Specify the burstiness of the traffic– Specify both the average rate and the burst size– Allows the sender to transmit bursty traffic– … and the network to reserve the necessary resources815Characterizing Burstiness: Token Bucket• Parameters– r – average rate, i.e., rate at which tokens fill the bucket– b – bucket depth (limits size of burst)– R – maximum link capacity or peak rate• A bit is transmitted only when token is availabler bpsb bits ≤ R bpsregulatortimebitsb·R/(R-r)slope Rslope rMaximum # of bits sent16Traffic Enforcement: Example• r = 100 Kbps; b = 3 Kb; R = 500 Kbps3KbT = 0 : 1Kb packet arrives(a)2.2KbT = 2ms : packet transmitted b = 3Kb – 1Kb + 2ms*100Kbps = 2.2Kb(b)2.4KbT = 4ms : 3Kb packet arrives(c)3KbT = 10ms : packet needs to wait until enough tokens are in the bucket(d)0.6KbT = 16ms : packet transmitted(e)917Source Traffic Characterization: Arrival Curve• Arrival curve – maximum amount of bitstransmitted during an interval of time Δt• Use token bucket to bound arrival curveΔtbitsArrival curvetimebps18Arrival Curve: Example• Arrival curve – maximum amount of bitstransmitted during an interval of time Δt• Use token bucket to bound arrival curvebitsArrival curvetimebps01 2 3 4 5121 2 3 4 51234(R=2,b=1,r=1)Δt1019QoS Guarantees: Per-hop Reservation• End-host: specify– arrival rate characterized by token-bucket with parameters (b,r,R)– the maximum admissible delay D, no losses• Router: allocate bandwidth ra, buffer space Ba such that– no packet is dropped– no packet experiences a delay larger than Dbitsb*R/(R-r)slope rArrival curveDBaslope raR20Ensuring the Source Behaves• Guarantees depend on the source behaving– Extra traffic might overload one or more links– Leading to
View Full Document