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