EE 122: Quality of Service and Resource AllocationIon StoicaNovember 6, [email protected] 2Limitations of IP Architecture in Supporting Resource ManagementIP provides only best effort serviceIP does not participate in resource management- Cannot provide service guarantees on a per flow basis- Cannot provide service differentiation among traffic aggregatesEarly efforts- Tenet group at Berkeley (Ferrari and Verma)- Asynchronous Transfer Mode (ATM) IETF (Internet Engineering Task Force) efforts - Integrated services initiative- Differentiated services [email protected] 3Service ClassesMultiple service classesService can be viewed as a contract between network and communication client- End-to-end service (multicast and anycast)- Other service scopes possible, e.g.,• Aggregates – all packets between to points (not necessary end-hosts) in the InternetThree common services- Best-effort (“elastic” applications)- Hard real-time (“real-time” applications)- Soft real-time (“tolerant” applications)[email protected] 4Example: Integrated ServicesEnhance IP’s service model- Old model: single best-effort service class- New model: multiple service classes, including best-effort and QoS classesCreate protocols and algorithms to support new service models- Old model: no resource management at IP level- New model: explicit resource management at IP levelKey architecture difference- Old model: stateless - New model: per flow state maintained at routers• Used for admission control and scheduling• Set up by signaling [email protected] 5QoS Network Flow or session as QoS abstractionsEach flow has a fixed or stable pathRouters along the path maintain the state of the [email protected] 6QoS Network OperationsControl plane: admission control- Reserve resources (i.e., link capacity and buffer space) at every router along the pathData plane: perform per flow- Classification: classify each packet to the flow it belongs to- Buffer management: decide when and which packet to drop- Packet scheduling: decide when and which packet to [email protected] 7Control Plane: Admission ControlSenderReceiverExample: achieve per-flow bandwidth and delay guarantees- Example: guarantee 1MBps and < 100 ms delay to a [email protected] 8Control Plane: Admission ControlSenderReceiverAllocate resources - perform per-flow admission [email protected] 9Control Plane: Admission ControlSenderReceiverInstall per-flow [email protected] 10SenderReceiverInstall per flow stateControl Plane: Admission [email protected] 11Data PlaneSenderReceiverPer-flow [email protected] 12Data PlaneSenderReceiverPer-flow buffer [email protected] 13Data PlaneSenderReceiver• Per-flow [email protected] 14Service ClassesMultiple service classesService can be viewed as a contract between network and communication client- End-to-end service- Other service scopes possibleThree common services- Best-effort (“elastic” applications)- Hard real-time (“real-time” applications)- Soft real-time (“tolerant” applications)[email protected] 15Service SpecificationLoss: probability that a flow’s packet is lostDelay: time it takes a packet’s flow to get from source to destinationDelay jitter: maximum difference between the delays experienced by two packets of the flowBandwidth: maximum rate at which the soourcecan send [email protected] 16Hard Real Time: Guaranteed ServicesService contract- Network to client: guarantee a deterministic upper bound on delay for each packet in a session - Client to network: the session does not send more than it specifiesAlgorithm support- Admission control based on worst-case analysis- Per flow classification/scheduling at [email protected] 17Soft Real Time: Controlled Load ServiceService contract:- Network to client: similar performance as an unloaded best-effort network- Client to network: the session does not send more than it specifiesAlgorithm Support- Admission control based on measurement of aggregates- Scheduling for aggregate [email protected] 18Traffic and Service CharacterizationTo quantify a service one has two know- Flow’s traffic arrival- Service provided by the router, i.e., resources reserved at each routerExamples:- Traffic characterization: token bucket- Service provided by router: fix rate and fix buffer [email protected] 19Token BucketCharacterized by three parameters (b, r, R)- b – token depth- r – average arrival rate- R – maximum arrival rate (e.g., R link capacity)A bit is transmitted only when there is an available token- When a bit is transmitted exactly one token is consumedr tokens per secondb tokens<= R bpsregulatortimebitsb*R/(R-r)slope Rslope [email protected] 20Characterizing a Source by Token BucketArrival curve – maximum amount of bits transmitted by time tUse token bucket to bound the arrival curvetimebitsArrival [email protected] 21ExampleArrival curve – maximum amount of bits transmitted by time tUse token bucket to bound the arrival curvesize of timeintervalbitsArrival curvetimebps01 2 3 4 5121 2 3 4 51234(b=1,r=1,R=2)[email protected] 22Per-hop ReservationGiven b,r,R and per-hop delay dAllocate bandwidth raand buffer space Basuch that to guarantee dbitsbslope rArrival curvedBaslope [email protected] 23End-to-End ReservationSource S sends a message containing traffic characteristics- r,b,R- This message is used to computes the number of hopsReceiver R sends back this information + worst-case delay (D)Each router along path provide a per-hop delay guarantee and forwards the message - In simplest case routers split the delay DS1S1S2S2S3S3SSRR(b,r,R)(b,r,R,3) num hops(b,r,R,2,D-d1)(b,r,R,1,D-d1-d2)(b,r,R,0,0)(b,r,R,3,D) worst-case [email protected] 24SummaryService: a contract between end-hosts and networkQoS goal: provide better than best-effort services to support new applications with more stringent delay and bandwidth requirements, e.g., IP telephony, videoconferencingQoS requires to manage flows/aggregates both on data and control planeTwo major proposals:- Integrated Services - Differentiated
View Full Document