Quality of ServiceAnnouncementsDistributed Multimedia SystemConsider End-to-End BehaviorBasic ChallengesPreliminariesReal Time (RT) ProcessDeadlinesCharacteristics of RT SystemsRT & MultimediaResourceResource ManagementSlide 13Resource ReservationResource AllocationQuality of Service (QoS)Layers of QoSSlide 18User and Application QoSSystem QoSNetwork QoSTypes of ServicesLinear Bounded Arrival ProcessLBAPWorkloadGraph of w(t)Logical Arrival Time (L)Logical Delay Between InterfacesResources and SessionsCompound SessionDelay and Buffer SizeQoS SpecificationTake Home ExerciseQuality of ServiceKarrie KarahaliosSpring 2007Announcements•Midterm•Final ProjectsDistributed Multimedia SystemDiskNetwork CPUNetworkApplicationServer ClientProcessDeviceSteps:Resources:Guarantees:Consider End-to-End BehaviorNetworkMemoryDisk CPUAppsOperating SystemNetwork MemoryDisk CPUOperating SystemMM apps Apps MM appsMeta-scheduler attempts to reserve resourcesto guarantee end-to-end behaviorBasic Challenges•Identification•Negotiation•Translation•Specification•EnforcementPreliminaries•Real-time systems•Resources•Management•Reservation•AllocationReal Time (RT) Process•Delivers results in predictable time–not necessarily fast–requests deterministic or stochastic•Correctness means–errorless computation–meeting deadlinesDeadlines•Hard deadlines–cannot be violated (if so, system fault)–cost money or human life•Soft deadlines–misses can be tolerated if–not too many and not missed by much•ExamplesCharacteristics of RT Systems•Predictable response times to time-critical events•Accurate system clocks and timing•Able to schedule almost all resources•Stability under overloadRT & Multimedia•To meet demands of multimedia, use RT techniques along entire data path•Relative to RT–relaxes deadline requirements and allows some deadlines to be missed entirely–periodic requests ease scheduling–continuous data allows adaptive allocationResource•Required by tasks for manipulating data–CPU, disk, memory, network, etc.•A resource has a capacity–space, utilization, bandwidth•A resource can be:–active or passive–exclusive or sharedResource Management•Maps multimedia requirements onto respective capacities of the system•Specified through a QOS model–parameters + relaxation procedures•Carried out by a resource manager–ensure adherence to QoS specificationResource ManagementTimeAudioMpeg-1Mpeg-2InteractiveVideoAbundantSufficient, but stressedInsufficientResource NeedsResource Reservation•Test schedulability–determine if enough remaining capacity•Negotiate QOS parameters–If not, determine how close it can come and when –application decides if this is acceptable•Reserve resources–allocates resources to meet negotiated QoS•Schedule resources–compute appropriate schedule for each resource–algorithm affects previous stepsResource Allocation•Pessimistic–reserve for the worst case–worse utilization, but more guarantees•Optimistic–reserve for average or minimum needs–better utilization, but less guaranteesQuality of Service (QoS)•Refers to how good provided services are–the more applications demand, the more difficult it is to meet those demands•Resource management realizes QoS–better management allow better QoS•ExamplesLayers of QoSUserApplicationSystemMM devices Networkuser QoSapplication QoSsystem QoSnetwork QoSdevice QoSLayers of QoSWhat are the right metrics?How to specify them?How to negotiate them?UserApplicationSystemMM devices Networkuser QoSapplication QoSsystem QoSnetwork QoSdevice QoSHow to enforce them?How to translate among them?User and Application QoS•Startup time•Sample rate•Bits per sample•Frame rate•Resolution•Skew relationships•Response time for interactionSystem QoSQuantitative•Bit rate•Error rate•Processing time•Buffer sizes•ThroughputQualitative•Ordered delivery •Error recovery•Scheduling optionsNetwork QoS•Network load –[min, avg, max] arrival times•Packet/cell size•Packet loss rate•End-to-end delay (latency)•Variability in delay (jitter)Types of Services•Guaranteed–threshold or range–deterministic or statistical•Predictive–match current to historical performance•Best Effort–none or only minimal guaranteesLinear Bounded Arrival Process•Divides end-to-end system view into a pipeline of discrete sessions–one session corresponds to a single resource•Defines parameterization of workload–arrival of messages at a particular interface•A message is one unit of work–typically blocks of CM data (bytes or time)Anderson, D. Metascheduling for Continuous Media, ACM TOCS, 11(3): 226-252LBAP•Models message arrival at a resource (I)–M - max message size (bytes)–R - max message rate (messages/second)–W – workload limit (max. messages that may arrive ahead of schedule)•Such that for all t0 < t1NI(t0, t1) < R|t1 – t0| + WWorkload•Workload W(t) of an LBAP at time t isw(t) = max{0, NI(t0, t) - R|t – t0| }•Property 1:w(t) < W for all t•Property 2:for all t1 < t2; NI(t1, t2) < w(t2) – w(t1) + R|t2 – t1|Graph of w(t)Logical Arrival Time (L)•Let m0…mn denote sequence of messages and let a0…an be their arrival timesL(m0) = a0L(mi+1)=max{ai+1, L(mi) + 1/R}Logical Delay Between Interfaces•Logical delay d(m) of message m between two interfaces is d(m) = L2(m) - L1(m), where Li(m) isarrival time of m at interface i.•Actual delay of message m may be> L(m), if m arrives ahead of schedule at I1< L(m), if m completed ahead of schedule at I2Resources and Sessions•A resource handles incoming messages–arrive at input interface, delivered to output interface•Clients must reserve resource–M (max message size)–R (max message rate)–Win = input max message burst (messages)–Wout = output max message burst (messages)–D = max logical delay (seconds),–A = min actual delay (seconds),–U = min unbuffered time (seconds)•Arrival process at input interface specified by M, R, Win•Arrival process at output interface specified by M, R, WoutCompound Session•S is a sequence of sessions S1…SN –input of S is that of S1; output is that of SN–output of Si is input to Si+1Delay and Buffer Size•d(m) = LSN(m) – LS1(m) < sum(di)•Maximum shared buffer size for SW + R(D – U), D = sum(di); W = w(t) for S1–realized when there is group of W messages followed by one message every 1/R and each resource uses its
View Full Document
Unlocking...