Transcript PROMISE: Peer-to-Peer Media Streaming Using CollectCast

Peer-to-Peer Media Streaming
ZIGZAG - Ye Lin
PROMISE – Chanjun Yang
SASABE - Kung-En Lin
Video Streaming Solutions


Dedicated Channel:
individual connection to
each receiver – Unicast
(server bottleneck)
IP Multicast:
Synchronized peers Server
problem.
Server
Cn
C1
C1
C2
……
Cn-1
C2
……
Cn-1
Cn
Chaining

Basic Idea


A client can forward its incoming video stream
to serve other clients
Server
Advantages



Each client can now contribute its computing
resource to serve the entire community, rather
than being just a burden to some central server
A new client can be chained to an early client,
making this service model highly scalable
It uses only unicast, but achieves the same
effect of using IP multicast

Since each server stream now can serve many
clients, this strategy is often called Application
Layer Multicast.
C1
C2
C3
Chaining Problems

End-to-end delay



Robustness requirement



Tree height: If a tree is too long, the forwarding delay will
be large, making it unsuitable for live streaming
Node degree: If a node has high degree, high forwarding
bandwidth is required
A receiver may join and leave at any time
If a forwarding client leaves, its downstream clients must
be hooked to some other clients
Assume peers are indifference


Different bandwidth
Different capacity
Solutions

ZIGZAG



PROMISE


Short End-to-End delay
Efficient join and failure recovery
Aggregate peers bandwidth
SASABE

QoS consideration and Efficient distribution
ZIGZAG: An Efficient Peer-to-Peer
Scheme for Media Streaming
Ye Lin
Proposed ZIGZAG

Administrative organization
ZIGZAG

Multicast tree



A peer, when not at its
highest layer, can not
have links to or from any
other peers.
A peer, when at its
highest layer, can only
link to its foreign
subordinates. The only
exception is the server.
At layer j<H-1, peer get
the content directly
from a foreign head.
ZIGZAG


Control protocol thru periodic
communication: clustermates, children
and parent.
Peer join: link node to the leaf cluster
that have minimum end-to-end delay.
ZIGZAG

Peer fails




The parent of X delete the link
to X.
Y, the cluster head of X ‘s
children, is responsible for
finding a new parent for X ‘s
children.
X’, A random subordinate of X at
layer 0 become new head of
each cluster that lost X
X’ gets link from X ‘s parent.
ZIGZAG

Performance Evaluation
ZIGZAG
NICE
Node degree
O(k2)
O(logN)
Height of multicast tree
O(logkN)
O((logkN)2)
Control overhead of a node
O(k*logkN)
O(k*logN)
Join overhead
O(logkN)
O(logN)
Split overhead
O(k2)
Number of peers that need to
reconnect due to a failure
O(k2)
Merge overhead
O(k2)
O(logkN)
ZIGZAG Conclusion

Major innovation


use of a foreign head to forward the
content .
Desirable properties


short end-to-end delay
efficient join and failure recovery
PROMISE: Peer-to-Peer Media
Streaming Using CollectCast
Chanjun Yang
Introduction to the Problem

Challenges of P2P real-time media streaming
•
•
•

A sender may stop contributing to a P2P session
The connections may have different bandwidth,
loss and failure rate
The connections between the senders and
receiver are not independent
Maintain the best possible streaming quality
•
Select, monitor and possibly switch sending peers
Relative Work

One sender, one receiver


The sender may not have enough
capability
Receive data from multiple senders


Do not select best senders
Ignores peer diversity and network
conditions
Proposed PROMISE



Selects best sending peers.
Monitors the senders and network
status.
Chooses new senders when trouble
occurs.
PROMISE - Architecture

P2P substrate
•

CollectCast
•
•

Independent from
PROMISE
A novel application
level P2P service
Middleware between
a lookup substrate
and applications
PROMISE
PROMISE - Operations






Send lookup request to the substrate for a media file.
Determine the set of active senders and passive
senders.
Active senders are the best choices
The receiver assigns a sending rate to the active
senders based on certain parameters.
Transmission continues unless a switch is needed.
A peer from the passive set is swapped in to the
active set.
PROMISE – Selecting Best
Senders

Random
•

End-to-end
•

Randomly chooses a number of peers
Estimates the “goodness” of the path from each
candidate peer to the receiver
Topology-aware
•
Infers the underlying topology and its
characteristics and considers the goodness of each
segment of the path
Selecting Senders – End-toend selection



Based on quality of
paths
Does not consider
shared segment
If peers sharing a
tight segment are
chosen in the active
set ?
Selecting Senders – TopologyAware Selection



Build the goodness
topology
Use the goodness
topology to estimate
the peer goodness for
the session
Formulate the peer
selection problem as an
optimization problem
Topology-Aware Selection –
Goodness Topology

Build the inferred topology
•
•

Infer the approximate topology
Annotate its edges with the metrics of interest.
(e.g., loss rate and available bandwidth)
Transform to the goodness topology
•
Compute a “logical” goodness metric for each
segment based on the metrics annotated
Topology-Aware Selection –
Segment Goodness
For each peer p chosen as an active peer,
 The goodness of segment i  j :
g ij = w ij x ij
 w i  j depends on the available bandwidth and
level of sharing on segment i  j .
 x i  j depends on the loss rate.
 The mean of x i  j :
E (x i  j ) = 1- average loss rate on i  j .
Topology-Aware Selection –
Segment Goodness (Cont’d)


W = 1 : aggregate rate of the peers
sharing the segment <= available bandwidth.
ij
Otherwise, it is proportioned to the shortage
of bandwidth if the peer is chosen with the
already selected peers.
W
ij
=(b
ij
- ∑s∈S, ij∈sr Rs ) / Rp
Topology-Aware Selection –
Peer Goodness

The goodness of each peer, G p depends on
 goodness of all segments on the path from
the peer to the receiver
 availability of the peer
Topology-Aware Selection –
Peer Goodness (Cont’d)

Peers with a goodness of close to 1:



Good availability
Reliable path
Therefore we expect they would be a
good choice for sender
Topology-Aware Selection Algorithm


Enumerate all possible sets satisfying the
constraint
Select the one with the highest rate
Topology-Aware Selection Example
Set loss rate in all path = 0
E (x
i->j)
= 1 for all i,j
Set Rl = RU = R0 = 1 Mb/s
R0: The playback rate
{P4, P6}, {P3, P5, P6},…
{P2, P3, P6},…{P1, P2, P3, P5}
E({P3, P5, P6})
= 1 x .8 x .25 + 1 x .8 x .25+
(.25 / .50) x.9 x .5
= 0.625
E({P2, P3, P6})
= 1 x .7 x .25 + 1 x .8 x .25+
1 x .9 x .5
= 0.825
PROMISE – Rate and Data
Assignment



A media file is divided into equal-length
segments. The active peers collectively send
the media file segment by segment.
Rate assignment: Each peer p is assigned an
actual sending rate Rp proportional to its
offered rate.
Data assignment: Each peer is assigned a
number of packets Dp to send in proportion to
its actual streaming rate
PROMISE – Dynamic Switching


Peers may fail or network paths may
become congested during a long
streaming session
Once a failure is detected, replacement
peers will be selected by using the
topology-aware selection
PROMISE – Performance
Evaluation
PROMISE – Performance
Evaluation (Cont’d)
PROMISE Conclusion

PROMISE

Multiple sender peers, single receiver peer


CollectCast



Select, monitor, and switch sending peers
Infer and exploit topology and performance
Realizing the functions of sender selection, monitoring,
and switching
PROMISE delivers high quality streaming and
is resistant to peer failure when using the
topology aware technique.
Scalable and Continuous Media
Streaming on Peer-to-Peer
Networks
Kung-En Lin
Introduction to the Problem

P2P Application Layer Multicast tree
•
•
•
•
Root peer is an original media server.
Other peers are intermediate nodes and
leaves.
Peers’ demands are simultaneous and
concentrated on a specific media stream.
(Effective)
A variety of media streams. (Problem)
Relative Work

PROMISE
•
•
•
•
Selection of Senders
Calculating parameter based on entire
media stream
Constant monitoring of sender/network
status
Switching of senders when the sender or
network fails
Proposed solution



Segmentation of media stream
Two scalable methods to find desired
media block
Two algorithms to determine an
optimum provider peer from the search
results
Basic concept – Media block



A “block” is a processing unit that can be
encoded and decoded by itself.
Example: A multiple of the GoP (Group of
Pictures) of MPEG-2
The number of blocks of a media stream affects
the system scalability in terms of the amount of
search traffic.
Per-group search
Searching Mechanism

Full flooding


Limited Flooding


Gnutella, Freenet
control by TTL
Selective Search


FL method
FLS method
Selective Search

FL method



Satisfy – Limited flooding
Otherwise, Full flooding
FLS method



Selective – peers contain all of the next
round’s blocks.
Limited – Missing one of next round’s block.
Full flooding – Missing all of next round’s
blocks.
Determination algorithm
Block 1
p1 p2 p3 p5 p6 p8 p9 p…
Block 2
p5 p8 p11
Block 3
p3 p4 p9 p10 p20
S
Determination algorithm
S’
t1 t2
t3 t5 t6
t8
t9 t…
> deadline of the block?
Time = max(A, B) + size of block / bandwidth of the peer
A: Estimated completion time of retrieval of the block
B: Time when this algorithm is performed + Round trip time of the peer
Determination algorithm
S’
t1 t2

SF method (Selected Fasted)


t5 t6 t…
Smallest completed time
SR method (Selected Reliable)


Lowest possibility of black disappearance.
Largest number
Determination algorithm


Recalculating retrieval time and request
block from the peer which we selected
If we have done all of blocks, we finish
determination algorithm. Otherwise,
repeat the first step to get next block.
Performance Evaluation
Performance Evaluation
(Cont’d)
Conclusion



FLS method provide users with
continuous media play-out without
introducing extra load on the system.
Unpopular media streams did not really
fulfill FLS method.
QoS is a trade-off of scalability.
Conclusion – P2P Streaming

Application Layer Multicast




Tree reconstructing (one-to-multi)
Resource aggregating (multi-to-one)
P2P Video Scheduling
P2P Video System