Quality of Service QoS EE 122 Intro to Communication Networks Fall 2006 MW 4 5 30 in Donner 155 Vern Paxson TAs Dilip Antony Joseph and Sukun Kim http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 Announcements Homework 3 solutions now available Reminder phase 1 of Project 3 due this Thurs evening with no slip days 2 1 Goals of Today s Lecture How can we get some sort of reliable performance from 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 3 Scheduling Decide when and what packet to send on output link Classifier partitions incoming traffic into flows each with their own FIFO queue flow 1 1 2 Classifier flow 2 Scheduler flow n Buffer management 4 2 Link 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 traffic 5 Link 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 first 6 3 Link 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 idle 50 red 25 blue 25 green 7 Max Min Fairness Denote C link capacity N number of flows ri arrival rate Max min fair rate computation 1 compute C N 2 if there are flows i such that ri C N update C and N C C i s t ri C N ri N N k for k such flows 3 if no f C N terminate 4 go to 1 Flows receive at most the fair rate i e min f ri 8 4 Example 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 4 8 6 2 10 4 4 2 f 4 min 8 4 4 min 6 4 4 min 2 4 2 9 Fair Queuing FQ DKS 89 Conceptually computes when each bit in the queue should be transmitted to attain max min fairness a fluid flow system approach Then serve packets in the order of the transmission time of their last bits 10 5 Example Flow 1 arrival traffic Flow 2 arrival traffic Service in fluid flow system Packet system 1 2 3 4 5 6 time 1 2 3 1 2 1 1 2 4 5 2 3 3 1 3 time 4 5 4 2 3 4 6 5 4 5 5 time 6 time 11 Fair Queuing FQ DKS 89 Conceptually computes when each bit in the queue should be transmitted to attain max min fairness a fluid flow system approach Then serve packets in the order of the transmission time of their last bits Provides isolation misbehaving flow can t impair others Doesn t solve congestion still need to deal with individual queues filling up Generalized to Weighted Fair Queuing WFQ 12 6 Reserving 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 13 Specifying 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 resources 14 7 Characterizing 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 available r bps Maximum of bits sent bits slope r b R R r b bits slope R R bps time regulator 15 Traffic Enforcement Example r 100 Kbps b 3 Kb R 500 Kbps b a 3Kb 2 2Kb T 2ms packet transmitted b 3Kb 1Kb 2ms 100Kbps 2 2Kb T 0 1Kb packet arrives c 2 4Kb T 4ms 3Kb packet arrives d 3Kb T 10ms packet needs to wait until enough tokens are in the bucket e 0 6Kb T 16ms packet transmitted 16 8 Source Traffic Characterization Arrival Curve Arrival curve maximum amount of bits transmitted during an interval of time t Use token bucket to bound arrival curve bps bits Arrival curve t time 17 Arrival Curve Example Arrival curve maximum amount of bits transmitted during an interval of time t Use token bucket to bound arrival curve bits R 2 b 1 r 1 Arrival curve 2 5 4 bps 3 2 2 1 1 0 1 2 3 4 5 time 1 3 4 t 18 9 QoS 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 D slope ra slope r bits Arrival curve b R R r R D Ba 19 Ensuring the Source Behaves Guarantees depend on the source behaving Extra traffic might overload one or more links Leading to congestion and resulting delay and loss Solution need to enforce the traffic specification Solution 1 policing Drop all data in excess of the traffic specification Solution 2 shaping Delay the data until it obeys the traffic specification Solution 3 marking Mark all data in excess of the traffic specification and give …
View Full Document