11Quality of Service (QoS)EE 122: Intro to Communication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Next week I will give the same lecture on bothWednesday (usual time) and next Monday– Same time and room– Reminder, no lecture next Friday due to holiday• I will hold extra office hours next Monday, 3-4PM3Goals 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• How the lack of working QoS becomes a businessopportunity4Scheduling• Decide when and what packet to send on output link• Classifier partitions incoming traffic into flows each with theirown FIFO queue12Schedulerflow 1flow 2flow nClassifierBuffermanagement5Link 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 delayo 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 transmissiono High-priority packet arrives during transmission of low-priorityo Router completes sending the low-priority traffic first27Link 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/N (= the remaining fair share)2. if there are flows i such that ri ≤ C/Nthen update C and Nand go to 13. if not, f = C/N; terminate• 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)9Example• 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 bits11Example1 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)313Reserving 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 resourceso E.g., “the link has 6 Mbps left”– Checks if enough resources remaino E.g., “6 Mbps > 5 Mbps, so circuit can be accepted”– Creates state for flow and reserves resourceso E.g., “now only 1 Mbps is available”14How to Specify Bursty Traffic• Option #1: Specify the maximum bit rate.Problems?– Maximum bit rate may be much higher average– Reserving for the worst case is wasteful• Option #2: Specify the average bit rate.Problems?– 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 resources15Characterizing 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 can be transmitted only when a token isavailabler bpsb bits ≤ R bpsregulatortimebitsb·R/(R-r)slope Rslope rMaximum # of bits sentb/(R-r)16Traffic 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)175 Minute BreakQuestions Before We Proceed?18Source Traffic Characterization: Arrival Curve• Arrival curve – maximum amount of bitstransmitted during any interval of time Δt• Use token bucket to bound arrival curveΔtbitsArrival curvetimebps419Arrival Curve: Example• Arrival curve – maximum amount of bitstransmitted during any 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)Δt20QoS Guarantees: Per-hop Reservation• End-host: specify– arrival rate characterized by token bucket with parameters (b,r,R)– the maximum tolerable delay D, no losses• Router: allocate bandwidth ra, buffer space Ba such that– no packet is dropped– no packet experiences a delay
View Full Document
Unlocking...