Transcript PPT

CS 414 – Multimedia Systems Design
Lecture 20 –
TCP Augmentations for
Multimedia &
Midterm Review Session
Klara Nahrstedt
Spring 2009
CS 414 - Spring 2009
Administrative

Homework 1
– March 6
 solutions will be posted on March 7
 deadline
CS 414 - Spring 2009
Transport Protocols (Layer 4)

Existing Protocols –
– Reliable Transport Protocol
 UDP – Unreliable Transport Protocol
 TCP

New Protocols –
– Real-time Transport protocol
 RTCP – Real-time Control Protocol
 RTP
CS 414 - Spring 2009
TCP- Transmission Control
Protocol - Features
Serial communication path between
processes exchanging a full-duplex stream of
bytes
 Sequential delivery (no reordering required)
 Reliable delivery

 Achieved
through retransmission via timeouts and
positive acknowledgement on receipt of information

Flow and congestion control is based on
window technique
CS 414 - Spring 2009
TCP Header
Bit offset
Bits 0–3
0
Source port
32
Sequence number
Acknowledgment number
64
4–7
Reserved
8–15
16–31
Destination
port
96
Data offset
CWR
128
Checksum
160
Options (optional)
160/192
+
Data
ECE
URG
ACK
PSH
RST
SYN
FIN
Window
Urgent pointer
CS 414 - Spring 2009
Flow and Congestion Control in TCP



Slow-start algorithm – basic flow and congestion
control in TCP
The algorithm requires sender to keep
congestion window which is the estimate of how
much traffic the network can actually take (innetwork traffic)
Congestion window is managed using two-part
algorithm:
 Sender
sends exponentially until TCP segment gets
lost
 Sender sends exponentially up to half the previous
window, then window grows linearly
CS 414 - Spring 2009
Techniques for Going Faster
TCP predictions (1987) that TCP/IP
cannot go faster than 10 Mbps
 Van Jacobson investigated making TCP
faster
 Techniques:

management – reduce copying
 Interrupt handling – clocked interrupts
 Memory
CS 414 - Spring 2009
Techniques for Going Faster

Better lookup techniques
 TCP
must lookup connection block for each segment
received
 IP must find a route to be able send IP packet

Use caches of frequently used information
 Maximize
hit rate, minimize search and
maintenance
Most effective – small caches
 Packets travel in packet rates


CACHE OF 20 ROUTES SHOWED HIT RATE OF 90%
CS 414 - Spring 2009
Techniques for Going Faster

Lookup algorithm
using open chaining – head of each
hashed link list keeps a cache of the last
accessed control block
 Hashing

Prediction
 TCP
behavior is highly predictable and one
can take advantage by optimizing the frequent
path through TCP code at sender/receiver
 Header prediction
CS 414 - Spring 2009
Sequence Numbers

High delay-bandwidth product has implication on
TCP window size and sequence space;
 Delay-bandwidth
product means how many bytes
(represented via packets) are currently in-flight (i.e., inside
the network)
 Example:


If EED is 1 second and network bandwidth (inside network) is 10
Mbps, then delay-bandwidth product is equal to 10 Mbits (1second
* 10 Mbps) and this means that one can have 10 Mbits worth of
data inside the network before seeing it at the receiver
TCP window size is 64 KB – we need possibility to
negotiate the window size
CS 414 - Spring 2009
Sequence Numbers

Sequencing uses wrap-around counters to put in
sequence numbers
 Sequence

number space is too small
Examples:


In case of 10 Mbps, the IP packet lifetime was designed with 120
seconds and sequence space of 32 bits – takes about 1700
seconds to send 231 bytes
In case of 1 Gbps, it takes 17 seconds to send 231 bytes
CS 414 - Spring 2009
Conclusion

TCP has been augmented and can achieve high
performance suitable for multimedia, but one
must optimize TCP for performance
 Especially
for large video streams
CS 414 - Spring 2009
Midterm
March 9 (Monday), 11-11:50am, 1302 SC
 Closed Book, Closed Notes
 You can bring calculator and 1 page cheat
sheet

CS 414 - Spring 2009
Covered Material
Class Notes (Lectures 1-17)
 Book Chapters to read/study:

 Media
Coding and Content processing book
Chapter 2,
 Chapter 3.1-3.2, 3.8,
 Chapter 4.1-4.2.2.1,
 Chapter 4.3 (as discussed in lecture)
 Chapter 5, chapter 7.1-7.5, 7.7

 Multimedia
Systems book
Chapter 2, (not 2.4.4 – we have not covered QoS routing ),
 Chapter 5.1

CS 414 - Spring 2009
Material

Media Characteristics
 Synchronous,
Isochronous, Asynchronous
 Regular, irregular
 Weakly and strongly periodic streams

Audio Characteristics
 Samples,
frequency,
 Perception, psychoacoustic effects, loudness,
pitch, decibel, intensity
 Sampling rate, quantization
CS 414 - Spring 2009
Material

Audio Characteristics
 PCM,

DPCM, ADPCM, signal-to-noise ratio
Image Characteristics
 Sampling,
quantization, pixels
 Image properties: color, texture, edges
 Simple edge detection process
CS 414 - Spring 2009
Material

Video technology
 Color
perception: hue, brightness, saturation,
 Visual representation: horizontal and vertical
resolution , aspect ratio; depth perception,
luminance, temporal resolution and motion
 Flicker effect
 Color coding: YUV, YIQ, RGB
 NTSC vs HDTV formats
CS 414 - Spring 2009
Material

Basic Coding schemes
 Run-length
coding
 Statistical coding
Huffman coding
 Arithmetic coding


Hybrid codes
 JPEG:
image preparation, DCT
transformation, Quantization, entropy coding,
JPEG-2000 characteristics
CS 414 - Spring 2009
Material

Hybrid Coding
 Video
MPEG: image preparation, I, P, B
frames characteristics, quantization, display
vs processing/transmission order of frames
 Audio MPEG: role of psychoacoustic effect,
masking, steps of audio compression
 MPEG-4: differences to MPEG-2/MPEG-1

Audio-visual objects, layering
CS 414 - Spring 2009
Material

Quality of Service concepts
classes, QoS specification –
deterministic, predictive, best effort, QoS
classification – application, system, network
QoS, relation between QoS and resources
 QoS operations: translation, negotiation of
QoS parameters
 Service
CS 414 - Spring 2009
Material

Resource Management concepts
 QoS
and resources, establishment phase and
transmission/enforcement phase
 Admission control of resources, reservation
and allocation of resources
 LBAP arrival model
 Enforcement of guarantees: rate control, error
control, resource monitoring and adaptation
CS 414 - Spring 2009
Material

Multimedia Transport
 Requirements
and constraints
 Examples of translation and negotiation
protocols
 Admission control for bandwidth and delay
 Reservation protocols, types of reservations
 Traffic Shaping, how is a traffic shape
expressed

CS 414 - Spring 2009
Material

Multimedia Transport
Shaping – Leaky Bucket, (r,T) shaping,
Token Bucket, difference between them
 Rate control – fair queuing, delay earliest
deadline first, stop-and-go scheme, jitterearliest deadline first scheme
 Error control – go-back-N retransmission,
selective retransmission, difference to FEC
(forward error correction) ,
 Traffic
CS 414 - Spring 2009
Sample Problems
Consider the following alphabet {C,S,4,1},
with probabilities: P(C) = 0.3, P(S) = 0.2,
P(4)= 0.25, P(1) = 0.25.
 Encode the word CS414 using

 Huffman
coding and arithmetic coding
 Compare which encoding requires less bits
CS 414 - Spring 2009
Sample Problems

Describe briefly each step in MPEG-1
audio encoding. Specify the functionality,
which is performed in each step. You don’t
have to provide equations, only a clear
explanation of the functionality that is
performed inside each step.
CS 414 - Spring 2009
Sample Problems
What is flicker effect and how to remove
it?
 Explain difference between synchronous
and isochronous transmission stream
modes
 Provide five differences between MPEG-4
video encoding standard and the previous
MPEG video encoding standards

CS 414 - Spring 2009
Sample Problems

Consider voice application (like Skype). If
you could redesign the underlying protocol
(think about a session layer
algorithms/services/protocols) under the
voice application, what multimediasensitive algorithms would you deploy to
achieve appropriate multimedia protocol?
Specify clear design of order of
algorithms/protocols to be used
CS 414 - Spring 2009