Systems \ protocols sorted by name
APES
Apocrypha
Astrolabe
Bayeux
BigBang
BitTorrent
Borg
Bullet
CAN
CANMulticast
Capriccio
Chord
ChunkCast
CoBlitz
CollectCast
CoolStreaming
CoopNet
COPACC
Coral
DarkNet
DigitalFountain
DONet
SRM
esrm
eMule
estar
FastReplica
FatNemo
Fcast
FEC
FPRF
Freenet
GNP
Gnustream
Gnutella
GreedyDual
GTITM
Hostmulticast
HSM
i3
IDA
IDMaps
INET
Ivy
Julia
King
LH
Lighthouses
Livny
LT
LVRM
MACEDON
MaybeCast
MDC
Meridian
MNCodes
ModelNet
Mutualcast
Narada
Nettimer
Nice
OCD
OceanStore
oStream
Overcast
P2cast
P2vod
PALS
PAST
Pastry
Pbcast
PeerCast
PeerStreaming
PET
PIC
PIER
Pixie
PlankBeck
Pond
Porcupine
PRM
PRO
Promise
PROMISE
Raptor
RBUDP
RDP
RocketFuel
RTMP
RTP
RTSP
CAN
SCP
Scribe
SEDA
Shark
Skip_Graphs
SkipNet
Skype
Slurpie
SplitStream
SRM
STUN
Tangler
Tapestry
TCP
TCPNice
TFRC
TIERS
Tulip
Turbo
TURN
Vivaldi
WebTorrent
YMTP
Yoid
Zigzag
Conferences sorted by name
Globecom 2002
Globecom 2003
Globecom 2004
ICDCS 2000
ICDCS 2001
ICDCS 2001
ICDCS 2002
ICDCS 2003
ICDCS 2004
ICDCS 2004
ICNP 1998
ICNP 1999
ICNP 2000
ICNP 2001
ICNP 2002
ICNP 2003
ICNP 2004
INFOCOM 1995
INFOCOM 1996
INFOCOM 1997
INFOCOM 1998
INFOCOM 1999
INFOCOM 2000
INFOCOM 2001
INFOCOM 2002
INFOCOM 2003
INFOCOM 2004
INFOCOM 2005
INFOCOM 2005
IPTPS 2002
IPTPS 2003
IPTPS 2004
Multimedia 2001
NGC 1999
NGC 2000
NGC 2001
NGC 2002
NGC 2003
NOSSDAV 1995
NOSSDAV 1996
NOSSDAV 1997
NOSSDAV 1998
NOSSDAV 1999
NOSSDAV 2000
NOSSDAV 2001
NOSSDAV 2002
NOSSDAV 2003
NOSSDAV 2004
SIGCOMM 1997
SIGCOMM 1998
SIGCOMM 1999
SIGCOMM 2000
SIGCOMM 2001
SIGCOMM 2002
SIGCOMM 2003
SIGCOMM 2004
SIGCOMM 2005
SIGCOMM 2005
SIGMETRICS 1999
SIGMETRICS 2000
SIGMETRICS 2001
SIGMETRICS 2002
SIGMETRICS 2003
SIGMETRICS 2004
SOSP 1997
SOSP 1999
SOSP 2001
SOSP 2003
SOSP 2005

Content Distribution Resources
Selected relevant large scale content distribution, application layer multicast, high speed data
dissemination papers reviewed by Danny Bickson.
List of recommended articles including protocols, deployed applications, measurements, modeling,
error correcting codes, network positioning, search, streaming media and video on demand, transport
layer optimizations.
Color map:
Green  recommended to start with.
Purple  interesting theoretical work.
Note: star ratings are a suggestion for the reading order for begginers who would like to learn
more about this field. The stars (or lack of them) are not hinting about the quality of importance of the
work. This is only a useful suggestion.
A must read  highly important system
Important paper in this field, or a very well written paper
Interesting paper
Read if you have time
Read if you like..
Last updated

January 16th, 2008

Protocols and Deployed Systems
1987

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturighis. D. Swinehart
and D. Terry, Epidemic Algorithms for Replicated Database Maintenance, In PODC, 1987
Summary: The authors examine several methods for updating database replicas which are
geographically spreaded. First is using point to point updates using email, Second is antientropy
where each machine is constantly probing other machines and update its storage when needed and the
third is rumor spearing where the machines are initially idle, and when hot rumors arrive they
spread it randomly around the network. The rumors have some aging period which after it they
are not forwarded any more. Using the communication cost as a performance measure, they suggest to
use spatial distributions where closer nodes are contacted more frequency with some exponentially
growing probability.
For saving
communication cost a spatial distribution is constructed, where the probability of contacting another node at distance d is
d^a. Furthermore, through experimentation they found out that using a commulative probability function greatly
improves network performance. Thus they define Qs(d) to be a distribution function where the probability
is taking nodes with commulative distances up to d diminished exponentially as the distance grows.
In their simulation cross Atlantic link
traffic was reduces at a factor of about 30 using this spatial function vs. uniform distribution.
1997

Floyd, S., Jacobson, V., Liu, C., McCanne, S., and Zhang, L., "A Reliable Multicast Framework for
Lightweight Sessions and Application Level Framing", IEEE/ACM Transactions on Networking, December
1997, Volume 5, Number 6, pp. 784803 (SRM).
ps
Summary: SRM is a framework for scalable reliable multicast. it does not define topology not
application demands (ordering etc.). Giving objects a persistent name (and not seq. number 19201)
can help group members ask for missing parts from other nodes and not from the source. For doing
the actual multicast, a multicast group is formed, where everyone is talking to everyone and
updating about the progress of the download. In case of missing parts, one waits random time and
asks for the part. Anyone who has it can answer and sent it to everyone else. Suggested
a possible optimization of getting the parts from close nodes, but did not implement it.

E. Schooler and Jim Gemmel, Using Mulitcast FEC to Solve the Midnight Maddness Problem, MS Research Tech Report MSTTR9725, 1997
Summary: Combine multicast with forward error correction to handle the flash crowd problem.
1998

P. Rodriguez, E. W. Biersack and K. W. Ross, "Improving the Latency in the Web: Caching or Multicast?",
International Caching Workshop, Manchester, England. June 1517, 1998 pdf
Summary: Consider two schemes for distribution of web documents. First is a repeatedly multicast and
the second is hierarchical caching of web servers. Develop analitical model for comparison. The
conclustion is that for all but fast changing document caching is superior in terms of bandwidth
and latency.
 K. Hua, Y. Cai, and S. Sheu, Patching: A multicast technique for true
ondemand services,” presented at the ACM Multimedia, Bristol, U.K.,
1998.
Summary: for enabling server distribution of video file, propose using the client buffer for
reducing network and server load. The server multicasts the video in a regular multicast stream.
When clients later enter the system, the server uses a patching channel which is used for viewing
the movie. The clients concurrently store the regular multicast channel in their buffer. The
patching multicast channel enables the clients to catch up with the future position of the stream.
1999

K. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu and Y. Minsky, Bimodal Multicast.
ACM Transactions on Computer Systems 17(2) (May 1999), 4188
pdf
Summary: the basic problem of SRM is that each member is monitoring the
download progress of all group members. Thus the rate of retransmissions increases with the
group size.
SRM can scale up to 50100 receivers, with higher population and or higher
error rate it might not
perform well in practice. The basic idea of Pbcast (probabilistic broadcast or bimodal multicast)
is first to make an unreliable hierarchical broadcast using a best effort for all the users.
Second, to use a two phase antientropy protocol which fills in the gaps of lost messages. The
first phase detects message loss and the second is run only when needed and fills in the gaps. An
emphasize on achieving a common suffix of the information (and not the prefix as in other
protocols). When a message becomes old enough the protocol gives up and marks the message as lost.
This is done to avoid situations of nodes which are constantly hanging and unable to catch up. The
antientropy is run by every node in the system. Each member chooses another random member and send
it a digest (summary) of it's message histories. The digest is compared in the receiving side, and
if it has message which are not in the digest it forwards them to the sender.
Several proposed optimizations: retransmission requests are served only in a small timeframe after
the the original transfer. The maximum number of message retransmit is bounded (to avoid nodes
which try to catch
up everything at
once).
Nodes getting retransmission request cycle through their inventory to prevent redundancies.
Messages are retransmitted in the order of most recent first. Each node can have only a subset
view of the whole network in condition it is chosen at random. Possibly closer nodes to improve
latency.
2000

Y. Chu, S. G. Rao, and H. Zhang, "A Case For End System Multicast", Proceedings
of ACM SIGMETRICS 2000, Santa Clara,CA, June 2000, pp 112. (Narada).
pdf
Summary: Application level multicast is done in two stages. First, a mesh in constructed along
all group members. (The assumption is that the group size is small). Then edges are removed from
the mesh using DV algorithm for finding better routes inside the message. Thus a tree is formed.
Define a parameter of resource usage which is the delay of a link multiplied by the stress on that
link, summed up of all links. The stress is the number of identical packets which travel a single
link. Ratio of the delay between two members is the RDP
(relative delay penalty) relating to the
physical path. Group management protocol handles joins leaves and maintenance of links. Mesh
quality is improved by probing other members periodically and trying to find better paths. For that
routing tables are exchanged between members. When changing a link of the tree, gains and losses to
members of the group are calculated as well. The DV algorithm sends full paths in order to avoid
loops. Simulation show that about 50% of the nodes have RDP up to 3. On average physical link
stress up to 7. Saving of 20% of network resources compared to unicast.

P. Francis, Yoid: Extending the Internet multicast architecture, Unpublished paper, April
2000. ps
Summary: Yoid is a suite of protocols that allows all of the replication and forwarding
required for distribution of content. The topology management protocol is called YMTP, which
allowed hosts dynamically create a topology of of either shared tree or mesh. Each such topology
group has one or more rendezvous points associated with it. Yoid pros: router forwarding table
size is kept small relative to IP multicast. Avoiding IP multicast infrastructure which is
complicated to use and does not have enough demand. Congestion control achieved using point to
point links. Higher reliability. Possible buffering can be made in the overlay hosts. Cons: more
work is induced in the overlay relative to IP multicast, the overlay network does not resemble the
physical network, thus close nodes services are harder to find.
It is interesting to node that Yoid is using a "Pushback" mechanism which is exactly the
chocking/unchocking mechanism of BitTorrent. One bit is sent in order to
signal start and stopping
of transmission. There is a lot of work dealing on how to contract the trees, either by mesh ( as
in
Narada)
or trees, how to avoid circles etc.

W. Litwin, T. Schwarz, LH*RS: A HighAvailability Scalable Distributed Data Structure using
Reed Solomon Codes, In ACM MOD 2000.
Summary: Suggest storage of file parts using k out of n servers. Beginner level explanation of
RS codes using examples.
2001

S. Rantansamy, M. Handley, R. Karp, S. Shenker. Applicationlevel Multicast using Content Addressable Networks
n Proceedings of Third International Workshop on Networked Group Communication NGC 2001), London,
England, 2001. (CANMulticast)
pdf
Summary: Group multicast address is hashed and mapped into a responsible node. Joining the multicast
group is done using that node. Multicast in the group is done by flooding.
 L. Xu, "Efficient and Scalable OnDemand Data Streaming Using UEP Codes, ACM Multimedia,
Ottawa, Canada, Oct. 2001".
pdf
Summary: used for streaming media where users join arbitrarily but must start from the start
of the stream. Using UEP (unequal error protection) codes. For decoding the first part only 1
received part is needed. For decoding the second, 2 and so on. Thus when joining, the recipient
immediatly can start playing the stream. For immediate playing, 12.9 resources are needed at the
server relative to native multicast. User buffer space used up to 40% of the file. Did only
simulations.

H. Deshpande, M. Bawa, and H. GarciaMolina. Streaming live media over a peertopeer network.
Technical
report, 200131, Stanford University, 2001. (PeerCast).
pdf
Summary: propose tree based overlay(PeerCast) intended for hundred of clients in the
multicast group. Stream is divided into data (using RTP) and control (using RTSP). Redirect
message enable a peer to redirect another peer to get the data from some other peer. Join is done
using a search on the tree for unsaturated node. Leaving is done using redirect message for the
affected children of a leaving node. Forwarding a search message on the tree is done by one of the
following policies: random, RR, SP(smart placement)  the node with the minimal latency is
picked. Optimizations: nodes can be swapped for improving bandwidth. leaf sink  slow node can be
downgraded to be leaf on the tree. Did simulations.

R. Izmailov, S. Ganguly, N. Tu, "Fast Parallel File Replication in Data Grid", In proc. of the
future of the data grid workshop, 2001.pdf
Summary: suggest performing point to multipoint trasnfer while using as many links as
possible. The file F is split into small and equal subfiles which are disseminated using a forest
of trees. Several approaches for creating the trees are suggest: Hierarchical approach (as in
FastReplica),
Iterative DFS/BFS approaches, the first tree is built using DFS/BFS, and it's bandwidth is set to
the minimal links bandwidth. Then other trees are constructed along other paths until the full
capacity is obtained. Did prototype which run on Planetlab with up to 50 nodes.
 M. Waldman, D. Mazieres, Tangler: A censorshipresistant publishing system based on document
entaglements, in ACM CCS 2001.
Summary: the main idea is to have dependancies between new file blocks inserted into the system
into existing blocks. When publishing, the publisher has to use some older blocks already in the
system to construct the new document. Thus old docs are republished. The publish key of each user
is used as the key for data retrieval. Each user has a collection of document she published. In
this collection there are inodes which point to the actual blocks. The inode have an inheret
replication such that only a part of the blocks is needed to reconstruct the file.
2002
 J. Byers and J. Considine, "Informed Content Delivery Across Adaptive Overlay Networks",
Proc. of ACM SIGCOMM 2002.
pdf
Summary: argue that using source encoding improved bandwidth. Using digital fountain approach. Since
there are infinitely many parts using bloom filters to detect heuristically dissimilarities. Also
discuss recoding of the data (network coding). Compare strategies: random selection, random with
bloom filters, recoding, with b.f. etc.

Banerjee, S. and Bhattacharjee, B. and Kommareddy, C., "Scalable Application Layer
Multicast", Proceedings of SIGCOMM 2002
August, 2002. (Nice)pdf
Summary: present the Nice multicast protocol, used for low bandwidth data streaming
applications. Based on hierarchical clustering, the multicast is done on trees on possibly several
options. On average, each members, keep state of constant number of other members, where worst is
(logN) information. The control topology is based on hierarchy of clusters. All nodes
participate on Level 0 (L0). Cluster leaders participates in L1, and thus recursively. Cluster
leader is chosen by graph theoretic center of participating nodes where the distance is the network
latency. The transmission can be done in
one of several trees based upon those clusters. Control topology is a clique, where data topology
on each cluster is a star. Main referred previous work is Narada.
New host join using a RP (rendezvous point) doing a search on the tree
for joining the optimal cluster. The join operation costs kLogN steps. HeartBeat messages are sent
in the control topology for maintenance and estimation of distances. Clusters may split and merge
based on their size. Performance metrics are quality of data path (tree degree, link stress, and
stretch), recovery from host
failures and control traffic overhead. Did simulations using GTITM with 10,000 routers and
implemented the Narada protocol as reference. Did real life implementation with up to 100
machines in 8 sites. Claim to improve up to 25% in link stress relative to Narada.

V. Padmanabhan, H. Wang, P. Chou, and K. Sripanidkulchai, "Distributing Streaming Media
Content Using Cooperative Networking", Proc. of NOSSDAV 2002, May 2002. (CoopNet)pdf
pdf
Summary: Streaming media is grouped using MDC codes into multiple multicast trees. (like
SplitStream)
When a
intermediate tree node disconnects, only one stream of data is affected. Degradation in the video
quality depends on the number of received channels. Where most of the channels are received the
image is very good. Handles both live streaming (i.e. olympics) and ondemand streaming.

V. N. Padmanabhan, H. J. Wang, and P. A. Chou.
Resilient peertopeer streaming. In IEEE ICNP
2003.pdf
Summary: Another paper describing the CoopNet network. Improvements are better construction of
multicast trees (deterministically balanced that each node will be intermediate node in one tree
at most vs. random construction of trees.) The drawback is that the trees
construction is done using a centralized controller. Added also receiver feedback that aggregate
histograms of frames received up the tree and thus enables better FEC coding at the source. Did
simulations using MSNBC video broadcast of 11.9.01.
Regarding the actual encoding, group the frames into GOF (groups of frames) and encode with
prioirity sorted by reduction of signal distortion value. Based on feedback from users and the
priority of the GOF the packets are encoding using FEC which has better protection for higher
prioirty frames.

W. Wang, D. Helder, S. Jamin, L. Zhang, "Overlay Optimizations for Endhost
Multicast", In Proceedings of Fourth International Workshop on Networked Group Communication
(NGC 2002), Oct 2002 (TMesh)
pdf
Summary: Working on Planetlab, used for streaming media. Creates first a multicast tree, and
then makes shortcuts in the tree in order to acheive better performence. Claim that data delivery
can achieve between 0.3 to 2.5 latency relative to IP multicast. Can use their protocol to
improve any other tree based algorithms. Define RDP which is the average delay
penalty among all
pairs of nodes. Claim that node pairs latency improve 510% above Narada. RDP is used since
adding a link might shorten distances to several nodes and adding it on another place my shorten
to other number of nodes so it is hard to compare we need some ratio between the number of
affected nodes and the total change in path lengths. Method: collect offline information of
latencies between all pairs of nodes and try to heuristically choose another link each time to get
better results. Uses dijkstra shortest path first algorithm. Two createria for shortcuts: first
the shortcut has to improve RDP and also the utility (the total effect on neighbors)
has to be above certain threshold.

M. Castro, P. Druschel, A.M. Kermarrec, and A. Rowstron. Scribe: A largescale and decentralized
applicationlevel multicast infrastructure. IEEE Journal on Selected Areas in Communications,
20:14891499, 2002.
pdf
Summary: Built upon pastry. Any Scribe node can create a group, others may join the group or
multicast message to all group members. To create a groupid a hash function is used over some
textual name. The peer responsible of that name is the RP (rendezvous point). The multicast tree
is created using reverse path forwarding. The tree is formed by joining the Pastry routes from
each group members member to the RP.

S. Atchley, M. Beck, J. Hagewood, J. Millar, T. Moore, S. Plank, S. Soltesz, "Next Generation
Content Distribution Using the Logistical Networking Testbed". Technical Report UTCS02498,
University of Tennessee Department of Computer Science, December, 2002.
pdf
Present the logistical network testbed which consists of several hundreds of machine spread
around the world. Developed networking stack based on the need for file transfer and changed the
Linux file system to support files which are stored on the network.

S. Graupner, W. Kalfa, C. Reinmann, "Modeling and simulation of mediaondemand service 
evaulating a digital media grid architechture", in HP Lab technical report, HPL2002192,
2002.
pdf
Summary: Present a 3tier proxy caching which are used for media on demand. The upper layer is
the content provider, middle layer are various regional caches and lower layer are metropolitan
caches. Content is pushed into caches and pulled to the clients.

P. Druschel, A. Rowstron, PAST: A largescale, persistnet peertopeer storage utility. In
Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles, pages 188201,
Chateau Lake Louise, Banff, AB, Canada, October 2001.
Summary: PAST nodes serve as access points for clients, practicipate in routing and provide
sotrage. Based on the Pastry routing and location scheme. Assume the PAST nodes are servers based
on the ISPs. Use assymertic enctyption for security and hashing for content verification. A
central broker is responsible of qouta enforecement.

CAN">
Y. Chen, R. H. Katz and J. D. Kubiatowicz, CAN: a Dynamic Scalable and Efficient Content
Distribution Network, Proceedings of the First International Conference on Pervasive Computing
(PERVASIVE), Zurich, Switzerland, Aug. 2002.
Summary: Propose CAN (Scalable Content Access Network) using twotier architecture. The small
primary tier is the content producer and the second is a large softstate tier. Built on top of
Tapestry routing. Use a synamic placement of replicas, where clients first search for a replica
with a certain QoS, and create one if it does not exist. Tested several placement strategies like
eager (closest to the client) and lazy (far away from the client as possible). Discuss tradeoff
between search heuristics and the placement of the cache. Replicas are maintained using a dtree.
Dod simulation using GTITM and MSNBC traces.
2003

Y. Birk and D. Crupnicoff, "A Multicast Transmission Schedule for Scalable MultiRate
Distribution of Bulk Data using NonScalable Erasure Correcting Codes". In IEEE INFOCOM 2003, March
2003.
pdf
Summary: Discusses transfer of bulk data (not streaming). In order to allow users with various
speeds to participate in the multicast, the multicast is channeled into exponential size channels
where 0 is the slowest. The file is distributed into n chunks(groups) where each packet on each
channel is composed from packets of distinct groups, and the channels are comulative (no
duplication).
Subscription to channel is done acommulatively.
Uses erasure code for k out of n received in case of loss. Invariant to starting time.

B. Cohen, "Incentives build robustness in BitTorrent", P2P Economics Workshop, 2003.
(BitTorrent)
pdf
Summary: presents BitTorrent protocol.

Bayeux: An Architecture for Scalable and Faulttolerant Widearea Data Dissemination.
(Bayeux)
pdf
Summary: Built on top of Tapestry. Multicast groups are hashed into an identifier. Node which
is responsible of that identifier is the root node. Using tapestry support for multicast, routing
is done. A tree topology is used. Did simulations.

L. Cherkasova, J. Lee. FastReplica: Efficient Large File Distribution within Content
Delivery Networks. HP Labs Technical Report HPL200343, Feb. 2003.
(FastReplica)
pdf
Summary: Discuss small groups of nodes 1030 which are fast servers. File is partitioned into n
parts, the source sends in parallel on part to each member, and then the members exchange among
themselves using full mesh. For scalability, a tree of several such meshes can be formed.

D. Kostic, A. Rodriguez, J. Albrecht, and A. Vahdat, "Bullet: High Bandwidth Data Dissemination
Using an Overlay Mesh", Proc. of the 19th ACM Symposium on Operating Systems Principles
SOSP 2003), 2003. (Bullet)
pdf
Summary: in order to improve tree bandwidth, the root node and intermediate nodes sends
disjoints set of data to their children. The children are getting data from tree parent and
allowed to search other peers with disjoint data. Uses TFRC. Constant gossiping of topology. Uses
Runsub for maintenance and node information like current state of the download. Uses bloom filters
for ticketing the data. Has an 10\% packet duplicate avg. 6\% overhead. Did run on Planetlab with
47 nodes.

M. Castro, P. Druschel, A.M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh, "SplitStream:
HighBandwidth Multicast in Cooperative Environments", Proc. of the 19th ACM Symposium on
Operating Systems Principles (SOSP 2003), October 2003.
pdf
Summary: present the SplitStream system. In SplitStream the content is divided into k stripes
and on each stripe a spanning tree of the nodes is built using all the nodes. Suggest k=16 as the
number of trees. In this setting, most nodes are nonleaf nodes in 15 trees w.h.p. Thus load
balancing of nodes and balancing of edge use is obtained. SplitStream is built using the Pastry
overlay and the multicast into groups is done using Scribe. Did simulations
using GTITM model.

Early Experience with an Internet Broadcast System Based on Overlay Multicast
Yanghua Chu, Aditya Ganjam, T. S. Eugene Ng, Sanjay G. Rao, Kunwadee Sripanidkulchai, Jibin Zhan,
Hui Zhang.
pdf
Summary: deployed a video broadcast system which where used totally by several tousand
clients. Support dynamic participation, NAT and firewalls. Basic topology is a tree which is
optimized first for bandwidth and second for delay. Since MDC coding are not supported by players
yet, they used encoder which supplies several encoded rates. Audio is priotorized first, then
lower qulity video and then higher quality video. Used initially TCP and then TFRC. Player used is
quicktime. Encoder used is Sorenson 3. Define quality index as the possible quantity of flows.

Algorithms for High Performance, Widearea Distributed File Downloads
James S. Plank, Scott Atchley, Ying Ding, Micah Beck
Parallel Processing Letters, Volume 13, Number 2, June, 2003, pages 207224
pdf
Summary: Describe the motiviation for data transfer on the grid, which started from the
Logistical Runtime System. In their file system, and exNode contains pointers to the file parts
located at different servers. The task is the download all the stream segments efficiently. Basic
algorithm is composed of several threads downloading simulataneously several file parts and each
finishing thread gets another part to download. The problem is that some of the downloads might
fail. Propose the progress driven redundancy. Intuitively, the progress parameter P is the value of
the segment for the streaming. As more and more future parts from the stream arrive, the missing
part is more critical and thus we allow more threads to try to download it. Tested their algorithm
using several grid sites and different parameters for P and R (the redundancy parameter  how many
threads are allowed to download the
same part).

M. S. Allen and R.Wolski. The Livny and PlankBeck Problems:
Studies in data movement on the computational grid.
In SC2003, Phoenix, November 2003.
Summary: present two problems. The Livny problem states that given k parts of a file
distributed over k hosts the transfer of all files to a centeral location s.t. the maximum number
of file arrive in the minimum amount of time. The PlankBeck problem: given a file divided into k
ordered parts where each segment is found on r replicas, minimize the time necessary to deliver
each segment in order. For the PlankBeck problem, did a simulation of several heuristic
strategies like random, history based and using weather forcast. Experimented using some variants
of the progress driven algorithm.

Y. Chi and K. Nahrsted. Layered PeertoPeer Streaming. In Proc. of NOSSDAV 2003.
Summary: Propose a solution for the ondemand media distribution problem, handling asynchrony
of user requests (user can start viewing the movie in any desired offset) and heterogeneity of
peer network bandwidth. Clients may request streams of different quality based on their bandwidth
constraints. Define the system benefit as the overall strean quality of all peers. System cost is
the server bandwidth consumption. The net benefit is the system benefit exluding system cost which
should be maximized. Formluate the problem as linear programming problem under the constraints
that the number of received layers should not exceed the incoming bandwidth, and the supplying
peer can not output more layers then its output bandwidth. Prove that this problem is NPcomplete
using a reduction from the singlesource unsplittable flow problem.
Propose a basic algorithm using the greedy approach. It maximizes the outbound bandwidth of a peer
with the minimal number of layers. Give an enhanced algorithm where there is a limited number of
supplying peers for each peer.

M. Hefeeda, A. Habib, B. Botev, D. Xu and B. Bhargava. PROMISE: PeertoPeer Media Streaming
using CollectCast. In MM 2003.
Summary: deploy a streaming P2P application over the CollectCast overlay. A requesting peer uses
the underlaying DHT to get a set of candidate peers. The protocol examines the topology of these
peers and runs a selection algorithm to use an active set of peers out of them. The other peers
are a standby set. Once the active set is determined the receiver open several UDP connections to
download the stream and TCP channels for control. Peer selection is based either on endtoend
properties or on topology aware selection which tries to identify shared paths. The topology is
deduced by running traceroute, learning the paths and then infering the bandwidth and loss of
segments in the path. The loss estimation of the path is used for determining the FEC level of the
UDP streams. Did a simulation using 1000 nodes (GTITM topology) and also some Internet experiments
using PlanetLab.
2004

Ying Zhu, Baochun Li, Jiang Guo, "Multicast with Network Coding in ApplicationLayer Overlay
Networks", IEEE Journal on Selected Areas in Communications, January 2004.
pdf
Summary: Topology of 2redundant multicast graph. Each nodes gets two disjoints paths from the
source. Network coding in intermediate leaf nodes is used to increase throughput.
Definitions: individual maxflow, simultaneous maxflow, kredundant multicast graph.
Linear coding multicast: assigns a linear transformation for each edges s.t. the vector send is a
linear combination of the incoming edges of that node. Source can send any vectors. All vectors
are on the same vector space over some base field.
Li and Koetter theorem: for every multicast graph there exists a set of linear codes s.t.
simultaneous maxflow of the graph is equal maxflow of every node.
Algorithm for building the overlay: first, building relatively dense graph of all nodes in the
group (called rudimentary graph). Second, a spanning tree is constructed among nodes where the
source is the root (called rudimentary tree). Third, new edges are added in order to have the
2redundant property. BFS of the tree can be done to find unsaturated nodes.
For deciding which coding to use for each intermediate node, a spanning tree is built from the
root. Nodes who has only 1 incoming edge just forward the stream. Nodes that have 2 incoming edges
do a linear combination of the two edges as decided by the root. Basically they are taking factors
which are prime numbers so any two factors do not divide each other, so any two vectors are
linearly independent.
For performance evaluation refer to the Narada protocol. Using INET topology. Performance metrics
are: session throughput at end receivers, end to end delay, stress, normalized stress (
the ratio of stress over the achievable bandwidth) resource usage (same as in Narada).
Number of receivers is 250.

Tran, Hua, Do. A PeertoPeer Architecture for Media Streaming(Zigzag) In IEEE Journal of
selected areas of communications, January 2004, pp. 121133.
pdf
Summary: Topology of clusters. Multicast tree is built on top of hirarchy of clusters. Divide
responsibility of multicasting and membership management to two nodes. On each cluster the head is
responsible of getting the data and transmitting it to all cluster members. The assistant is
tracking group membership. or vice versa.

Rob Sherwood, Ryan Braud, Bobby Bhattacharjee, "Slurpie: A Cooperative Bulk Data Transfer
Protocol", IEEE INFOCOM 2004, March 2004. (Slurpie)
ps
Summary: Claim that their novelty is in the backoff algorithm used by clients in order to keep
an even load on the source. The load is independent on the number of clients. Another benefit is
that the server does not need to be modified. FTP and HTTP servers can be used. Data integrity
check is done out of band. Designed for bulk data transfer. Links are added and dept for
transferring a small number of blocks. Main objective in creating the topology is minimizing
control overhead and not necessarily network level efficiency. Compared to BitTorrent, the Slurpie
client can adapt to varying bandwidth conditions while increasing or decreasing the number of used
connections. Do not use coding at this stage. The tracker always returns the last x nodes who contact
it. The client connects to a subset of y neighbors, where y is constantly updated based on the
available bandwidth. The neighbors are picked uniformly at random and not by their distance.
y is estimated to be lo(N). On the mesh propagation messages are passed containing, node address,
bitmap of parts and number of hops away. The updates rate can be controlled based on the link
status. The update tree is a tree formed by xoring nodes bitmaps recursively. It is used for
detecting frequency of chunks. (The tree is used only for efficiency). Backing off algorithm: each
round each peer decides with a probability of k/n if to contact the source node. Block size is
256Kb. Each node monitors is bandwidth into tree states: underutilized, atcapacity and throttle
back. Client command line resembles wget interface and is open source project. On the LAN tested
using 48 clients and on PlanetLab tested over 55 clients. Compared it to BitTorrent 3.2.1.
 Wang, C. Jin, S. Jamin, "Network Overlay Construction under Limited EndtoEnd
Addressability" Technical Report CSETR48904, EECS Department, University of Michigan, 2004.
pdf

R. Rejaie and S. Stafford, "A Framework for Architecting PeertoPeer Receiverdriven Overlays",
Nossdav 04, Ireland, June 2004. (PRO)
pdf
Summary: PRO designed for noninteractive streaming applications, mail goal is to maximize
bandwidth. Selfishly determines the best subset of parent peers in order to maximize the
delivered bandwidth. Make a distinction between two key machanisms: PD (peer discovery) and PS
(parent selection). Regarding PD, selection creteria are both relative delay done by some global
network positioning like GNP. Mention that sometimes delay and bandwidth optimization might be
contradicting. Explain why single parent topologies(trees) are not working well. That is because
that if the bottleneck is on the outgoing link of the parent, we need to find more parents. Second,
if the bottleneck is somewhere in the network, more parents will initiate more paths.
Multiple senders will need tight coordination. Delivered segments might not arrive in the right
time. A possible solution is to build multi parent overlay tress. cons are that bandwidth
constraints on the minimal path on the trees creates a bottleneck. It is hard to build separate
trees which will optimize a single creteria like latency. Connections across trees might compete
over same links. Suggest properties for the ideal topology: use unstructured multi parent P2P
overlay. Scalable discovery. Detect bottlenecks across links. Deploy congestion control
connections.
In PRO, PD is done using gossip based approach. PD are needed in two cases, first bootstrapping
where a list of potential nodes are received (sever can do a smart node selection) and
periodically each peer initiates target selection based on some utility function.
Regarding PS, each peer tries to maximize the bandwidth selection of parents (similar to
BitTorrent).
However, if the total parents bandwidth is not sufficient, more parents are added. Parent
selection is characterized to one of the following cases: initial, replacing poorly performing
parent, improvement of performance. When a peer detects correlation between bandwidths of two
parents it tries to replace one of them in case their performance is degraded.

Jin Li, Philip A. Chou and Cha Zhang, Mutualcast: An Efficient Mechanism for Content Distribution in a PeertoPeer (P2P) Network
Microsoft Research, Communication and Collaboration Systems
pdf
Summary: using a fixed network topology, but adapts to changing network conditions by letting
peers with different upload bandwidth to distribute different portion of the file. Each node is
assigned a unique block to distribute. If the source node has more reources, it will distribute
parts itself. In current implementation block size is 1Kb. The network topology is similar to
FastReplica. However, Mutualcast does not seperate distribution and collection steps. The amount
of data distributed by each peer is not fixed. They allow intermediate nodes to help in the
delivery although they do not need the file. Modeled only upload capacity of the bandwidth as the
bottleneck of the network. Did a prototype which worked with one source on four machines only.

M. Hefeeda, A. Habib, D. Xu, B. Bhargava, and B. Botev, CollectCast:
A peertopeer service for media streaming,," ACM/Springer Multimedia
Systems Journal, October 2003.
pdf
Summary: Coolectcast is used for media streaming. While programmed at the application level,
it infers and exlpoits properties of the network layer (topology and performance). Each
session is composed of two sets of senders: standby and active. Members of the two sets can
changed dynamically during the session. Logical components are: topology inference, peer
selection, rate and data assignment, and monitoring. Current implementation is built on top of
pastry.
A streaming session is established as follows. A peer runs a lookup request on top of Pastry to
get a set of candidates which have the movie. The peer runs inference for detecting network
topology to this set of peers. The selection algorithm chooses a subset with best properties. Data
assignment and rate component is called to determine appropriate rate and data portions from each
peer. Data stream is transferred over UDP using FEC, and control channel is implemented over TCP.
Monitoring and adaptation components tracks performance of the session and makes changes in the
sets if needed.
Peer selection policies are random, endtoend and topologyaware. Endtoend technique estimates
the path to the sending peer. Topologyaware infers the underlying topology and infers properties
of segments in the paths. A graph is built where each edge has a wight composed of the loss rate
and aggregate rate of peers sharing this link. Goodness of a peer is a function of availability
multiplied by all segments weights along the path. Regarding data transmission, FEC rate is
determined by the link loss, using Tornado codes.
For inference of topology first a traceroute tool is used to build the physical topology.
Branching points are merged together. No bandwidth is spared for path detection, but data is send
in growing rate using accurate intervals which are measured by the receiving side. The receivers
detects congestion by detecting delays between packets. Sending rate is incremented as possible.
To computer loss rate of path segments inference using Gibbs sampling is done. Transfer rate is
kept below the TCP friendly rate. Simulation was done on top of GTITM with 600 routers and 1000
hosts. Each link has a stochastic error probability, and a random link bandwidth. Loss model is
done using a two state markov model. On each experiment 20 peers are selected at random for the
candidate set. As predicated, topology aware policy works best in terms of time, and random the
worst. PROMISE was run on top of 15 PlanetLab machines.

Tai T. Do, Kien A. Hua, Mounir Tantaoui. P2VoD: Providing Fault Tolerant VideoonDemand Streaming
in PeertoPeer Environment. In proc. of the IEEE International Conference on Communications,
Paris, June 2004
pdf
Summary: P2VoD is P2P architecture for Vod (Video on Demand). In P2VoD clients are grouped
into generation, where each generation is a group of clients which are watching the movie more or
less in the same offset. The generations are chained to form a hierarchical structure. The first
chain is connected to the video server. The server coordinates arrival of peers and decides when
to open a new generation. Each peer chooses its parent in the previous generation either by round
robin (by picking clients which did not server for the longest time) or delay or bandwidth.
Did a simulation using GTITM network of about 100 nodes. Compared their system into P2Cast in
terms of failure recovery or join performance.

S. Birrer, D. Lu, F. E. Bustamante, Y. Qiao, and P. Dinda. FatNemo: Building a Resilient
MultiSource MulticastFatTree. In Workshop on Web Content Caching and Distribution, October
2004.
pdf
Summary: Optimize the Nice system by using the Fat Tree topology from parallel computing where
higher tree nodes have higher bandwidth for supporting faster multicast. By increasing the number
of links closer to the root, a fat tree can overcome the root bottleneck relative to conventional
tree. Leiserson intorduced universal routing network for connecting processors of a parallel
supercomputer where communication can scale independently of the number of computers. The proposed
way for approximating fattrees is an overlay is to place nodes with higher bandwidth closer to
the root. In Nemo, participating peers are organized in cluster based on network proximity. Each
cluster selectes a leader which because a member of a higher level cluster. Coleaders are used for
fault tolerance (they are also called a crew). Coleaders are used also for the data forwarding and reduce the outdegree of
cluter leaders like in Nice. A peer sends a message to one of the leaders for its layer. Leaders
(primary and coleaders) forward received message to all peers in their cluster and up the next
higher layer. For building a fat tree, higher bandwidth nodes are placed closer to the root. Each
cluster members forwards the data and cluster size increases exponentially as one ascends the
tree. Uses a mixed metric of latency and loss rate for proximity estimation. For simulation used
GridG topology which leverages Tiers to generate three tier hiearchical network structure.
To sum up: main differences from Nice: all peers in a cluster are craw members which help forward
the data. Higher bandwidth nodes are neer the root. Clusters are growing in size towards the root.
In other words, the root have an exponential outgoing degree, which is reduced exponentially when traveling down
the tree.

J. Li, PeerStreaming: A Practical ReceiverDriven PeertoPeer Media Streaming. Microsoft Research
Techcnical Report MSTR2004101.
pdf
Summary: present P2P streaming protocol based on MS DirectShow framework. Uses double
encoding: first the video is divided in channels with growing quality. Each channel is erasure
coded using RS variant. Uses TCP for the transport layer. Suggest partial caching of layers where
on each layer a certain percentage of the information is cached. Most important layers have higher
percentage of caching. Each node have fixed generating vectors for applying the network coding.
Other nodes can check the validity of those vectors to verify they are spanning. The client
handles request queue where the request to other peers are allocated in propotion to their
available bandwidth. Requests to failing peers are returned to the key and reassigned.

S. AndroutsellisTheotokis and D. Spinellis, A Surevy of PeertoPeer Content Distribution
Technologies. ACM Computing Surveys, Vol. 36, No. 4, Dec. 2004, pp. 335371.
Summary: details routing mechanisms and DHT topologies, security and incentive mechnisms.
The title is misleading since this paper does not discuss specifically content distribution.

Y. Cui, B. Li, K. Nahrstedt, "oStream: asynchronous streaming
multicast in applicationlayer overlay networks", IEEE Journal
of Selected Areas in Comm., vol. 22, no. 1, pp. 91106, Jan.
2004.
Summary: Addresses the ondemand media distribution problem over overlay networks. Propose to use
buffers at end hosts thus enable what they call AS (asymchroneous multicast). Searn for a spanning
tree called MDT (media stribution tree). Propose two algorithms for joining and leaving the
overlay. Relate to HSM (hierarchical stream merging) algorithm as a reference. Provide both
numerical analysis and simulation results. Do not mention the Stiener tree problem.
2005

X. Zhang, J. Liu, B. Li, and T.S. P. Yum, DONet/CoolStreaming: A Datadriven Overlay Network for
Live Media Streaming, Technical Report, June 2004. (A short version is to appear in IEEE
INFOCOM'05, Miami, FL, USA, March 2005) pdf
Summary: DONet is a datacentric streaming overlay used ofr live media streaming. Unlike
traditional tree based solution, it forms an unstructed mesh where there is no fixed flow paths,
but peers can exchange information based on missing frames. Membership management is done using a
gossiping protocol SCAM. Each node keeps information about the current missing frames in a fixed
future time frame called BM (buffer map). The node continueusly exchange BP with their parters.
Scheduling algorithm decides which frames to take next. They use a heuristic algorithm which
first calculates the number of potential suppliers for each segment. Then segments with only one
supplier are first selected, then with two suppliers etc. In case there are multiple suppliers the
one with the largest available bandwidth is selected. Loaded nodes are allowed to lie in their BM
updates. Implementation is using TFRC. Deployed about 200 nodes on planetlab and check control
overhead based on the number of neighbors and define continuity index which is the percentage of
frames which arrive before their display deadline. Coolsrtreaming is a python client based on
their implementation which was used by 30,000 unique users with a peek of several thousands.

D. Bickson and D. Malkhi. The Julia Content Distribution Network.
In the 2nd Usenix Workshop on Real, Large Distributed Systems (WORLDS '05), Dec. 05', SF, CA.
pdf
Summary: present the Julia content delivery network, based one of the first locality preserving
algorithms, where most of the file parts are downloaded from the close vicinity of the node. Using
both simulations and WAN experiments over the PlanetLab testbed, show a reduced network load while
competing with the stateoftheart BitTorrent protocol.

“Maintaining Highbandwidth under Dynamic Network Conditions”, Dejan Kosti?, Ryan Braud,
Charles Killian, Erik Vandekieft, James W. Anderson, Alex C. Snoeren and Amin Vahdat,
Proceedings of 2005 USENIX Annual Technical Conference, April 2005.
Summary: describes the implementation of the bullet' system which is based on the Bullet protocol.
The bullet' protocol is adaptive to the changing network conditions. Advantages of it that the
number of concurrent connections of each peer is dynamic, the pipeline size used for download in
each connection is dynamic. The rarest part first strategy is used to decide which part to get
next. Information about location of the file parts is disseminated using a control tree. Use a
congestion control algorithm over TCP to improve utilization of the line similar to XCP. The source node is
working in push mode while the other nodes are working in pull mode. Implement source coding and
conclude that it has a minor effect on download speed because of its overhead. Claim the
bulletprime protocol is wokring better then the BitTorrent client over the PlanetLab testbed.
Shotgun is a replication mechanisms building a spanning tree over rsync.
2006

B.G. Chun, P. Wu, H. Weatherspoon and J Kubiatowicz, ChunkCast: An Anycast Service for Large
Scale Content Distribution, In IPTPS 2006.
Summary: Identifies two problems in current content delivery networks related to uploading peer
selection. In BitTorrent type systems
the tracker returns a random set of nodes as neighbors without utilizing their locality
information. In systems like Shark, the clients asks for specific chunks from a directory and try
to optimize the selection from the received set of nodes. In both cases the selection of nodes is
suboptimal. In the later case, the client might change the ordering of requested chunks to get a
better set of uploading nodes.
For improving this situation, they propose a distributed directory approach where client can ask for
a range of chunks from a directory and get a set of the closet nodes which have chunks in this
range. Proximity is measured using a distributed coordinates approach like Meridian or Vivaldi.
ChunkCast was implemented on top of the Bamboo DHT.
For simulations, they used the ModelNet WAN simulator, using INET topology, simulating 180 index nodes
and 200 nodes. Compared three peer selection policies: random, constraint locality (get the
closest set of
nodes for a
specific
chunk)
and ChunkCast policy (get the closet set of nodes for a range of chunks).

B.J Ko and D. Rubenstein. Distributed SelfStabilizing Placement of Replicated Resources in
Emergin Networks. IEEE/ACM transactions on networking, vol. 13, no. 3, June 2005.
Summary: present a protocol for data placement in P2P networks s.t. each node is close to some
copy of the object. Initially, each node selects its own color. Use a color changing rule, where a
non locally stable node tries to select the furthest color possible. This local move is
desireable since it decreases the average distance to a color and surely do not increase the
distance to the furthest color. To prevent oscillations they add a
3way handshake to synchronize color exchanges between nieghbors. Possible applications are
wireless channel allocation, distributed leader election and distribution resource directory.

"BAR Gossip," H. Li, A. Clement, E. Wong, J. Napper, I. Roy, L. Alvisi, M. Dahlin, Proceedings
of the 2006 USENIX Operating Systems Design and Implementation (OSDI) conferenc, Nov 2006.
Summary: model streaming application as an instance of gossip where on each round a
deterministic
set of nodes is contacted (instead of random). The determinism helps prevent free riders that rely
on random encounters. Use signatures and publickey encryption for
enforcing fair sharing. First the ecnrypted data is transferred and last the keys to decrypt the
data are exchanged.
Distributed Hash Tables

M. J. Freedman, E. Freudenthal, D. Mazieres, Democratizing content publications with Coral
Proceedings of the 1st Symposium on Networked Systems Design and Implementation (NSDI 2004).
pdf
Summary: P2P content distribution network which allows a user to run a website with high
performance. Client side is not modified by running simple web browser. Server side is composed of
DNS system which redirects website sites into a modified DNS system which returns locally mapped
proxies or caches which keep the content. One of the nice implementation details is that the DNS
server checks distance to back to the client in order to return answered based on TTL. File
placement in the DHT is sloppy and not absolute. Regarding indexing service nice locality
properties, where the data is first search closely and on increasing distances.

[CAN] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. A scalable
contentaddressable network. In Proc. ACM SIGCOMM 2001, August 2001. (CAN)
pdf
Summary: present CAN network, which is based on a ddimentional cartezian coordinate space on
dtorus. Each node has about 2d neighbors, and path length us O(n^1/d). Routing is done by
picking a node which is closer to the target. Joining is done in some random location where the
existing node splits its responsibility space into two.
Optimizations: tradeoff between the number of dimensions and performance. Routing can be done by
choosing the neighbor with the smallest RTT. Multiple nodes can share the same zone where routing
is done by anycast to anyone of them. Uniform partioning: when a joining node enters, the node it
is joining to is checking the load balancing of its neighbors in order to load balance (and not
imediatly
split into
two).
Landmark based placement: joining nodes try to join the network on coordinates of nodes which are
near them physically. This is done b measuring distances to known landmarks.

[Pastry]
A. Rowstron, P. Druschel, "Pastry: Scalable, Decentralized Object Location and Routing for
LargeScale PeertoPeer Systems", 18 Conference on Distributed Systems Platforms, Heidelberg(D),
2001. (Pastry)
pdf
Summary: Pastry uses circular 128 bit namespace. Each node is assigned a random id. Routing is
done to the node which is numerically closest to the destination. The routing is done by grouping b
bits of information, thus working in base 2^b. Each node keeps a routing table of 128/b levels
with 2^b entries in each level. The expected route length is log2^(N).
Optimizations: for the routing tables, nodes with minimal RTT which match the constrains are
picked.

[Tapestry]
B. Y. Zhao, J. Kubiatowicz, a. Joseph, Tapestry: An Infrastructure for Faulttolerant Widearea Location and Routing UCB Tech. Report UCB/CSD011141. (Tapestry)
pdf

Ion Stoica, Daniel Adkins, Shelley Zhuang, Scott Shenker, and Sonesh Surana. Internet indirection
infrastructure. In Proc. ACM SIGCOMM 2002 Conference SIGCOMM 2002), pages 7388, August 2002.(I3)
pdf
Summary: propose overlay based internet indirection infrastructure (i3) which offers a
rendezvous based communication abstraction. Another level of abstraction is added to the
communication protocol. Instead of sending a message to a receiver, a message is sent to an id,
which represent either a receiver or a group of receiver. The sender might be server senders. In
order to receive message the receiver is sending a trigger to the nearest i3 server. The id object
is 256 bits where a match can be from 128 and up. The i3 system is an overlay network based on
Chord overlay network. Optimization: i3 servers can redirect users to work with nearer servers.
Did a simulation using INET and GTITM topologies with 5000 nodes.

M. A. Zaharia, S. Keshav,
Design Analysis and Simulation of a System for FreeText Search in P2P Networks, unpublished.
pdf
Summary: propose hierarchy in order to support free text search in CDNs. Top layer (0.10.2%
of the
nodes)
are global index nodes connected for example as a Chord network. The nodes map keywords into nodes
in the middle layer. In it 12% of the nodes which store lists of documents by keywords and can do
a search by flooding. Search algorithms are either limited flooding or DHT search. Optimizations:
adaptive flooding: nodes estimates the number of replies and limit the flooding accordingly.
Efficient batch updates: search for several keywords is done by the order they are stored in the
DHT. Topology of the middle network is trying to maximize differences in documents they store.
Delayed publishing is done in order to avoid publishing butterfly clients which disconnect very
fast from the network. Another improvement can be publishing only rare documents into the top
layer since common documents can be found easily be flooding the middle layer. Did simulation up
to 15K users.

S. Rhea, C. Wells, P. Eaton et al. Maintenancefree global data storage", in IEEE Internet
Computing, pp. 4049, Sept. Oct. 2001..
pdf
Summary: distributed storage facility, where routing and search is based on Tapestry.
Includes four mechanisms: a self organizing routing infrastructure, m out of n data coding,
Byzantine update commitment, and introspective replica management. Each object has a unique GUID name of
it's content and fragments using SHA1. Since names are based on the file contents, objects
named by GUIDs are read only. Using Tapestry, object GUIDs are mapped into individual servers.
Uses versioning, where each object can be modified and inserted again into the system. Thus
another level of mapping is used: active GUID, which maps into the GUID of the last version. This
mapping is accomplished by the inner ring, a group of servers working on behalf of the object. The
system builds a mapping from huma readable names to active GUIDs with a hierarchy of OceanStore
servers. The inner ring is protected against f faulty servers using commitment protocols. For
efficiency, reconstructed objects can be cached.

Practical LocalityAwareness for Large Scale Information Sharing.
By Ittai Abraham, Ankur Badola, Danny Bickson, Dahlia Malkhi, Sharad Maloo and Saar Ron.
The 4th Annual International Workshop on PeerToPeer Systems (IPTPS '05).
pdf
Summary: based on the theoretical foundations of Ittai Abraham et. al. we present the Tulip
overlay which has a stretch 2 w.h.p. Each node is using sqrt() links to other nodes in the system
and another sqrt() links to nodes within its vicinity. Route length is 2 hops in almost all cases.

J. Aspnes and G. Shah, Skip Graphs.
Summary: Skip Graphs are a distributed data structure based on skip lists that provides the
funtionaility of a balanced tree while enableing range queries. As in skip list, each node is
member of multiple linked lists. Level 0 consists of all nodes. In skip graph, there could be
several lists at level i. Each list is doubly linked. The node degree is O(logN) and the search time is O(logN) as well.

S. Marti, P. Ganesan, and H. GarciaMolina. DHT routing using social links. In 3rd
International Workshop on PeertoPeer Systems (IPTPS 2004)
Summary: use social links to extended the CHORD overlay. When possible, the social links are
used first. The assumption is that friend peers will forward the messages with higher reliability.
Performance Evaluation

[Ri2001]: Why Gnutella Can't Scale. No, Really, Jordan Ritter, online
publication.
Summary: shows that using exponential flooding, a huge amount of bandwidth is generated and
the network becomes congested very fast.
 Wang, H. Chang, A. Zeitoun, S. Jamin, "Characterizing Guarded
Hosts in PeertoPeer File Sharing Systems" To appear in IEEE Global Communications Conference
(Globecom 2004)Global Internet and Next Generation Networks, Nov 2004, Dallas, USA.
pdf
Summary: measured the prevalance of guarded hsots (hosts behind firewall and NATs in eMule and
Gnutella. Conclusion is that 2536% of the hosts on those networks are gaurded. The percentage of
popluar files which is stored on guarded hosts is about 2530%. eMule
measurements where done by
changing the eMule client, which connects to the server and asks for file suffixes which are
common like avi, mp3, mpg. From that list the 15 highest ranked file are chosen. In Gnutella, they
have used mutella which collects query hit and pong messages. In eMule, the
percentage of guarded
hosts varies a lot between eMule servers since this is configurable by the server.

W. Wang, Cheng Jin, Sugih Jamin, "Network Overlay Construction under Limited EndtoEnd
Addressability" Technical Report CSETR48904, EECS Department, University of Michigan, 2004.
(e*).
pdf
Summary: Design overlay construction called e* for supporting gaurded hosts (hosts behind
firewall and
NATs).
The construction is composed from locality based clusters, where each cluster has a cluster center
and clients. Guarded hosts can only be clients. Cluster center selection is based on capacity and
latency. Shortcut selections adds shortcut between the clusters. Measured eMule network and found
that 34% are guarded hosts. e* algorithm stages: first partitions the hosts into clusters, then
selects cluster center. Cluster centers are connected among themselves to form a backbone.
Shortcuts are added to improve routing.

T. Karagiannis, A. Broido, M. Faloutsos, Transport Layer Identification of P2P Traffic.
In Proceedings of the USENIX/ACM Internet Measurement Conference, Taormina, Sicily, Italy, October
2004.
pdf
Summary: Detect P2P flows at transport layer. Main heuristics are to detect TCP/UDP traffic
flows from the same pairs of computers, and track IP and ports pair which are connected to a lot
of computers. After those two heuristics they do some filtering of email, and DNS traffic. Using
this methods 99.5% of the P2P traffic is identified, with 8% to 12% false positives.

[FHKM04] F. Le Fessant, S. Handurukande, A. M. Kermarrec amd L. Massouli´e, Clustering in PeertoPeer
File Sharing Workloads, IPTPS 2004
pdf
Summary: Search for overlap in file sharing contents between peers by active probing of peers.
Did measurements on the eMule network. Modified ML donkey and connected 12,000 clients which
shared files. 68% are free riders. Checked geographical clusterings of video files and internet
based clusterring (similar groups of files on the same users). Say that future work will be
examining the KaZaA network.

M. Izal, G. UrvoyKeller, E.W. Biersack, P. elber, A. Al Hamra, and L. GarcesErice, "Dissecting
BitTorrent: Five Months in a Torrent's Lifetime", Passive and Active Measurements 2004, April
2004.
pdf
Summary: Analyze BitTorrent over 5 months in download of RedHat 9 (1.7GB) with 180,000 clients
out of them 50,000 in the initial 5 days. Observed that seed contributed twice as leechers.
Average download rate of the whole period is 500Kbps. Divide observed sessions into single,
multiple, seed sessions and incomplete. Single sessions achieved download rate of 1.3Mbps.
Geographical analysis showed that US had 45%, Europe 15%, Australia 13%. Conclude that traffic
volumes are correlated and the titfortar method is working.

N. Leibowitz, M. Ripeanu, A. Wierzbicki, "Deconstructing the KaZaA Network". In proc. of
IEEE Workshop on Internet Applications (WIAPP 2003), June 2003.
Summary: Analyze KaZaA traffic based on Israeli ISP traces.
Capture done using a layer 4 switch which identifies KaZaA traffic.
Identified 50,000 unique users and 300,000 files. Trace consisting of two days.
Conclusions: traffic is highly
concentrated around a small minority of large popular items. 30% of the files remain popular from
day to day. Graph of users connections resembles small worlds.
 T. Karagiannis, A. Broido, N. Brownlee, K. Claffy, M. Faloutsos. "Filesharing in the
Internet: A charachterization of P2P traffic in the backbone". Technical Report, University of
California, Nov. 2003
Summary: Examined several P2P traffic flows done at 08/02 and 05/03. Identified P2P flows by
charachteristic block sizes. Identified FastTrack, eMule, Gnutella, DC, Napster, BitTorrent.
 J. A. Pouwelse, P. Garbacki, D.H.J. Epema, H.J.Sips, "A Mesaurement Study of the BitTorrent
PeertoPeer File Sharing System, Technical Report PDS2004007, Delft University of
Technology.
Summary: Used three tools. First fo connecting SuperNova databse and finding files for
download. Second connects to tracker and find peers. Third contacts peers and get their status.
Average download speed for all peers is 30Kbps. 0.4% of the peers where active for more than 100
hours.

M. Castro, M.B. Jones, A.M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman. An
evaluation of scalable applicationlevel multicast built using peertopeer overlays. In IEEE INFOCOM 2003,
2003.
pdf
Summary: did comparison of hypercube overlay network performance (Pastry) vs. cartezian space
(CAN). There are two options for doing multicast over an overlay: either flooding everyone or
building a distribution tree. Flooding is done in CAN by broadcasting on the dimensions of the
torus. In pastry, flooding is done as follows: the initiating nodes sends the message to everyone
in his routing table which marking of the current level of the recipient. The other nodes forward
the message only the nodes with higher levels. For tree based multicast they use Scribe
approach. (Which uses reverse path forwarding) to build the multicast tree by forming the union of
routes from all multicast destinations to the root. Each group is identified by the group id. The
node which is responsible of the group id identifier is the root of the tree. Optimization: for
decreasing the load, a loaded node can attach requesting node to one of its sons.
(called bottelneck remover).
For simulation used GTITM with 80,000 end nodes. Evaluation criteria: RDP, Link stress, nodes
tress, duplicates. Conclusion: tree based multicast is much more efficient then per groups. Also
the creation of subgroups for doing to multicast is costly. Advantage: only group members forward
the traffic. RDP of pastry is better 20%50% than CAN both for trees and subgroups.

[Borg] R. Zhang and Y. C. Hu. Borg: a hybrid protocol for scalable application level multicast in
peertopeer networks.
In IEEE INFOCOM 2003, 2003(Borg)
pdf
Summary: Suggest improvement for building multicast tree over hypercube overlays. Since Scribe
is using reverse path forwarding (over Pastry), and Bayeux is using forward path forwarding (over Tapestry),
they suggest to combine both techniques and create a hybrid protocol. Forward path multicast
incurs higher RDP, since longer and longer edges are incurred by moving from the root to the
leaves, it is better to have the long edges near the root and not near the leaves. Did simulations
with 64,000 nodes on the Pastry overlay and showed the Bordg achieves lower routing delay which
retaining the lower link stress of the revese path multicast scheme.

Jacky Chu, Kevin Labonte, and Brian Neil Levine, "Availability and locality measurements of
peertopeer file systems," in ITCom: Scalability and Traffic Control in IP Networks. July 2002,
vol. 4868 of Proceedings of SPIE, Proceedings of SPIE.
ps
Summary: measured file names of files stored in the Napster (2001) network and Gnutella
(2002).
Find that both network exhibit locality of files which exhibit log quadratic distribution. The
most popular 10% of the file in Gnutella account for more than 50% of the stored files. The most
popular 10% of transferred file account for over 60% of the total transfers.

P. Rodriguez, E. Biersack, "Dynamic ParallelAccess to Replicated Content in the Internet", IEEE
Transactions on Networking, August 2002 pdf
Summary: Propose a parallel access scheme where users can access multiple servers at the same
time, fetching different potions of the file from different servers and assembling them locally.
Two possible schemes are presented: history based TCP where each client tracks bandwidths of
several servers and choose the best servers from this group where each servers is assigned a part
of the file to upload, and dynamic parallel access where each client contacts all the servers
asking for a small chunk from each. The fastest servers are contacted again in order to fetch more
chunks. Did experiments with 8 mirror sites and file size of 750Kb where parallel access
improves with a factor of 1.58 download time.

Anthony Bellissimo, Prashant Shenoy, Brian Neil Levine, "Exploring the Use of BitTorrent as the
Basis for a Large Trace Repository", Technical report 0441. June 2004
pdf
Summary: Another measurement of the BitTorrent network. Measured 4 monthis (10/2003 1/2004) by using popular
BitTorrent sites. Median file size is 600Mb, sessions length can last for several hours or days.
Mean session length of 13 hours and max session length of 35 days. Good behvaiour in cases of
flash crowds. 10% of the users obtained all the data in only one session. 90% the session
downloaded less than 1 Gb.

Downloading Replicated, WideArea Files  a Framework and Empirical Evaluation
Rebecca L. Collins, James S. Plank
3rd IEEE International Symposium on Network Computing), Cambridge, MA, August, 2004
pdf
Summary: In a Grid settings, each client has to optimize the servers to get the file parts
from. Compare two main algorithms using a simulation. The first algorithm is greedy, where the
client downloads block from random servers using several threads and uses th eprogres of the
download to specify when a block's download should be retries. This is termed progressdriven
redundancy. The second algorithm is downloading from the closest location using timeoutes to
detemine when to retru a download. This is termed bandwidth predication strategy.
Variants of the server selection are: random, forecast (using monitoring to determine the link
bandwidth)
strict load (allows only 1 connection per server), and fasteset which minimized either, download time or a
product of the download time and the server load.
Simulation is done using one client that downloads from 4 different geographical regions a file of 100 MB
divided into 100 parts of 1Mb each. Fastest algoriths performed best.
 Can SelfOrganizing P2P File Distribution Provide QoS Guarantees?, to appear in OSR Special
Issue on SelfOrganizing Systems, 2006.
Summary: run two BitTorrent clients on the same
machine and noticed a large difference in download time. Anazlying the logs found out that only
a small subset of nodes uploaded the majority of the file to the test nodes. The difference in
download time is explained by the stability of the fixed set of nodes. Propose to relate to the
download problem as a stable matching problem.
Modeling and Incentives
 T. W. J. Ngan, D. S. Wallach, and P. Druschel. "Enforcing fair sharing of peertopeer resources".
In Proc. IPTPS 2003, Berkeley, CA, Feb. 2003.
pdf
Summary: Pretty much the same as the below paper. Did some simulations compared to quota
managers which suffers less than 1/3f faulty nodes.

Kevin Foltz, Jehoshua Bruck, "Splitting Schedules for Internet Broadcast Communication," IEEE
Transactions on Information Theory, vol. 48, number 2, February 2002, pp. 345358.
Summary: discuss how to transmit information from a server to many clients using a broadcast
disk. Propose splitting the information into smaller pieces to gain better shcdules with lower
expected wiating time. Dicuss the case of two items at the same length where both item are split
into two.

T. W. Ngan, A. Nandi, A. Singh, D. S. Wallach ,P. Druschel
"On designing incentivescompatible peertopeer systems" 2nd Bertinoro Workshop on Future Directions
in Distributed Computing (FuDiCo 2004), Bertinoro, Italy, June 2004.
pdf
Summary: Propose two mechanisms, one for storage and one for network bandwidth sharing.
Regarding storage, count on digital signatures and public keys. Each node maintains a list of
all the files he stores for others and all the files stored for it remotely. Other nodes keeps constant
probing of those lists. If the remote list is shrink ed, remote nodes will delete it's files. If
the local list is expanded, nodes which supposed to be keeping files at this node will be probed.
Content of the node's files is also verified using challenge mechanism. About network bandwidth,
credit is maintained either by a couple of nodes which transfer data mutually, or by doing some
transitive paths.
 X. Yang and G. de Veciana, "Service capacity of peer to peer
networks", in Proc. IEEE INFOCOM 2004.
pdf
Summary: Analyse flash crouds arrival model. Divide it into two phases: transient ragime where
the system is server constrained and service capacity is increased exponentially. Second phase is
the steady state where service capacity depends on fluctuations in demand.
 [VY03] G. de Veciana and X. Yang, "Fairness, incentives and performance
in peertopeer networks", in Proc. Allerton Conference on Communication, Control and Computing, 2003.
pdf
Summary: Consider service capacity of P2P file sharing to demands user cooperation and
supplying incentives to cooperate. Divide download to 2 parts. First is the transient regime,
where a flash crowd is accessing the file and the service capacity is increase exponentially.
This stage is modeled by branching processes. Calculate average latency in getting the file  very
similar calculation to Julia  logarithmic in the number of participants. Multi k parts speed up download with a factor of k.
For the steady state regime, develop a markovchain model which is analyzed numerically.
Suggest several modelings of fairness. First is that each peer will get the exact service capacity
from the network as it gives (hard to maintain). Second, dual exchanges. Third, credit with
parameter of epsilon.

Ahsan Habib, John Chuang "Incentive Mechanism for PeertoPeer Media Streaming," International
Workshop on Quality of Service(IWQoS) pp. 171180, June, 2004.
pdf
Summary: propose a rankbased peer selection for P2P media streaming. Each user contribution is
mapped into a score which is mapped into a percentile rank. Initially, each peer has a score of
zero and gets a best effort service. Based on the data served a peer starts to earn score. Example
of a score function is the upload to download ratio (which they claim used in KaZaA). Did
simulation using GTITM topology and evaulated their scheme also on PlanetLab using 18 nodes. The
problem with this approach is that there are no mechanisms to verify that the peers are not lying.
 D. Qiu and R. Srikant. "Modeling and Performance Analysis of BitTorrentLike PeertoPeer
Networks", In Proc. of the ACM SIGCOMM 2004, Portland, Oragon.
Summary: Develop a simple deterministic fluid model. Add to [VY03] possibility for nodes to
leave before download is completed and also bandwidth constraints. Some insights: the average
download time is not related to the arrival rate. Define an effectiveness of sharing which is the
probability to have a certain part of the file out of the k neighbors assuming a random
distribution of parts. Analyze also fair sharing behavior, and decide that a free rider can get
20% of the possible maximum download rate.
 Zongpeng Li, Baochun Li, Dan Jiang, and Lap Chi Lau, "On Achieving Optimal Endto
End Throughput in Data Networks: Theoretical and Empirical Studies", ECE Technical Report,
University of Toronto, February 2004.
pdf
Summary: Investigate upper and lower bounds for optimal end to end throughput for single
multicast session using network coding. Show that finding optimal solution can be done in
polynomial time. Extend the results to multiple sessions of unicast multicast and broadcast.
Conclusion is that on most topologies network coding will not improve optimal throughput but will
make the solution for finding the throughput easier. Paper explains well theoretical background of
max network flow. Steiner tree: a subtree of the network which connects every multicast node.
Steiner packing tree problem decomposes the network into weighted Steiner trees such that the
total of three weights is maximized. The total weight of trees using a common edge should not
exceed the edge capacity. A solution of this problem achieves optimal bandwidth. However, the
problem is NPhard. Network coding in directed networks reveals that if rate x can be achieved for
each receiver of the group independently, it can be achieved for the whole group as well. This
theorem is not valid on undirected networks. We define a partition of the network as one that
have one source or receiver at each side of the partition.
The steiner strength of a graph is the min of all partitions of the cut capacity divided
by the number of components in the partition minus one. Prove that the optimal throughput is more
than the steiner packing number and less than the Steiner strength. For solving the optimal
throughput suggest formulation of linear equations.

P. A. Felber, E. W. Biersack, "Selfscaling Networks for Content Distribution". In
SelfStar: International Workshop on Self* Properties in Complex Information Systems, 2003,
Italy
pdf
Summary: Did simulation of cooperative network. Node selection policies include random, least
missing most missing and adaptive missing (nodes with less contact nodes with more parts and vice
versa). Chunks selection of random and rarest. Do not
distinguish between source and node policies. Nodes arrival either all at the start or flash crowd
using poisson dist. Peer either disconnect immidialty or wait 5 minutes before disconnecting.
Links are either symmetric or assymetric.
 E.W.Biersack, P. Rodriguez, and P. Felber, "Performance Analysis of PeertoPeer Networks for File
Distribution", QOFIS 2004, Barcelona, Sept 04
Summary. Derive an upper bound for the number of served peers at time t for three topologies:
linear chain, tree, krooted trees. Assumptions: all peers including source node have equal rate
b. There are C chunks. Time needed to download the complete file at rate b is 1.
At the linear topology, the number of peers get served is roughly C*t^2. If N/C is very small, the
time is 1+epsilon. For N/C=1, the time about 2. For N/C very big the time is about
sqrt(N/C).
Regarding tree topology, server sends to k connected nodes using b/k bandwidth. Latency of the
tree is k(1+logk(N/k)1/C)
In PTree the time is 1+log(N)(k/C)

J. Mundinger and R.R. Weber, "Efficient File Dissemination using PeertoPeer Technology"
Technical Report, Statistical Laboratory Research Reports 200401, 2004.
pdf
Summary: Making connections to the 'broadcast problem' show a solution and lower bound where
all upload capacities are equal. Carry simulations to assess the performance of randomized
algorithm instead of algorithm which is based on global knowledge, and show that the randomized
algorithm has only 10% latency. Lower bound where all upload capacities are equal to 1, is T = 1
+log(N)/M. Where M is the number of parts. The proof is simple  since to get the complete file
out of the source we need 1, and to get the last part got out we need another logN. Consider two
scenarios, one with a full knowledge of nodes but without the knowledge of their parts, and the
other it a knowledge of nodes who already contacted the source. Did a simulation for various
values of M and N (exponents of 2) and did curve fitting using Markov chains.

D. Bickson, D. Malkhi and D. Rabinowitz.
Efficient Large Scale Content Distribution. In the 6th Workshop on Distributed Data and Structures
(WDAS 2004), Lausanne, Switzerland.ps
Summary. Present the Julia content distribution protocol which is motivated by reducing Work 
the number of bits multiplied by the link distance which is summed over all links.
The algorithm is based on the butterfly
network where in each round the number of file parts exchanged between two nodes is doubled, and
the link used is half the distance. Model several other protocols like SplitStream, FastReplica
and apllication multicast tree. Show that the protocol reduces work and running time regarding all
of the above protocols.

[NCR+03] T. S. E. Ng., Y. H. Chu, S. G. Rao, K. Sripandkulchai, H. Zhang, "Measurementbased
optimization techniques for bandwidthdemanding peertopeer systems, in proceedings of IEEE
INFOCOM 2003, SF. Apr. 2003.
pdf
Summary: peer selection strategies is one of the complicated problems in CDNs dues to the
extreme heterogeneity in the P2P environment.
In this paper, the authors examine a combination of several leight weight
probing techniques like RTT, 10Kb TCP transfer and bottleneck probing for combining a more
successful prediction of peer selection in CDNs. By conducting trace based analyses, they conclude
that those basic techniques can achieve 40 to 50% optimal performance. However, for adaptive
overlays that can constantly change the selection of peers, the basic techniques can do much
better. 80% optimal peer can be selected by just examining 5 candidates. A simple combined
technique can boost performance up to 60% of the optimal.
Performance metrics used for file sharing are OR (optimality ratio) which is the rate between the bandwidth using
the peer picked then that of the optimal. For application layer multicast another measure is the
convergence time, which is the time the topology needs in order to converge to a stable state.
Traces where collected using the OpenNapster network in 20012. They sampled 10,000 peers using 4
data collection nodes in CMY, UIUC and others. The client is based on a Linux OpenNapster client,
to log into servers, find common files, and download 500Kb of data from the found nodes. The
light weight techniques for probing other nodes is RTT probing (using ICMP ping), transfer of
10Kb of data, and BNBW probing using Nettimer.
Regarding RTT probing, they note that latency is divided into two: the first hop and the rest of
the path.
Doing simulations, they show that by using the above techniques (for nonadaptive networks) about 4050% optimality is obtained.
Regarding adaptive networks, the combine the three techniques together to first eliminate slower
nodes and then try to chose from the remaining.
Regarding file sharing they assume the entire file is donwnloaded from the same node. They
proposed "joint ranking" where the peers are tested for each technique, the "grades" are summed
up, and the peer with the highest grade is chosen. They note that 73% of the time, combine
technique can rank the best 5 candidates either the best or second best. Only in 44% of the time,
it ranks the best candidate at the top.
For multicast streaming, they extended Narada systems and used 29 hosts spread geographically.
As expected, the combined ranking achieved the lowest convergence time.
 Z. Ge, D. R. Figueiredo, S. Jaiswal, J. Kurose, D. Towsley, "Modeling PeertoPeer file
sharing systems, In Proceedings of IEEE Infocom 2003 SF, Apr. 2004.
pdf
Summary: Main paper goal is to evaluate performance issues of file sharing systems. They
divide the systems into tree: centralized indexing, distributed indexing with flooded queries
(Gnutella) and distributed indexing with hashing directed queries. Main results: not surprisingly
flooding of limited scope queries has negative impact on system performance. Freeloaders does not
have significant impact of performance.
Model: class close queueing system, several classes of nodes, which can be either on line or
offline. The common services component of the system is abstracted by having a single server
queue represent query processing. A single server queue is associated with each file (in order to
district
different
service
capacities of
files).
The used probability distribution for distributing the files in the system is the Zipf
distribution. In it, Pj is proportional to 1/j^alpha. Did simulation which is a bit unrealistic
since they assume that average file size is 3.5Mb and avg. links is 200Kbps. Simulation results
are as expected central server has limited capacity, and distributed indexing using hash has much
better performance. Assumes that distribution of files and queries is both based on Zipf dist. For
creating a more realistic scenario, did a mismatch between probabilities. The result is that
performance drops if the most requested files are not highly replicated.

K. P. Gummadi, R. J Dunn, S. Saroiu, S. D. Gribble, H. M. Levy, J. Zahorjan,
Measurement, Modeling and Analysis of a PeertoPeer File Sharing Workload, In proc. of ACM SOSP 2003.
Summary: Analyzed 200 day trace of over 20Tb of KaZaA P2P traffic collected at the university
if Washington. Develop a model of multimedia workloads, explore the impact of locality awareness
is KaZaA. Analyze the peers behavior and compare it to Zipf's law.
Regarding the KaZaA traces, capture one way traffic: outgoing requests to external peers. Capture
the download HTTP traffic which is unencrypted. Regarding users, the deduce that KaZaA users are
patient. For small objects, 30% of the request take over and hour and 10% nearly a day. For large
objects (> 100Mb), 20% of the request take a week or more. Average session lengths are
typically small (in other words the client is idle most of the time). The media session length is
2.4 minutes. The median client was only active about 5% of the time.
Objects workload is divided into two, small objects and large. Since objects are files which never
change, most of the clients will download an object only once (94% once, 99% twice or less). This
differs a lot from web traffic where sites are accessed frequently. The popularity of file is
mostly short, only for large files there was some overlap. The most popular objects are recently
born objects. Old objects are objects which are more than 1 month in the network. 72% of the
request are for old objects for large objects and 52% of the small objects are for old ones.
Discuss the difference between file popularity and Zipf's law. Refined Zipf's probability to be
a fetch once probability. The results are very close to reality.
Argue that new files arrival improve the hit rate of the network, where new arrival of clients
cannot compensate of the for the hitrate penalty of aging clients.
Regarding locality, deduce that a proxy cache would reduce outgoing traffic in 86%. Because of
legal issues propose redirection of queries which performs with 68% hitrate of lo and 37%
hitrate of so. Highly available peers tend to consume more bandwidth and thus both necessary and
sufficient for obtaining high hitrate.

J.A. Pouwelse, P. Garbacki, D.H.J. Epema, H.J. Sips,
The Bittorrent P2P Filesharing System: Measurements and Analysis,
4th International Workshop on PeertoPeer Systems (IPTPS'05), Feb 2005.
pdf

"MACEDON: Methodology for Automatically Creating, Evaluating, and Designing Overlay Networks",
Adolfo Rodriguez, Charles Killian, Sooraj Bhat, Dejan Kostic, and Amin Vahdat, Proceedings of the
USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004), March 2004
pdf
Summary: MACEDON is an infrastructure for specifying distributed algorithms and generating
code which implements them. Algorithm behavior is specified in terms of event driven finite
state machine and transitions indicating actions to take in case of events. Using this
infrastructure it is easier to compare and develop distributed algorithms. MACEDON creates C++
that runs on Linux or on top of ModelNet network emulator. Among the provided statistics for
overlay evaluation is RDP, communication overhead and stretch. Implemented algorithms/protocols
consists of Nice, Bullet, Chord, Overcast, Pastry , Scribe, SplitStream and others.

Kunwadee Sripanidkulchai, Aditya Ganjam, Bruce Maggs, and Hui Zhang
The Feasibility of Supporting LargeScale Live Streaming
Applications with Dynamic Application EndPoints, In Proc. of SIGCOMM 2004, Portland, Oregon,
Sept. 2004.
pdf
Summary: The authors examine 3 key requirements for feasability of streaming video: are there
enought resources, can the topology be maintained given the network dynamics, can an efficient
overlay be constructed. The analysis is based on logs taken from Akamai over 3 months at the end
of 2003 using three popular formats: QuickTime, Real and Windows Media. Streams where classified
into audio (below 80 kbps) and otherwise as video. Regarding the video, two categories where used,
nonstop events (like a radiostation) or short duration events. Only large scale streams (above
1000 users where used in the analysis). For checking the resource, outgoing bandwidth estimation
was done using results from speed tests (www.broadbandreport.com), aggregated groups of IP hosts
where probed, EdgeScape product of Akamai is used to estimate link bandwidth as users report it by
configuring the software, and host DNS names where evaluated. Using all 4 above techniques 90% of
the hosts where bandwidth identified. Used resource index metric which is the overall bandwidth
demand to supply ratio. Traces where playbacked using either a tree or a multiple trees
protocols.
Regarding stability several parent selection methods where tested: oracle, uptime, min depth and
random. As expected oracle is the best and afterwards min depth. Multiple trees are better for
fault tolerance but overall events of failures is growing higher.
Regarding efficiency clustering methodsof network delay (using GNP) and geographical distance
where compared. Evaluation metric was avg and max intra cluster distance. As expected best
clustering was done using GNP, then greographical and then no clustering.

Chip Killian, Michael Vrable, Alex C. Snoeren, Amin Vahdat and Joseph Pasquale,
The Overlay Network Content Distribution Problem. Technical Report CS20050824 USCD, May 2005.
ps
Brief Announcement in PODC 2005 pdf
Summary: provide a formal problem statement for the content distribution problem.
The bandwidth is modeled using unit sized tokens. Tokens start at one or more nodes, and the goal
is to transfer them to a set of receivers. The h (have) function denotes the initial distirbution
of parts in the networks, and the w (want) function inidiates which tokens each node would like to
get eventually. A timestamp is an algorithm round and a scheduale is a serias of rounds from the
starting state (have) to the desired state (want). Define the Fast Overlay Content Distribution
problem ( OCD) to be the answer to the question is a scheduale of minimal length t exists. Prove
that this problem is NPComplete using a reduction from the dominating set problem.
 L. Massoulie and M. Vojnovic. Coupon Replication Systems. In Sigmetrics 2005. June
2005.
Summary: Based on the works of Srikant and Veciana extend the modeling of system P2P content
distribution network behaviour. View the CDN as a coupon replication systems, where a set of users
would like to complete a collection of distint coupons. Divide CDN into two: open systems where
users are constantly joining and closed systems where the set of nodes is fixed. In open systems
discuss cases of users which exchange coupons with users with the same number of coupons or with
random users. Users are assumed to leave the network when finished. Results suggest that
performance of CDN does not depend on either altruistic user behaviour or on load balancing
strategies as rarest first. The exchange between random users or users with the same number of
coupns does not significantly change system performance.

R. Bindal, P. Cau, W. Chan, J. Medval, G. Suwala, T. Bates and A. Zang. Imprvoing Traffic Locality in BitTorrent via Biased Neighbor Selection.
in ICDCS 2006
Summary: propose to improve the BitTorrent tracker by returning a majority of local nodes,
reducing
cross ISP traffic.

A. Legout, G. UrvoyKeller, and P. Michiardi. Rarest First and Choke
Algorithms Are Enough.In Proceedings of ACM SIGCOMM USENIX IMC'2006, October 2527, 2006, Rio de
Janeiro, Brazil.
Summary: shows what we know  that the BitTorrent algorithm is working very efficiently on
practice.
Deployed systems

Y. Kulbak, D. Bickson, The eMule protocol specification, Hebrew University
Technical Report TR200503, January 2005.
pdf

Clip2, The Gnutella Protocol Specification, version 1.2
pdf

[BS2004] An Analysis of the Skype PeertoPeer Internet Telephony
Protocol, Salman A. Baset and Henning Schulzrinne, unpublished 2004. (Skype)
pdf
Present a reversed engineered research of the Skype network. It seems that the overlay
resembles KaZaA where there are hierarchy of supernodes. An ordinary host must be connected to a
supernde to get service. Skype login server is a server which is responsible of storing all
usernames and passwords. It seems that Skype is using a variant of the STUN protocol for
connecting behind NATs and firewalls.
The client is listening to several ports, TCP, UDP, HTTP and HTTPS. A host cache is saved on the
registry which is a list of other supernodes. Buddy list is also stored in the registry. For end
to end encryption Skype is using AES with keys of 256 bits. Skype client can not prevent itself
from becoming a supernode.
For experimenting they places several clients some of them behind firewall or NAT. For the first
time after installation, the clients send an HTTP request for the Skype login server. It seems
that the Skype client is trying to connect to superndoes with any of the above protocol which
succeeds. There are several bootstrap supernodes which are contacted after the successful login.
It seems that the user search is very efficient and clients always succeeded in finding other
clients. For call setup, if both users have a publish IP and are in the buddy list of each other,
the call is initiated directly between the parties. In case any node is behind firewall, some
supernode is forwarding the call information. Supernode is able to transfer data and control
either over UDP or TCP based on the node properties. The average transfer rate is about 5Kbps,
using 140 packets. There is no silence suppression, constant flow is kept even in silence
periods. For conferencing, a middle node is used as a mixer of both channels. Using several
remote computers evaluated Skype void quality as better than MSN and Yahoo messenger.

Simson L. Garfinkel, VoIP and Skype Security.
pdf

Analysis of Skype security using reverse engineering  by BlackHat Europe
pdf

S. Guha, N. Daswani, and R. Jain. An experimental study of the Skype peertopeer VoIP system.
In IPTPS, 2006
Summary: provide some details regarding the sessions lengths and peer interarrival times using
Skype. Recorded traffic for several months in late 2005 in Cornel.

A. W. Moore and D. Zuev. Internet Traffic Classification using Bayseian Analaysis Techniques.
In SIGMETRICS 05'.
pdf
Summary: the goal is to classify interent traffic to several classes like WWW, P2P, Games etc.
The proposed method is using Baysian method where the hidden variable is the class type. Using
traces they compute the prior probability for each class. That is why this paper uses supervised
learning since some of the traffic was classified by hand. Besides of using the naive Bayes
method, the use KDE (kernel density estimation) for approximating f(.c_i) of the descriminators
(isntead of approximating it by a Gaussian). Example descriminators are flow duration, TCP port,
packet interarrival time, effective bandwidth etc. Used the WEKA software for calculating KDE and
FCBF.
However, increasing the complexity in the
description of descriminators complicates the problem. For filtering important descriminators from
unimportant one they use FCBF filtering.
A list of descriminator used for traffic classification is found here:
pdf

J. Erman, A. Mahanti and M. Arlitt. Internet Traffic Identification using Machine Learning. In
Globecom 06'. pdf
Summary: propose to use unsupervised learning, using clustering techniques. Use an
implementation of EM called AutoClass.

J. Erman, M. Arlitt and A. Mahanti. Traffic Classification using Clustering Algorithms. In
Workshop of Mining Data, SIGCOMM 06'
pdf
Summary: propose to classify traffic using two clustering algorithms KMeans and DBScan.
Unlike the classification work of Moore (SIGMETRICS 05') they use unsupervised learning. Use
Euclidean metric for calculating the distance between data points.
Network positioning

A lightweight approach to network positioning(Meridian)  Wong, Sirer
Summary: Loosely structured overlay networks, does not use network embedding but relative
direct measurements. Each node keeps track for a fixed number of other nodes in exponentially
increasing radii. Justify this categorization using 4000 pairs of nodes calculation of distances
using King method. In each ring a geographical diversity is obtained. Routing is done while
increasing half the distance to the target. Did implementation in planetlab. Median error on
position is quite low relative to other techniques. Support firewalls.

K. Gummadi, S. Saroiu, S. Gribble, King estimating Latency between Arbitrary Internet End Hosts,
In Proceedings of the SIGCOMM Internet Measurement Workshop (IMW 2002).
Summary: present a tool which can measure latency between any two end hosts using DNS query
between their two local DNS hosts. The main insight in King is using existing infrastructure in
unanticipated way. The measurement from A to B is done by A issuing a recursive DNS query to
DNS_A, DNS_A forwards the query to DNS_B ad the time is measured. The time from A to DNS_A is
sabstructed to have an estimate between DNS_A and DNS_B which should represent accurately the
latency between A and B. Checked accuracy of the technique using 16K Napster clients and 8K name
servers.

P. Ganesan, Q. Sun, and H. GarciaMolina, "Apocrypha: Making
p2p overlays networkaware", Tech. Rep., Stanford University,
2003.
pdf
Summary: Uses swaping of nodes, in order to improve heuristically the network structure. Each
nodes probes periodically another random node and check if a swap will imrpove average cost of
links to swapped neighbors.

[CCR+2004] PIC: Practical Internet Coordinates for Distance Estimation,
Manuel Costa, Miguel Castro, Antony Rowstron, and Peter Key,ICDCS 2004.
(PIC)
Summary: PIC stands for practical coordinate based mechanism to estiamte network distances.
Unlike GNP, it does not require infrastructure nodes, and it can compute coordinates even when some
of the peers are malicious. PIC maps each node to a paint in a ddimensional Euclidian space. When
a node joins in, it probes the distance to a set of landmarks L, where L size is at least d+1
members. It uses a multidimensional global optimization algorithm (e.q. Simplex downhill) to
compute its coordinates s.t. that errors in the L predicated distances are minimized. The probe
can use ICMP, application level RTT, or hops numbers. Unlike GNP, it does not use a constant set
L. It can peek any node with already computed coordinates. Authors discuss random and closest
methods and hybrid which is using both. The utility function is the sum of sqaures of relative errors (unlike Vivaldi where it the
sum of non relative errors).
For the simulations, they used GTITM, Mercator, a topology of about 100,000 nodes obtained by the
mercator system, CorpNet which is a topology of the ms corporate network. Experiments used 8
dimensions and 16 landmarks. Hybrid strategy got accuracy results similar to GNP. Discuss how to
find closest node to a node without global knowledge. Suggest using random strategy, having rough
coordinates, searching close nodes using the coordinates and not the probing in order to save work
and finally using the hybrid strategy to refine results. Used M Pastry for the overlay.
Devised a security test to eliminate malicious nodes based on eliminating nodes which do not hold
the triangle inequality.

[Vivaldi] F. Dabek, R. Cox, F. Kaashoek, R. Morris, Vivaldi: A Decentralized Network Coordinate System,
In Proc. of SIGCOMM 2004.(Vivaldi)
pdf
Summary: Vivaldi is a simple lightweight algorithm that assigns
synthetic coordinates to
hosts s.t. the distance between the coordinates of two hosts accurately predicts the communication
latency between the hosts. The main idea is to use physics spring model, where each host is
influencing a small group of other hosts. The spring system tries to maintain some equilibrium
of a minimal system energy. Algorithm goals are finding appropriate metric space, scalability,
decentralized implementation, minimized probes traffic, and supporting dynamic network changes.
Coordinate space includes a notion of height that improves prediction based on real Internet data
sets. Did simulation including 1740 hosts based on real measurements and achieved low error rates
like GNP.
The utility function is sum of square errors between the prediction and the real data. Given this
sum of errors E, simulating a network of physical springs produces coordinates which minimize E.
The minimization places a spring between each pair of nodes which the rest length set to the real
RTT. The potential energy of such a spring is proportional to the square of the displacement from
its rest length which is exactly the function E. The force of a spring from i to j Fij is defined
to be Fij = (Lij  XiXj)*u(xixj). Where the first quantity is the displacement and the
second is the direction of the force. The total sum of a force Fi is the sum over all Fij where j
are i's neighbors. The algorithm step is moving each node Xi a small distance in the coordinate
space in the direction Fi, and then calculating Fi again. Xi = Xi+Fi*t where t is the length of
the time interval. A main parameter of the algorithm is the time step t (called delta). t which is
too large will cause oscillations, where too small t will converge very slowly. Their method is to
have delta based on how to node is sure about its coordinates. At the joining of a new node, its
coordinates are not accurate, so other nodes will take a small delta towards it. And vice versa.
This time step is implemented by taking the ratio between the local error and sum of local and
remote errors. EMA is used for giving higher value to newer samples.
Simulations are based on both PlanetLab full mesh latency measurements and both on DNS estimations
of 1740 nodes using the King method. They also used a grid and GTITM topology. Simulation show
fast convergence when using the changing delta. They also discuss that sampling only close nodes
might lead to skew coordinates and several far nodes should be chosen. Unlike GNP, no landmarks
are needed.
They discuss also a model selection of coordinates with heigts which help to model access links
like cable modem or ADSL with relatively high first hop.
Topology

Ellen W. Zegura, Ken Calvert and S. Bhattacharjee. How to Model an Internetwork. Proceedings of
IEEE INFOCOM 1996, San Francisco, CA. (GTITM)
ps.gz
Download software
Fixed compiling version for linux

C. Jin, Q. Chen, S. Jamin, Inet: Internet Topology Generator University of Michigan Technical
Report CSETR43300. (INET) pdf
Download v. 3

A Better Model for Generating Test Networks, M. Doar, IEEE Global Telecommunications
Conference/ Globecom 1996, London, November 1996. ps
Download Source code for the TIERS random
network topology generator ver 1.1 tar.gz

"Medusa  New Model of Internet Topology Using kshell Decomposition," Shai Carmi, Shlomo
Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir. condmat/0601240
Summary: present the Medusa model of Internet topology based on the DIMES project
measurements.
Error Correcting Codes, Source Coding and Network Coding
1989

M. O. Rabin, Efficient Dispersal of Information for Security, Load Balancing,
and Fault Tolerance. In Journal of the ACM, Volume 38, pp. 335
348, 1989.(IDA)
Summary: In the first part of the paper, the author suggest an encoding scheme of m out of n,
using m independent vectors which create a linear combination of each file part.
A file is divided into N parts. Each part is considered as string of residues in Zp.
m is selected which n=m+k satisfies n/m < 1+epsilon. Chose n vectors ai in Zp^m which every
subset of m vectors is independent. (Or with high probability). The encoding is done by
multiplying*(F1)=(C1). The decoding is done using (F1) =^1 * (C1). Several methods are
proposed for chosing the independet vectors Ai. Either by taking vandermonde matrix lines, or
chosing two vectors x and y which each i xi+yi is not zero, and for different i and j the values
of x and y are different. Then we calcaulte a fields to be 1/(ai+b1) for each i.
In the second part, the author suggest a routing scheme over n dimensional hypercube which
creates n disjoints paths for the data in order to overcome failures. The IDA encoding technique
is used for protect the data.
1993

G. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon limit
errorcorrecting coding: Turbo codes, in Proc. 1993 Int. Conf. Commun.,
Geneva, Switzerland, May 1993, pp. 10641070.
Composed of two simple encoders taking a block length of k, creating inetrleaving output
simbols at rate R=1/2. The advantage is that the input is permuted before it is inserted to the second
decoder. The permutation enables avoiding lowweight codewords by creating highweight codewords
by the other decoder. Gain performance of random block codes. Decoding is done using the
alphabeta algorithm which minimizes of the bit error rate (and not the word error rate as in
Viterbi).
1995

D. J. C. MacKay and R. Neal, Good codes based on very sparse matrices, in Proc. 5th IMA Conf.
Cryptography and Coding, C. Boyd, Ed. Berlin, Germany: Springer Lecture
Notes in Computer Science, vol. 1025, 1995, pp. 100111.
ps
Summary: present a family of error correcting codes for the BSC. The codes are designed for a
sparse source. Generaly linear codes are build of NxK matrices where NK extra bits are for
redundancy. Since the source is redundant, we no longer need N>K. The symbols rate is defined
to be K/N. Information rate is K/N, where fs is the source redundancy. The encoding is done
t = [Cn^1Cs]s . received r=t+n . The deocding is done by first
z=Cn*r and then solving Ax = z. Propose two possible ways for the decoding: either by
free energy minimazation or by BP. It can be proved that those codes achieve the Shannon limit.

J. Blomer, M. Kalfane, R. Karp, M. Karpinsky, M. Luby and D. Zukerman, An XORbased ersure
resilient coding scheme, Technical Report TR95048, Internation Computer Science Institure,
Berkley, 19995.
Summary: one of the first implementations of erasure codes using 32 bit words and the XOR
operation (instread addition in GF(2^32)). Use Couchy matrices that provide MDS (maximum distance seperatable) codes, which means
that any n out of n+r coded words are enough to decode the original message of size n. The Couchy matrices
are useful since any submatrix has a non zero determinant, which means it is reversible. The
reversible matrix is used for decoding. A fast reverse matrix is computed using an application of
the Kramer rule.
1996

A. Albanese, J. Blonder, J. Edmonds, M. Luby and M. Sudan. Priority encoding transmission. IEEE
Trans. Information Theory, 42:17371744, Nov. 1996.(PET)
Summary: In PET, the user specifies a priority value for each part of the message. Based on
this priorities the system encodes each part of the message for transmission. The priority
parameter of each part determines the fraction of encoding packets sufficient to recover that
part. This technique can be very useful for video multicasting since the different types of frames
used in MPEG have different importance. I frame can be displayed indepenedently of other frames. P
frame and B frames are incremental updates to the previous and next frames  so they can be
encoded with lower importance.
In a PET system, the priority function p defines what is the precentage of the received messages
(out of n) are needed to decode a certain message word. The encoding is done by first partitioning
the message into blocks baed on the priority function p and then encoding each block seperatly by
an erasure code with different properties. The total encoding length is called the grith, which is
the sum of one over the different priorities. Show a way to overcome rounding erros when the
prioirties do not sum up nicely.
1998

John W. Byers, Michael Luby, Michael Mitzenmacher, and Ashutosh Rege, "A DigitalFountain
Approach to Reliable Distribution of Bulk Data", In proc. of the ACM
SIGCOMM 1998.
ps
Summary: describe an ideal and scalable protocol which is intended for distribution bulk data
to a large set of receivers. A digital fountain approach allows users to aquire the data at the
time of their choosing where clients vary in network speed in links vary with loss
characteristics. A digital fountains injects a stream of distinct (and possibly infinite) encoding
packets into the network, the source data can be reconstructed by the clients from ANY subset of
the encoded data. Tornado codes are based on two bipartite graphs, where the first column is the
actual code, and 24 columns are bipartite graphs. The graphs are representing XOR of input
symbols. A method of interleaving can be used for sending blocks from subsequent packets by their
order. For allowing multicast groups with different rates, a layered (or pyramid) multicast is
used which each layer can be subscribed accumulatively by the client. Did simulations with film
size of 2MB, divided into 8264 packets of 500 bytes. Packets header where 12 bytes of (index, s/n
and group

R. J. McEliece, D. J. MacKay and J. F. Cheng, Turbo Decoding as an Instance of Perl's "Belief
Propagation" Algorithm, IEEE Journal of Selected Areas in Communication, Vol. 16, No. 2, Feb.
1998.
Summary: discuss similiarity of decoding several codes and the BP algorithm. In general the
decoding can be viewed as message passing betweens output symbols which have common input symbols
and vice versa. Written really unclearly and full of formulas.
number).
1999

John Byers, Michael Luby, and Michael Mitzenmacher, "Accessing Multiple Mirror Sites in
Parallel: Using Tornado Codes to Speed Up Downloads", INFOCOM 1999.
pdf
Summary: enabling a client to access multiple mirror sites in parallel, where the file is
encoded using Tornado coding, the client has to obtain only k*epsilon out of n in order to obtain
the full file. Using the stretch factor of c, instead of giving each mirror a responsibility of
1/s of the file, using coding each mirror can be responsible of c/s of the file, and thus we have
more flexibility in choosing the data from the servers. The servers permute the list of codewords
before they start the transmit. The protocol is done without any feedback
from the client. Show that the speedup goes up by about 2 when doubling the amount of servers.
Suggest also many to many distribution using multicast. Optimizations: client is allowed to ask
the server from which offset to start transmitting the file and thus can coordinate receiving
different portions of the file, another optimization is that client can ask for ranges of packets
and then for other ranges.
2000

R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, "Network Information Flow", IEEE Transactions
on Information Theory, July 2000.
pdf
Summary: This paper initiated the network coding reserach. in it they authors devise a theory
for network information flow which is similar to the maxflow mincut
theorem. Show that in general is not optimal to relate the network flow as a fluid which can
simply be routed or replicated. By employing coding in the nodes (network coding) bandwidth in
general can be saved.
Model: X1, .. , Xm are mutually independent information sources. The information rate for each Xi
is hi. A is the mapping to specific source nodes, B is the mapping to subset of receiver nodes.
The mapping A,B,h define a set of multicast requirements. Rij is a nonnegative real number which
is the edge capacity. For a fixed set of multicast requirements R is adimissible iff exists a coding
scheme satisfying the set of multicast requirements. They relate to the case of single source s,
and L receivers sinks. F is maxflow from s to tk in G if F is a flow from s to tl whose value
is greater then or equal to any other flow from s to tl. For a graph with one source and one sink
the flow from the source to sink is called the capacity of the graph. The conjecture: given a
graph G with source s and sinks s1..sL. Then (R,h,G) is admissible iff the values of the maxflow
from s to any tl are greater than or equal to h, the rate of the information source.
Another result is that it is sufficient for the encoding functions to be linear.
2001

Vivek K Goyal, Multiple Description Coding: Compression Meets the Network, IEEE Signal
Processing Magazine, May 2001.
pdf
Summary: Show that for example for image transfer over the web multiple description coding is
a better alternative than channel coding.
2002

M. Luby. LT Codes. Proc. IEEE Symposium on Foundations of Computer Science, 2002.
pdf
Summary: present LT codes which are rateless (the number of symbols is potentially limitless) erasure
codes that are very efficient as the data length grows. The symbols length l is variable. If the
original data has k input symbols then each encoding symbol can be generated, independently with
any other symbol on average by O(ln(k/delta)) symbol operations, and the original k symbols can be
recovered from any k+O(sqr(k)ln^2(k/dela) of the encoding symbols with probability 1delta on
average O(kln(k/delta) symbol operations. In other words, the decoder has to
receive a total which is slightly larger than the original data in order to
decode. LT codes uses graphs of logarithmic degree. The process of
encoding is done by randomly choosing a degree d of the encoded
symbol from a degree distribution. d random distinct input symbols
are chosen uniformly at random. The value of the encoded symbol is
the XOR of the chosen input symbols. The decoder has to know the
encoding graph in order to decode. In RS codes, for comparison,
only k symbols are needed to decode but we pay with more complex math
In tornado codes, the rate c=n/k is predetermined and can not be
changed. the receiver has to know the exact graphs. A different
graph structure is required for every data length. Since LT codes
support various data length no previous knowledge is needed to
calculate the graphs. Also Tornado codes has a limited set of
created symbols.
The design of the degree distribution is to prevent the balls and bins bihaviour of nlo(n) steps
needed to fill in n bins. Thus the redundency is kept minimal.
 Weatherspoon, H., AND Kubiatowicz, J. Erasure coding
vs. replication: A quantitative comparison. In Proc. of International
Workshop on PeertoPeer Systems (2002).
Summary: Compare erasure coding and replication. Shown that coding with rate of 32/64 vs. a
replication of two for the same storage requirment acheive an order of magnitude higher MTTF. The
same about bandwidth needed and repairs needed. Propose a hybrid system of both replicas and
fragments (as done in OceanStore). Replicas are used for low latency retreval and fragments for
high resiliency.
2003

Petar Maymounkov and David Mazires, "Rateless Codes and Big Downloads", IPTPS 2003,
February 2003.
pdf
Summary: present Online codes. Coding have outer and inner encodings. First a several
auxiliary
blocks are created using xor combination of file blocks and appended into the original file. The
inner encoding is done by selecting using random number generator a level d with certain
probability, than uniformly d blocks of the composite messages a re selected and XORed.

T. Ho, R. Koetter, M. Medard, D. Karger, and M. Effros, "The Benefits of Coding over Routing
in a Randomized Setting", ISIT, Yokohama, Japan, 2003.
ps
Summary: Present a randomized coding approach, give a lower bound on the success of random
network code. Demonstrate advantage of randomized coding over routing on a grid.
Network model: acyclic directed graph on a rectangular grid. X1..Xr are transmissions,(l) is the
transfer on link l, Z(b,i) is the output process of the receiver. Link capacity is one bit per
link per time unit. All vectors of bits with equal size. linear coding is considered on acyclic
delay free networks. In a linear code, the signal (j) is a linear combination of processes Xi
generated node and signals on incident incoming links. The main problem (for dummies:) sending two
processes from a source node to receiver nodes in random unknown locations on a rectangular grid
network. Transmission to a particular receiver is successful if there receiver gets two
different processes instead of duplicates of the same process.

A. Shokrollahi, Raptor Codes, Technical Report, Digital Fountain, EPFL.
pdf
Summary: The paper presents raptor codes which is an extension of LTcodes with linear time
encoding and decoding. The paper includes a very good overview of coding, digital fountain codes
and LTCodes.
In all of the encoding techniques discussed in this paper, the blocks of the original file forms
the encoding input (and not the bits) and thus when a block is lost we can mark it as erased and
thus use the BEC (binary erasure channel) model. When the erasure probability is p, ML (maximum
likelihood) decoding can be used with an exponential small error. The decoding is done using
guassian elimination, which takes polynomial time. RS (reed solomon) codes can be used to perform
a more efficient decdoing in quadratic time in the dimension. Luby suggested Tornado codes with
linear time decoding which are proportional to the block length. Thus for small rates, the
encoding and decoding are slow. DigitalFountain codes are intended to slove the problem of
multiple receives, each one with a different loss rate, thus is is impossible to calculate a
single rate for all receives. A fountain code produces an almost infinite set of output symbols.
The output symblos are linear combination of the k input symblos. For decoding, n output symbols
are needed. In case n is close to k, the code has a universality property. The codes proposed by
Luby are LTCodes. One of their properties that the average weight of the output symbols is
omega(log(k)). Raptor codes are used for making the average weight constant using a precoding of
the input and then using raptor code.
Additional difference between fountain codes and block codes is that on block codes the structure
of the code is determind prior the use for transmission and in digital fountain codes are
generated online. The code of decoding algorithm is the number of arithmetic operation divided to
the nunber of symbols k. The decoding graph of an algorithm of length n is a bipartite graph with
k nodes on the one side (the input nodes or symbols) and n node in the other (the output nodes or
symbols). There is
an edge between an input and output symbol if the input symbol contributes the the value of the
output synbols. It can be shown that an LTcode with k input symbols needs at least cklog(k)
edges, where c is some constant. That is to cover all input symbols with high probability. Raptor
codes relax this assumption and require that only a constant fraction of the input symbols be
recoverable. That is done by using precoding to increase the number of input symbols.

P. A. Chou, Y. Wu, and K. Jain, "Practical network coding," Allerton Conference on Communication,
Control, and Computing, Monticello, IL, October 2003. Invited paper.
ps
Summary: propose a packet format which removes the need for any centralized knowledge of the
graph topology or endocing or decoding functions. In their scheme, packet size is 1400 bytes.
Withim each packet an hdimensional global encoding vector g(e). In this way, the global encoding
vectors needed to invert the code at any receiver can be found in the arriving packets tehmselves.
Suggest usage of priority encoding using PET to support audio and video file using MDC. For
handling asynchrony of communication links, they group the packets into generations. Each
generation has a seperate buffer where the packets of this generation are stored. Each arriving
packet results in a Guassian elimination of the packet for finding the global vectors and deciding
if the packet data is redundant or not (noninnovative vs. innovative). For each
outgoing tranmission random packets from this generation are selected and encoded again. The
encoding vector for each packet is selected at random. For simulations, used first a maxflow
algorithm for deciding the flow paths and the network coding is done only using those paths.
Written a siulation is C++, for topology used Rocketfuel traces. Show that throughput increases as
the latency decreases (thus coding is more synchronized).
 S.Y. R. Li and R. W. Yeung and N. Cai "Linear Network Coding", IEEE Trans.
on Information Theory, IT49(2):371381, Feb. 2003.
Summary: show that it is sufficient of the network coding fucntions to be linear.
2004

M. Krohn, M. Freedman, D. Mazieres, “OntheFly Verification of Rateless Erasure Codes for
Efficient Content Distribution”, IEEE Symposium on Security and Privacy, Berkeley, CA, 2004.
pdf
Summary: This paper discuesses how to protect file parts against malicius users which sends
bogus information. Propose a method for creating file parts hashes even when the file is erasure coded.
The idea is to hash the output symbols of the precoder. They propose to use homomorphic hash
function, h(i+j)=h(i)*h(j). Thus each coded symbol is combined from linear combination of parts,
and thus when you have the hash of all the initial parts, you can verify each encoded block. For
supporting the hash over some GFq they change the linear combination operations to addition and
subsruction modulo GFq instead of XOR operations.
 S. Deb, M. M?dard, Algebraic Gossip: A Network Coding Approach to Optimal Multiple Rumor
Mongering”, presented at the Allerton Conference on Communication, Control, and Computing,
September 29 to October 1, 2004.
For solving the problem of one to all broadcast of k=O(n) messages using the phone call model (each node communicates with
another random node at each round) they propose to gossip using a random linear combination of
obtained messages. Initially each message is distributed to O(1) nodes. On each round each nodes
contants another node at random and sends it a random linear combination of the messages received
so far. Examined also variants of push and pull. The main results is that the needed time to send
n messages in expactation is O(n) instead of O(nlogn) using regular gossip.
 K. Jain, L. Lovasz and Philip A. Chou,
Building Scalable and Robust PeertpPeer Overlay Networks for Broadcasting using Network Coding
Microsoft Research Technical Report MSRTR2004135, December 2004.
pdf
Summary: Using a centeral topology maintenence, the joining nodes are getting several input
streams and produce several output streams. The streams are decoded using random linear
combinations.
2005

C. Gkantsidis and P. Rodriguez "Network Coding for Large Scale Content Distribution, IEEE INFOCOM
2005, Miami. March 2005"
pdf
Summary: Good overview of previous work. Did simulation of 200 nodes which show that network
coding is working better then source coding or no coding, especially when facing network partitions.

K. Jain, L. Lovasz and P. A. Chou, Building scalable and robust peertopeer overlay networks
for broadcasting using network coding, In PODC 2005.
Summary: provide extended version of the tech report from 2004. Suggest that an indexing server
handles joins and leaves and thus creates the network topology. Analyze this system theoretically
and prove near optimal bounds ont he parameters defining robustness and scalability. Show that
adverserial failures and no more harmful than random failures.

R. W. Yeng, S. Robert Li, N. Cai and Z. Zhang: Theory of Network Coding.
Summary: good overview of the network coding field.
Searching
 Efficient Content Location using Internet Based Locality in PeertoPeer Systems 
Srianidkulchai, Maggs, Zhang
Summary. Propose adding shortcuts to the Gnutella network such that nodes with locality in the
data will make shortcuts to each other. Initially peers are starting with no known shortcuts.
After several answers, they start to rank peers based on some utility. Peers which answer requests
are candidate for adding shortcuts to. Did some monitoring in CMU of Gnutella and KaZaA networks.
Based on those traces, who that if nodes first query the shortcuts and only if there is no answer
starts to flood the network, traffic is reduced drastically something like 80% and average path to
destination is reduced from average of 4 to 1.5.

SkipNet: A Scalable Overlay Network with Practical Locality
Properties, Nicholas J. A. Harvey, Michael B. Jones, Stefan Saroiu,
Marvin Theimer, and Alec Wolman, USITS '03.
Summary: common DHTs do not provide controlled data placement (specifying where the item should be
stored)
and no gurentee for routing paths remain within an administrative domain whenever possible.
SkipNet solves those two problem by adding another abstraction layer. The SkipNet topology is a
distributed skip list, where items are sorted by their string names. Each node maintains O(logN)
pointers (like the fingers in Chord). The pointers point to exponentially growing distances over
the ring. Besides of the string identifies, each node picks also a random numeric ID. This is a
second addres space where node IDs are uniform. Unline chord, the finger skip exponential distance
in the string space. The search of an item is composed of first searching it in the string space
(in an average of O(logN) hops  a search over the skip list) and then as in chord in the numeric space
by grouping the numeric IDs into digits and routing digit by digit as done in hypercube routing.
Properties: routing locality can be presenved when using a DNS like naming system where a
domin has a certain perfix. Constrained load balancing is acheived by specifying a domain prefix
where data items should be stored, the load balancing is done within that domain.
 Sarunas Girdzijauskas, Anwitaman Datta, Karl Aberer, Oscar: Smallworld overlay for realistic key distributions,
DBISP2P 2006, The Fourth International Workshop on Databases, Information Systems and
PeertoPeer Computing (DBISP2P), September 11, 2006, Seoul, Korea. pdf
Summary: deal with contruction of long fingers in a network with a desired small world
property (using Kleinberg's "efficient routing" approach). The population of peers
is skewed and thus choosing peers by partitioning the identifier space results in imbalanced
partitioning. For fixing the imbalanced partitioning an estimation for the identifiers consisting
each partition is done using a ranom walk, sampling k nodes from each partition. Each node locally
chooses at random one partition and points to a random node in it.
Caching

M. R. Kuripolu, M. Dahlin, Coordinated Placement and Replacement for LargeScale Distributed
Caches, In proc. of the Workshop on Internet Applications, July 1999.
ps
Summary: Compare several caching placement algorithms using simulation. Use clustered topology
where distance of every two nodes is measured by the closest cluster they are both participate in.
Called also the Ultrametric model. Divide inspected algorithms to two: noncooperative and
cooperative. Among the tested noncooperative algorithms are: MFU placement (most frequently
used),
LRU (least recently used) are evicted upon miss, LFU (local least freqnecy used), GreedyDual: each
object has a fixed miss cost. The objects with the larger costs should stay in the cache as
possible. When an object is inserted to the cache, it's value is set to it's fetch cost. When a
cache miss occurs, the object with the minimum value is evicted and all other objects value is
reduced by the minimal cost of the object removed. If an object was accesses, it cost is raised
into it's fetch value.
Regarding cooperative placement algorithms. First, the system cost is define to be the sum over
all nodes and all objects alpha of the access frequency for object alpha and node u times the
distance from node u to the closet copy of the object. The goal of those algorithm is to find the
placement with the minimal cost. An optimal algorithm for the placement is described on KPR+99 which uses a reduction to the minimum cost flow problem. The greedy
algorithm starts with a tentative placement which each cache picks the locally most valuable set
of objects. The algorithm then proceeds up the cluster tree improving the placement iteratively.
The amortized placement algorithm is an improvement for the greedy algorithm, where we are trying
to avoid local maximum which prevents higher global maximum. A potential function is added which
accumulates the values of all the missing objects and accumulated potential is used to reduce the
benefits of certain secondary items. All above algorithms are described in
KPR+99. Propose a novel algo called Hierarchical GreedyDual where each cache is
running the GreedyDual itself, and evicted values are proposed for higher cluster layers.
Simulation settings: topology of growing clusters. (like Meridian). All cache sizes are the same.
Workload divided into sharing parameter r which is the faction the client sends into leveli
objects (objects in the ith cluster) is proposional to r^i. Within each cluster, they select
object with either Zipf's like or uniform distributions. Conclusions: increaing coordination can
improve performance. Furthermore, when the frequency predictors are accurate the caching is more
efficient.

M. R. Korupolu, C. G. Plaxton and R. Rajaraman. Placemnt algorithms for hierarchical cooperative
caching. In proc. of the 10th Annual ACMSIAM Symposium on Discrete Algorithms, pp. 586595,
January 1999. ps
Summary: Although their propose a very interesting algorithm, the paper is so badly written it is
impossible to understand the construction. Look at p. 5 and find how many times the letter Q
repeats there.

D. Karger, E. Lehman, F. T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. Consistent hashing
and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In
Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 654663, May 1997.
Summary: introduce consistent hashing: hash function which change minmally as the range of the
function grows. Create a forest of trees, disjoint for each items to load balance the caching. The
main idea of the consistent hashing is that each bucket is replicated logN times. When a new
bucket is added, items are moved to it only within its small region. The client inserts the
objects randomly to one of the buckets and thus load balancing this structure. This is very
similar to later DHTs where bucket is a node, and a new node joins the ring in a random point it
splits the region with its closet neighbors.

N. Leibowitz, A. Bergman, R. Ben Shaul, A. Shavit, "Are File Swapping Networks Cacheable?
Characterizing P2P Traffic, presented at 7th International Workshop on Web Content Caching and
Distribution (WCW 03') Buolder, CO, 2002.
Summary: show that P2P traffic measured on ISP is highely repetative and responds well to
caching.
Network/Transport Layer Optimizations

M. Sally Floyed, J. Padhye, J. Widmer. Equation Based Congestion Control for Unicast
Applications, In proc. of SIGCOMM 2000.
(TFRC)
pdf
Summary. Propose mechanism to maintain more or less fixed sendingrate preventing
TCP flactuations. The sending rate is based on eqaution based congestion control. The flow should
resemable TCP fair sharing. In order to estimate right sending rate T, following parameters are
evaluated: RTT, p  loss rate, s packet size, TCP retransmittion time (estimated by 4*RTT).

E. he, J. Leigh, O. Tu, T.A. DeFanti, "Reliable Blast UDP: Predictable high Performence
Bulk Data Transfer", In proc. of IEEE Cluster Computing 2002, Chicaho, Illinois, 2002.
(RBUDP)
Summary. Using UDP to avoid TCP slow start and flactuations.
Sender sends using UDP a full window, and then sends end tranmission mark using TCP control
channel. The receiver answers with a bitmap of missing packets in the TCP control channel. The
sender answers recuresivelly with the remaining packets.

A. Venkataramani, R. Kokku, M. Dahlin, TCP Nice: A Machanism for Background Transfers.
Fifth USENIX Symposium on Operating System Design and Implementation (OSDI 2002). Boston, MA.
Summary: Modified TCP implementation based on Vegas. First, a predetection of congestion is
done using RTT estimations. Second, multiplicative decrease is done in sending window size. Third,
congestion window can be lowered below one. Purpose of all those changes is to allow a background
transfer when the network has free resources and almost not to affect current transfers.
 S. Cen, C. Pu, J. Walpole, Flow and Congestion Control for Internet Media Streaming
Applications, In Proceedings of Multimedia Computing and Networking, 1998.
Summary: Propose SCP (straming control protocol) for real time streaming. Main idea: uses TCP
congestion control and flow controls. However, when there is congestion, the congestion windows
size is reduced by half (instead to 1 as in TCP). Tries to estimate the bandwidth delay product
and not to send more to the network. Thus the queues in the intermediate routers are kept minimal
and there is less jitter.

J. Rosenberg, J. Weinberger, C. Huitema, and R. Mahy.
STUN: Simple Traversal of User Datagram Protocol(UDP)
Through Network Address Translators(NATs). RFC 3489, IETF, Mar. 2003.
Summary: suggest a protocol for detection of types of NATs the client is behind. General idea is
to try several probes to determine NAT type. Some NATs allow UDP for restricted ports, some allow
only outgoing connections. The client sends a packet to a server in a public network. The server
replies using several methods to the client and writes down the IP src address of the client. The
client examines this IP, and if it is not identical to the one he has privatly he knows it is
behind NAT. There are 4 types of NATs discussed: Full cone (external host can send IP to mapped
external address),
restricted cone (the same but internal client has to initiate connection first),
port restricted cone (same as above, but the port has to be the same port the client send the
packet to),
summetric (NAT allocate for each pair of IPs a new IP and port).

B. Carmeli et Al. High Throughput Reliable Message Dissemination. In Proceedings of the 2004
ACM symposium on Applied computing.
Summary: proposes to aggregate messages for achecing high throughput in highend server
environment when the bottleneck is not the bandwidth but server processing time.
Parallel and Network Computation

Fast Tuning of Intra Cluster Collective Communications. Luiz Angelo BarchetEstefanel., Gr´egory Mouni´e

P. Tvrdik. Onetoall broadcast algorithms. Lecture notes of topics in parallel computing
course, University of Wisconsin Medison, 1999.
ps
Summary: first define communication model and performance metrics
which a very similar to
ours. Define Work exactly as define in Julia. Present onetoall
broadcast in the SF (store and forward) model
in Erew PRAM and hypercube using SBT (spanning binomial tress) to both
1port and kport models.
Same algorithm for meshes and tori.
Define a set of deomination nodes D in directed network G is a subset of nodes which that every
node in G is either in D or is a neighbor of at least on node in D. EDS (extended dominating set)
D2 of D1 iff there exists a set of link disjoint paths under R such taht every node in D1  D2 is
reachable along one such path. Show algorithm for 2 dimentional mesh which uses this appoach.
Another nice algorithm is for 2D tori T(5^k, 5^k) is the dilated digaonal based approach.

P. Tvrdik. Multicast, IRC, and onetoall scatter algorithms. Lecture notes of topics in parallel
computing course, University of Wisconsin Medison, 1999.
ps
Summary: Show multicast in hypercubes using the dimension order chain. (Chain multicast).
Apply recursive doubling in the WH model in logN rounds. Does multicast on meshes recursivly.
Another interesting algo is for the allport noncombining hc, where necklaces are created in order
to create disjoint spanning trees.

P. Tvrdik. Alltoall broadcast algorithms. Lecture notes of topics in parallel
computing course, University of Wisconsin Medison, 1999.
ps

P. Tvrdik. Alltoall scatter algorithms. Lecture notes of topics in parallel
computing course, University of Wisconsin Medison, 1999..
ps

Q. F. Stout and Bruve Wagar. Intensive Hypercube Communication: Prearranged Communication in LinkBound Machines. In Journal of
Parallel and Distributed Cmoputing 10 (1990), pp. 167181.

A. BarNoy and Shlomo Kipnis. "Broadcasting multiple messages in simultaneous send/receive
systems". In Discrete Applied Mathematics 55 (1994) pp. 95105.
Summary: Relate to a send/receive model where each processor can send and receive 1 message in
each round. Show an optimal broadcast algorithm for any number of messages m, and any number of
processors n, which work in the optimal time of m+roof(log(n)). The idea is to construct BST on
chain of hypercubes where the total number n is composed of powers of 2.

A. BarNoy and C. T. Ho. Broadcasting multiple messages in the multiport model. IEEE Trans on
Parallel Dist. Sys. 10(5):500508, 1999.

A. BarNoy, S. Kipnis, and B. Schieber. Optimal multiple message broadcasting in telephonelike
communication systems. Discrete Applied mathematics, 100:115, 2000.

A. BarNoy, J. Brick, C.T. Ho, S. Kipnis, B. Schieber. Computing Global Combine Operations in the
MultiPort Postal Model.
Summary: n processor are holding one piece of data, and would like to calculate some
associative operation and make the result known to all. Multiport postal model is charachterized
by 3 parameters: n, the number of nodes, k the ports and lambda which is the communication
latency. Messages which are sent arrive after lambda rounds.

L. G. Valiant, A scheme for fast parallel communication. SIAM J. Comput. 11,2 (1982), 350361.

Jehoshua Bruck, ChingTien Ho, Eli Upfal, Shlomo Kipnis and Derrick Weathersby, Efficient
Algorithms for AlltoAll Communications in Multiport MessagePassing Systems,in IEEE Trans.
Parallel Distrib. Syst. 8:11 11431156, 1997.
Summary: proposed efficient algorithms for alltoall communications in message passing systems
index (scatter) and concatenation (all to all broadcast). The model is of a fully connected
network with 1 or more ports. For the index propose an algorithm which is optimal either for the
startup time or with respect to the mesaure of data transfer time. Propose concatantion algorithm
which is optimal for most values of n in the number of communication rounds and the amount of data
transferred.
Fault Tolerance and Load Balancing

S. Banerjee, S. Lee, B. Bhattacharjee, A. Srinivasan,
"Resilient Multicast using Overlays," ACM Sigmetrics, June 2003. (PRM)
Summary: Present PRM (Probabilistic Resilient Multicast) a multicast data recovery scheme.
Useful for application which can tolerate low data losses like video streaming. Uses two simple
techniques:
1. Randomized forwarding: each overlay node with a small probability sends few extra transmissions
across random overlay links. Motivation is that when a subtree gets disconnected numerous of nodes
do not receive the stream, the probability of some random edges to reach that subtree is high as
the subtree gets larger. A tree discovery mechanism is implemented using random walks on the
multicast tree in order to select nodes at random to forward to.
2. Triggered NAKs: bitmaps of missing packets are sent up in the tree or to the cross edges for
generating their restransmissions.
Optimization: the random edges can be selected using the lowest correlation of missing packets.
In case of loss, the nodes can signal a sending node of the cross edges to increase transmission
volume.
Did statistical analysis which shows high percentage of recieving nodes under random selection of
edges. Did ideal simulation against besteffort, HHP (hop by hops naks), FEC and PRM. Did
simulation using GTITM with 22K nodes.

P. Ganesan, M. Bawa, H. GarciaMolina, "Online Balancing of Range Partitioned Data with
Applications to PeertoPeer Systems". In proc. of VLDB 2004.
Summary: Consider building blocks in load balancing. NBRAdjust is when two neighboring nodes
alter the boundary between their ranges by transferring data. Reorder is that when a node with an
empty range changes its location and splits the data with a loaded node. An alogirhm called the
doubling algorithmn is formed out of those two building blocks.

Stefan Birrer and Fabi?n E. Bustamante.
Nemo  Resilient PeertoPeer Multicast without the Cost.
Technical Report NWUCS0436, Department of Computer Science, Northwestern University
pdf
Summary: Based on Nice, optimizations are that cluster members help forward the data. Also
probablistic heart beats are sent to identify failures.

K. Aberer, A. Datta, M. Hauswirth and R. Schmidt. Indexing dataoreinted overlay networks. In
VLDB 2005.
Summary: present the PGrid AEP (adaptive eager partitioning) algorithm. The problem is the
parition the nodes into two partitions zero and ones with a proportion p, where each node
should know another node from the other partition.
Learning
General

J. Jordan and Yair Weiss, "Probabilistic inference in graphical models".
ps

L. R. Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech
Recognition", Proc. of IEEE, vol. 77, no. 2, Feb. 1989.
Summary: good overview of HMM altough different notations are confusing. Explain well the tree
problems (likelyhood, inference and finding a model). Good explanation of Viterbi algorithm.

R. Vicente, D. Saad, Y. Kabashima, Low density parity check codes  a statistical physics
perspective
ps
Summary: Another explanation of the BP algorithm (pp. 1116), and good overview of LDPC codes.

Y. Weiss, Approximate inference using loopy belief propagation
ps
Summary: numeric example of BP calcaultions from some lecture.

Y. Weiss, Exact inference in tress using belief propagation
pdf
Summary: lecture notes

M. Jordan, Y. Weiss, Graphical models: probabablistic inference
ps
Summary: an overview of this field including exact and approximate inference, variational and
sampling methods.

D. J. C. MacKey, Information Theory, Inference, and Learning Algorithms
pdf

Webpage explaining junctions tree construction.
html

M. Paskin, A short course of graphical models
lecture 1 (pdf)
lecture 2 (pdf)
lecture 3 (pdf)

M. Paskin, Exploiting Locality in Porbablistic Inference, Ph. D. thesis, Univ. of Clifornia,
Berkeley, Fall 2004.
pdf

D. J. C. Mackay, Introduction to Monte Carlo Methods.
ps
Summary: Discusses importance sampling, rejection sampling, Metropolis method, Gibbs sampling.
The assumption is that we can draw samples from a function P*(x) which can be evaulated with
multiplicative constant 1/Z. This is hard to do since first we don't know Z and second the
sampling is hard to do. In uniform sampling we draw samples unifromaly from the sate space,
evaulting P*(x) in this points and calcaulting Zr=sum(P). In importance sampling we assume
there is a simpler density Q(x) which is easier to sample from, and we assign wights to each
sample by Wr = P/Q. In Rejection sampling, we have a proposal density and the value
of a constant c s.t. cQ > P. We chose a random interval u from the interval [0,cQ*(x)].
If u < Q*(x) the sample is accepted else it is rejected. Metropolis method, unlike rejection
sampling is MCMC (markov chain monte carlo) since each sample is depended in the previous sample.
However, their is not gurentee in advancing towards the right goal. Metropolis method is one
dimensional sampling where Gibss is mutlidimensional sampling. A single iteration involves
sampling one parameter at a time.

K. M. Murphy, Y. Weiss abd M. I Jordan,Loopy Belief Propagation for Approximate Inference: An
Empirical Study, in Proc. of UAI 1999.
Did simulations over several models in order to better understand when BP converges and when
it does not. Conclusion is that for very small probabilities the algorithm oscillate. Propose the
method of damping (call it momentum).

C. Yanover and Y. Weiss, Finding the M most probable configurations using Loopy Belief Propagation,
in proc. of NIPS 2003.

iccv

Y. Weiss and W. T. Freeman, On the optimiality of solutions of the maxproduct belief propagation
algorithm in arbitrary graphs. IEEE Transactions on Information Theory 47:2 pages 723735. (2001).
pdf
Summary: Show that the max product algorithm acheives strong local maximum (which is a
suboptimal
solution)
when it converges.

M. Wainwright, T. Jaakkola and A. Willsky, "Treebased reparameterization framework for analysis
of belief propagation and related algorithms," IEEE Trans. Information Theory, 2003

M. J. Wainwright, T. Jaakkola, A. S. Willsky. "Treebased reparameterization for approximate
estimation on loopy graphs. In NIPS 2001. Dec. 2001.
Summary: Present TRP, a generalization of BP which performs exact computations over spanning
trees om graph with cycles. TRP typically converges faster as well in cases BP does not converge.
The basic idea is to perform succesive reparameterization updates on trees embeded in the original
graph.

M. J. Wainwright, T. Jaakkola, and A. S. Willsky. Exact MAP estimates by (hyper)tree agreement. In
Advances in Neural Processing Systems. MIT Press, 2003.
Summary: propose a variant of BP which always converges even on graph with cycles. The
drawback that the results might be trivial. The basic idea is to represent to original problem on
the graph with cycles as a conves combination of treestructured problems.

J. S. Yedidia, W. T. Freeman and Y. Weiss. Bethe free energy, Kikuchi approximations, and
belief propagation algorithms. Mitsubishi Electric Research Labs, Technical Report TR200116, May
2001.
Summary: explain the derivation of the generalized BP algorithm from Kikuchi free enery
approximation.

A. Braunstein, M. Mezard, M. Weight, R. Zecchina. Constraint Satisfsaction By Survey
Propagation. condmat 0212451. Sept. 2003. pdf

A. Braunstein, M. Mezard, R. Zecchina. Survey Propagation: an Algorithm for Satisfiability.
condmat 0212002, Nov. 2003
Summary: Explain the Survey Propagation tehcnique used for solving random 3SAT and qcoloring
problems.

J. S. Yedidia, W. T. Freeman and Y. Weiss.
Understanding Belief Propagation and its Generalization.
Merl Tech Report TR200122, January 2002.
Summary: explain equivalence between various graphical models, like MRF, factor graphs, Tanner
graphs, Beysean networks. Explain standard BP on MRF. Explain free energy drivations from the
simpler Mean Field approximation, Bethe free energy and finally Kikuchi approximtions. Show
derivation of the Generalized BP algorithm based on Kikuchi approximation.
 T. Jaakola, Tutorial on variational approximation methods.
ps
 Y. Weiss and W. T. Freeman. Correctness of belief propagation in Gaussian graphical models of
arbitrary topology
Summary: Show that when the nodes of a graph descrive jointly random Gaussain random variables,
when the BP algorithm converges, it gives the exact posterioir probability on any graph topology.
The basis foundations for the Consensus propagation work.
 iJ. K. Johnson. Term Paper for 6.291 Graphical Modeling Seminar taught by S. Mitter:
WalkSummable GaussMarkov Random Fields, Feb. `02.
pdf
Summary: explore the connection between
walk sums on a graph (the probability for each node to start a random walk and return to that
node)
and Gaussian Markov Random fields.

WalkSum Interpretation and Analysis of Gaussian Belief Propagation
Jason Johnson, Dmitry Malioutov, Alan Willsky. NIPS 05. pdf

G. Elidan, I. McGraw and D. Koller. Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
Twenty Second Conference on Uncertainty in Artificial Intelligence (UAI), 2006.
Summary: propose to change node message update order to achieve a faster convergence. Show that
when BP is a contraction under any norm, it will converge into a fixed point even in asynchrounous
settings.

K. Crammer and Y. Singer. Pranking with ranking. In Proceedings of the conference on Neural
Information Processing Systems (NIPS), 2001.html
Summary: propose an online algorithm for solving the ranking problem. Extend the perceptron
algorithm for supporting classification to several ordred classes.

Minka. Expectation Propagation for Approciximate Bayesian Inference. UAI 2001.
pdf
Summary: An extension of ADF (assumed density filtering), a one pass sequencial method
for computing an approximate posterior distribution. EP extends ADF to include iterative
refinement
of the approximation.
ADF applies we have a joint distribution p(x,y) where y is observed and we want to know the
posterior p(xy). Using the Bayesian approach, p(x,y) = p(x) * prod(p(y_ix)).
We use an approximated familty q(x) where q(x) is a normal distribution. In each step
we compute p^(x) = c * p(y_i x) * q\i(x). Then we minimize the KL distawnce D(p^(x)q(x)).
The EP algorithm is a modification of the ADF algorithm where the order of operation is changed.
In ADF each observation was treated exactly and then the posterior which includes it was
approximated. In EP first the approximation is done and then the exact posterior is calculated.
 T. Joachims, Making largescale support vector machine learning practical, in B. Scholkopf,
C. Burges, A. Smola. Advances in Kernel Methods: Support Vector Machines, MIT Press,
Cambridge, MA, December 1998.
html
Summary: describe the Osuna algorithm  select a working set which is a subset of the
variabels and fix the others. Iteratively optimize subset until convergence. Proposes to select
a subset which will result in the steepest descent towards the minimum. Discusses efficient
implementations.
 R. Collobert, S. Bengio, and Y. Bengio. A parallel mixture of SVMs for very large scale
problems. Neural Computation, 14(5), 2002. html
Summary: propose to divide the training set into M random subsets, train each expert separatly
over one of the subsets. A centeral module assigns weight to the output of the different agents and
tries to minimize the squared diffrence between the tags and their
defined function f(). Then they sort the data items based on their relative weight and reshuffle
them between exprets again with a balanced portion to each expert. Then this process repeats until
convergence.
 S. Vijayakumar and S. Wu: "Sequential support vector classifiers and regression", Int.
Conf. Soft Computing, pp. 610619 (1999).html
Summary: the trick they use for simplifying the SVM problem formulation is to add another
dimension to the input vector. x' = (x1, ... , xn, lambda) abd the weight vector w' = (w1, ...,
wn,
b/lambda)
where lambda is a scalar constant. In this case the dual formulation does not need to constraint
that y'h = 0. However the cost function is updated since we minimize w'^2 which is equal to
w^2 + b^2/lambda^2. Maximizing the modified margin will give an approximated solution.
However, when the dimension increases the accuracy of the solution is getting better.
The dual formulation changes as well. In the dual the term lambda^2 * y_i * y_j is added to each
cell in the matrix D.
They propose to solve the modified problem with a gradient decent algorithm which is a "line
search" algorithm.
 A. J. Smola, S. V. N. Sishwanathan and E. Eskin. Laplace Propagation. In NIPS 03'.
html
Summary: present a method for approximate inference. Given a set of observations Xi we would
like to infer a parameter theta p(thetaX). We would like to approximate mean and variances of p.
The mean is approximated by max_theta(log p) and the variance by the second derivative of
log(p). The result is exact for normal distribution and very good approximation when theta is
centered around its mean.
Instead of working with p(thetaX) we assume the components t_i are indepenent and we get
p(thetax) = \pi t_i(theta) where t_i = p(thetax_i). The strategy is to find a good approximation
to each t_i and by that to find a global maximizer to p(thetaX). The idea is to work in rounds,
and calculate each t_i based on the other approximated t~_i.
They prove that the theta* is a fixed point of Laplace propagation iff it is a local optimum of
p(thetaX). This method can be applied to arbitrary graphs assuming p(thetaX) can be represented
as a multiplication of potentials. The messages sent consists of mean and variance. Each t_i
computes its own value using only graph neighbors t~_j. They show that BCM (Bayes Committee
Machine) is equivalent
to running only one step of updates of Laplace Propagation.
Regarding the relation to SVM, since log p(ThetaX) corresponds to the objective funciton of the
SVM, LP is used. Present a logarithmic version of LP for solving SVM. Show also that chunking, is
also equivalent to LP. In chunking the idea is to optimize subsets at a time.
 Wikipedia: Method of steepest descenthtml
Summary: explains the Laplace method (known also as saddle point approximation). The idea is
to approximate a twice defrentiable function using Taylor serias using the first and second derivatives.
In the maximum, the first derivative is zero, so only the second derivative is used. f(x) = f(xo)
+ 1/2 f''(x0)(xx0)^2 + O(xx0)^3. To increase the accuracy of this method we use e^Mf(x) where M
is a large integer and compute the integral \int(e^Mf(x)) in the vicinity of x0. In other areas it
exponentially decays to zero, since x0 gives the maximum and we multiple it with a large intereger
M. This method is used for finding the contour with the steepest descent.

Laplace's Method  Mackey's book  chapter 27pdf
 An Introduction to Support Vector Machines and Other Kernelbased Learning Methods
by Nello Cristianini and John ShaweTaylor ISBN:0521780195 Cambridge University Press 2000 (190
pages)
Summary: chapter 6 deals with SVMs.
 WEKA software: html

Bruno A. Olshausen and David J. Field.
Emergence of simplecell receptive field properties by learning a sparse code for natural images.
Nature 381, 607  609 (13 June 1996); doi:10.1038/381607a0.
Summary: for making the solution sparse, they propose to add to the minimized cost function a function
of the form log(1+x) or e^x^2
 S. G. Mallat and Z. Zhang. Matching pursuits with timefrequency dictionaries. IEEE
Transactions on Signal Processing, 41(12), December 1993.
html
Summary: propose a method which decomposes any vector to a linear combination of dictionary
vectors. This is done by succesive approximations starting with the dictionary vector that the
project of the approximated vector is maximal.
f = < f' g0> g0 + Rf
Matching pursuit is an iterative algorithm which
subcomposes the residue Rf by projecting it on a vector of the dictionary D that match it almost
at best. Finally
f = \sum( < R^nf,gn > gn) + Rmf
If we stop at this point, we have an approximation with error equal to Rmf. However this some is
not a linear expension of the vectors g0..gm which approximates f at best (since the vectors g in
general are not
orthogonal).
Note PVm as the orthogonal projection on Vm (the subspace not spanned by the all of the dictionary
vector selected to represent f). PVm(Rmf) = \sum xi
gi. In total we store < R^nf,gn > gn + xn. xn is solved using Y = < R^mf,gi >. Let G = <
gi,gj > the Graham matrix. We can solve the equations Y=GX to get X.
In finite spaces, the algorithm converges exponentially.
 Distributed SVM applied to image classification
Kokiopoulou, E. ; Frossard, P. IEEE Int. Conf. on Multimedia & Expo (2006)
pdf
Summary: the assumption is the the SVM problem is already solved, the support vector, bias and
lagrange multipliers are known. A network of sensors observe a noisy signal that needs to be
classified. Using the matching pursuit construction, each sensor projects the input on its part of
the dictionary and keeps the largest components. A central server collects all the components from
the sensors and evaluates the SVM discriminant (to decide if the sign of the checked signal). A
method is given for the calculation of the descriminant function is given. First by translating
the support vectors into the dictionary base atoms, and then by calculating < s_i,x > = \sum
< beta_j d_j, x >

"The Forgetron: A KernelBased Perceptron on a Fixed Budget" Ofer Dekel, Shai ShalevShwartz and
Yoram Singer, Advances in Neural Information Processing Systems 18, MIT Press, 2005.
pdf
Summary: propose to keep only a bounded set of support vectors based on some budget. Each
vector in the active set is assigned a weight and vectors with the least weight are removed.

"A New Perspective on an Old Perceptron Algorithm" Shai ShalevShwartz and Yoram Singer,
Proceedings of the Sixteenth Annual Conference on Computational Learning Theory, 2005
pdf
Summary: propose an extension to the perceptron algorithm by considering the margin. When a
very close point (below some threshold r) is classified correctly the hyperplane is modified
(unlike the original perceptron which updates the classifier only on mistakes). Assume a stronger
assumption that all points in the ball with radius r should be classified to the same cluster.
Discuss an extension for supporting multiclass.
Communications related

Nonparametric Belief Propagation for SelfCalibration in Sensor Networks"; Ihler, Fisher, Moses,
Willsky; Information Processing in Sensor Networks 2004. (Best Student Paper Award)
pdf
Summary: the papers discusses the task of sensor self calibration of their geographical
positioning over a planar region using a graphical model
approach. They apply nonparametric belief propagation to obtain an approximate solution. It
exploits the local distributed nature of the problem, it produces both an estimate of sensor
location and a representation of the location uncertainties. Sensors gets noisy readings regarding
their location with some probability of error. Solving the maximal likelihood of sensor location
(ML) is a complex nonlinear optimization problem. For avoiding relative location which is subject
to translations rotation and negation errors, they assumption that a triangle of three sensor
positions is known. First, authors show that the problem is local in nature. The sensor network is
modeled as an undirected graph, where each node has a probability positioning X, a probability of
being observed O, and a probability of distance to other nodes. The total probability is the
multiplication of all the cliques. The self potentials are defined by the probability of a node to
be in a certain location, and the edge potentials are defined by the error probability (measured
distance
minus
treal
distance).
Since the variables are continues they use monte carlo NBP.

Robust Probabilistic Inference in Distributed Systems;
Mark Paskin and Carlos Guestrin;
In the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI 2004), Banff, Canada,
July 2004.
pdf
Summary: The problem is to calibrate tempreture readings in a sensor network. For solving the
problem, first a spanning tree is created. Second, a junction tree is formed where each network node is
responsible for some cliques and factors. Third, the junction tree is optimized to contain small
cliques and separators. Then BP algorithm is run.
Simulation show that the new algorithm converges faster and will less fluctuations into the
optimal result.

A Robust Architecture for Distributed Inference in Sensor Networks;
Mark Paskin and Carlos Guestrin;
In Intel Research Technical Report, IRBTR03039, last updated April 2004.
pdf
Summary: extended technical report of the above paper.

C. Crick and A. Pfeffer, Loopy Belief Propagation as a Basis for Communication Networks.
In Proceedings of the 19th Conference on Uncertainty in AI, 2003.
pdf
Summary: Argue that one should produce and communication beliefs rather than raw sensor
readings. BP algorithm is highly suitable for sensor networks since it is distributed and has
simple calculations. Confirm using a simulation that even in asynchronous settings the algorithm
still performs well, even facing different communication speeds. Redundancy of sensors enables the
algorithm operation even when nodes fail. Also show that even in dynamic environment which can
degrade the operation of the algorithm and prevent it from converging, it performs well.

Rui Castro, Mark Coates and Robert Nowak, "Likelihood Based Hierarchical Clustering", IEEE
Transactions on Signal Processing, 52, no. 8, pp. 23082321, August 2004.
pdf
Summary: Clustering of objects is represented as a tree. The input is a matrix of nodes
pairwise similiarity (which can be noisy) and the output is a tree which represents close nodes.
Each intermidiate node has a metrics which represents the similarity of the nodes in the subtree
it represents. The LT (maximum likelihood tree) is constructed pairs of nodes with the highest
similarity are taken to contstruct a binary tree until no nodes are left. This solution is a
greedy solution based on local decisions. The global approach is done using MCMC method.

Mark Coates, Al Hero, Robert Nowak and Bin Yu, "Internet Tomography", in IEEE Signal Processing
Magazine, May 2002
ps

M. Jain and C. Dovrolis, "Endtoend available bandwidth: measurement methodology, dynamics, and
relation with TCP throughput," ACM SIGCOMM, August 2002.
ps

R. Rosales, K. Achan, B. Frey, Learning to Cluster using Local Neighborhood Structure, in Proc.
of the 21st int. conf. on machine learning.
pdf
Summary: cluster neighborhoods using the maxproduct algorithm.

M. L. Littman, G. A. Keim and N. Shazeer. A probalistic approach to solving crosswords puzzles.
Atificial Intelligence 134 (2002) 2355.
Summary: model crossword puzzles using a probabilistic graphical model. Each word has a
certain probability to appear in the puzzel based on the clues. Proposed several heuristics for
learning the clues. Define two optimization problems: either a full match of all the words
of the puzzel (maximum probability solution), or a match of maximal number of words (maximal
overlap) to the solution. Use BP for solving the optimization problems. Implemented a program
called proverb.

V. padmanabhan, L. Qiu, and H. Wang. Serverbased inference of Internet link lossiness. In Proc. of
IEEE INFOCOM'03, San Francisco, CA, USA, April 2003.
pdf
Summary: using passive observation of client server traffic infer packet loss characteristics.
Propose three techniques for doing the inference. The first is random sampling. Assign a loss rate
of each link to zero. Each link loss rate is bounded by the maximal value seen by the client. Pick
a random edge and assign it random loss rate bounded by the above values. Then continue with the
same techqniue. At the end a sample solution was created. Iterate R times to produce R such
solutions. If the average loss rate of a link is higher then a threshold decide this link is
lossy. The problem is that higher up links in the tree are picked early in the process and
assigned higher loss rate. Because of avergaing done, a client with high loss rate might have
lower loss rate in the sample. The benefit is that the algorithm is simple.
The second alogrithm is done using linear optimization. Slack variables are used to allow higher
flexibility. (A client may have a little higher loss rate than in the input). Drawbacks are that
in order to computer pi, the avergae loss of a client enough samples must be obtained or else the
estimate is not accurate. Also there is no rigorous justification for the objective function. The
third technique is using Gibbs sampling. They start with initial assignment of loss rate. At each
step, pick on of the links, calculate the potserior distribution of loss rate of this link alone
conditioned on the observed data and the loss rate assigned to all other links. Then this process
is repeated. A sample from distributed is collected. The benefit is that the number of packets is
used and not the loss rate as done in the previous methods.
Simulation results done using a simulation tree from 20 to 3000 nodes and traces collected from
about 40,000 clients using MS website. Traceroute was used to learn the paths. Loss models are
either random or Gilbert . In the later the link has two states. In the good all
packets are reliably transferred and the opossite. The prob. of remaining in the bad state is 35%.
Show that the random technique is very accurate while having a large false positive rate. The best
results are obtained by Gibbs sampling.

C. C. Moallemi and B. Van Roy, Consensus Propoagation. Technical Report, Stanford, June
2005.
Summary: proposed an algorithm for caculating a cardinality of a set and the set average
value. This algorithm is exact on trees. For dealing with loops they suggest a fix that hopefuly
should converge to the right value.

M. Alanyali, V. Saligrama, InNetwork Decision Making via Local Message Passing, in Advances
in Pervasive Computing and Networking, (Szymanski/Yener Editors) Kluwer 2004.

M. Alanyali, S. Venkatesh, O. Savas, S. Aeron, Distributed Bayesian Hypothesis Testing in
Sensor Networks, American Control Conference 2004.
Summary: In sensor network settings, the problem of classification of an event such that all
sensor will reach a consensus. There are m possible classes of events. There is also prior
probability for each event. Using Loopy BP. Edge potentials are constructed using identity matrix.
Self potentials are contstructed using sqrt_ multiplied by the local observation. Try to
identify conditions where the BP converges in the MAP. On trees it is trivial. Show that on
topologies with symmetric out degress the BP converges to the MAP (like torus). Give numerical
constradicting example of nonsymmtric graph with 0 nodes. Also have interesting example of 4
nodes where BP convergence is depended on the initial values. In the first it converges right, in
the second there are oscillations relative the trivial (but correct) solution.
 V. Saligrama, M. Alaynyali, O. Savas. Asynchronous Distributed Detection in Sensor Netowrks.
Unpublished, 2005.
Summary: consider the problem of classification in sensor networks. There are M possible
hypothesis, all sensors have their readings and a prior information. The task is to arrive to a
concensus about the occured hypothesis. Initilize the self potentials of each hypothesis to be the
nroot of the prior of that hypothesis multiplied by the observation. The edge pontetnails are
identity matrix. Show that the node reach concensus if the prob. of all the wrong hypothesis is
going to zero. Show that on graphs where all the nodes have fixed outgoing degree the BP converges
into the MAP. Propose to fix graphs without a common outgoing degree by either adding self edges
up to the degree and using them to send message or by normalizing the outgoing message by the node
degree. Discuss also resilence to failures, energy consumption of the algorithm and extend it to
continues variables.
 Y. Rachlin, R. Negi and P. Khosla. Sensing Capacity for Discrete Sensor Netowks
Applications.
Model the state of nature being sensed as descrete vector. Bound the number of sensors
required to acheive a desired level of sensing accuracy. Use information theory techniques by
relating to the sensors as encoders.
 Y. Mao, F. R. Kschischang, B. Li and S. Pasupathy. A Factor Graph Approach to Link Loss
Monitroing in Wireless Sensor Networks.
Monitor data aggregated back to some centerial node. By monitoring the aggregated data they
infer the link states in the network. Use the SumProduct algorithm for inference. Network model
is of a directed graph, each node is a sensor, router or central collecting node. Assume a reverse
multicast path exists from each node to the central node. Each node sends packets constantly to
the center. Assume each link can be in two states: good or bad. Each path is the AND of all links
on the path. There is a probability of each link to be down. The problem is to estimate this
probability based on the path knowledge, using ML approach. Assume that each link suffers from
indenpendent loss. Use a factor graph, where each edge is connected to each path. Did simulations
of up to 50000 nodes.
 E.B. Ermis, V. Saligrama, Adaptive Satistical Sampling Methods for Decentralized Estimation
and Detection of Localized Phenomena.
 J. Consodine, F. Li, G. Kollios and J. Bayers. Approximate Aggregation Techniques for
Sensor Databases.
Summary: Use FM (Flajolet and Martin) counting sketches. A hsah function gives and output of size
k where one bit is flagged for each item. Duplication and ordering does not effect the result.
Extend the FM work for supporting summation as well. Instead of doing r inserts do one summation
which is much more efficient.
 M. Bayati, D. Shah and M. Sharma, Maximum Weight Matching via MaxProduct Belief
Propagation. In ISIT 05'.
Summary: solve the maximal weight matching problem using a construction of a fulll bipartite
graph, applying the max product belief propagtion algorithm. Prove that in case of a unique
solution the BP always converges to the right global maximum.
 R. Schmidt and K. Aberer. Efficient PeertoPeer Belief Propagation.
Fourteenth International Conference on Cooperative Information Systems (CoopIS),
Montpellier, France, November 13, 2006pdf
Summary: propose to use a spring relaxation technique for moving variable between P2P nodes,
to mimimize the total number of messages sent in the network.
MANET

A. Datta, S. Qouateroni and K. Aberer. Autonomous Gossiping: A SelfOrganizing Epidemic Algorithm
for Selective Information Dissemination in Wireless Mobile AdHoc Networks, In proc. of ICSNW
2004.
Summary: suggest a biological inspired mechanism for the dissemination of data. When mobile
hosts are meeting at ranom, information is exchanged and thus data item can exchange their hosts.
The data items like to replicate and survive in an environment where the hosts have only limited
memory and thus the more necessary ones survive and the others are deleted. The data has some
utility function which decides measured their improtance to the host based on both regional and
intereset creterias. Data items have a certain probability to either migrate, replicate or to be
deleted.

Y. Wu, P. A. Chou, and S.Y. Kung, "Minimumenergy multicast in mobile ad hoc networks using
network coding," IEEE Trans. on Communications. Submitted March 2004.
pdf
Summary: Model the MANET using a set of linear equations enableing the minimization of power
consumption. Uses network coding for enabling more data paths.

B. Xu, A. Ouksel, and O.Wolfson. Opportunistic resource exchange in intervehicle
adhoc networks. In Mobile Data Management, 2004.
Summarry: defined data importance based on distance from the data origin and its age. Each
vehicle has a fixed memory and stores the data with the higher importance. Vehicles exchange
information when they are in tranmission range. Each vehicle is moving between two fixed points in
a fixed speed.

H. Zhou and S. Singh. Content based multicast (cbm) for ad hoc networks. In
Mobihoc, 2000.
Summary: mixed network of sensorts and moving vehicles. The sensor alert for dangers and push
the information into affected regions. The vehicles are using pull for requesting information from
the sensorts. The data is relevant based on location and its age.

Yuval Shavitt and Amir Shay. Optimal Routing in Gossip Networks.
IEEE Transactions on Vehicular Technology, accepted.
Summary: Introduce the gossip network model where travelers obtain information about the state
of the network (like traffic jam) and gossip it to other travelers. Information about state of
network links might be found at some other points of the network. Thus, it is sometimes preferable
to make detours from the shortest path in order of finding information about the network state.
Propose a dynamic programming algorithm (like belman ford) where increasing iterations makes the
routing tables more accurate. Unlike BF, routing loops are quite possible. It is sometimes better
to circle in a loop until we gain information about certain path then traveling the path and
hitting a traffic jam.

S. Kraus, R. Parshani and Y. Shavitt. A Study of Gossiping in Tranportation Networks.
Summary: use a model whre drives lean expected congestion in different roads. Some of the
drives have gossiping capacility to help them learn the network. Use a directed graph, where
each edge weight models the current congestions. Agent learn the network using the following
options: either travesing an edge, arriving to a junction of an edge, or gossiping. Agents gossip
when they meet by several possible policies: randomly exchanging a fixed set, randomly exchanging
a random set or by ranking importance of edges and exchanging the most important subset. Used
simultion model where the road is divided into sections and cars are moved between sections. Each
road is implemented by a finite queue. Avg. number of cars using a simulation run is about 70,000
where on each step there are about 3,500. During the run randomly selected junctions are randomly
or fully blocked. Different levels of gossiping agents percentage where used. Future extensions:
moving between fixed points, lying agents, coordinated travel on edges.
Network Flows
 D. R. Karger and M. Minkoff. Building Steiner Trees with Incomplete Global Knowledge. In
proc. of the 41th annual symposium on Founations of Computer Science, 2000.
Summary: the goal is to distribute single data item to multiple while minimizing network
usage. The set of client requesting the data is known by probabiliy. Introduce a new version to
the factility location problem where each facility has to have a minimal demand assigned to it.
Formal problem statement (the MaybeCast problem:) given a network of n nodes, a root node each
node contact the root with probability pi. We must choose for each node a path to the root. In
case the client is active, the path becomes active. The output of the solution should give the
path specification from the active clients to the root node. The problem is NPcomplete even when
unit cost paths.
Motiviation for the solution: selecting the shortest path tree might leed to a solution which is
sqrt(n) slower then the optimal solution. Divide the construction into a hub and spoke. The hub is
the backbone where most of the edges should be used anyway. The spokes are groups of nodes that
can be agregated to save the tree cost. Define a unit cost of an edge as the probability that the
edge becomes active. Use a linear approximated of the unit cost to derive an approximate
solution.
Define the rgathering problem to be a variant of the facility location problem where each
facility should have at least r demand.
 K. Munagala. Approximation Algorithms for Concave Cost Network Flow Problems. Ph. D.
Dissertation. University of Stanford. May 2003.ps
 A. Goel and D. Estrin. Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source
BuyatBulk. Preliminary version appeared in 14th ACMSIAM symposium on descrete algorithms.
Summary: Consider the problem of finding efficient trees to send information from k source to a
single sink in a network where information can be aggregated at intermediate nodes in the tree.
The goal is to find a tree which is a good approximation simultaneously to the optimum tree for
all such concave cost functions. Present a randominzed tree construction algorithm that guarantees
the the expectation of the solution relative to the optimal cost is less then 1+logK.
Propose an hierarchical matching algorithm of the steps, first find a min cost perfect matching,
nd then chooseon of the node for each match and remove it. The size of the set gets halved in each
phase. The set of the output edges is the aggregation tree.
 M. Charikar and S. Guha. A constantfactor approximation algorithm for the kmedian problem.
In proc. 40th symposium on foundations of computer science, pp 378388, 1999.
 S. Guha, A. Meyerson and K. Mungala. Hieratchical placement and network design problems. In
proc. 41st annyal symposium on foundations of computer science, 2000.
 S. Guha, A. Meyerson and K. Mungala. A constant factor approximation for the single edge
installation problem. In proc. of the 33rd ACM symposium on theory of computing, 2001.
 S. Khuller, B. Raghavachari and N. Young. Balancing minimum spanning and shortest path trees.
Algorithmica 14(4):305321, 1994.
 P. Raghavan. Probablistic construction of deterministic algorithms: Approximating packing
integer problems. Hournal of Comp. Sys. Sci. 37:13043, 1988.

G. Robins and A. Zelikovsky, Improved Steiner Tree Approximation in Graphs, Proceedings
of the 7th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2000), 2000.
ps
Summary: the Steiner tree problem seeks a minimum weignt connected subgraph connecting a given
subset of nodes. Present a polynomial time heuristic with an approximation ration of 1.55.
The algorithm is called kLCA. In a nutshell they construct a spanning tree, and in a loop
find the krestricted full componenet with max gain to loss ratio and attach it to the tree.
The algorithm finishes when no such component is found.

R. Jothi, Approximation algorithm for singlesink edge instllation problems and other graph
problems. Ph.D. Dissertation, the university of Texas at Dallas, 2004.
 V. Arya, a. Meyerson and V. Pandit, Local Search Heuristics of kmedian and Facility Location
Problems. In proc. of STOC 01'.
Summary: Show of the uncapacitation Facility Location problem that local
search which permits adding dropping and swapping a facility is bounded by 3approximation from
the optimal solution.
Gossip
 P. Flajolet and G. N. Martin. Probabilistic counting algorithms for data base applications.
Journal of computer and system sciences, 31, 1985.
Summary: present the FM counting sketches. The goal is to count a cardinality of a set (while
ignoring
dulplicates).
The method works as follows: given a hash function with an output of size L bits, each data item
is hashed. For each item, the longest pattern 0^i is recorded of the item hash value. With probability
2^i, the longest zero prefix of length i exists since the output of the hash function is assumed
to be random. If there are more data items in the set, the probability of some node to have the
identifier with a prefix of i zeros is growing. The accuracy of the basic scheme is with a factor
of 2. To improve accuracy, several counting procedures can be done at once, using several
different hash functions.
 S. Boyd, A. Ghosh, B. Prabhakar and D. Shah, Gossip Algorithms: Design Analysis and
Applications.
Summary: Analyze the convergence time for gossip algorithm for an arbitrary network topology, show that the
convergence time depends on the second largest eignevalue of a doubly stochastic matrix describing
the algorithm. Show that minimizing this quantity is an SDP problem.

H. Holbrook, S. Singhal, and D. Cheriton. Logbased receiverreliable multicast for distributed
interactive simulation. In SIGCOMM, 1995.
Summary: Uses logger to provide storage and handle reliable transmission of missing messages.

R. M. Karp, C. Schindelhauer, S. Shenker, and B. V¨ocking. Randomized rumor
spreading. In FOCS, 2000.
Summary: propose a protocol which combines both push and pull phases. In the first phase nodes
are pushing the message, in the second phase the nodes which did not get the message are using
pull to randomized members to get it.

A. M. Kermarrec, L. Massoulie and A. J. Ganesh. Probabilistic reliable dissemination in largescale systems
, IEEE Trans. Parallel and Distributed Systems, 2003.
Summary: Examine efficient gossip under the following assumptions: each peer has only a small
subset of total membership information, and more important, organizing the peers into heirarchical
structure. Propose a hierarchy of clusters. The algorithm consists of each node sending message
both to in cluster and outside of the cluster. Discuss the affect of the paraneters of the intra cluster fanout and inter clusterfan
out and run simulations using GTITM topology to test in how many cases all nodes will get the
gossiped message for fine tuning those parameters.

A. Khelil, C. Becker, J. Tian, and K. Rothermel. An epidemic model for information
diffusion in manets. In Proceedings of the 5th ACM international workshop
on Modeling analysis and simulation of wireless and mobile systems, pages 54–60.
ACM Press, 2002.
Summary: apply random gossip to wireless setting and analyze it using the special network
characteristics like area, communication range etc.

D. Kempe, A. Dobra, and J. Gehrke. Gossipbased computation of aggregate information. In Proc.
of FOCS, 2003 (PushSum)
Summary: present a very elegant and simple algorithm to calculate distributed average using
gossip. On each message to values are sent W (weight) and S (sum). When contacting a random node
using gossip, the current values of W,S of the those nodes are summed and then averaged. Each node
holds half of the total information. W = 1/2(Wi+Wj), S= 1/2(Si+Sj).
The algorithm is based on the mass conservation property: the initial share of each node in the
sum is divided among nodes but the sum of each share is kept constant.

D. Kempe and F. McSherry. A decentralized algorithm for spectral analysis. In Proceedings of the
36th ACM Symposium on Theory of Computing (STOC'04), New York, NY, 2004. ACM.
Summary: extend the PushSum algorithm to compute matrix eigenvalues using orthogonal iterations.

On Collaborative Content Distribution Using MultiMessage Gossip.
By Coby Fernandess and Dahlia Malkhi.
Best Paper Award in Twentieth IEEE International Parallel and Distributed Processing Symposium
(IPDPS 2006), Greece, April 2006. pdf
Summary: optimize the gossip process for multiple messages simultaneously. Assume the k parts
are found in k different nodes and the goal is to disseminate the k parts to all n nodes. The
gossip is done in rounds, where the question is which message to send to the random node contact
in the gossip round. In the first phase, nodes are randomly "colored" by one of the k messages.
Coloring means the node is responsible for disseminating this message. In the second phase all
nodes have each message with a proabilibity at least half. The total time is O(k+logN) where the
previous known bound was O(klogN).

D. MostAoyama and D. Shah. Computing Separable Functions via Gossip. In PODC 2006.
Summary: seperable functions are functions which are linear combinations of individual
variables. The authors present a simple distributed randomized algorithm for calculating seperable
function. Each node has an initial value yi, draws at random r values from an exponential
distribution with mean 1/yi. The nodes exchange information about their values using gossip.
For each value 1..r the nodes select the minimal values encountered in the incoming messages and
compute r/sum(min_val)
for estimating the sum. The algorithm is based on the fact that given n random exponential i.i.d. variables
with rates y1..yn. , their minimum W is distributed as an exponential random
variable with rate sum(y1..yn).

A. Montresor, M. Jelasity, and O. Babaoglu. Gossipbased Aggregation in Large Dynamic Networks.
ACM Transactions on Computer Systems, vol. 23, no. 3, 219252, August 2005.
Summary: analyze the pairwise avergaing algorithm, which performs worser then the PushSum
algorith.

Efficient GossipBased Aggregate Computation (with Supratim Deb, K.V.M. Naidu, Rajeev Rastogi and
Anand Srinivasan). To appear in ACM
SIGMODSIGACTSIGART Symposium on Principles of Database Systems (PODS) 2006.
Propose hierarchical solution to improve the known gossip results to o(n log log n) messages
and O(log n log log n) communication rounds.
Security and Trust
 Karl Aberer and Zoran Despotovic. Managing trust in a Peer2 Peer information system. In
Henrique Paques, Ling Liu, and David Grossman, editors, Proceedings of the Tenth International
Conferenceon Information andKnowledgeManagement(CIKM01) , pages 310317, New York, November 510
2001. ACM Press.html
Propose to maintain a distributed database of complaints on transactions. To check if a
certain node is honest, a query about this node is presented to the distributed database. The
answer is replicated on several different places. A malicious nodes will have many complaints
filed, and a relatively high level of complaints will inidiate it.
 D. Kamvar, M. T. Schlosser, and H. GarciaMolina. The EigenTrust Algorithm for Reputation
Management in P2P Networks. In Proceedings of the Twelfth International World Wide Web Conference,
2003. pdf
Summary: Assign each peer a global trust value which reflects the experiance of the other peers
with it. Propose to use the stationary state of a Markov chain for calculaing the trust. Propose
to use a correction p towards a known set of trusted nodes. To allow secure computation of the
trust the trust value of each peer is calculated by another set of peers while their output will
be compared to prevent forgery.
 R. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of Trust and Distrust. In
International World Wide Web Conference, 2004. pdf
Summary: propose several modes of propagation trust: a) atomic propagation (similar to a random
walk of one edge)
b) cocitation (a trusts b and c, d trusts b causes d trust c). c) transpose trust (a trusts b
causes b to
develop some
level of trust
in a).
d) turst coupling (a trust b propagates to c since b and c trust people in common.) Propose to use
a weighted matrix composed of those four options. Also consider the possibility to create a
distrust matrix with negative trust values that will be combined into the calculation. However,
the basic problem here is that a distrusts b, b distrusts c does not imply that a
distrusts c.
Regarding the computation, propose to use either the stationary eigenvector (as in Eigentrust) or
a walksum limited to k hops. Did simulations using the "Epinions" database where several turst
links where omitted and they guessed based on the other trust values what will be the trust level
over the link, using binary trust.
Social Networks
David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social
network. In Proceedings of the Ninth International Conference on Knowledge Discovery and Data
Mining, 2003.
Summary: discuss how to choose k nodes (active nodes) that will maximize their influence on a decision in the
network on the other nodes (inactive nodes). Uses a linear threshold model where each node picks a random threshold that if it gets
from neighboring nodes commulative recommandations which have larger weight then its threshold it will
become active as well. Proposes an approximation algorithm for this problem (which they call the
influence
maximization problem)
which is a greedy hill climbing algorithm.

Yehuda Koren, Stephen C. North, Chris Volinsky:
Measuring and extracting proximity in networks. In KDD 2006. p. 245255
Summary: proximities can be used in a social network to predict connections which has
not been made, or ind links that have been removed or not observed. Ideally, proximity should be
more sensitive to edge between low degree nodes and also take into account multiple paths between
the nodes. Discuss several possible approaches:
* max flow  does not take into account path lengths.
* Effective conductance (EC)  regards the network as an electric network, settings a voltage
of zero and one to the tested nodes and computing the current. Accounts for both the path lengths
and the number of alternative paths. There is also a relation between EC to random walks. The
monotonicity propoerty says that when edges are added the current can only increase. In some cases
it has undersitable properties, where nodes with one edges "waste" hops in the random walk and add
nothing to the calculation.
* Sink augemented EC  a sink is added to the network and each node is connected to it using a
link. It solves the backtracking problem in EC, but adds undisirable property when the network
scales there is an increasing chance for getting into the sink.
Propose to use a new approach: CFEC  cycle free effective conductance. The idea is to relate to
the computation as a random walk. Define a cycle free escape probability: the probability of a
random walk starting in node s will reach t without visiting any node more then once. The
benefits: preferes shorter paths, prefers pairs that are connected with many shorter paths, dead
end paths reduce proximity. Proposes to extract a subgraph that will be used for a close
approximation of the proximity value. That is because shorter paths have much greater significant
we can ommit a large part of the calculation and still get a very good approximation. Propose to
use a branch and bound algorithm for doing the calculation.

PeertoPeer Rating
by Danny Bickson, Dahlia Malkhi, Lidong Zhou.
In the Seventh IEEE International Conference on P2P computing (2007).

Fast discovery of connection subgraphs
by Christos Faloutsos, Kevin S Mccurley, Andrew Tomkins

A new status index derived from sociometric analysis
Psychometrika, Vol. 18, No. 1. (27 March 1953), pp. 3943.
by Leo Katz

On the structural properties of massive telecom call graphs: findings and implications
(2006)
by Amit A Nanavati, Siva Gurumurthy, Gautam Das, Dipanjan Chakraborty, Koustuv Dasgupta, Sougata
Mukherjea, Anupam Joshi

Assortative mixing in networks
(20 May 2002)
by MEJ Newman

Centrality Measures Based on Current Flow
STACS 2005 (2005), pp. 533544.
by Ulrik Brandes, Daniel Fleischer

Random Walks and Electric Networks
by Peter G Doyle, Laurie J Snell

The structure and function of complex networks
MEJ Newman

Mapping Small Worlds
PeertoPeer Computing, 2007. P2P 2007. Seventh IEEE International Conference on (2007), pp.
by Matteo Dell'amico
219228.

Modeling relationships at multiple scales to improve accuracy of large recommender systems
Robert Bell, Yehuda Koren, Chris Volinsky
 Improved Circular Layouts
Graph Drawing (2007), pp. 386398.
by Emden Gansner, Yehuda Koren
T.B.D

Proc. 9th ACMSIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the
ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
Summary: present the Hits algorithm for calculating the page ranking of webpages.
A bipartite graph is built, where each webpage has two nodes. A directed edge is added if a
left node has a link pointing to a right node. Each iteration is composed of left to right
computation where the right node sums up all incoming messages from the left and the opposite.
After each iteration the results x (right) and y (left) are normalized. It can be shown that
those iteration converge to the principal eigenvector of the matrixes A'A and AA' where A is the
adjacency matrix.
 A. Langville and C. Meyer. Deeper inside pagerank. Internet Mathematics, 1(3):335380,
2005.
Summary: explain the pagerank algorithm.

K. Jain, M. Mahdian, and M. R. Salavatipour, "Packing Steiner Trees", Proceedings of the 10th
Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2003), 2003.
ps

[26] M. Thimm, “On The Approximability Of The Steiner Tree Problem”, Mathematical Foundations
of Computer Science 2001, Springer LNCS, 2001.

[28] G. Pandurangan, P. Raghavan and E. Upfal, “Building Lowdiameter P2P Networks”, 42nd Annual
Symposium on Foundations of Computer Science (FOCS01), pp. 492499, 2001.

[30] E. Adar, B. Huberman, “Free Riding on Gnutella”, First Monday, Available at:
http://www.firstmonday.dk/issues/issue5 10/adar/, 2000.
 A. Ghodsi, L. O. Alima, S. Haridi, "Increasing Robustness and Minimizing Bandwidth Consumption in Strucured PeertoPeer
Systems"
 R. Koetter and M. Medard, "Beyond Routing: An Algebraic Approach
to Network Coding", in Proc. of IEEE INFOCOM 2002.

Jannotti, J., Gird, D., Johnson, K.: Overcast: Reliable multicasting with an
overlay network. In: Proceedings of the Symposium on Operating Systems Design
and Implementation OSDI 2000). (Overcast).

Y.H. Chu and S. G. Rao and S. Seshan and H. Zhang, "Enabling Conferencing Applications on the Internet using an Overlay Multicast Architecture,"
Proceedings of ACM SIGCOMM 2001, August, 2001

J. Byers, M. Luby, M. Mitzenmacher,
"A DigitalFountain Approach to Asynchronous Reliable Multicast,"
Journal on Selected Areas of Communication, Volume 20, Number 8, October 2002.

S. Banerjee, B. Bhattacharjee, and C. Kommareddy.
Scalable application layer multicast. In ACM
SIGCOMM 2002.

T. S. E. Ng and H. Zhang. Predicting internet
network distance with coordinatesbased approaches.
In IEEE INFOCOM 2002.

R. Rejaie and A. Ortega. PALS: PeertoPeer
Adaptive Layered Streaming. In NOSSDAV, 2003.
 S. Saroiu, P. K. Gummadi, S. D. Gribble, “A Measurement Study of PeertoPeer File
Sharing Systems”, Multimedia Computing and Networking 2002 (MMCN 2002).

J. Chu, K. Labonte, and B. Levine, “Availability and locality measurements of peertopeer
file systems”, ITCom: Scalability and Traffic Control in IP Networks, July 2002.
 S. Sen and J. Wang, “Analyzing PeertoPeer Traffic Across Large Networks”,
ACM/IEEE Transactions on Networking, Vol. 12, No. 2, April 2004, pp. 137–150.
 C. Nieman, Digital Decoys”, IEEE Spectrum, May 2003, p. 27.

Y. Guo, K. Suh, J. Kurose, and D. Towsley, P2cast: peertopeer patching
scheme for vod service," in Proceedings of the twelfth international conference
on World Wide Web, 2003, pp. 301  309.

"A peertopeer ondemand streaming service and its performance
evaluation," in Proceedings of 2003 IEEE International Conference on Multimedia
& Expo, 2003.

M. Hefeeda, A. Habib, B. Botev, D. Xu, and D. B. Bhargava, Promise:
Peertopeer media streaming using collectcast," Proc. of ACM Multimedia
2003, November 2003.

Gnustream: a p2p media streaming system proptoptype.
Xuxian Jiang Yu Dong Dongyan Xu Bharat Bhargava.
pdf

[9] S. M. Hedetniemi,T. Hedetniemi,an d A. L. Liestman.
A Survey of Gossiping and Broadcasting in
Communication Networks. NETWORKS,18, 1988.

[11] C. Huitema. The case for packet level FEC. In Proc.
5th International Workshop on Protocols for High
Speed Networks, Oct. 1996.

[12] J. Leibeherr and M. Nahas. Applicationlayer
Multicast with Delaunay Triangulations. In IEEE
Globecom, Nov. 2001.

[13] B. Levine and J. GarciaLunaAceves. A comparison
of reliable multicast protocols. Multimedia Systems
Journal,6( 5), Aug. 1998.

[14] B. Levine,D . Lavo,an d J. GarciaLunaAceves. The
case for concurrent reliable multicasting using shared
ack trees. In Proc. ACM Multimedia, Nov. 1996.

[15] X. Li,S. Paul, P. Pancha,a nd M. Ammar. Layered
video multicast with retransmissions (LVRM):
Evaluation of error recovery schemes. In Proc.
NOSSDAV,1997.

[19] C. Papadopoulos,G. Parulkar, and G. Varghese. An
error control scheme for largescale multicast
applications. In Proc. INFOCOM 1998.

S. Paul,K. Sabnani,J . Lin,a nd S. Bhattacharyya.
Reliable multicast transport protocol(rmtp). IEEE
Journal on Selected Areas in Communications,15( 3),
Apr. 1997.

X. Rex Xu, A. Myers,H . Zhang,an d R. Yavatkar.
Resilient multicast support for continuousmedia
applications. In Proceedings of NOSSDAV 1997.

D. Rubenstein,S . Kasera, D. Towsley, and J. Kurose.
Improving reliable multicast using active parity
encoding services(APES). In Proc. INFOCOM 1999.

Z. Xiao and K. Birman. A randomized error recovery
algorithm for reliable multicast. In Proc. INFOCOM 2001.

[27] B. Zhang,S . Jamin, and L. Zhang. Host multicast: A
framework for delivering multicast to end users. In
Proc. IEEE INFOCOM 2002.

Z. Wang and J. Crowcroft. QualityofService Routing for Supporting Multimedia Applications. IEEE
JSAC, 14(7):12881234, September 1996. pdf

D. Xu, M. Hefeeda, S. Hambrusch, and B. Bhargava. On PeertoPeer Media Streaming. Purdue Computer
Science Technical Report, Apr. 2002.
html

Schulzrinne, A., Casner, S., "RTP: A Transport Protocol for REALTime Applications ",
Internet Engineering Task Force, Internet Draft, Oct. 20, 1993.(RTP)
html

H. Schulzrinne, A. Rao, R. Lanphier, "Real Time Streaming Protocol(RTSP)," Internet RFC 2326,
Apr. 1998.(RTSP)
html

[CSW+2000] Freenet: A Distributed Anonymous Information Storage and
Retrieval System, I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong,
WDIAU 2000.

[SGD+2002] An Analysis of Internet Content Delivery Systems, Stefan
Saroiu, Krishna P. Gummadi, Richard J. Dunn, Steven D. Gribble, and
Henry M. Levy, OSDI 2002.

Chord: A Scalable Peertopeer Lookup Service for Internet
Applications, Ion Stoica, Robert Morris, David LibenNowell, David R.
Karger, M. Frans Kaashoek, Frank Dabek and Hari Balakrishnan, IEEE/ACM
Transactions on Networking, Vol. 11, No. 1, pp. 1732, February 2003.

[ZHS+2004] Tapestry: A Resilient Globalscale Overlay for Service
Deployment, Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea,
Anthony D. Joseph, and John D. Kubiatowicz, IEEE JSAC 2004.

[DZD+2003] Towards a Common API for Structured P2P Overlays, Frank
Dabek, Ben Zhao, Peter Druschel, John Kubiatowicz, and Ion Stoica,
IPTPS 2003.

[CDG+2002] Secure Routing for Structured PeertoPeer Overlay Networks,
Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron, and Dan
S. Wallach, OSDI 2002.

[GGG+2003] The Impact of DHT Routing Geometry on Resilience and
Proximity, Krishna P. Gummadi, Ramakrishna Gummadi, Steven D. Gribble,
Sylvia Ratnasamy, Scott Shenker and Ion Stoica, SIGCOMM 2003.
Performance Measurement and Evaluation

[WLS+2002] An Integrated Experimental Environment for Distributed
Systems and Networks, Brian White, Jay Lepreau, Leigh Stoller, Robert
Ricci, Shashi Guruprasad, Mac Newbold, Mike Hibler, Chad Barb, and
Abhijeet Joglekar, OSDI 2002

[VYW+2002] Scalability and Accuracy in a LargeScale Network Emulator,
Amin Vahdat, Ken Yocum, Kevin Walsh, Priya Mahadevan, Dejan Kostic, Jeff
Chase, and David Becker, OSDI 2002
pdf

[REG+2003] Pond: the OceanStore Prototype, Sean Rhea, Patrick Eaton,
Dennis Geels, Hakim Weatherspoon, Ben Zhao, and John Kubiatowicz,
FAST'03.

[RD2001] Storage management and caching in PAST, a largescale,
persistent peertopeer storage utility, Antony Rowstron and Peter
Druschel,SOSP 2001.

[MRG+2002] Ivy: A Read/Write Peertopeer File System, A.
Muthitacharoen, R. Morris, T. Gil, and B. Chen, OSDI 2002.

[HHL+2003] Querying the Internet with PIER, Ryan Huebsch, Joseph M.
Hellerstein, Nick Lanham, Boon Thau Loo, Scott Shenker, Ion Stoica,
VLDB'03.

[ABKM2001] Resilient Overlay Networks, David G. Andersen, Hari
Balakrishnan, M. Frans Kaashoek, Robert Morris,SOSP 2001.

[RS2002] The Design and Implementation of a Next Generation Name Service
for the Internet, Venugopalan Ramasubramanian, Emin Gun Sirer,
SIGCOMM 2004.

[NPB2004] A Routing Underlay for Overlay Networks, Akihiro Nakao, Larry
Peterson, Andy Bavier, SIGCOMM 2004.

[Br2001] Lessons from GiantScale Services, Eric Brewer, IEEE Internet
Computing 2001.

[FGC+1997] Scalable Network Services, Armando Fox, Steven D. Gribble,
Yatin Chawathe, Eric A. Brewer, and Paul Gauthier,SOSP 1997.

[WDB2001] SEDA: An Architecture for WellConditioned, Scalable Internet
Services, Matt Welsh, David Culler, and Eric Brewer,SOSP 2001.

[BCZ+2003] Capriccio: Scalable Threads for Internet Services, Rob von
Behren, Jeremy Condit, Feng Zhou, George C. Necula, Eric Brewer,
SOSP 2003.

[GBHC2000] Scalable, Distributed Data Structures for Internet Service
Construction, Steven D. Gribble, Eric A. Brewer, Joseph M. Hellerstein,
and David Culler, OSDI 2000.

[SBL2000] Manageability, Availability, and Performance in Porcupine: A
Highly Scalable, ClusterBased Mail Service, Yasushi Saito, Brian N.
Bershad, and Henry M. Levy, TOCS '00.

P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and
L. Zhang. IDMaps: A global Internet host distance
estimation service. IEEE/ACM Transactions on Networking,
Oct. 2001. (IDMaps)
Summary: IDMaps is an infrastructure to help hosts measure the cooredinates to other hosts.
The infrastructure contains of a few hundrands or thousands tracer nodes. The traces measure the
distance to every CIDR address prefix and jointly determines which traces is closer to which
prefix. The distance is estiamted by the total distance from node A to its near tracer, the
distance between the two tracers and nodes B distances to its close tracer. The advantage it is
using prefexis thus can predit distances of hosts which are not aware of the system.

T. S. E. Ng and H. Zhang. Predicting internet network distance
with coordinatesbased approaches. In IEEE INFOCOM 2002,
June 2002.(GNP)
GNP software
Summary: GNP (Global network positioning) relies on a small number (520) of landmark nodes,
other nodes choose coordinates based on RTT measurements to the landmarks, the choice of landmark
significantly affects the accuracy of RTT predictions. Requiring certain nodes to be landmarks
might be a bruden on p2p symmetry. Communication between other nodes can not compute the position.

J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti.
Lighthouses for scalable distributed location. In IPTPS 2003.
Summary: Extention of GNP that is intended to be more scalable. A joining node can query a set
of already joined node in order to calaulte its position. Then a transormation is done in order to
to relate the coordinates into the global landmarks.

Y. Shavitt and T. Tankel. Bigbang simulation for embedding
network distances in Euclidean space. In Proc. of IEEE
INFOCOM 2003, April 2003. (BigBang)
Summary: simulates a potential field.

T. E. Ng and H. Zhang. A network positioning system for the
Internet. In Proc. USENIX Conference, June 2004.
Summary: A version of GNP which encorporate hirarchy of nodes in order to reduce load on the
landmarks, a congestion control mechanism and workaround for firewalls and NATs.

R. Govindan and H. Tangmunarunkit. Heuristics for internet
map discovery. In Proc. 19th IEEE INFOCOM 2000, pages 1371?
1380, Tel Aviv, Israel, March 2000. IEEE.

M. Castro, M. Costra, and A. Rawstron, Performance and dependebability of structured peertopeer
overlays. Technical report MSRTR200394, Microsoft Research, Dec. 2003.
Pastry.ps">ps

J. Rosenberg, R. Mahy, C. Huitema. TURN: traversal using
relay NAT. Internet draft, Internet Engineering Task Force,
July 2004. Work in progress.
pdf

K. Lai and M. Baker, Nettimer: a tool for measuring bottleneck link bandwidth, in Proceedings of
the 3rd USENIX Symposium on Internet Technologies and Systems, March 2001.

A. El Gamal and T. M. Cover, “Achievable rates for multiple descriptions,”
IEEE Trans. Inform. Theory, vol. IT–28, pp. 851–857, Nov. 1982.

D. Slepian and J. K. Wolf, “Noiseless coding of correlated information
sources,” IEEE Trans. Inform. Theory, vol. IT19, pp. 471–480, July
1973.

R.W. Yeung, “Multilevel diversity coding with distortion,” IEEE Trans.
Inform. Theory, vol. 41, pp. 412–422, Mar. 1995.

L. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenjer, Web Cahcing and Zipf like distributions:
Evidence and implications. In proc. of IEEE INFOCOM 1999, March 1999.

I. Chawate, S. Rantasamy, L. Breslau, N. Lanham, S. Shenker, Making Gnutella like P2P systems
scalable, In proc. of the ACM SIGCOMM 2003.

D. Karger, E. Lehman, F, T. Leighton, M Levine, D. Lewin, R. Panigrahy. Consistant hasing and
random trees: Dsitributed caching protocols for relieving hot spots on the world wide web. In
Proc. of the 29th Annual ACM Symphsium on Theory of Computing, pp. 654663, 1997.

"Pixie: A Jukebox Architecture to Support Efficient Peer Content
Exchange", S. Rollins and K. Almeroth, ACM Multimedia 2002, Juan Les
Pins, France, December, 2002.

SRM">
J. Gemmell, “E SRM – Erasure Correcting Scalable Reliable Multicast,”
Microsoft Research Technical Report MSTR9720, June 1997.

M. Luby, M. Mitzenmacher, and A. Shokrollahi, “Analysis of Random
Processes via AndOr Tree Evaluation.” In Proceedings of the 9th Annual
ACMSIAM Symposium on Discrete Algorithms, January 1998.

N. F. Maxemchuk, “Dispersity Routing.” In Proc. of the International Conference
on Communications, pp. 4110 – 4113, 1975.

J. Nonnenmacher, E.W. Biersack, and D. Towsley, “ParityBased Loss Recovery
for Reliable Multicast Transmission.” In Proc. of ACM SIGCOMM
’97, 1997.

L. Rizzo, “Effective Erasure Codes for Reliable Computer Communication
Protocols.” In Computer Communication Review, April 1997.

E. Schooler and J. Gemmell, “Using multicast FEC to solve the midnight madness problem,”
Microsoft Research Technical Report MSTR9725, September 1997.

A. T.S. Ip, J. Liu, and J. C.S. Lui, COPACC: A Cooperative ProxyClient Caching System for
OnDemand Media Streaming, Technical Report, July 2004.
pdf

J. Liu, B. Li, and Y.Q. Zhang, Optimal Stream Replication for Video Simulcasting, to appear in
IEEE Transactions on Multimedia, 2005.

"Scalability in Adaptive MultiMetric Overlays," Adolfo Rodriguez, Dejan Kostic, and Amin Vahdat,
Proceedings of the International Conference on Distributed Computing Systems, March
2004.
pdf

LoDN: Logistical Distribution Network
Micah Beck, JeanPatrick Gelas, Dustin Parr, James S. Plank, Stephen Soltesz
Workshop on Advanced Collaborative Environments, Nice, France, September, 2004
pdf

G. Kortuem, J. Schneider, D. Preuitt, T. G. C. Thompson, S. Fickas, Z. Segall. When Peer to
Peer comes FacetoFace: Collaborative PeertoPeer Computing in Mobile Ad hoc
Networks. In Proc. 1st International Conference on PeertoPeer Computing (P2P 2001),
Linkoping, Sweden, August 2001.

D. S. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins,
Z. Xu. PeertoPeer Computing. Technical Report HPL200257, HP Labs.

L. Yan and K. Sere. Stepwise Development of PeertoPeer Systems. In Proc. 6th
International Workshop in Formal Methods (IWFM'03). Dublin, Ireland, July 2003.

Z. Ge, D. Figueiredo, S. Jaiswal, J. F. Kurose, D. Towsley. Modeling peertopeer file
sharing systems. In Proc. IEEE Infocom, 2003.

F. L. Piccolo, G. Neglia. The Effect of Heterogeneous Link Capacities in BitTorrentLike
File Sharing Systems. In Proc. Intl. Workshop on Hot Topics in PeertoPeer Systems
(HOTP2P'04), Oct, 2004.

M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, \Errorcient erasure correcting
codes," IEEE Trans. Inform. Theory, vol. 47, pp. 569{584, 2001.

R. G. Gallager, Low Density ParityCheck Codes, MIT Press, Cambridge, MA, 1963.

P. Maymounkov, \Online codes," Preprint, 2002.

H. Jin, A. Khandekar, and R. McEliece, \Irregular repeataccumulate codes," in Proc. 2nd
International Symposium on Turbo Codes, 2000, pp. 1{8.

C. Di, D. Proietti, E. Telatar, T. Richardson, and R. Urbanke, \Finitelength analysis of
lowdensity paritycheck codes on the binary erasure channel," IEEE Trans. Inform. Theory, vol.
48, pp. 1570{1579, 2002.

Francesca Lo Piccolo, Giovanni Neglia,
The Effect of Heterogeneous Link Capacities in BitTorrentLike File Sharing Systems
2004 International Workshop on Hot Topics in PeertoPeer Systems (HOTP2P'04)
October 08  08, 2004, Volendam, The Netherlands
html

S. Banerjee, C. Kommareddy, K. Kar, S. Bhattacharjee, and S. Khuller. Construction
of an efficient overlay multicast infrastructure for realtime applications. In
INFOCOM, 2003.

C. Borcea, C. Intanagonwiwat, A. Saxena, and L. Iftode. Selfrouting in pervasive
computing environments using smart messages. In Proceedings of the First
IEEE International Conference on Pervasive Computing and Communications
(PerCom’03). IEEE Computer Society, March 2003.

C. de M. Cordeiro, H. Gossain, and D.P. Agrawal. Multicast over wireless mobile ad
hoc networks: present and future directions. IEEE Network Magazine, 17(1):52–59,
JanFeb 2003.

O. Dousse, P. Thiran, and M. Hasler. Connectivity in adhoc and hybrid networks.
In Proc. IEEE Infocom, June 2002.

P. Th. Eugster and R. Guerraoui. Probabilistic multicast. In 3rd IEEE International
Conference on Dependable Systems and Networks (DSN 2002), pages 313–
322, June 2002.

R. Frenkiel, B.R. Badrinath, J. Borras, and R. Yates. The Infostations challenge:
Balancing cost and ubiquity in delivering wireless data. IEEE Personal Communications
Magazine, Feb. 2000.

M. Grossglauser and M. Vetterli. Locating nodes with ease: Mobility diffusion of
last encounters in ad hoc networks. In The Proceedings of IEEE Infocom, 2003.

C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: A scalable
and robust communication paradigm for sensor networks. In Mobile Computing
and Networking, pages 56–67, 2000.

L. Ji and M. S. Corson. Differential destination multicast  a manet multicast
routing protocol for small groups. In Proceedings of Infocom, 2001.

Y. B. Ko and N. H. Vaidya. Floodingbased geocasting protocols for mobile ad
hoc networks. Mobile Networks and Applications, 7(6):471–480, 2002.

M. Papadopouli and H. Schulzrinne. A Performance Analysis of 7DS, A Peerto
Peer Data Dissemination and Prefetching Tool for Mobile Users. In Advances in
wired and wireless communications, IEEE Sarnoff Symposium Digest, March 2001.

S. Ratnasamy, B. Karp, Y. Li, F. Yu, R. Govindan, S. Shenker, and D. Estrin.
GHT: A Geographic Hash Table for DataCentric Storage. In Proceedings of the
First ACM International Workshop on Wireless Sensor Networks and Applications
(WSNA 2002), Oct. 2002.
Summary: maps a data key to a geographical location. Use geographical routing to find the data.

Y. Sasson, D. Cavin, and A. Schiper. Probabilistic broadcast for flooding in wireless
mobile ad hoc networks. In IEEE Wireless Comm. and Networking Conference
(WCNC 2003), 2003.

J.E. Wieselthier, G.D. Nguyen, and A. Ephremides. On the construction of energyefficient
broadcast and multicast trees in wireless networks. In Infocom, 2000.

N. Sprintg, R. Mahajan and D. Wterall. Measuring ISP topologies with Rocketfuel. In proc. SIGCOMM
2002, Pittsburg, PA, Aug. 20002.

J. S. Plank, S. Atchley, Y. Ding, and M. Beck. Algorithms
for high performance, widearea distributed file downloads.
Parallel Processing Letters, 13(2):207224, June 2003.
15(5):757768, October 1999.
pdf

J. Li, "Embedded audio coding with implicit psychoacoustic
masking", ACM Multimedia 2002, Nice, France, Dec.16, 2001.

D. Eager, M. Vernon, and J. Zahorjan, “Minimizing bandwidth requirements
for ondemand data delivery,” IEEE Trans. Knowl. Data Eng., vol. 13, pp. 742–757, Sept.–Oct. 2001.
 S. Jin and A. Bestavros, “Scalability of multicast delivery for nonsequential
streaming access,” presented at the ACM SIGMETRICS, Marina
Del Rey, CA, 2002.
 S. Sheu, K. Hua, and W. Tavanapong, “Chaining: A Generalized batching technique for videoondemand systems,” in Proc. IEEE
ICMCS, June 1997, pp. 110–117.
 A. Dan, D. Sitaram, and L. V. Environments, “A generalized interval caching policy for mixed interval and long video environments,” presented
at the SPIE MMCN, San Jose, CA, 1996.

M.J. Lin, K. Marzullo, and S. Masini. Gossip versus deterministic flooding: Low message
overhead and highreliability for broadcasting on small networks. In 14th International
Symposium on Distributed Computing, pages 253–267, 2000.

R. van Renesse, K. Birman, "Scalable management and data mining using Astrolabe", IPTPS, Mar 2002.
Summary: Propose a heirarchy of clusters where data aggregation is done using gossip with
higher probability within the cluster.

S. Nelakuditi, Z.L. Zhang, and D. H. C. Du, "On selection of candidate paths for proportional
routing," Computer Networks, vol. 44, no. 1, pp.
79~102, Oct. 2004.

H. Xie, L. Qiu, Y. Yang, and Y. Zhang, "On self adaptive routing in dynamic environments  an
evaluation and design using a simple, probabilistic scheme," in Proceedings of ICNP IEEE
International Conference on Network Protocols, 2004, pp. 12 ~ 23.
Propose a distributed proababilistic routing scheme. Routing distances are based on the
latency. Try to minimize both average latency and link costs. Each node has a routing table with a
probability for each neighbor. Useroptimal routing is called Wardrop routing: "the journy time on
all routes actually used are equal or less than those which would be experianced by a single
vehicle on any unused route". Each user optimizes its own path delay and the network reaches an
equilabrium.

L. Qiu, Y. R. Zhang and S. Shenker, On selfish routing in Internetlike envorinments, In proc. of
ACM SIGCOMM 2003, Germany, Aug. 2003.

D. Kempe, A. Dobra and J. Gehrke. Gossip based computation of a ggregate information. In Proc.
Conference on Foundations of Computer Science, IEEE 2003.

W. Wei, and A. Zakhor, “Multipath unicast and multicast video communication over
wireless ad hoc networks,” Proc. Int. Conf. Broadband Networks, Broadnets, pp. 496505, 2002.

E. Setton, T. Yoo, X. Zhu, A. Goldsmith, and B. Girod, “Crosslayer design of ad hoc
networks for realtime video streaming,” IEEE Wireless Communications Mag., vol. 12, no. 4,
pp. 5965, Aug. 2005.

R.F. Liao, R. Wouhaybi and A. Campbell, “Wireless Incentive Engineering,” IEEE J. on
Select. Areas in Commun., Special Issue on Recent Advances in Multimedia Wireless, 4th Quarter
2003.

S. Shenker, “Efficient network allocations with selfish users,” in Proc. Perform. ’90.
Edinburgh, Scotland, pp. 279–285, September 1990.

J. MacKieMason and H. Varian, “Pricing Congestable Network Resources,” IEEE J. on
Select. Areas in Commun., vol. 13, no.7, pp. 11411149, September 1995.

R. La and V. Anantharam, “Optimal Routing Control: Repeated Game Approach,” IEEE
Trans. Automatic Control, Vol. 47, No. 3, pp. 437 450, March 2002.

Y. Guo, K. Suh, J. Kurose, and D. Towsley, “A PeertoPeer OnDemand Streaming Service and
Its Performance Evaluation,” Proc. International Conference on Multimedia and Expo (ICME
'03), 69
July 2003, vol.2, pp.64952.

S. Annapureddy, M. J. Freedman and D. Mazieres. Shark: Scaling file servers via cooperative
caching. In NSDI 2005.

K. Park and V. S. Pai. Deploying large file transfer on an HTTP conetent distribution network. In
WORLDS 04'. (CoBlitz)

A. Vadat, K. Yocum, K. Walsh, P. Mahadevan, D. Kostic, J. Chase and D. Becker. Scalability and
accuracy in a large scale network emulator. In OSDI 2002.(ModelNet)

S. Iyer, A. Rowstron, and P. Druschel. Squirrel: A decentralized peertopeer
web cache. In Proc. 21st ACM SIGACTSIGOPS Symposium on Principles of
Distributed Computing (PODC), 2002.",

K. Ranganathan, M. Ripeanu, A. Sarin, and I. Foster, “To share or
not to share: An analysis of incentives to contribute in collaborative
file sharing environments,” in Workshop on Economics of PeertoPeer
Systems, Berkeley, California, June 2003.

C. Buragohain, D. Agrawal, and S. Suri, “A game theoretic framework
for incentives in P2P systems,” in proceedings P2P, Sweden, Sept. 2003.
V. Vishnumurthy, S. Chandrakumar, and E. Gun Sirer,

KARMA: A secure economic framework for P2P resource sharing,” in Workshop on
Economics of PeertoPeer Systems, Berkeley, California, June 2003.

J. Kangasharju, J. Roberts, and K.W. Ross, “Object replication strategies
in content distribution networks,” Comput. Commun., vol. 25, no. 4, pp.
376–383, Mar. 2002.

J. Kangasharju, “Internet content distribution,” Ph.D. dissertation, Dept.
Comput. Sci., Univ. Nice, Nice, France, Apr. 2002.

B.J. Ko and D. Rubenstein, “A greedy approach to replicated content
placement using graph coloring,” in Proc. SPIE ITCom Conf. Scalability
and Traffic Control in IP Networks II, Jul. 2002, pp. 289–298.

E. Cohen and S. Shenker, “Replication strategies in unstructured peertopeer
networks,” in Proc. ACM SIGCOMM, Pittsburgh, PA, Aug. 2002,
pp. 177–190.

Gerard Salton and Chris Buckley. Term weighting approaches in
automatic text retrieval. Technical report, Ithaca, NY, USA, 1987.

H. Schutze and C. Silverstein. A comparison of projections for efficient
document clustering. In Prooceedings of ACM SIGIR, pages 74–81,
Philadelphia, PA, July 1997.

C. L. Viles and J. C. French, “Dissemination of collection
wide information in a distributed information retrieval system,” in
Proceedings of the 1995 ACM SIGIR Conference, 1995

Dina Katabi, Mark Handley, and Charles Rohrs, "Internet Congestion Control for Future High
BandwidthDelay Product Environments." ACM Sigcomm 2002, August 2002.

D. B. Johnson and D. A. Maltz. Dynamic Source Routing in
Ad Hoc Wireless Networks. In Mobile Computing, volume
353. Kluwer Academic Publishers, 1996.
Summary: introduce the random waypoint model for MANETs (each node selects a destination at random
and travels to it with a fixed speed).

M. Li, W.C. Lee, and A. Sivasubramaniam. Efficient peer
to peer information sharing over mobile ad hoc networks. In
Proc. of Second WWW Workshop on Emerging Applications
for Wireless and Mobile Access (MobEA04), May 2004.
Summary: An extension of GHT. MPI stands for a multilevel peer index. Instead of routing to a fixed
geographical location, the routing is done to a spatial erea.
 G. Resta and P. Santi. An analysis of the node spatial distribution
of the random waypoint model for Ad Hoc networks.
In Proc. of ACM Workshop on Principles of Mobile Computing
(POMC), October 2002.
Summary: paper analyzing the random waypoint model RWM.

B. Karp and H. T. Kung. GPSR: greedy perimeter stateless
routing for wireless networks. In Proc. of ACM International
Conference on Mobile Computing and Networking
(MobiCom), August 2000.
Summary: routing is done greedily towards destination. When the route is stuck in a local minimum
a bypass is done.
Others
 Analysis of BitTorrent and its use for the Design of a P2P based streaming Protocol for a
Hybrid CDN  Skevik, Goebel, Plgemann

C. Riley and C. Scheideler. Guaranteed broadcasting using SPON: A supervised peer overlay network.
In 3rd
International Z¨urich Seminar on Communications(IZS), 2004. ps
Summary: built an overlay tree which centeral servers which assignes node to the topology.
 Speedup of Data Access using Error Correcting code in P2P Networks

WebTorrent: a BitTorrent Extension for High Availability Servers 
Sivek, Wolfe, Zhivich
Summary: proposed using BitTorrent for avergaing load on web servers. When the server is
loaded, the content is disseimated using BitTorrent to clients. Wrote plugin for mozilla which
receives the content using BitTorrent and displays it. Wrote a plugin for apache web server.

The Darknet and the Future of Content Distribution
Peter Biddle, Paul England, Marcus Peinado, and Bryan Willman, Microsoft Corporation
pdf
Summary: A document discussing legal economic and social aspects of illegal file sharing.
 Optimal Unconditional Information Diffusion  Malkhi, Pavlov, Sella
 Circus: Oppotunistic Block Reordering for Scalable Content Servers  Anastasiadis,
Wickremesignhe, Chase
 B. J. Frey, H. A. Loeliger, F. R. Kschichang, N. Wiberg. Factor graphs and algorithms.
 P. Oude and B. Ottens and G. Pavlin. Information Fusion with Distributed Probabalistic
Networks.
 C. Borcea, C. Intanagonwiat, A. Saxena and L. Iftode, Selfrouting in pervasive computing
environment using smart messages.
 D. Slepian and J. K Wolf. Noiseless Coding of Correlated Information Sources. IEEE transaction
on information theory, 1972.
Summary: determines the maximum rate for noisless coding of two sources.

J. Li. The efficient implementation of high rate ReedSolomon erasure resilient code. In ICASSP
2005.
Summary: good overview of RS codes. Proposes two optimization for speeding up the coding
implementation.

H. Ma, K. G. Shin and W. Wu. BestEffort Patching for Multicast True VoD Service. Multimedia Tools
and Applications archive Volume 26 , Issue 1 (May 2005), pp. 101  122.
Summary: Propose a patching scheme called BestEffot Patching (BEP) that supports bost request
admission and VCR interactivity. The basic idea is that when a client changes its stream location,
two channels are used, one to immediatly play the new location (called patching channel) and the other to be buffered
until the client reaches the latest multicast channel.

George Pallis, Athena Vakali. Insight and
perspectives for content delivery networks. Commun. ACM 49 (1): 101106 (2006)

Athena Vakali George Pallis: Content
Delivery Networks: Status and Trends. IEEE Internet Computing 7 (6): 6874 (2003)

Konstantinos Stamos George Pallis, Athena Vakali: Integrating Caching Techniques
on a Content Distribution Network. ADBIS 2006 : 200215

George Pallis, Konsta$ntinos Stamos. Replication Based on Objects Load under
a Content Distribution Network. ICDE Workshops 2006: 53
Not related
A graph based approach to the
convergence of some iterative methods for
singular Mmatrices and Markov chains pdf
Matthias Pott. On the convergence of asynchronous iteration methods for nonlinear
paracontractions and consistent linear systems. Linear Algebra and its Applications, 283:133,
1998. html
Grinstead and Snell's Introduction to Probability
The CHANCE Project. Chapter 11  Markov chains. pdf
Y. Saad. Iterative Methods for Sparse Linear Systems", WPS, (1996). zip
J.R. Shewchuk. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain.
Technical Report CMUCS94125, School of Computer Science, Carnegie Mellon University, 1994.
pdf
J. K. Jophnson. Term Paper for 6.291 Graphical Modeling Seminar taught by S. Mitter:
WalkSummable GaussMarkov Random Fields, Feb. `02pdf
J. Kleinberg, M. Sandler, "Convergent Algorithms for Collaborative Filtering, " Proc. ACM
Conference on Electronic Commerce, 2003.
E. Cohen. Sizeestimation framework with applications to transitive closure and reachability.
Journal of Computer and System Sciences, 55(3):441453, December 1997.
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, "Gossip and mixing times of random walks on
random graphs," unpublished, 2004
Peterson and Pederson. The matrix Cookbook. pdf
Amnon Shashua and Anat Levin. Ranking with large margin principle: Two approaches. In NIPS*14,
2003.html
Summary: Extend the SVM algorithm by using
several parallel hyperplanes.
Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the
Web. In Proceedings of the 10 th International World Wide Web Conference, Hong Kong, May 2001.
html Summary: given several partial
ordred list discuss ways to merge them into one ranked list. Example application is for getting
results from multiple search engines and merging them.
J. Shlens. A tutorial on Principal Component Analysis.pdf
Acknowlegements
The following people contributed interesting papers to this site: (or where kind enough to answer
tehcnical questions about their
papers)
Prof. Pascal Felber, University of Neuchatel
Prof. Dahlia Malkhi, HUJI, Microsoft Research
Dr. Pablo Rodriquez, Microsoft Research
Dr. Johan Pouwelse, Delft University of
Technology, The Nederlands
Prof. Danny Dolev, HUJI
Prof. Scott Kirkpatrick, HUJI
Dr. Yair Weiss, HUJI
Prof. Karl Aberer, EPFL
Dr. Scott Atchley, University of Tennessee
Prof. Amin Shokrollahi, EPFL
Yaron Weinsberg, HUJI
Dr. Yuval Shavitt, TAU
Prof. Philip Chou, MS Research
Prof. Alex C. Snoeren, USCD
Dr. Jin Li, MS Research
Dr. Alexander T. Ihler, MIT
Ciamac C. Moallemi, Stanford
Michael J. Freedman, NYU
Prof. Vankatesh Saligrama, BU
I will be very happy to get comments or other interesting papers, please email me at: daniel51 {AT}
cs.huji.ac.il
