EECS 122 Introduction to Computer Networks Packet Scheduling and QoS Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Today s Lecture 15 2 17 18 19 6 10 11 Transport 14 15 16 7 8 9 21 22 23 25 Application Network IP Link Physical Katz Stoica F04 2 Packet Scheduling Decide when and what packet to send on output link Usually implemented at output interface of a router flow 1 1 2 Classifier flow 2 Scheduler flow n Buffer management Katz Stoica F04 3 Goals of Packet Scheduling Provide per flow aggregate QoS guarantees in terms of delay and bandwidth Provide per flow aggregate protection Flow Aggregate identified by a subset of following fields in the packet header source destination IP address 32 bits source destination port number 16 bits protocol type 8 bits type of service 8 bits Examples All packets from machine A to machine B All packets from Berkeley All packets between Berkeley and MIT All TCP packets from EECS Berkeley Katz Stoica F04 4 Outline QoS guarantees Link sharing Service curve short Katz Stoica F04 5 Recap Token Bucket and Arrival Curve Parameters r average rate i e rate at which tokens fill the bucket b bucket depth R maximum link capacity or peak rate optional parameter A bit is transmitted only when there is an available token Arrival curve maximum number of bits transmitted within an interval of time of size t r bps Arrival curve bits slope r b R R r b bits slope R R bps time regulator Katz Stoica F04 6 How Is the Token Bucket Used Can be enforced by End hosts e g cable modems Routers e g ingress routers in a Diffserv domain Can be used to characterize the traffic sent by an end host Katz Stoica F04 7 Source Traffic Characterization Arrival curve maximum amount of bits transmitted during an interval of time t Use token bucket to bound the arrival curve bps bits Arrival curve t time Katz Stoica F04 8 Source Traffic Characterization Example Arrival curve maximum amount of bits transmitted during an interval of time t Use token bucket to bound the 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 Katz Stoica F04 t 9 QoS Guarantees Per hop Reservation End host specify the arrival rate characterized by token bucket with parameters b r R the maximum maximum admissible delay D Router allocate bandwidth ra and buffer space Ba such that no packet is dropped no packet experiences a delay larger than D slope ra bits slope r Arrival curve b R R r D Ba Katz Stoica F04 10 Packet Scheduling Make sure that at any time the flow receives at least the allocated rate ra The canonical example of such scheduler Weighted Fair Queueing WFQ Katz Stoica F04 11 Recap Fair Queueing Implements max min fairness each flow receives min ri f where ri flow arrival rate f link fair rate see next slide Weighted Fair Queueing WFQ associate a weight with each flow Katz Stoica F04 12 Fair Rate Computation Example 1 If link congested compute f such that min r f C i i 8 6 2 10 4 4 2 f 4 min 8 4 4 min 6 4 4 min 2 4 2 Katz Stoica F04 13 Fair Rate Computation Example 2 Associate a weight wi with each flow i If link congested compute f such that min r f w C i i i w1 3 8 w2 1 6 w3 1 2 10 4 4 2 f 2 min 8 2 3 6 min 6 2 1 2 min 2 2 1 2 Flow i is guaranteed to be allocated a rate wi C k wk If k wk C flow i is guaranteed to be allocated a rate wi Katz Stoica F04 14 Fluid Flow System Flows can be served one bit at a time WFQ can be implemented using bit by bit weighted round robin During each round from each flow that has data to send send a number of bits equal to the flow s weight Katz Stoica F04 15 Fluid Flow System Example 1 Packet Size bits Packet inter arrival time ms Rate Kbps Flow 1 1000 10 100 Flow 2 500 10 50 Flow 1 w1 1 100 Kbps Flow 2 w2 1 Flow 1 arrival traffic 1 2 5 time Flow 2 arrival traffic Service in fluid flow system 4 3 1 1 0 3 4 3 2 10 2 1 20 6 4 2 30 5 3 40 5 4 50 time 5 60 6 70 80 time ms Katz Stoica F04 16 Fluid Flow System Example 2 link Red flow has packets backlogged between time 0 and 10 Backlogged flow flow s queue not empty flows Other flows have packets continuously backlogged All packets have the same size 0 2 4 6 weights 8 5 1 1 0 1 1 1 15 Katz Stoica F04 17 1 Implementation In Packet System Packet Real system packet transmission cannot be preempted Why Solution serve packets in the order in which they would have finished being transmitted in the fluid flow system Katz Stoica F04 18 Packet System Example 1 Service in fluid flow system 1 3 2 1 4 2 3 5 4 5 6 time ms Select the first packet that finishes in the fluid flow system Packet system 1 2 1 3 2 3 4 4 5 5 6 time Katz Stoica F04 19 Packet System Example 2 Service in fluid flow system 0 2 4 6 8 10 Select the first packet that finishes in the fluid flow system Packet system 0 2 4 6 8 10 Katz Stoica F04 20 Implementation Challenge Need to compute the finish time of a packet in the fluid flow system but the finish time may change as new packets arrive Need to update the finish times of all packets that are in service in the fluid flow system when a new packet arrives But this is very expensive a high speed router may need to handle hundred of thousands of flows Katz Stoica F04 21 Example Four flows each with weight 1 Flow 1 time Flow 2 time Flow 3 time Flow 4 time Finish times computed at time 0 time 0 1 2 3 Finish times re computed at time time 0 1 2 3 4 Katz Stoica F04 22 Solution Virtual Time Key Observation while the finish times of packets may change when a new packet arrives the order in which packets finish doesn t Only the order is important for scheduling Solution instead of the packet finish time maintain the number of rounds needed to send the remaining bits of the packet virtual finishing time Virtual finishing time doesn t change when the packet arrives System virtual time index of the round in the bit by bit round robin scheme Katz Stoica F04 23 System Virtual Time V t Measure service …
View Full Document
Unlocking...