DOC PREVIEW
USC CSCI 551 - 13a_clark92a

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS551Integrated ServicesPacket Networks[Clark92a]Bill Chenghttp://merlot.usc.edu/cs551-f121 Computer Communications - CSCI 551 Copyright © William C. ChengguaranteedArchitecture: should allow traffic guarantees2Key Ideas Computer Communications - CSCI 551 Copyright © William C. Chengpredictedbest effortmotivate admission controlAQM strategy: FIFO+Mechanisms:service interface: token bucket defining rate & burstinessbandwidth below which video and audio are not intelligibleSome applications require minimum level of networkperformance3Motivation Computer Communications - CSCI 551 Copyright © William C. ChengSome less elastic applications are not able to adapt tochanges in bandwidth and delayinternet telephones, teleconferencing with high delay(200 - 300ms) impair human interactionThe problemset a playback point in the futurePlayback applications4A Class of Real-time Applications Computer Communications - CSCI 551 Copyright © William C. Chengbuffer packets until playback pointearly packet arrival okFeatures that you can leverageperformance improves with lower delay need absolute or statistical bound on delaytolerate some lossPlaying outPacketsCircular BufferRigid/adaptiveTwo classes of playback applications5Rigid vs. Adaptive Applications Computer Communications - CSCI 551 Copyright © William C. ChengTolerant/intolerantRigid applicationsSet fixed playback point (a priori bound)Adaptive applicationsAdapt playback point (de facto bound)A priori bound > de facto boundthe distinction here is whether the application wouldtolerate interruptionsGamble that network conditions will be the same now as inthe past6Adaptive Applications Computer Communications - CSCI 551 Copyright © William C. ChengAre prepared to deal with errors in their estimateWill in general have an earlier playback point thanrigid applicationsExperience has shown that they can be built(e.g., vat, various adaptive video apps)7Real-time Applications Computer Communications - CSCI 551 Copyright © William C. ChengDelayadaptiveRateadaptiveNon-adaptiveRateadaptiveNon-adaptiveAdaptiveLoss, delaytolerantIntolerantReal-Time Applicationstype of service the network providesCommitments made by network8Architectural Components Computer Communications - CSCI 551 Copyright © William C. Chengcharacterization of source trafficService interfacealgorithms, information in headersPacket schedulingpolicingAdmission controlcharacterization of QoS network will deliverFor intolerant and rigid applicationsApplications gamble, why not the network?Guaranteed service9Types of Network Service Commitments Computer Communications - CSCI 551 Copyright © William C. ChengFor tolerant and adaptive applicationsPredicted serviceIf conditions do not change, commit to current serviceTwo components:If conditions change, take steps to deliver consistentperformance (help apps set playback point byminimizing post facto delay bounds)Tspec: describes the flow’s traffic characteristics10Service Interface: Flowspecs Computer Communications - CSCI 551 Copyright © William C. ChengRspec: describes the service requested from the networktoken rate r: rate of tokens placed in the bucketDescribed by 2 parameters:11Token Bucket Filter Computer Communications - CSCI 551 Copyright © William C. Chengbucket depth B: capacity of the bucket tokens are placed in bucket at rate rOperation:if bucket fills, tokens are discardedsending a packet of size P uses P tokensif bucket has P tokens, packet sent at max rate, else mustwait for tokens to accumulate12Token Bucket Operation Computer Communications - CSCI 551 Copyright © William C. ChengtokensoverflowEnough tokenspacket goesthrough, tokensremovedNot enoughtokens - waitfor tokens toaccumulatetokens tokensPacket Packettraffic = B + r × TIn the long run, rate is limited to r13Token Bucket Characteristics Computer Communications - CSCI 551 Copyright © William C. ChengIn the short run, a burst of size B can be sentAmount of traffic entering at interval T is bounded by:Information useful to admission algorithm14Token Bucket Specs Computer Communications - CSCI 551 Copyright © William C. ChengFlow A: r = 1 MBps, B=1 byteFlow B: r = 1 MBps, B=1MBtokens accumulating hereBW1 2 312Flow ATimeFlow BExample:delay pkts from entering net (shaping)network drops pkts without tokens in time of congestionShaping, policing, marking15Possible Token Bucket Uses Computer Communications - CSCI 551 Copyright © William C. Chengdrop pkts that arrive without tokens (policing)let all pkts pass through, mark ones without tokensgets a rate r at every router in networkSuppose a flow16Guarantee Proven by Parekh Computer Communications - CSCI 551 Copyright © William C. Chengand all routers in network do WFQ... and the corresponding token bucket burst size is bCumulative queuing delay Di suffered by flow i has upperbound b/rThen, in any arbitrary topologyeven if the switch is shared with unshaped flowsAdditional terms to the delay bound with a packetapproximationThis result holds for a fluid flow approximationImagine flow i shaped with token bucket,Intuition:... then all delay is incurred at entrance to networkDelays can be high unless one reserves a rate r which ishigher than the average rateUse token bucket filter to characterize traffic17Scheduling Guaranteed Traffic Computer Communications - CSCI 551 Copyright © William C. ChengUse WFQ at the routersParekh’s bound for worst case delayUse token bucket filter to characterize trafficNetwork can then be significantly underutilizedProvides isolation, but the delay is not sharedbut jitter can increase in a multi-hop caseWFQ not suitable18Predicted Service Computer Communications - CSCI 551 Copyright © William C. Cheng... and can self-impose jitter in post facto delayFIFO with multiple priority levels might workAt each hop: measure average delay for class at that routerSo, use FIFO+ for multi-hop sharingFor each packet: compute difference of average delayand delay of that packet in queueAdd/subtract difference in packet headerFIFO+ has characteristics similar toerror diffusion in computer graphics19FIFO+ And Error Diffusion Computer Communications - CSCI 551 Copyright © William C. ChengOriginal pixel value is an intensity valuebetween 0 (black) and 1 (white)Represent the picture in pure black andwhitethresholding -- e.g., replace value by1 if intensity ≥ 0.5 and replace valueby 0 if intensity < 0.5error diffusion -- start withthresholding, carry error into the nextpixelerror


View Full Document

USC CSCI 551 - 13a_clark92a

Download 13a_clark92a
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 13a_clark92a and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 13a_clark92a 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?