This preview shows page 1-2-3-4-5-6-7-50-51-52-53-54-55-56-100-101-102-103-104-105-106 out of 106 pages.
1Quality of Service2MP4 MP4 handed out Due Dec 8th Design due Nov 29th Largest component: correctness Reliably transfer files Performance “contest” Lowest transfer time get highest grades Up to 20% bonus for the assignment NO credit if correctness fails3DV reviewabcd1124c4db2ca1bNextNodeDistto aNode4DV reviewabcd100124c4db2ca100bNextNodeDistto aNodec4db101cd8bNextNodeDistto aNodec103db9cd8bNextNodeDistto aNode5DV reviewabcd100124c4db2ca1bNextNodeDistto aNodec4db2cd8bNextNodeDistto aNodec4db9cd8bNextNodeDistto aNode6When Best Effort is NotEnough IP service model: best effort Packets dropped, reordered, modified,duplicated TCP makes up for most shortfalls Reliable transport What doesn’t TCP fix? What applications are unsatisfied by TCP?7Quality of Service QoS - network-level guarantee of quality ofservice Usually includes delay and bandwidth Both important to real-time/multimediaapplications Sometimes loss is also specified Guarantees added on top of IP Don’t want to switch to ATM architecture Want to coexist with normal IP traffic8QoS overview QoS mechanisms Fair sharing (bandwidth guarantees) Traffic shaping / policing (delayguarantees) Reservation systems9The problems caused by FIFOqueues in routers1. In order to maximize its chances ofsuccess, a source has an incentive tomaximize the rate at which it transmits.2. (Related to #1) When many flows passthrough it, a FIFO queue is “unfair” – itfavors the most greedy flow.3. It is hard to control the delay of packetsthrough a network of FIFO queues.FairnessDelay Guarantees10Fair Sharing TCP sources Fair (mostly) sharing implemented by congestioncontrol mechanisms non-TCP (UDP) sources TCP-friendly design to support fair sharing withTCP TCP-unfriendly sources Intentionally or accidentally use more bandwidththan fair share How do we handle these?11Max-Min FairnessA common way to allocate flowsN flows share a link of rate C. Flow f wishes tosend at rate W(f), and is allocated rate R(f).1. Pick the flow, f, with the smallest requestedrate.2. If W(f) < C/N, then set R(f) = W(f).3. If W(f) > C/N, then set R(f) = C/N.4. Set N = N – 1. C = C – R(f).5. If N > 0 goto 1.121W(f1) = 0.1W(f3) = 10R1CW(f4) = 5W(f2) = 0.5Max-Min FairnessAn example121W(f1) = 0.1W(f3) = 10R1CW(f4) = 5W(f2) = 0.5Max-Min FairnessAn exampleRound 1: Set R(f1) = 0.1121W(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.3121W(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.3121W(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 Fairness How can an Internet router allocatedifferent rates to different flows? First, let’s see how a router canallocate the same rate to differentflows…14Fair Queuing Two flows must share 1 Mbps linkfairly How does router guarantee this? ATM: use TDMA Alternate cells between flows15Fair Queueing1. Packets belonging to a flow are placed in aFIFO. This is called “per-flow queueing”.2. FIFOs are scheduled one bit at a time, in around-robin fashion.3. This is called Bit-by-Bit Fair Queueing.Flow 1Flow NClassification SchedulingBit-by-bit round robin16Weighted Bit-by-Bit FairQueueingLikewise, flows can be allocated differentrates by servicing a different number ofbits 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 Rates Each flow may not always send at fullfractional rate Round-robin skips flows that don’thave packets queued Best of both worlds: Each flow guaranteed rate of at least R(f) Can use more capacity if available18Packetized Weighted FairQueueing (WFQ)Problem: We need to serve a whole packet at atime.Solution:1. Determine what time a packet, p, would complete if weserved flows bit-by-bit. Call this the packet’s finishingtime, 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 WFQ4 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 Time19Understanding bit by bit WFQ4 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 = 2 D1 = 1C2 = 1 C1 = 1A1B1C1D1A2 = 2C3 = 2Weights : 1:1:1:1D1, C1 Depart at R=1A2, C3 arrive TimeRound 119Understanding bit by bit WFQ4 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 = 2 D1 = 1C2 = 1 C1 = 1A1B1C1D1A2 = 2C3 = 2Weights : 1:1:1:1D1, C1 Depart at R=1A2, C3 arrive TimeRound 1Weights : 1:1:1:111116 5 4 3 2 1 0B1 = 3A1 = 4D2 = 2 D1 = 1C2 = 1 C1 = 1A1B1C1D1A2 = 2C3 = 2A1B1C2D2C2 Departs at R=2TimeRound 1Round 220Understanding bit by bit WFQ4 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 = 1A1B1C1D1A2 = 2C3 = 2A1B1C2D2D2, B1 Depart at R=3A1B1C3D2TimeRound 1Round 2Round 320Understanding bit by bit WFQ4 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 = 1A1B1C1D1A2 = 2C3 = 2A1B1C2D2D2, B1 Depart at R=3A1B1C3D2TimeRound 1Round 2Round 311116
View Full Document
Unlocking...