Transcript Look at the number of code bits allocated to that subband!

Background
Peer-to-Peer File Sharing Network
Constantly changing network, no central server.
Gnutella, Napster, Swarmcast
~50,000 users/day and increasing
Clip2. Gnutella http://www.clip2.com/gnutella.html
Problems - Scenario A
Ticcy’s trying to download a song on 56K modem
and $15 speaker
Have to download the whole file before you can listen
to the whole song.
Host can drop off, leaving the song incomplete.
Can’t control the quality/size of the song.
She’d rather have the whole song with lower quality
than an incomplete song
Problems – Scenario B
Doddie’s on ADSL, trying to download a movie
10 hits, only one free, but slow.
Can’t switch to faster peer when it becomes available.
Solutions
Progressive Audio
Quality increases as file size grow
Allows preview
Control Quality
Good for users with slow connection
Parallel download from multiple peers
Faster download
Don’t miss out on good connections
Good for broadband users
Related work on Progressive Audio
Audio streaming
Requires copies of the same file at different quality
Can’t build on downloaded file to increase quality
Progressive JPEG
Next slide…
Progressive JPEG
Sequential
Progressive
Buffer
•Stores all DTC coefficients of image.
•Group DCT coefficients into serveral spectral bands.
•Typically, low-frequency bands are sent first, and then highfrequency bands.
Similar approach may be taken for progressive audio, except that sound
has a more complicated model of perception.
It also requires that the file is encoded & decoded as progressive JPEG.
B. Furht, Y. Weng, and J. Celi, "Interactive Progressive Encoding System for
Transmission of Complex Images", Proc. of SPIE Symposium on Multimedia
Storage and Archiving Systems, Boston, Nov 1998.
Figs from http://wwwicg.informatik.uni-rostock.de/Projekte/MoVi/jpeg/pexamples.html
MPEG Overview
"A tutorial on MPEG/Audio Compression" by Davis Pan.
Motorola Inc, 96
MPEG Overview cont..
Psychoacoustic model works out the signal energy to
masking threshold ratio for each frequency subband
How sensitive human ear is to that frequency
Neighboring frequencies make it more/less audible
The bit allocation block uses the signal-to-mask ratios to
decide how many code bits to allocate for quantization of
that subband.
Allocates more code bits to subband with low mask-to-moise ratio.
"A tutorial on MPEG/Audio Compression" by Davis Pan. Motorola Inc, 96
http://www.cs.sfu.ca/undergrad/CourseMaterials/CMPT365/material/
notes/Chap4/Chap4.3/Chap4.3.html
Progressive
Constraints
Transfer any mp3 file progressively
end file should be identical to original file
Real time
Technique
Decode the mp3 file -> 32 quantized subbands/packet
Rate the importance of subbands (signal-to-mask ratios)
Running the signal through psychoacoustic model again
Or
Look at the number of code bits allocated to that subband!
Send each subband in the order of importance.
Maximum 32 passes, but normally a few subband dominates.
Minimum 1 pass (all the sound appears in one subband, unlikely)
Fast
Peer-to-Peer
Connection Manager
Search
Resource Manager
Transport
Searching in P2P
Files are found by forwarding queries to one’s neighbors until the target is
found. Broadcast search is costly on bandwidth and not scalable.
Search utilizing high degree nodes
Each client keep lists of files stored by their first and second degree
neighbors.
passed when a new node joins the network.
Update periodically.
Pass queries along the highest degree nodes.
IP of the nodes already queried are appended to the query, and avoided.
Simulation shows 50% of files can be found in 8 steps or less.
“Search in Power-Law Networks” A Adamic et al,
Stanford University, March 2001
Parallel Download
Take advantage of the replication of data in P2P and
download from multiple peers simultaneously.
Task allocation to peers
QoS (available bandwidth, latency)
Divide file up accordingly and assign to peers
Adapt to network changes (drop out, degraded QoS)
Submit new request for resource from reliable peer
Terminate or update request for a smaller file from bad QoS peers.
"Resource Management in Networked Multimedia Systems" K.
Nahrstedt, Distributed System Lab, UPenn, R. Steinmetz, IBM
European Networking Center
"The Dynamic MAnagement of Guaranteed Performance Connections
in Packet Switched Integrated Service Networks" C Parris et al,
Berkeley, 94.
Transport Protocol
70% of people don’t share their files because uploading their files slows
their downloads. Our modems have separate channels for upload and
download so why would upload affect download?
Problem in TCP
TCP use acks for congestion control. i.e. if sender receives few acks it
slows down transmission and vice-versa.
when uploading, acks are queued behind data packets => the slow
download.
Solution
Reduce frequence of acks (red marking)
Handle infrequent acks
Implement own congestion control using UDP
TCP friendly – user control
“How to get good TCP performance over asymmetric networks”
H. Balakrishnan, MIT Nov 99
“Free Riding on Gnutella” Eytan Adar and Bernardo A.
Huberman. Xerox Palo Alto
File Hashing – MD5
Same file can have different filename, different file can
have same filename.
The original file needs an unique key to ensure file
integrity for parallel download and file resume (for
progressive)
Solution - MD5
A message-digest algorithm provides a output a 128-bit
"fingerprint" of a file of arbitrary length.
Simple to implement (source available).
Fast to compute.
R. Rivest, "MD5 Digest Algorithm." RFC 1321, MIT and RSA
Data Security, Inc., April 1992.
System Overview
Reuse of existing software
LAME encoder http://www.mp3dev.org
MPG123 decoder http://mpg.123.org/
MD5 http://www.fourmilab.ch/md5/
Plan of Action
Thank you
Appendix - MD5
Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo
512
Step 2. Append Length
A 64-bit representation of b (the length of the message before the padding bits were added)
is appended to the result of the previous step.
Step 3. Initialize MD Buffer
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Step 4. Process Message in 16-Word Blocks
Too long..
Step 5. Output
R. Rivest, "MD5 Digest Algorithm." RFC 1321, MIT and RSA
Data Security, Inc., April 1992.
Appendix – Fourier analysis
Any wave may be represented as a sum of sine waves. Fourier
analysis help us determine which sine waves must be used.

F (u ) 
 f ( x)[cos 2ux  i sin 2ux]dx

F (u)  R 2(u)  I 2 (u)
Fig taken from http://www.bores.com/courses/intro/freq/3_dist.htm
Computer Graphics – Foley, 97