Quality of ServiceMP4DV reviewSlide 4Slide 5When Best Effort is Not EnoughSlide 7QoS overviewThe problems caused by FIFO queues in routersFair SharingMax-Min Fairness A common way to allocate flowsMax-Min Fairness An exampleMax-Min FairnessFair QueuingFair QueueingWeighted Bit-by-Bit Fair QueueingVariable RatesPacketized Weighted Fair Queueing (WFQ)Understanding bit by bit WFQ 4 queues, sharing 4 bits/sec of bandwidth, Equal WeightsSlide 20The use of WFQ for (weighted) fairnessSlide 22Some applications that would like bounds on packet delayThe need for a playback bufferSlide 25In real life: Delay VariationSlide 27Slide 28Slide 29Playback bufferSome observationsA router queueA simple deterministic modelA simple deterministic model bytes or “fluid”Simple deterministic modelExampleDeterministic analysis of a router queueSo how can we control the delay of packets?PowerPoint PresentationHow to bound packet delay?Traffic ConstraintsThe leaky bucket “(s,r)” regulatorLeaky Bucket RegulatorLeaky Bucket Uses(s,r) Constrained Arrivals and Minimum Service RateHow the user/flow can conform to the (s,r) regulationProviding Delay Guarantees: SummaryFlow aggregationIETF Integrated ServicesIntserv: QoS guarantee scenarioCall AdmissionIntserv QoS: Service models [rfc2211, rfc 2212]IETF Differentiated ServicesDiffserv ArchitectureSlide 55Classification and ConditioningSlide 57Forwarding (PHB)Slide 59Signaling in the InternetRSVP Design GoalsRSVP: does not…RSVP: overview of operationPath msgs: RSVP sender-to-network signalingRSVP: simple audio conferenceRSVP: building up path stateSlide 67Slide 68reservation msgs: receiver-to-network signalingRSVP: receiver reservation example 1Slide 71RSVP: receiver reservation example 1 (more)RSVP: receiver reservation: issuesRSVP: example 2Slide 75Slide 76RSVP: soft-stateThe many uses of reservation/path refreshRSVP: reflectionsQuality of Service in the Internet1Quality of Service2MP4MP4 handed outDue Dec 8thDesign due Nov 29thLargest component: correctnessReliably transfer filesPerformance “contest”Lowest transfer time get highest gradesUp to 20% bonus for the assignmentNO credit if correctness fails3DV reviewabcd1124Node Dist to aNext Nodeb 1 ac 2 bd 4 c4DV reviewabcd100124Node Dist to aNext Nodeb 100 ac 2 bd 4 cNode Dist to aNext Nodeb 8 dc 101 bd 4 cNode Dist to aNext Nodeb 8 dc 9 bd 103 c5DV reviewabcd100124Node Dist to aNext Nodeb 1 ac 2 bd 4 cNode Dist to aNext Nodeb 8 dc 2 bd 4 cNode Dist to aNext Nodeb 8 dc 9 bd 4 c6When Best Effort is Not EnoughIP service model: best effortPackets dropped, reordered, modified, duplicatedTCP makes up for most shortfallsReliable transportWhat doesn’t TCP fix?What applications are unsatisfied by TCP?7Quality of ServiceQoS - network-level guarantee of quality of serviceUsually includes delay and bandwidthBoth important to real-time/multimedia applicationsSometimes loss is also specifiedGuarantees added on top of IPDon’t want to switch to ATM architectureWant to coexist with normal IP traffic8QoS overviewQoS mechanismsFair sharing (bandwidth guarantees)Traffic shaping / policing (delay guarantees)Reservation systems9The problems caused by FIFO queues in routers1. In order to maximize its chances of success, a source has an incentive to maximize the rate at which it transmits. 2. (Related to #1) When many flows pass through it, a FIFO queue is “unfair” – it favors the most greedy flow.3. It is hard to control the delay of packets through a network of FIFO queues.FairnessDelay Guarantees10Fair SharingTCP sourcesFair (mostly) sharing implemented by congestion control mechanismsnon-TCP (UDP) sourcesTCP-friendly design to support fair sharing with TCPTCP-unfriendly sourcesIntentionally or accidentally use more bandwidth than fair shareHow do we handle these?11Max-Min FairnessA common way to allocate flowsN flows share a link of rate C. Flow f wishes to send at rate W(f), and is allocated rate R(f).•Pick the flow, f, with the smallest requested rate.•If W(f) < C/N, then set R(f) = W(f). •If W(f) > C/N, then set R(f) = C/N.•Set N = N – 1. C = C – R(f).•If N > 0 goto 1.121W(f1) = 0.1W(f3) = 10R1CW(f4) = 5W(f2) = 0.5Max-Min FairnessAn exampleRound 1: Set R(f1) = 0.1Round 2: Set R(f2) = 0.9/3 = 0.3Round 3: Set R(f4) = 0.6/2 = 0.3Round 4: Set R(f3) = 0.3/1 = 0.313Max-Min FairnessHow can an Internet router allocate different rates to different flows? First, let’s see how a router can allocate the same rate to different flows…14Fair QueuingTwo flows must share 1 Mbps link fairlyHow does router guarantee this?ATM: use TDMAAlternate cells between flows15Fair Queueing1. 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. 3. This is called Bit-by-Bit Fair Queueing.Flow 1Flow NClassification SchedulingBit-by-bit round robin16Weighted Bit-by-Bit Fair QueueingLikewise, flows can be allocated different rates by servicing a different number of bits for each flow during each round. 1R(f1) = 0.1R(f3) = 0.3R1CR(f4) = 0.3R(f2) = 0.3Order of service for the four queues:… f1, f2, f2, f2, f3, f3, f3, f4, f4, f4, f1,…Also called “Generalized Processor Sharing (GPS)”17Variable RatesEach flow may not always send at full fractional rateRound-robin skips flows that don’t have packets queuedBest of both worlds:Each flow guaranteed rate of at least R(f)Can use more capacity if available18Packetized Weighted Fair Queueing (WFQ)Problem: We need to serve a whole packet at a time.Solution: 1. Determine what time a packet, p, would complete if we served flows bit-by-bit. Call this the packet’s finishing time, Fp.2. Serve packets in the order of increasing finishing time.Theorem: Packet p will depart before Fp+ TRANSPmaxAlso called “Packetized Generalized Processor Sharing (PGPS)”19Understanding bit by bit WFQ 4 queues, sharing 4 bits/sec of bandwidth, Equal WeightsWeights : 1:1:1:111116 5 4 3 2 1 0B1 = 3A1 = 4D2 = 2D1 = 1C2 = 1 C1 = 1 Time11116 5 4 3 2 1 0B1 = 3A1 = 4D2 = 2D1 = 1C2 = 1 C1 = 1A1B1C1D1A2 = 2C3 = 2Weights : 1:1:1:1D1, C1 Depart at R=1A2, C3 arrive TimeRound 1Weights : 1:1:1:111116 5
View Full Document
Unlocking...