Announcements Next week I will give the same lecture on both Wednesday usual time and next Monday Same time and room Reminder no lecture next Friday due to holiday Quality of Service QoS EE 122 Intro to Communication Networks I will hold extra office hours next Monday 3 4PM Fall 2007 WF 4 5 30 in Cory 277 Vern Paxson TAs Lisa Fowler Daniel Killebrew Jorge Ortiz http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 2 Goals of Today s Lecture Scheduling How can we get some sort of reliable performance from the network Decide when and what packet to send on output link Classifier partitions incoming traffic into flows each with their own FIFO queue If we need it QoS mechanisms from fine grained to large scale flow 1 Queuing algorithms beyond FIFO isolation fairness End to end network reservations Integrated Services First Class vs Coach Differentiated Services 1 Classifier flow 2 2 Why none of this actually works Scheduler flow n Buffer management At least not end to end How the lack of working QoS becomes a business opportunity 3 Link Scheduling FIFO 4 Link Scheduling Strict Priority What if scheduler uses one first in first out queue Strict priority Simple to implement But restrictive in providing guarantees Multiple levels of priority Always transmit high priority traffic when present and force the lower priority traffic to wait Example two kinds of traffic Isolation for the high priority traffic Video conferencing needs high bandwidth and low delay o E g 1 Mbps and 100 msec delay Almost like it has a dedicated link Except for the small delay for packet transmission E mail transfers not very sensitive to delay o High priority packet arrives during transmission of low priority o Router completes sending the low priority traffic first Cannot admit much e mail traffic Since it will interfere with the video conference traffic 5 6 1 Link Scheduling Weighted Fairness Max Min Fairness Limitations of strict priority Denote 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 C link capacity N number of flows ri arrival rate Weighted fair scheduling Max min fair rate computation 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 1 compute C N the remaining fair share 2 if there are flows i such that ri C N then update C and N C C i s t ri C N ri N N k for k such flows and go to 1 3 if not f C N terminate 50 red 25 blue 25 green 7 Example C 10 Flows receive at most the fair rate i e min f ri 8 Fair Queuing FQ DKS 89 r1 8 r2 6 r3 2 N 3 C 3 3 33 Conceptually computes when each bit in the queue should be transmitted to attain max min fairness a fluid flow system approach 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 10 6 4 4 2 2 Then serve packets in the order of the transmission time of their last bits f 4 min 8 4 4 min 6 4 4 min 2 4 2 9 Example Fair Queuing FQ DKS 89 Flow 1 arrival traffic Flow 2 arrival traffic Service in fluid flow system Packet system 10 1 2 1 2 3 1 2 1 1 2 1 3 3 3 4 4 5 2 3 2 3 4 4 5 4 6 5 4 5 5 5 Conceptually computes when each bit in the queue should be transmitted to attain max min fairness a fluid flow system approach time time Then serve packets in the order of the transmission time of their last bits time Provides isolation misbehaving flow can t impair others 6 6 Doesn t solve congestion still need to deal with individual queues filling up time 11 Generalized to Weighted Fair Queuing WFQ 12 2 Reserving Resources End to End How to Specify Bursty Traffic Option 1 Specify the maximum bit rate Problems Source sends a reservation message E g this flow needs 5 Mbps Maximum bit rate may be much higher average Reserving for the worst case is wasteful Each router along the path Keeps track of the reserved resources Option 2 Specify the average bit rate Problems o E g the link has 6 Mbps left Checks if enough resources remain 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 o E g 6 Mbps 5 Mbps so circuit can be accepted Creates state for flow and reserves resources o E g now only 1 Mbps is available Option 3 Specify the burstiness of the traffic 13 Parameters r 100 Kbps b 3 Kb R 500 Kbps 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 b a 3Kb A bit can be transmitted only when a token is available 2 2Kb T 2ms packet transmitted b 3Kb 1Kb 2ms 100Kbps 2 2Kb T 0 1Kb packet arrives Maximum of bits sent bits c slope r b R R r 14 Traffic Enforcement Example Characterizing Burstiness Token Bucket r bps Specify both the average rate and the burst size Allows the sender to transmit bursty traffic and the network to reserve the necessary resources 2 4Kb b bits d 3Kb e 0 6Kb slope R T 4ms 3Kb packet arrives R bps regulator b R r time 15 T 10ms packet needs to wait until enough tokens are in the bucket T 16ms packet transmitted 16 Source Traffic Characterization Arrival Curve Arrival curve maximum amount of bits transmitted during any interval of time t Use token bucket to bound arrival curve 5 Minute Break bps bits Arrival curve Questions Before We Proceed time 17 t 18 3 Arrival Curve Example QoS Guarantees Per hop Reservation Arrival curve maximum amount of bits transmitted during any interval of time t End host specify arrival rate characterized by token bucket with parameters b r R the maximum tolerable delay D no losses Use token bucket to bound arrival curve R 2 b 1 r 1 bits Arrival curve Router allocate bandwidth ra buffer space Ba such that no packet is dropped no packet experiences a delay larger than D 4 bps slope ra slope r 3 bits 2 2 1 1 0 1 2 3 4 5 Arrival curve b R R r 1 time 2 3 4 5 R t Ba D 19 20 Integrated Services Required Elements Ensuring the Source Behaves Reservation Protocol Guarantees depend on the source behaving How service request gets from host to network Extra …
View Full Document
Unlocking...