On Peer-to-Peer Media Streaming_

Dongyan Xuy, Mohamed Hefeeda, Susanne Hambrusch, Bharat Bhargava

Department of Computer Sciences

Purdue University,West Lafayette, IN 47907

fdxu, hefeeda, seh, bbg@cs.purdue.edu

 

 

Abstract

 

STUDY peer-to-peer media streaming

system with the following characteristics:

 

(1) its streaming

capacity grows dynamically;

 (2) peers do not exhibit serverlike

behavior;

(3) peers are heterogeneous in their bandwidth

contribution; and

(4) each streaming session may

involve multiple supplying peers.

 

investigate two problems:

(1) how to assign media

data to multiple supplying peers in one streaming session

and

 

1. solution

optimal media data assignment algorithm OTSp2p

minimum buffering delay in the consequent streaming session

 

 

(2) how to fast amplify the system’s total streaming

capacity.

 

2. soln

distributed differentiated admission control protocol DACp2p

differentiating between requesting peers with different outbound

bandwidth,

DACp2p achieves

  • fast system capacity amplification
  • benefits all requesting peers in
    • admission rate,
    •  waiting time, and
    • buffering delay;
  • incentive for peers to offer their truly available out-bound bandwidth.

 

 

1. Introduction

 

[10, 11, 12,

15, 14]

research efforts in

peer-to-peer systems during the past two years

 

ýless attention: the peer-to-peer media streaming system

 

major difference

data sharing mode among peers:

  • general                   open-after-downloading’
  • media stream         ‘play-while-downloading

 

 

requesting peers

playback and store the media data during the streaming

session, and they become supplying peers of the media

file after the streaming session.

 

 

assume

 

  • selfgrowing

requesting peers later becoming supplying

peers

 

  • serverless

 

  • heterogeneous

out-bound bandwidth

contribution

o        different access networks

o        different willingness

 

o        out-bound bandwidth

less than the original

playback rate

multiple supplying peers

 

 

problems

  • media data assignment

multi-supplier peer-to-peer streaming session.

 

 

  • fast amplification

service priority à promise higher out-bound bandwidth

 

 

OTSp2pàoptimal media data assignment

minimum buffering delay experienced by the requesting

peer

 

DACp2p,à distributed differentiated admission control protocol

both supplying

and requesting peers

 

(1) faster amplification

(2) higher admission rate and fewer

rejections

(3) shorter average buffering delay

 

differentiates between requesting peers

with different out-bound bandwidth promises, = incentive

 

 

2 Peer-to-Peer Media Streaming Model

 

(1) Roles of peers

  • requesting peers

requesting peer becomes a

supplying peer

 

 

avoid server-like behavior,

supplying peer at most one peer-to-peer streaming

session at any time.

 

‘seed’ supplying peers,

obtain external source.

 

 

(2) Bandwidth of peers

R0         playback rate

Pr            requesting peer

Rin(Pr) = R0         in-bound bandwidth

 

Ps           supplying peer

                Rout(Ps)                 out-bound bandwidth

                                R0             R0                   R0

2              4          2N

 

 

 

 

(3) Classes of peers

 

N classes          possible values of their out-bound

bandwidth offer

 

 

 

out-bound bandwidth         R0    (1<n<N)           (class n peer)

2n

 

lower the n, higher the class.

                (out BW higher if n low)

 

 

(4) Capacity of the peer-to-peer streaming system

 

 

capacity

number streaming sessions simultaneously

 

multiple supplying peers

Rout(Ps) add up to R0,

 

capacity of the system at time t

 

 

 

set of supplying peers in the system at t).

 

 

(5) Segments of media data

Assume:

small sequential segments of equal sizes

Constant-Bit-Rate (CBR)

∂t            playback time each segment is the same

 

 

3 Optimal Media Data Assignment

 

requesting peer                    Pr

set of supplying peers       

 

 

R0 = Rin(Pr) =

 

 

(playback rate = in-bound stream = sum out bound streams)

 

Determine:

(1) the media data segments to

be transmitted by

 

 

(2) the playback start time for Pr

 

 

goal

  • continuous playback,
  • minimum buffering delay at Pr.

 

buffering delay

time interval between

  • start of media data segment transmission
  • start of playback at Pr

 

 

different media data assignments lead to different buffering delays.

Buffer delay    =          5∂t

Buffer delay    =          4∂t

Uses OTSp2p

 

 

 

OTSp2p

optimal media data assignment

minimum buffering delay

executed by the requesting peer

 

1. computing the media data assignment,

2. initiate the peer-to-peer streaming session

notifying each participating supplying peer of the corresponding assignment.

 

pseudo-code

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

m supplying peers

descending order (m = lowest out bound BW offer)

 

class-n   lowest class

 

compute assignment of the first  2n  segments;

 

assignment repeats itself every 2n segments

 

 

first ‘while’           

second ‘while’     

third ‘while’

                fourth

                P1            7              3              2              0

                P2            6                              1

                P3            5

                P4            4

 

 

Theorem 1

m supplying peers

requesting peer Pr

 

R0 =     

 

 

 

OTSp2p 

optimal media data assignment,

minimum buffering delay

 

 

 

4 Fast System Capacity Amplification

  • problem of fast capacity amplification
  • how to select a set of supplying peers for a peer-to-peer streaming session,

 

peer-to-peer streaming system

capacity dynamically grows

 

time t0

[four supplying peers

two class-2 peers

                PS1 PS2

 

two class-1 peers

                PS3 PS4

 

 

 

               

 

 

system can admit one requesting peer at t0

 

[three requesting peers:

two class-2 peers

                PR1 PR2

 

                one class-1

                PR3

 

(hi class = low BW offer)

 

 

ýadmit P1 at t0

                capacity still 1

 

þadmit P2

capacity will grow to 2

at t0 + T,

 

                both PR1 PR2 admitted

                at t0 + T.

 

waiting time

interval between

its first streaming request

earliest time it can be

admitted

 

average waiting time

  1. (0 + T + 2T)=3 = T;
  2. (T + T + 0)=3 = 2 T

3

 

differentiated admission policy

[ favors higher-class requesting peers

faster amplification

 

requirements

(1) not starve lower-class requesting peers,

     even in the short term;

(2) enforced in a purely distributed fashion;

(3) differentiating:

      higher the outbound bandwidth pledged by a requesting peer,

  • the greater the possibility that it will be admitted,
  • and the shorter the waiting time and
  •  buffering delay

 

incentive truly available out-bound

 

distributed admission control protocol DACp2p.

  1. supplying peer individually decides whether or not to participate in a streaming session

[different probability values applied to different classes of requesting peers

[dynamically adjusted

 

  1. reminder:

requesting peer Pr may send a ‘reminder’ to a busy

supplying peer Ps

Ps not to elevate its admission

preferences to requesting peers of classes lower than

that of Pr  (stop starving???)

 

 

4.1 DACp2p Supplying Peers

 

supplying peer

admission probability vector

<Pr[1], Pr[2]….. Pr[N] >  ý   Pr[i] (1 < i <N)

applied to class-i requesting peers:

 

[class-i requesting peer contacts Ps for streaming service

                not busy

grant the request with  probability Pr[i]

 

[ Ps itself is a class-k peer

 values in the probability vector of Ps

(a) Ps becomes a supplying peer,

1 <i < k,

initialize Pr[i] = 1

 

k < i < N,

 

 

A) Initially

favor requesting peers

of class-k and higher

always granting requests.

 

exponentially decrease the admission probability.

 

 

i a favored class    Pr[i] = 1

 

eg.           class-2 supplying peer

                N = 4

                admission probability vector < 1:0; 1:0; 0:5; 0:25 >

initial favored classes  1 and 2.

 

B) Ps has been idle,

probability vector updated timeout period of Tout

 

k < i < N

Pr[i] =Pr[i] * 2.

 

‘elevate’ the admission

probabilities of lower-class requesting peers,

 

performed after every period of Tout

 

 

C) just finished serving

update its probability vector

 

  • not receive request favored class,

=elevate

 

  • least one request favored class, busy.

= ‘tightens’

left a ‘reminder’ to Ps

 

                ^

                k  = highest favored class, left reminder

then,

1 < i< ^k,      Pr[i] = 1

 

 

 

 

4.2 DACp2p Requesting Peers

 

requesting peer Pr

1. obtains a list of M randomly

selected candidate supplying peers via some peerto-

peer lookup mechanism

eg. Napster               centralized directory server

 eg. Chord [12].        distributed lookup service

 

2. contacts from high to low classes:

 

 

Pr will be admitted,

  • Permissions from enough supplying peers

 

(1) neither down nor busy

(2) they are willing passed the

probabilistic admission test

(3) their aggregated

out-bound bandwidth offer is Rsum = R0

 

 

3. execute Algorithm OTSp2p

-compute the media data assignment

-triggers

 

Pr will be rejected,

not able to get permission from enough supplying peers

leave a ‘reminder’ to a subset W of the busy candidates.

 

W

high-class to low-class busy candidates

first few that…..

 

(1) the candidate currently favors the class of Pr

                i.e. at Ps      Pr[i]  = 1   (i favoured class)

 

(2) the aggregated out-bound

bandwidth offer of the candidates in W is equal to

(R0 - Rsum)

(make up defecit of Ro   needed)

 

 

W senders keep reminder

Finished, reminder to update its probability vector,

 

may not in the future serve exactly

the same requesting peer which left the reminder.

 

reminder

distributed mechanism to realize differentiated and adaptive admission

control

 

streaming session is over,

become a supplying peer.

 

[ Pr is rejected,

backoff for at least a period of Tbkf

 

xth rejection.

 

 

 

 

5 Performance Study

5.1 Simulation Setup

 

 

FINISH THIS LATER!!!!!!!!!!!!!!!!!!!

 

 

 

 

 

6 Related Work

eg. Napster [3], Gnutella [2], and Freenet [4]

 

þde-centralized data exchange

þdynamic growth of system capacity

 

data lookup/discovery schemes

  • Napster                  centralized directory servers,
  • Gnutella [2]            controlled query flooding.

 

data sharing mode

  • ‘open-afterdownloading’mode,
  • ýnot the ‘play-while-downloading’

 

 

 

[11], a detailed measurement

study of Napster and Gnutella is presented.

  • degree of heterogeneity in the peers’bandwidth availability;
  • future: built-in incentive

 

 

CAN [8], Chord

[12], and Pastry [9]

distributed peer-to-peer lookup services

 

 

PAST [10] and OceanStore [6]

persistent storage services

 

 

ýTHIS PAPER: do not study the problems of peer-to-peer data

lookup and storage management;

 

 

 

multi-source media streaming

[7], a distributed video streaming system

þsession involves multiple replicated video servers

                ý problem of system capacity amplification,

                                client-server v P2P

 

 

C-star [1]

commercial multi-source streaming service.

ýnot differentiate between suppliers of different

out-bound bandwidth capability

 

 

[5] SpreadIt architecture

streaming live media over a peer-to-peer network

dynamic construction of a multicast tree among peers requesting a live media.

 

ýnot intended for the asynchronousstreaming of stored media data.

 

 

 

7 Conclusion

 

two key problems

  1. the assignment of media data to multiple supplying peers
  2. fast capacity amplification of the entire peer-to-peer streaming system

 

Soln:

  1. OTSp2p  algorithm

optimal media data assignments for peer-to-peer streaming sessions

 

  1. fully distributed DACp2p protocol.

Differentiating between requesting peers according their classes,

(1) achieves fast system capacity amplification,

(2) benefits all requesting peers in

o        admission rate,

o        waiting time, and

o        buffering delay

(3) creates an incentive truly available out-bound bandwidth.