CS 194: Distributed Systems Resource AllocationGoals and ApproachType of ResourcesAllocation ModelsNot in this Lecture…In this Lecture…Two ModelsIntegrated Services ExampleSlide 9Slide 10Slide 11Integrated Services Example: Data PathSlide 13Slide 14Service ClassesHard Real Time: Guaranteed ServicesSoft Real Time: Controlled Load ServiceRole of RSVP in the ArchitectureRSVP Design FeaturesRSVP Basic OperationsRSVP ProtocolPATH and RESV messagesToken Bucket and Arrival CurveHow Is the Token Bucket Used?Traffic Enforcement: ExampleSource Traffic CharacterizationSource Traffic Characterization: ExampleQoS Guarantees: Per-hop ReservationEnd-to-End ReservationWeighted Fair Queueing (WFQ)Fair Rate Computation: Example 1Fair Rate Computation: Example 2Fluid Flow SystemFluid Flow System: Example 1Fluid Flow System: Example 2Implementation In Packet SystemPacket System: Example 1Packet System: Example 2Properties of WFQHierarchical Link Sharing1CS 194: Distributed SystemsResource AllocationScott Shenker and Ion Stoica Computer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Goals and ApproachGoal: achieve “predicable” performance (service)Three steps:1) Estimate application’s resource needs (not in this lecture)2) Admission control3) Resource allocation3Type of ResourcesCPU Storage: memory, diskBandwidthDevices (e.g., vide camera, speakers)Others:-File descriptors-Locks -…4Allocation ModelsShared: multiple applications can share the resource -E.g., CPU, memory, bandwidthNon-shared: only one application can use the resource at a time-E.g., devices5Not in this Lecture…How application determine their resource needsHow users “pay” for resources and how they negotiate resourcesDynamic allocation, i.e., application allocates resources as it needs them6In this Lecture…Focus on bandwidth allocation -CPU similar-Storage allocation usually done in fixed chunksAssume application requests all resources at once7Two ModelsIntegrated Services-Fine grained allocation; per-flow allocationDifferentiated services (not in this lecture)-Coarse grained allocationFlow: a stream of packets between two applications or endpoints8Integrated Services Example SenderReceiverAchieve per-flow bandwidth and delay guarantees-Example: guarantee 1MBps and < 100 ms delay to a flow9Integrated Services Example SenderReceiverPerform per-flow admission control10Integrated Services Example SenderReceiverInstall per-flow state11 SenderReceiverInstall per flow stateIntegrated Services Example12Integrated Services Example: Data Path SenderReceiver Per-flow classification13Integrated Services Example: Data Path SenderReceiver Per-flow buffer management14Integrated Services Example SenderReceiver •Per-flow scheduling15Service ClassesMultiple service classesService: 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)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 routers17Soft 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 possible18Role of RSVP in the ArchitectureSignaling protocol for establishing per flow stateCarry resource requests from hosts to routersCollect needed information from routers to hostsAt each hop-Consult admission control and policy module-Set up admission state or informs the requester of failure19RSVP Design FeaturesIP Multicast centric design (not discussed here…)Receiver initiated reservationSoft state inside network20RSVP Basic OperationsSender: sends PATH message via the data delivery path-Set up the path state each router including the address of previous hopReceiver sends RESV message on the reverse path-Specifies the reservation style, QoS desired-Set up the reservation state at each routerThings to notice-Receiver initiated reservation-Decouple routing from reservation-Two types of state: path and reservation21RSVP Protocol Problem: asymmetric routes-You may reserve resources on RS3S5S4S1S, but data travels on SS1S2S3R !Solution: use PATH to remember direct path from S to R, i.e., perform route pinning S1S1S2S2S3S3SSRRS5S5S4S4PATHRESVIP routing22PATH and RESV messagesPATH also specifies -Source traffic characteristics•Use token bucket-Reservation style – specify whether a RESV message will be forwarded to this serverRESV specifies -Queueing delay and bandwidth requirements -Source traffic characteristics (from PATH)-Filter specification, i.e., what senders can use reservation-Based on these routers perform reservation23Token Bucket and Arrival CurveParameters-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 tokenArrival curve – maximum number of bits transmitted within an interval of time of size tr bpsb bits <= R bpsregulatortimebitsb*R/(R-r)slope Rslope rArrival curve24How 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-host25Traffic Enforcement: Exampler = 100 Kbps; b = 3 Kb; R = 500 Kbps 3KbT = 0 : 1Kb packet arrives(a)2.2KbT = 2ms : packet transmitted b = 3Kb – 1Kb + 2ms*100Kbps = 2.2Kb(b)2.4KbT = 4ms : 3Kb packet arrives(c)3KbT = 10ms : packet needs to wait until enough tokens are in the bucket!(d)0.6KbT = 16ms : packet transmitted(e)26Source Traffic CharacterizationArrival curve – maximum
View Full Document
Unlocking...