CS 414 – Multimedia Systems Design Lecture 16 – Multimedia Transport (Part 2)AdministrativeOutlineQoS Enforcement – Traffic ShapingPurpose of Traffic ShapingExampleFlow’s Traffic Shape Parameters (Network QoS)Source ClassificationBandwidth AllocationIsochronous Traffic Shaping (Simple Leaky Bucket Traffic Shaper)ExampleIsochronous Traffic Shaping (r,T)-smooth Traffic Shaper(r,T) Traffic ShaperComparisonLimitations of Isochronous Traffic ShapingIsochronous Traffic Shaping with PrioritiesShaping Bursty Traffic Patterns (Token Bucket)Token BucketComparison between TB and LBToken Bucket LimitationToken Bucket with Leaky Bucket Rate ControlComposite ShaperSlide 23ConclusionCS 414 - Spring 2011CS 414 – Multimedia Systems Design Lecture 16 – Multimedia Transport (Part 2)Klara NahrstedtSpring 2011CS 414 - Spring 2011Administrative HW1: due on Wednesday, March 2Midterm review session: Friday, March 4, in classMidterm: Monday March 7, in classClass canceled on Friday, March 11 due to EOHAndroid TutorialMar 1st, 7 – 8:30 pm, 2405Mar 8th, 8 – 9:30 pm, 2405OutlineData Streaming/Transmission PhaseTraffic Shaping Isochronous Traffic Shaping Shaping Bursty Traffic Rate Control Error Control CS 414 - Spring 2011QoS Enforcement – Traffic ShapingIn Packet Network, admission control, reservation is not sufficient to provide QoS guaranteesNeed traffic shaping at the entry to network and within networkTraffic shaping Decides how packets will be sent into the network , hence regulates trafficDecides whether to accept a flow’s dataPolices flowsCS 414 - Spring 2011Purpose of Traffic Shaping Traffic shapeA way of a flow to describe its traffic to the network Based on traffic shape, network manager (s) can determine if flow should be admitted into the network Given traffic shape, network manager(s) can periodically monitor flow’s traffic CS 414 - Spring 2011ExampleIf we want to transmit data of 100 Mbps, Traffic Shape A: Do we take 1 packet size of size 100 Mbit and send it once a second, or Traffic Shape B: Do we take 1 packet of size 1 Kbit and send it every 10 microseconds?CS 414 - Spring 20111 Mbit1 MbitKth second K+1 th secondABFlow’s Traffic Shape Parameters (Network QoS)Traffic Envelope Peak rateAverage rateBurst lengthBurst durationService EnvelopeMaximum tolerable delayDesired delay jitterothersCS 414 - Spring 2011Source ClassificationClassification of sources : Data – bursty, weakly periodic, strongly regular Audio – continuous, strong periodic, strong regular Video – continuous, bursty due to compression, strong periodic, weakly regular Classification of sources into two classes:Constant Bit Rate (CBR) – audio Variable Bit rate (VBR) – video, dataCS 414 - Spring 2011Bandwidth Allocation CBR traffic (shape defined by peak rate)CBR source needs peak rate allocation of bandwidth for congestion-free transmissionVBR traffic (shape defined by average and peak rate) average rate can be small fraction of peak rate underutilization of resources can occur if pessimistic allocation (peak rate allocation) is appliedLosses can occur if optimistic allocation (average rate allocation) is appliedCS 414 - Spring 2011Isochronous Traffic Shaping(Simple Leaky Bucket Traffic Shaper) CS 414 - Spring 2011Developed by Jon Turner, 1986 (Washington University, St. Louis)Example Consider for audio flow, size of the bucket β = 16 Kbytes Packet size = 1 Kbytes (one can accumulate burst up to 16 packets in the bucket) Regulator’s rate ρ = 8 packets per second, or 8KBps or 64Kbps Consider video flow, size of bucket β = 400 KbytesPacket size = 40 Kbytes (burst of 10 packets)Regulator’s rate ρ = 5 packets per second, 200 KBps, 1600KbpsCS 414 - Spring 2011Isochronous Traffic Shaping (r,T)-smooth Traffic Shaper Developed by Golestani, 1990Part of stop-and-go queuing/scheduling algorithmTraffic divided into T-bits frames, where T is fixed r-bits packet size per flow is considered, where r varies on a per flow basisCS 414 - Spring 2011(r,T) Traffic ShaperCS 414 - Spring 2011Time lineT-bits frames, sent every T-bit timesr-bits packets• Flow is permitted to inject no more than r bits of data into the network frame in any T bit times• if the sender wants to send more than one packet of r-bits, it must wait for next T-bit frame.• A flow that obeys this rule has (r,T)-smooth traffic shape. r ≤ TComparison •It is relaxed from the simple leaky bucket traffic shaper because•Rather than sending one packet of size c every 1/ρ time units, (in simple leaky bucket )•The flow can send c*k bits every 1/ρ time units , where k is T-bits times within the period 1/ρCS 414 - Spring 20111/ρK=2Limitations of Isochronous Traffic ShapingIn case of (r,T)-smooth traffic shaping, one cannot send packet larger than r bits long, i.e., unless T is very long, the maximum packet size may be very small. The range of behaviors is limited to fixed rate flowsVariable flows must request data rate equal to peak rate which is wasteful CS 414 - Spring 2011Isochronous Traffic Shaping with PrioritiesIdea: if a flow exceeds its rate, excess packets are given lower priorityIf network is heavily loaded, packets will be preferentially droppedDecision place to assign priorityAt the senderApplication marks its own packets since application knows best which packets are less important In the network (policing)Network marks overflow packets with lower priorityCS 414 - Spring 2011Shaping Bursty Traffic Patterns (Token Bucket)CS 414 - Spring 2011Token BucketThe effect of TB is different than Leaky Bucket (LB)Consider sending packet of size b tokens (b<β): Token bucket is full – packet is sent and b tokens are removed from bucketToken bucket is empty – packet must wait until b tokens drip into bucket, at which time it is sentBucket is partially full – let’s consider B tokens in bucket; if b ≤ B then packet is sent immediately, Else wait for remaining b-B tokens before being sent. CS 414 - Spring 2011Comparison between TB and LBToken Bucket Simple Leaky BucketTB permits burstiness, but bounds it LB forces bursty traffic to smooth outBurstiness is bounded as follows:- Flow never sends more than β+τ*ρ tokens worth of data in interval τ and - Long-term transmission
View Full Document