Transcript 102802-nibedita

NIBEDITA MAULIK
GRAND SEMINAR PRESENTATION
OCT 21st 2002
On Peer-to-Peer Media Streaming
Purdue University
•P2P data streaming
Supplying Peers stream media file to requesting peers
Requesting peers play back and store media data during streaming session
Requesting peers become supplying peers after streaming session
• Characteristics self growing, server less, heterogeneous in outbound
bandwidth contribution, supplying peers/requesting peer relation is many to one
• Problems
Media data assignment for a multi-supplier P2P streaming session (Optimal Media Data Assignment)
Fast amplification of P2P streaming capacity (Fast System Capacity Amplification)
• Streaming model
Each supplying peer participates in at most one P2P streaming session at any time
Capacity of the P2P system is the total number of P2P streaming sessions simultaneously provided by the system
The in-bound bandwidth of the requesting peer Pr is related to Ro i.e. the playback rate of the media data as
Rin( Pr ) = Ro,
The out-bound bandwidth of the supplying peers Ps has values Ro/2, Ro/4, Ro/8…..Ro/2 N classified as class-n
peers for the out-bound bandwidth of Ro/2n
OPTIMAL MEDIA DATA ASSIGNMENT
Buffering Delay : Time interval between the start of the transmission and the start of the playback at Pr
OPTIMAL MEDIA DATA ASSIGNMENT(Algorithm)
•Assignment of first 2n segments is computed ; the assignment repeats itself every 2n segments for
the rest of the media file.
•OTSp2p is optimal
FAST SYSTEM CAPACITY AMPLIFICATION
FAST SYSTEM CAPACITY AMPLIFICATION(Algorithm)
•Distributed Admission Control Protocol DACp2p
Each supplying peer individually decides in a probabilistic fashion with different probability value applied to
different classes of requesting peers, whether or not to participate in a streaming session
A requesting peer may send a ‘reminder’ to a busy supplying peer , reminding it not to elevate its admission
preferences to requesting peers of classes lower than that of the requesting peer
DACp2p – Supplying Peers
Ps maintains an admission probability vector <Pr[1], Pr[2], ….Pr[N]> Pr[i] = probability with which a class-I
requesting peer with be supplied in case Ps is not busy in another streaming session
The vector is computed as follows
1. If Ps is a class-k peer, for 1<=i<=k Pr[i] =1.0 & for k<i <=N Pr[i] = 1/ 2 i-k
2. If Ps has been idle, the probability vector will be updated after Tout. For k<i<N, Pr[i]=Pr[i]*2
3. If Ps just finished a streaming session, it will update it’s probability vector as follows
- if during the session it did not receive any request from it’s favored class then K<i<=N
Pr[i]=Pr[i]*2
- if it received at least 1 request from it’s favored class, however it was not granted because Ps was
busy and the requesting peer left a ‘reminder’ and the class of that requesting peer was L then 1<=i<=L
Pr[i]=1.0 and L<i<=N , Pr[i] = 1/2 i-k
FAST SYSTEM CAPACITY AMPLIFICATION(Algorithm)
DACp2p – Requesting Peer
- Pr obtains a list of M randomly selected candidate supplying peers by some P2P lookup mechanisms. The
class of each candidate is also obtained
- Pr obtains enough permissions from supplying peers such that
1. They are neither down nor busy
2. The are willing to provide streaming service
3. Their aggregated out-bound bandwidth offered is Rsum = Ro
- Pr executes algorithm OTSp2p to compute media data assignment, triggers the participating supplying
peers, and the session begins
- If Pr cannot get enough permission it leaves ‘reminder to a subset W of the busy candidates. Members of
W are selected as follows
1. The candidate currently favors the class of Pr
2. The aggregated out-bound bandwidth offer of the candidates in W is equal to Ro – Rsum
- If Pr is admitted, it becomes a supplying peer when the streaming session is over, if Pr is rejected it will
backoff for at least Tbkf before making the request again
THE NUMERIC INDEXING FOR MUSIC DATA
• Goal
Chaoyang University of Technology, Taiwan
Efficient Content based retrieval of audio & music data
To transform the music data into numeric forms and develop an index structure for effective retrieval
Ensure scalability in an efficient audio/music data retrieval system
• Suffix tree for Music Indexing
Constructed from a symbol with length m symbols, consists of m leaf nodes numbered from 1 to m
Any two branches from a non-leaf node should be labeled with different symbols
The number of each node points out the start position of the sub-string which consists of the symbols labeled
from the root to this leaf node of the tree
NUMERIC INDEXING
• Let music data consist of n notes Do, Re, Mi ….etc each note represented by a music symbol ‘a’, ‘b’, ……., ‘n’
respectively
• Each music symbol is mapped onto integer values 0, 1, ……., n-1
• For a music segment with m adjacent notes x1x2x3….xm, the integer value of each note is to be represented by
P(xi), this segment can be transformed into a numeric value by the function v(m) =  P(xi) X n i-1
• Modified R-tree to construct numeric index structure
Each non-leaf node of the modified R-tree consists of the upper bound and lower bound of numeric values of
the sub-tree under it
Each leaf node of the R-tree stores the transformed value of music feature string and a linked list of target
music
Each entry in the linked list consist of music information and a pointer
Each music information consist of the music ID in the database and the start position of the music segment in
the music
The pointer points to the next entry with the same transformed value
EXAMPLE FOR NUMERIC INDEXING
EXACT MATCHING
• The music query segment has to be found the exact same pattern in a melody from the music database
e.g Music query segment ccdbb . Two sub-segments of length 4 will be ccdb & cdbb of value 1322 & 1132
Leaf node 1322 -> (S2, 2) , (S3, 1)
Leaf node 1132 -> (S2, 3) , (S3, 4)
The intersection yields {S2, S3} -> both music feature strings consist of segments ‘ccdb’ & ‘cdbb’
• Check if the starting symbols of sub-segments found in each music feature string are adjacent each other as the
sequence of query segment. Here sub-segments ‘ccdb’ and ‘cdbb’ starting on 2nd and 3rd symbols of S2 have the
identical sequence as the query. Hence S2 is the target music
APPROXIMATE MATCHING
• Transform the music query string into numeric value
•Compare the value with the values in the leaf node
•Iff the difference between the transformed value and the value of leaf node matches one of the conditions listed
in Table 1, there will be a target node found and it will be the target music