Transcript Chapter 7

School of Computing Science
Simon Fraser University
CMPT 820: Multimedia Systems
Introduction
Instructor: Dr. Mohamed Hefeeda
1
Course Objectives
 Understand fundamentals of networked multimedia
systems
 Know current research issues in multimedia
 Develop research skills
2
Course Info
 Course web page
http://nsl.cs.sfu.ca/teaching/10/820/
 References





[SC07] Schaar and Chou (editors), Multimedia over IP and
Wireless Networks: Compression, Networking, and
Systems, Elsevier, 2007
[Burg09] Burg, The Science of Digital Media, Prentice
Hall, 2009
[KR08] Kurose and Rose, Computer Networking: A topdown Approach Featuring the Internet, 4th edition,
Addison Wesley, 2008
[LD04] Li and Drew, Fundamentals of Multimedia, Prentice
Hall, 2004
Complemented by research papers
3
Course Info: Grading
 Class participation and Assignments: 50%
 Few assignments and quizzes
 Present one chapter/paper (important)
 Read all Mandatory Reading and participate in discussion
 Final Project:
50%
 New Research Idea (publishable  A+)
 Implementation and evaluation of an already-published
algorithm/technique/system (Good demo  A+)
 Quantitative comparisons between two already-published
algorithms/techniques/systems.
 A survey of a multimedia topic
 …
 Check wiki page for suggestions
4
Course Info: Topics
 Introduction
 Overview of the big picture
 QoS Requirements for Multimedia Systems
 QoS in the Network
 Principles
 DiffServ and IntServ
 Multimedia Protocols
 RTP, RTSP, RTCP, SIP, …
 Image Representation and Compression
 Sampling, quantization, DCT, compression
 Color Models
 RGB, CMY, YIQ
5
Course Info: Topics
 Video Coding
 Compression methods
 MPEG compression
 Scalable video coding
 Error Control for Video Coding and Transmission
 Tools for error resilient video coding
 Error concealment
 Internet Characteristics and Impact on Multimedia
 Channel modeling
 Internet measurement study
 Multimedia Streaming
 Fundamentals
 On-demand streaming and live broadcast
6
Course Info: Topics
 Network-adaptive media transport
 Rate-distortion optimized streaming
 Wireless Multimedia

WLANs and QoS

Cross-layer design

QoS Support in mobile operating systems
7
Introduction
 Motivations
 Definitions
 QoS Specifications & Requirements
8
Definitions and Motivations
 “Multimedia” is an overused term
 Means different things to different people
 Because it touches many disciplines/industries
• Computer Science/Engineering
• Telecommunications Industry
• TV and Radio Broadcasting Industry
• Consumer Electronics Industry
• ….
 For users
 Multimedia = multiple forms/representation of
information (text, audio, video, …)
9
Definitions and Motivations
 Why should we study/research multimedia topics?
 Huge interest and opportunities
 High speed Networks
 Powerful (cheap) computers (desktops … cell phones)
 Abundance of multimedia capturing devices (cameras,
speakers, …)
 Tremendous demand from users (mm content makes life
easier, more productive, and more fun)

Here are some statistics …
10
Some video statistics
 Growth of various video traffic [Cisco 2008]
 Video traffic accounted for 32% of Internet traffic in
2008 and is estimated to account for 50% in 2012
14000
12000
10000
Internet Video to PC
8000
Internet Video to TV
6000
Non-Internet Consumer
Video
4000
2000
0
2006 2007 2008 2009 2010

2011
2012
Y-axis in Petabytes (1000 Terabytes) per month.
11
Some video statistics
 YouTube: fastest growing Internet server in history
 Serves about 300—400 million downloads per day
 Has 40 million videos
 Adds 120,000 new videos (uploads) per day
 CBS streamed the NCAA March Madness basketball
games in 2007 online


Had more than 200,000 concurrent clients
And at peak time there were 150,000 Waiting
 AOL streamed 8 live concerts online in 2006
 There were 180,000 clients at peak time
 Plus …
 All major web sites have multimedia
clips/demos/news/broadcasts/…
12
Definitions and Motivations
 Given all of this, are users satisfied?
 Not Really!
 We still get tiny windows for video
 Low quality
 Glitches, rebuffering
 Limited scalability (same video clip on PDA and desktop)
 Server/network outages (capacity limitations)
 Users want high-quality multimedia, anywhere,
anytime, on any device!
 We (researchers) still strive to achieve this vision
in the future!
13
Multimedia:The Big Picture [SN04]
14
QoS in Networked Multimedia Systems
 Quality of Service = “well-defined and
controllable behavior of a system according to
quantitatively measurable parameters”
 There are multiple entities in a networked
multimedia system



User
Network
Local system (memory, processor, file system, …)
15
QoS in Networked Multimedia Systems
 Different parameters belong to different
entities  QoS Layers
16
QoS Layers
Perceptual
(e.g., window size, security)
User
Application
Media Quality
(e.g., frame rate, adaptation
rules)
System
Local Devices
Processing
(e.g., CPU scheduling, memory,
hard drive)
Network
Traffic
(e.g., bit rate, loss,
delay, jitter)
17
QoS Layers
 QoS Specification Languages
 Mostly application specific
 XML based
 See: Jin & Nahrstedt, QoS Specification Languages for
Distributed Multimedia Applications: A Survey and
Taxonomy, IEEE MultiMedia, 11(3), July 2004
 QoS mapping between layers
 Map user requirements to Network and Device
requirements
 Some (but not all) aspects can be automated
 For others, use profiles and rule-of-thumb experience
 Several frameworks have been proposed in the literature
 See: Nahrstedt et al., Distributed QoS Compilation and
Runtime Instantiation, IWQoS 2000
18
QoS Layers
 QoS enforcement methods
 The most important/challenging aspect
 How do we make the network and local devices implement
the QoS requirements of MM applications?
 We will study (briefly)
 Enforcing QoS in the Network (models/protocols)
 Enforcing QoS in the Processor (CPU scheduling for MM)
 When we combine them, we get end-to-end QoS
 Notice:
 This is enforcing application requirements, if the
resources are available
 If not enough resources, we have to adapt (or scale) the
MM content (e.g., use smaller resolution, frame rate,
drop a layer, etc)
19
QoS Support in IP Networks
 Principles
 IntServ
 DiffServ
 Multimedia Protocols
 Reading: Ch. 7 in [KR08]
20
QoS in IP Networks: Two Models
 Guaranteed QoS
 Need to reserve resources
 Statistical (or Differential) QoS
 Multiple traffic classes with different priorities
 In both models, network devices (routers) should be
able to perform certain functions (in addition to
forwarding data packets)
21
Principles for QoS Guarantees
 Let us explore these functions using a simple example
 1Mbps IP phone, FTP share 1.5 Mbps link.
 bursts of FTP can congest router, cause audio loss
 want to give priority to audio over FTP
Principle 1
packet marking needed for router to distinguish
between different classes; and new router policy
to treat packets accordingly
22
Principles for QoS Guarantees (more)
 what if applications misbehave (audio sends higher
than declared rate)

policing: force source adherence to bandwidth allocations
 marking and policing at network edge:
Principle 2
provide protection (isolation) for one class from others
23
Principles for QoS Guarantees (more)
fixed (non-sharable) bandwidth to flow:
inefficient use of bandwidth if flows doesn’t use
 Allocating
its allocation
Principle 3
While providing isolation, it is desirable to use
resources as efficiently as possible
24
Principles for QoS Guarantees (more)

Basic fact of life: can not support traffic demands
beyond link capacity
Principle 4
Call Admission: flow declares its needs, network may
block call (e.g., busy signal) if it cannot meet needs
25
Summary of QoS Principles
Let’s next look at mechanisms for achieving this ….
26
Scheduling And Policing Mechanisms
 scheduling: choose next packet to send on link
 FIFO (first in first out) scheduling: send in order of
arrival to queue

discard policy: if packet arrives to full queue: who to discard?
• Tail drop: drop arriving packet
• priority: drop/remove on priority basis
• random: drop/remove randomly
27
Scheduling Policies: more
Priority scheduling: transmit highest-priority queued
packet
 multiple classes, with different priorities

class may depend on marking or other header info, e.g. IP
source/dest, port numbers, etc..
28
Scheduling Policies: still more
Weighted Fair Queuing:
 generalized Round Robin
 each class gets weighted amount of service in each
cycle
29
Policing Mechanisms
Goal: limit traffic to not exceed declared parameters
Three common-used criteria:

(Long term) Average Rate: how many pkts can be sent
per unit time (in the long run)


Peak Rate: e.g.,



crucial question: what is the interval length: 100 packets per
sec and 6000 packets per min (ppm) have same average!
Avg rate: 6000 ppm
Peak rate: 1500 ppm
(Max.) Burst Size: max. number of pkts sent
consecutively (with no intervening idle)
30
Policing Mechanisms
Leaky Bucket: limit input to specified Burst Size and
Average Rate.
 bucket can hold b tokens
 tokens generated at rate
r token/sec unless bucket
full
 over interval of length t: number of packets
admitted less than or equal to (r t + b).
31
Policing Mechanisms (more)
 Leaky bucket + WFQ  provide guaranteed upper bound
on delay, i.e., QoS guarantee! How?


WFQ: guaranteed share of bandwidth
Leaky bucket: limit max number of packets in queue (burst)
Ri  R wi /  w j
d
max
i
 bi / Ri
32
IETF Integrated Services (IntServ)
 architecture for providing QoS guarantees in IP
networks for individual application sessions
 resource reservation: routers maintain state info
of allocated resources, QoS req’s
 admit/deny new call setup requests:
33
IntServ: QoS guarantee scenario
 Resource reservation
 call setup, signaling (RSVP)
 traffic, QoS declaration
 per-element admission control
request/
reply

QoS-sensitive
scheduling (e.g.,
WFQ)
34
Call Admission
Arriving session must:
 declare its QoS requirement
R-spec: defines the QoS being requested
 characterize traffic it will send into network
 T-spec: defines traffic characteristics
 signaling protocol: needed to carry R-spec and Tspec to routers (where reservation is required)
 RSVP

35
IntServ QoS: Service models [rfc2211, rfc 2212]
Guaranteed service:
 worst case traffic arrival: leaky-bucket-policed source
 simple (mathematically provable)
1993, Cruz 1988]
arriving
traffic
bound on delay [Parekh
token rate, r
bucket size, b
WFQ
per-flow
rate, R
D = b/R
max
36
IETF Differentiated Services
Concerns with IntServ:
 Scalability: signaling, maintaining per-flow router
state difficult with large number of flows

Example: OC-48 (2.5 Gbps) link serving 64 Kbps audio
streams  39,000 flows! Each require state maintenance.
 Flexible Service Models: Intserv has only two classes.
Also want “qualitative” service classes

relative service distinction: Platinum, Gold, Silver
DiffServ approach:
 simple functions in network core, relatively complex
functions at edge routers (or hosts)
 Don’t define service classes, provide functional
components to build service classes
37
DiffServ Architecture
Edge router:
r marking
scheduling
 per-flow traffic management
 Classifies (marks) pkts
 different classes
 within a class: in-profile
b
..
.
and out-profile
Core router:
 per class traffic management
 buffering and scheduling based
on marking at edge
 preference given to in-profile
packets
38
Edge-router Packet Marking
 profile: pre-negotiated rate A, bucket size B
 packet marking at edge based on per-flow profile
Rate A
B
User packets
Possible usage of marking:
 class-based marking: packets of different classes marked
differently
 intra-class marking: conforming portion of flow marked
differently than non-conforming one
39
Edge-router: Classification and Conditioning
 Packet is marked in the Type of Service (TOS) in
IPv4, and Traffic Class in IPv6
 6 bits used for Differentiated Service Code Point
(DSCP) and determine Per-Hop Behavior (PHB)
that the packet will receive
 2 bits are currently unused
40
Edge-router: Classification and Conditioning
may be desirable to limit traffic injection rate of
some class:
 user declares traffic profile (e.g., rate, burst size)
 traffic metered, shaped if non-conforming
41
Core-router: Forwarding (PHB)
 PHB result in a different observable (measurable)
forwarding performance behavior
 PHB does not specify what mechanisms to use to
ensure required PHB performance behavior
 Examples:


Class A gets x% of outgoing link bandwidth over time
intervals of a specified length
Class A packets leave first before packets from class B
42
Core-router: Forwarding (PHB)
PHBs being developed:
 Expedited Forwarding (EF): pkt departure rate of a
class equals or exceeds specified rate



logical link with a minimum guaranteed rate
May require edge routers to limit EF traffic rate
Could be implemented using strict priority scheduling or
WFQ with higher weight for EF traffic
 Assured Forwarding: multiple traffic classes,
treated differently


amount of bandwidth allocated, or drop priorities
Can be implemented using WFQ + leaky bucket or RED
(Random Early Detection) with different threshold values.
• See Sections 6.4.2 and 6.5.3 in [Peterson and Davie 07]
43
Protocols For Multimedia Applications
 To manage and stream multimedia data
 RTP: Real-Time Protocol
 RTSP: Real-Time Streaming Protocol
 RTCP: Real-Time Control Protocol
 SIP: Session Initiation Protocol
44
Real-Time Protocol (RTP): FRC 3550
 RTP specifies packet structure
for audio and video data



payload type identification
packet sequence numbering
time stamping
 RTP runs in the end systems
 RTP packets are encapsulated in
UDP segments
 RTP does not provide any
mechanism to ensure QoS

RTP encapsulation is only seen
at the end systems
45
RTP Header
Payload Type (7 bits): Indicates type of encoding currently being
used: e.g.,
•Payload type 0: PCM mu-law, 64 kbps
•Payload type 33, MPEG2 video
Sequence Number (16 bits): Increments by one for each RTP packet
sent, and may be used to detect packet loss
Timestamp field (32 bytes long). Reflects the sampling instant of the
first byte in the RTP data packet.
SSRC field (32 bits long). Identifies the source of the RTP stream.
Each stream in a RTP session should have a distinct SSRC.
46
RTP Example
 consider sending 64
kbps PCM-encoded
voice over RTP.
 application collects
encoded data in
chunks, e.g., every 20
msec = 160 bytes in a
chunk.
 audio chunk + RTP
header form RTP
packet, which is
encapsulated in UDP
segment
 RTP header indicates
type of audio encoding
in each packet

sender can change
encoding during
conference.
 RTP header also
contains sequence
numbers, timestamps.
47
Real-Time Streaming Protocol (RTSP)
 RFC 2326
 client-server application layer protocol
 Used to control a streaming session
 rewind, fast forward, pause, resume, repositioning, etc…
What it doesn’t do:
 doesn’t define how audio/video is encapsulated for
streaming over network
 doesn’t restrict how streamed media is transported
(UDP or TCP possible)
 doesn’t specify how media player buffers audio/video
48
RTSP: out of band control
FTP uses an “out-ofband” control channel:
 file transferred over
one TCP connection.
 control info (directory
changes, file deletion,
rename) sent over
separate TCP
connection
 “out-of-band”, “inband” channels use
different port
numbers
RTSP messages also sent
out-of-band:
 RTSP control
messages use
different port
numbers than media
stream: out-of-band.
 port 554
 media stream is
considered “in-band”.
49
RTSP Example
 metafile communicated to web browser
 browser launches player
 player sets up an RTSP control connection, data
connection to streaming server
50
Metafile Example
<title>Twister</title>
<session>
<group language=en lipsync>
<switch>
<track type=audio
e="PCMU/8000/1"
src = "rtsp://audio.example.com/twister/audio.en/lofi">
<track type=audio
e="DVI4/16000/2" pt="90 DVI4/8000/1"
src="rtsp://audio.example.com/twister/audio.en/hifi">
</switch>
<track type="video/jpeg"
src="rtsp://video.example.com/twister/video">
</group>
</session>
51
RTSP Operation
52
RTSP Exchange Example (simplified)
C: SETUP rtsp://audio.example.com/twister/audio RTSP/1.0
Transport: rtp/udp; compression; port=3056; mode=PLAY
S: RTSP/1.0 200 OK
Session 4231
C: PLAY rtsp://audio.example.com/twister/audio.en/lofi RTSP/1.0
Session: 4231
Range: npt=0C: PAUSE rtsp://audio.example.com/twister/audio.en/lofi RTSP/1.0
Session: 4231
Range: npt=37
C: TEARDOWN rtsp://audio.example.com/twister/audio.en/lofi RTSP/1.0
Session: 4231
S: 200 OK
53
Real-Time Control Protocol (RTCP)
 Also in RFC 3550 (with RTP)
 works in conjunction with RTP
 Allows monitoring of data delivery in a manner scalable
to large multicast networks
 Provides minimal control and identification functionality
 each participant in RTP session periodically
transmits RTCP control packets to all other
participants.
 each RTCP packet contains sender and/or receiver
reports


report statistics useful to application: # packets sent,
# packets lost, interarrival jitter, etc.
used to control performance, e.g., sender may modify its
transmissions based on feedback
54
RTCP - Continued
 Each RTP session typically uses
a single multicast address
 All RTP/RTCP packets belonging
to session use multicast address
 RTP, RTCP packets
distinguished from each other
via distinct port numbers
 To limit traffic, each participant
reduces RTCP traffic as number
of conference participants
increases
55
RTCP Packets
Receiver report packets:
 fraction of packets
lost, last sequence
number, average
interarrival jitter
Sender report packets:
 SSRC of RTP stream,
current time, number of
packets sent, number of
bytes sent
Source description
packets:
 e-mail address of
sender, sender's name,
SSRC of associated
RTP stream
 provide mapping
between the SSRC and
the user/host name
56
Synchronization of Streams
 RTCP can synchronize
different media streams
within an RTP session
 consider videoconferencing
app for which each sender
generates one RTP stream
for video, one for audio.
 timestamps in RTP packets
tied to the video, audio
sampling clocks
 not tied to wall-clock
time
 each RTCP sender-report
packet contains (for most
recently generated packet
in associated RTP stream):


timestamp of RTP packet
wall-clock time for when
packet was created.
 receivers uses association
to synchronize playout of
audio, video
57
RTCP Bandwidth Scaling
 RTCP attempts to limit its
traffic to 5% of session
bandwidth.
Example
 Suppose one sender,
sending video at 2 Mbps.
Then RTCP attempts to
limit its traffic to 100
Kbps.
 RTCP gives 75% of rate to
receivers; remaining 25%
to sender
 75 kbps is equally shared
among receivers:

with R receivers, each
receiver gets to send RTCP
traffic at 75/R kbps.
 sender gets to send RTCP
traffic at 25 kbps.
 participant determines RTCP
packet transmission period by
calculating avg RTCP packet
size (across entire session)
and dividing by allocated rate
58
SIP: Session Initiation Protocol [RFC 3261]
SIP long-term vision:
 all telephone calls, video conference calls take
place over Internet
 people are identified by names or e-mail
addresses, rather than by phone numbers
 you can reach callee, no matter where callee
roams, no matter what IP device callee is currently
using
59
SIP Services
 Setting up a call, SIP
provides mechanisms ...
 for caller to let callee
know she wants to
establish a call
 so caller, callee can
agree on media type,
encoding
 to end call
 determine current IP
address of callee:

maps mnemonic
identifier to current IP
address
 call management:
 add new media streams
during call
 change encoding during
call
 invite others
 transfer, hold calls
60
Setting up a call to known IP address
Bob
Alice
167.180.112.24
INVITE bob
@193.64.2
10.89
c=IN IP4 16
7.180.112.2
4
m=audio 38
060 RTP/A
VP 0
193.64.210.89
port 5060
port 5060
Bob's
terminal rings
200 OK
.210.89
c=IN IP4 193.64
RTP/AVP 3
3
m=audio 4875
ACK
port 5060
Bob’s 200 OK message
indicates his port number,
IP address, preferred
encoding (GSM)

SIP messages can be
sent over TCP or UDP;
here sent over RTP/UDP.

m Law audio
port 38060
GSM
Alice’s SIP invite
message indicates her
port number, IP address,
encoding she prefers to
receive (PCM ulaw)

port 48753
default
is 5060.
time
time
SIP port number
61
Setting up a call (more)
 codec negotiation:
suppose Bob doesn’t
have PCM ulaw
encoder
 Bob will instead reply
with 606 Not
Acceptable Reply,
listing his encoders
Alice can then send
new INVITE
message, advertising
different encoder

 rejecting a call
Bob can reject with
replies “busy,”
“gone,” “payment
required,”
“forbidden”
 media can be sent over
RTP or some other
protocol

62
Example of SIP message
INVITE sip:[email protected] SIP/2.0
Via: SIP/2.0/UDP 167.180.112.24
From: sip:[email protected]
To: sip:[email protected]
Call-ID: [email protected]
Content-Type: application/sdp
Content-Length: 885
c=IN IP4 167.180.112.24
m=audio 38060 RTP/AVP 0
Notes:
 HTTP message syntax
 sdp = session description protocol
 Call-ID is unique for every call.
Here we don’t know
Bob’s IP address.
Intermediate SIP
servers needed.

Alice sends, receives
SIP messages using SIP
default port 5060

Alice specifies in
header that SIP client
sends, receives SIP
messages over UDP

63
Name translation and user locataion
 caller wants to call
callee, but only has
callee’s name or e-mail
address.
 need to get IP address
of callee’s current
host:



user moves around
DHCP protocol
user has different IP
devices (PC, PDA, car
device)
 result can be based on:
 time of day (work, home)
 caller (don’t want boss to
call you at home)
 status of callee (calls sent
to voicemail when callee is
already talking to
someone)
Service provided by SIP
servers:
 SIP registrar server
 SIP proxy server
64
SIP Registrar
 when Bob starts SIP client, client sends SIP
REGISTER message to Bob’s registrar server
(similar function needed by Instant Messaging)
Register Message:
REGISTER sip:domain.com SIP/2.0
Via: SIP/2.0/UDP 193.64.210.89
From: sip:[email protected]
To: sip:[email protected]
Expires: 3600
65
SIP Proxy
 Alice sends invite message to her proxy server
 contains address sip:[email protected]
 proxy responsible for routing SIP messages to
callee

possibly through multiple proxies.
 callee sends response back through the same set
of proxies.
 proxy returns SIP response message to Alice

contains Bob’s IP address
 proxy analogous to local DNS server
66
Example
Caller [email protected]
with places a
call to [email protected]
SIP registrar
upenn.edu
SIP
registrar
eurecom.fr
2
(1) Jim sends INVITE
message to umass SIP
proxy. (2) Proxy forwards
request to upenn
registrar server.
(3) upenn server returns
redirect response,
indicating that it should
try [email protected]
SIP proxy
umass.edu
1
3
4
5
7
8
6
9
SIP client
217.123.56.89
SIP client
197.87.54.21
(4) umass proxy sends INVITE to eurecom registrar. (5) eurecom
registrar forwards INVITE to 197.87.54.21, which is running keith’s SIP
client. (6-8) SIP response sent back (9) media sent directly
between clients.
Note: also a SIP ack message, which is not shown.
67
Comparison with H.323
 H.323 is another signaling
 H.323 comes from the ITU
protocol for real-time,
(telephony).
interactive
 SIP comes from IETF:
 H.323 is a complete,
Borrows much of its
vertically integrated suite of
concepts from HTTP
protocols for multimedia
 SIP has Web flavor,
conferencing: signaling,
whereas H.323 has
registration, admission
telephony flavor.
control, transport, codecs
 SIP uses the KISS principle:
 SIP is a single component.
Keep it simple stupid.
Works with RTP, but does
not mandate it. Can be
combined with other
protocols, services
68
Summary: Protocols
 Several protocols to handle multimedia data
 RTP: Real-Time Protocol
 Packetization, sequence number, time stamp
 RTSP: Real-Time Streaming Protocol
 Establish, Pause, Play, FF, Rewind
 RTCP: Real-Time Control Protocol

Control and monitor sessions; synchronization
 SIP: Session Initiation Protocol
Establish and manage VoIP sessions
 Simpler than the ITU H.323

 NONE enforces QoS in the network
69