Transcript PPT

CS 414 – Multimedia Systems Design
Lecture 18 –
Multimedia Transport
Subsystem (Part 3)
Klara Nahrstedt
Spring 2012
CS 414 - Spring 2012
Administrative

HW1 due March 1
Midterm: MONDAY, March 5, 11-11:50 in class
 Midterm: 1 side of cheat-sheet + calculator
 Midterm Material:

 MP1
Question(s) (see TA’s lecture on MP1)
 until Friday, February 24, Lectures 1-16
 Multimedia Coding and Content Processing Book
 Chapter 2, 3, 5, 7
 Multimedia Systems Book
 Chapter 2
CS 414 - Spring 2012
Covered Aspects of Multimedia
Image/Video
Capture
Audio/Video
Perception/
Playback
Audio/Video
Presentation
Playback
Image/Video Information
Representation
Transmission
Audio
Capture
Transmission
Compression
Processing
Audio Information
Representation
Media
Server
Storage
A/V
Playback
Multimedia Transmission Networks
CS 414 - Spring 2012
What we will talk today

Establishment Phase



Negotiation, Translation
Admission, Reservation
Transmission Phase

Traffic Shaping
 Stream Shapes – Strongly/Weakly Regular, Strongly/Weakly
Periodic, Asynchronous, Synchronous, Isochronous Streams
 Isochronous Traffic Shaping – Leaky Bucket
 Shaping Bursty Traffic – Token Bucket
 Rate
Control
 Error Control
CS 414 - Spring 2012
CLASSIFICATION, MARKING
AND TRAFFIC SHAPING
CS 414 - Spring 2012
Limitations of Isochronous
Traffic Shaping
In 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 flows
 Variable flows must request data rate
equal to peak rate which is wasteful

CS 414 - Spring 2012
Isochronous Traffic Shaping
with Priorities



Idea: if a flow exceeds its rate, excess packets
are given lower priority
If network is heavily loaded, packets will be
preferentially dropped
Decision place to assign priority
 At

 In

the sender – Classification and Marking
Application classifies and marks its own packets since
application knows best which packets are less important
the network (policing)
Network marks overflow packets with lower priority
CS 414 - Spring 2012
Shaping Bursty Traffic Patterns (Token
Bucket)
CS 414 - Spring 2012
Token Bucket


The effect of TB is different than Leaky Bucket
(LB)
Consider sending packet of size b tokens (b<β):
bucket is full – packet is sent and b tokens are
removed from bucket
 Token bucket is empty – packet must wait until b
tokens drip into bucket, at which time it is sent
 Bucket is partially full – let’s consider B tokens in
bucket;
 Token


if b ≤ B then packet is sent immediately,
Else wait for remaining b-B tokens before being sent.
CS 414 - Spring 2012
Comparison between TB and LB
Token Bucket
Simple Leaky Bucket
TB permits burstiness, but bounds it
LB forces bursty traffic to smooth out
Burstiness is bounded as follows:
- Flow never sends more than β+τ*ρ
tokens worth of data in interval τ and
- Long-term transmission rate will not
exceed ρ
Flow never sends faster than ρ worth of
packets per second
TB does not have discard or priority
policy
LB has priority policy
TB more flexible
LB is rigid
TB is easy to implement
-Each flow needs counter to count
tokens,
- each flow needs timer to determine
when to add new tokens to the counter
LB is easy to implement
CS 414 - Spring 2012
Token Bucket Limitation

Difficulty with policing
 At
any time the flow is allowed to exceed rate by
number of tokens

Reasoning
any period of time, flow is allowed to exceed rate ρ
by β tokens
 If network tries to police flows by simply measuring their
traffic over intervals of length τ, flow can cheat by
sending β+τ*ρ tokens of data in every interval.
 Flow can send data equal to 2β+2τ*ρ tokens in the
interval 2τ and it is supposed to send at most β+2τ*ρ
tokens worth of data
 At
CS 414 - Spring 2012
Token Bucket with Leaky
Bucket Rate Control
TB allows for long bursts and if the bursts
are of high-priority traffic, they may
interfere with other high-priority traffic
 Need to limit how long a token bucket
sender can monopolize network

CS 414 - Spring 2012
Composite Shaper
CS 414 - Spring 2012
Composite Shaper
Combination of token bucket with leaky
bucket
 Good policing

 But
remains hard, although confirming that
the flow’s data rate does not exceed C is easy

More complexity for implementation
 Each
flow requires two counters and two
timers (one timer and one counter for each
bucket)
CS 414 - Spring 2012
QUEUING
CS 414 - Spring 2012
Queuing and Queue Management



Every traffic management needs QUEUE
MANAGEMENT (QM)
Statistical versus Deterministic Guarantees
Conservation of Work
 QM
schemes differentiate if they are work conserving or
not
 Work conserving system – sends packet once the
server has completed service (examples – FIFO, LIFO)
 Non-work conserving scheme – server waits random
amount of time before serving the next packet in queue,
even if packets are waiting in the queue
CS 414 - Spring 2012
Rate Control

Multimedia networks use rate-based
mechanisms (conventional networks use
window-based flow control and FIFO)
Work-conserving schemes
Non-work-conserving schemes
Fair Queuing
Jitter Earliest-Due-Date
Virtual Clock
Stop-and-Go
Delay Earliest-Due-Data
Hierarchical Round-Robin
CS 414 - Spring 2012
Earliest Due Date (EDD) [Ferrari]
Based on Earliest Deadline First
Scheduling Policy
 EDD works for periodic message models

 Packet

has end-to-end deadline Di
EDD partitions end-to-end deadline Di into
local deadlines Di,k during connection
establishment procedure
CS 414 - Spring 2012
Delay EDD

Upon arrival of Packet j of connection i:
 Determine

aei,j = max(aei,j-1 + pi, ai,j)
 Stamp

effective arrival time:
packet with local deadline:
di,j = aei,j + Di,k
 Process
packets in EDF order
Delay EDD is greedy
 Problem with EDD: jitter

CS 414 - Spring 2012
Weighted Fair Queuing
CS 414 - Spring 2012
Weighted Fair Queuing
CS 414 - Spring 2012
WFQ vs FQ


Both in WFQ and FQ, each data flow has a separate FIFO
queue.
In FQ, with a link data rate of R, at any given time the N
active data flows (the ones with non-empty queues) are
serviced simultaneously, each at an average data rate of
R / N.


Since each data flow has its own queue, an ill-behaved flow (who has
sent larger packets or more packets per second than the others since
it became active) will only punish itself and not other sessions.
WFQ allows different sessions to have different service
shares. If N data flows currently are active, with weights
w1,w2...wN, data flow number i will achieve an average data
rate of R * wi/(w1+w2+…+wn)
CS 414 - Spring 2012
Class-based WFQ
PQ – Priority Queue
CS 414 - Spring 2012
Comparison between WFQ and
Jitter Control


WFQ guarantees packet delay less than a given
value D, but as long as delay is within bound it
does not guarantee what the delay will be
Example: send packet at time t0 over a path
whose minimum delay is d
 WFQ
guarantees that packet arrives no later than
t0+d, but packets can arrive any time t0+ x between
[t0+d, t0+D] .
 x is jitter
CS 414 - Spring 2012
Jitter Control Non-WorkConserving Schemes
CS 414 - Spring 2012
Implementation of Stop-and-Go
CS 414 - Spring 2012
Jitter-EDD





Delay-EDD: does not control jitter. This has effect on buffer
requirements.
Jitter-EDD is non-greedy.
Jitter-EDD maintains Ahead Time ahi,j, which is the difference
between local relative deadline Di,k-1 and actual delay at
switch k-1.
Ahead time is stored in packet header
Upon receiving j-th packet of connection i with ahi,j at time ai,j:

Calculate ready time at switch k:



aei,j=max(aei,j-1 + pi , ai,j)
ri,j = max(ae i,j , ai,j + ahi,j)
Stamp packet with deadline di,j=ri,j+Di,k and process according to EDF
starting from ready time ri,j.
CS 414 - Spring 2012
ERROR CONTROL:
AVOIDANCE, DETECTION,
CORRECTION
CS 414 - Spring 2012
Congestion Avoidance via Random Early Drop
(Active Queue Management)
RED = Random Early
Drop
Refined RED based on
IP packet preference is
Weighted RED (WRED)
Error Detection

Ability to detect the presence of errors
caused by noise or other impairments during
transmission from sender to receiver
 Traditional
mechanisms: check-summing, PDU
sequencing


Checksum of a message is an arithmetic sum of message code words
of a certain word length (e.g., byte)
CRC – Cyclic Redundancy Check – function that takes as input a data
stream of any length and produces as output a value (commonly a 32bit integer) – can be used as a checksum to detect accidental alteration
of data during transmission or storage
 Multimedia
mechanisms: byte error detection at
application PDU, time detection
Design of Error Correction Codes

Automatic repeat-request (ARQ)
 Transmitter
sends the data and also an error
detection code, which the receiver uses to check for
errors, and requests retransmission for erroneous
data
 The receiver sends ACK (acknowledgement of
correctly received data)

Forward Error Correction (FEC)
 Transmitted
encodes the data with an error-correcting
code (ECC) and sends the coded msg. No ACK
exists.
CS 414 - Spring 2012
Error Control

Error Correction
 Traditional
mechanisms: retransmission using
acknowledgement schemes, window-based flow
control
 Multimedia mechanisms:
Go-back-N Retransmission
 Selective retransmission
 Partially reliable streams
 Forward error correction
 Priority channel coding
 Slack Automatic Repeat Request

CS 414 - Spring 2012
Go-back-N Retransmission
CS 414 - Spring 2012
Jitter Control in Slack Automatic
Repeat Request Scheme
CS 414 - Spring 2012
Conclusion

Establishment Phase
 Negotiation,
Translation
 Admission, Reservation

Transmission Phase
 Traffic


Shaping
Isochronous Traffic Shaping
Shaping Bursty Traffic
 Rate
Control
 Error Control

Next: Case Studies of Multimedia Protocols
CS 414 - Spring 2012