Home

Protocols

Performance

Modeling and Incentives

Positioning

Error Correcting Codes

Caching

Searching

Deployed Systems

Transport Layer

Parallel and Network Computation

Fault Tolerance

Learning

Network Flows

Gossip

Security and Trust

Social Networks

T.B.D

Not related

Acks

Systems \ protocols sorted by name

Conferences sorted by name

Content Distribution Resources

Protocols and Deployed Systems

1987

1. 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 anti-entropy 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

2. Floyd, S., Jacobson, V., Liu, C., McCanne, S., and Zhang, L., "A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing", IEEE/ACM Transactions on Networking, December 1997, Volume 5, Number 6, pp. 784-803 (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.
3. E. Schooler and Jim Gemmel, Using Mulitcast FEC to Solve the Midnight Maddness Problem, MS Research Tech Report MST-TR-97-25, 1997
   Summary: Combine multicast with forward error correction to handle the flash crowd problem.

   1998

4. P. Rodriguez, E. W. Biersack and K. W. Ross, "Improving the Latency in the Web: Caching or Multicast?", International Caching Workshop, Manchester, England. June 15-17, 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.
5. K. Hua, Y. Cai, and S. Sheu, Patching: A multicast technique for true on-demand 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

6. K. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu and Y. Minsky, Bimodal Multicast. ACM Transactions on Computer Systems 17(2) (May 1999), 41-88 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 50-100 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 anti-entropy 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 anti-entropy 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

7. 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 1-12. (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.
8. 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.
9. W. Litwin, T. Schwarz, LH*RS: A High-Availability 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

10. S. Rantansamy, M. Handley, R. Karp, S. Shenker. Application-level Multicast using Content Addressable Networks n Proceedings of Third International Workshop on Networked Group Communication NGC 2001), London, England, 2001. (CAN-Multicast) 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.
11. L. Xu, "Efficient and Scalable On-Demand 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.
12. H. Deshpande, M. Bawa, and H. Garcia-Molina. Streaming live media over a peer-to-peer network. Technical report, 2001-31, 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.
13. 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.
14. M. Waldman, D. Mazieres, Tangler: A censorship-resistant 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

15. 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.
16. 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 GT-ITM 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.
17. 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 on-demand streaming.
18. V. N. Padmanabhan, H. J. Wang, and P. A. Chou. Resilient peer-to-peer 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.
19. W. Wang, D. Helder, S. Jamin, L. Zhang, "Overlay Optimizations for End-host 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 5-10% 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.
20. M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. Scribe: A large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in Communications, 20:1489-1499, 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.
21. 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 UT-CS-02-498, 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.
22. S. Graupner, W. Kalfa, C. Reinmann, "Modeling and simulation of media-on-demand service - evaulating a digital media grid architechture", in HP Lab technical report, HPL-2002-192, 2002. pdf
    Summary: Present a 3-tier 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.
23. P. Druschel, A. Rowstron, PAST: A large-scale, persistnet peer-to-peer storage utility. In Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles, pages 188--201, 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.
24. 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 two-tier architecture. The small primary tier is the content producer and the second is a large soft-state 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 d-tree. Dod simulation using GT-ITM and MSNBC traces.

    2003

25. Y. Birk and D. Crupnicoff, "A Multicast Transmission Schedule for Scalable Multi-Rate Distribution of Bulk Data using Non-Scalable 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.
26. B. Cohen, "Incentives build robustness in BitTorrent", P2P Economics Workshop, 2003. (BitTorrent) pdf
    Summary: presents BitTorrent protocol.
27. Bayeux: An Architecture for Scalable and Fault-tolerant Wide-area 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.
28. L. Cherkasova, J. Lee. FastReplica: Efficient Large File Distribution within Content Delivery Networks. HP Labs Technical Report HPL-2003-43, Feb. 2003. (FastReplica) pdf
    Summary: Discuss small groups of nodes 10-30 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.
29. 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.
30. M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh, "SplitStream: High-Bandwidth 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 non-leaf 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 GT-ITM model.
31. Early Experience with an Internet Broadcast System Based on Overlay Multicast Yang-hua 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.
32. Algorithms for High Performance, Wide-area Distributed File Downloads James S. Plank, Scott Atchley, Ying Ding, Micah Beck Parallel Processing Letters, Volume 13, Number 2, June, 2003, pages 207-224 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).
33. M. S. Allen and R.Wolski. The Livny and Plank-Beck 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 Plank-Beck 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 Plank-Beck 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.
34. Y. Chi and K. Nahrsted. Layered Peer-to-Peer Streaming. In Proc. of NOSSDAV 2003.
    Summary: Propose a solution for the on-demand 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 NP-complete using a reduction from the single-source 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.
35. M. Hefeeda, A. Habib, B. Botev, D. Xu and B. Bhargava. PROMISE: Peer-to-Peer 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 end-to-end 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 (GT-ITM topology) and also some Internet experiments using PlanetLab.

    2004

36. Ying Zhu, Baochun Li, Jiang Guo, "Multicast with Network Coding in Application-Layer Overlay Networks", IEEE Journal on Selected Areas in Communications, January 2004. pdf
    Summary: Topology of 2-redundant 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, k-redundant 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 2-redundant 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.
37. Tran, Hua, Do. A Peer-to-Peer Architecture for Media Streaming(Zigzag) In IEEE Journal of selected areas of communications, January 2004, pp. 121-133. 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.
    
38. 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, at-capacity 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.
39. Wang, C. Jin, S. Jamin, "Network Overlay Construction under Limited End-to-End Addressability" Technical Report CSE-TR-489-04, EECS Department, University of Michigan, 2004. pdf
    
40. R. Rejaie and S. Stafford, "A Framework for Architecting Peer-to-Peer Receiver-driven Overlays", Nossdav 04, Ireland, June 2004. (PRO) pdf
    Summary: PRO designed for non-interactive 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.
41. Jin Li, Philip A. Chou and Cha Zhang, Mutualcast: An Efficient Mechanism for Content Distribution in a Peer-to-Peer (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.
42. M. Hefeeda, A. Habib, D. Xu, B. Bhargava, and B. Botev, CollectCast: A peer-to-peer 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, end-to-end and topology-aware. End-to-end technique estimates the path to the sending peer. Topology-aware 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 GT-ITM 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.
43. Tai T. Do, Kien A. Hua, Mounir Tantaoui. P2VoD: Providing Fault Tolerant Video-on-Demand Streaming in Peer-to-Peer 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 GT-ITM network of about 100 nodes. Compared their system into P2Cast in terms of failure recovery or join performance.
44. S. Birrer, D. Lu, F. E. Bustamante, Y. Qiao, and P. Dinda. FatNemo: Building a Resilient Multi-Source MulticastFat-Tree. 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 fat-trees 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. Co-leaders are used for fault tolerance (they are also called a crew). Co-leaders 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 co-leaders) 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.
45. J. Li, PeerStreaming: A Practical Receiver-Driven Peer-to-Peer Media Streaming. Microsoft Research Techcnical Report MS-TR-2004-101. 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.
46. S. Androutsellis-Theotokis and D. Spinellis, A Surevy of Peer-to-Peer Content Distribution Technologies. ACM Computing Surveys, Vol. 36, No. 4, Dec. 2004, pp. 335-371.
    Summary: details routing mechanisms and DHT topologies, security and incentive mechnisms. The title is misleading since this paper does not discuss specifically content distribution.
47. Y. Cui, B. Li, K. Nahrstedt, "oStream: asynchronous streaming multicast in application-layer overlay networks", IEEE Journal of Selected Areas in Comm., vol. 22, no. 1, pp. 91-106, Jan. 2004.
    Summary: Addresses the on-demand 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

48. X. Zhang, J. Liu, B. Li, and T.-S. P. Yum, DONet/CoolStreaming: A Data-driven 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 data-centric 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.
49. 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 state-of-the-art BitTorrent protocol.
50. “Maintaining High-bandwidth 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

51. 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).
52. B.J Ko and D. Rubenstein. Distributed Self-Stabilizing 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 3-way handshake to synchronize color exchanges between nieghbors. Possible applications are wireless channel allocation, distributed leader election and distribution resource directory.
53. "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 public-key encryption for enforcing fair sharing. First the ecnrypted data is transferred and last the keys to decrypt the data are exchanged.

    Distributed Hash Tables

54. 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.
55. [CAN] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. A scalable content-addressable network. In Proc. ACM SIGCOMM 2001, August 2001. (CAN) pdf
    Summary: present CAN network, which is based on a d-dimentional cartezian coordinate space on d-torus. 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.
56. [Pastry] A. Rowstron, P. Druschel, "Pastry: Scalable, Decentralized Object Location and Routing for LargeScale Peer-to-Peer 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.
57. [Tapestry] B. Y. Zhao, J. Kubiatowicz, a. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing UCB Tech. Report UCB/CSD-01-1141. (Tapestry) pdf
58. Ion Stoica, Daniel Adkins, Shelley Zhuang, Scott Shenker, and Sonesh Surana. Internet indirection infrastructure. In Proc. ACM SIGCOMM 2002 Conference SIGCOMM 2002), pages 73--88, 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 GT-ITM topologies with 5000 nodes.
59. M. A. Zaharia, S. Keshav, Design Analysis and Simulation of a System for Free-Text Search in P2P Networks, unpublished. pdf
    Summary: propose hierarchy in order to support free text search in CDNs. Top layer (0.1-0.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 1-2% 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.
60. S. Rhea, C. Wells, P. Eaton et al. Maintenance-free global data storage", in IEEE Internet Computing, pp. 40-49, 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 SHA-1. 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.
61. Practical Locality-Awareness 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 Peer-To-Peer 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.
62. 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.
63. S. Marti, P. Ganesan, and H. Garcia-Molina. DHT routing using social links. In 3rd International Workshop on Peer-to-Peer 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

64. [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.
65. Wang, H. Chang, A. Zeitoun, S. Jamin, "Characterizing Guarded Hosts in Peer-to-Peer 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 25-36% of the hosts on those networks are gaurded. The percentage of popluar files which is stored on guarded hosts is about 25-30%. 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.
66. W. Wang, Cheng Jin, Sugih Jamin, "Network Overlay Construction under Limited End-to-End Addressability" Technical Report CSE-TR-489-04, 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.
67. 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.
68. [FHKM04] F. Le Fessant, S. Handurukande, A. M. Kermarrec amd L. Massouli´e, Clustering in Peer-to-Peer 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.
69. M. Izal, G. Urvoy-Keller, E.W. Biersack, P. elber, A. Al Hamra, and L. Garces-Erice, "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 tit-for-tar method is working.
70. 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.
71. T. Karagiannis, A. Broido, N. Brownlee, K. Claffy, M. Faloutsos. "File-sharing 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.
72. J. A. Pouwelse, P. Garbacki, D.H.J. Epema, H.J.Sips, "A Mesaurement Study of the BitTorrent Peer-to-Peer File Sharing System, Technical Report PDS-2004-007, 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.
73. M. Castro, M.B. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman. An evaluation of scalable application-level multicast built using peer-to-peer 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 GT-ITM 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.
74. [Borg] R. Zhang and Y. C. Hu. Borg: a hybrid protocol for scalable application level multicast in peer-to-peer 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.
75. Jacky Chu, Kevin Labonte, and Brian Neil Levine, "Availability and locality measurements of peer-to-peer 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.
76. P. Rodriguez, E. Biersack, "Dynamic Parallel-Access 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.5-8 download time.
77. Anthony Bellissimo, Prashant Shenoy, Brian Neil Levine, "Exploring the Use of BitTorrent as the Basis for a Large Trace Repository", Technical report 04-41. 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.
78. Downloading Replicated, Wide-Area 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 progress-driven 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.
79. Can Self-Organizing P2P File Distribution Provide QoS Guarantees?, to appear in OSR Special Issue on Self-Organizing 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

80. T. W. J. Ngan, D. S. Wallach, and P. Druschel. "Enforcing fair sharing of peer-to-peer 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.
81. Kevin Foltz, Jehoshua Bruck, "Splitting Schedules for Internet Broadcast Communication," IEEE Transactions on Information Theory, vol. 48, number 2, February 2002, pp. 345-358.
    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.
82. T. W. Ngan, A. Nandi, A. Singh, D. S. Wallach ,P. Druschel "On designing incentives-compatible peer-to-peer 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.
83. 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.
84. [VY03] G. de Veciana and X. Yang, "Fairness, incentives and performance in peer-to-peer 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 markov-chain 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.
85. Ahsan Habib, John Chuang "Incentive Mechanism for Peer-to-Peer Media Streaming," International Workshop on Quality of Service(IWQoS) pp. 171-180, June, 2004. pdf
    Summary: propose a rank-based 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 GT-ITM 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.
86. D. Qiu and R. Srikant. "Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer 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.
87. Zongpeng Li, Baochun Li, Dan Jiang, and Lap Chi Lau, "On Achieving Optimal End-to- 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 sub-tree 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 NP-hard. 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.
88. P. A. Felber, E. W. Biersack, "Self-scaling Networks for Content Distribution". In Self-Star: 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.
89. E.W.Biersack, P. Rodriguez, and P. Felber, "Performance Analysis of Peer-to-Peer 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, k-rooted 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)
90. J. Mundinger and R.R. Weber, "Efficient File Dissemination using Peer-to-Peer Technology" Technical Report, Statistical Laboratory Research Reports 2004-01, 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.
91. 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.
92. [NCR+03] T. S. E. Ng., Y. H. Chu, S. G. Rao, K. Sripandkulchai, H. Zhang, "Measurement-based optimization techniques for bandwidth-demanding peer-to-peer 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 2001-2. 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 non-adaptive networks) about 40-50% 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.
93. Z. Ge, D. R. Figueiredo, S. Jaiswal, J. Kurose, D. Towsley, "Modeling Peer-to-Peer 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 off-line. 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.
94. K. P. Gummadi, R. J Dunn, S. Saroiu, S. D. Gribble, H. M. Levy, J. Zahorjan, Measurement, Modeling and Analysis of a Peer-to-Peer 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 hit-rate 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% hit-rate of lo and 37% hit-rate of so. Highly available peers tend to consume more bandwidth and thus both necessary and sufficient for obtaining high hit-rate.
95. J.A. Pouwelse, P. Garbacki, D.H.J. Epema, H.J. Sips, The Bittorrent P2P File-sharing System: Measurements and Analysis, 4th International Workshop on Peer-to-Peer Systems (IPTPS'05), Feb 2005. pdf
96. "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.
97. Kunwadee Sripanidkulchai, Aditya Ganjam, Bruce Maggs, and Hui Zhang The Feasibility of Supporting Large­Scale Live Streaming Applications with Dynamic Application End­Points, 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, non-stop events (like a radio-station) 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.
98. Chip Killian, Michael Vrable, Alex C. Snoeren, Amin Vahdat and Joseph Pasquale, The Overlay Network Content Distribution Problem. Technical Report CS2005-0824 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 NP-Complete using a reduction from the dominating set problem.
99. 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.
100. 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.
     
101. 
     A. Legout, G. Urvoy-Keller, and P. Michiardi. Rarest First and Choke Algorithms Are Enough.In Proceedings of ACM SIGCOMM USENIX IMC'2006, October 25--27, 2006, Rio de Janeiro, Brazil.
     Summary: shows what we know - that the BitTorrent algorithm is working very efficiently on practice.

     Deployed systems

102. Y. Kulbak, D. Bickson, The eMule protocol specification, Hebrew University Technical Report TR-2005-03, January 2005. pdf
103. Clip2, The Gnutella Protocol Specification, version 1.2 pdf
104. [BS2004] An Analysis of the Skype Peer-to-Peer 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.
105. Simson L. Garfinkel, VoIP and Skype Security. pdf
106. Analysis of Skype security using reverse engineering - by BlackHat Europe pdf
107. S. Guha, N. Daswani, and R. Jain. An experimental study of the Skype peer-to-peer VoIP system. In IPTPS, 2006
     Summary: provide some details regarding the sessions lengths and peer inter-arrival times using Skype. Recorded traffic for several months in late 2005 in Cornel.
108. 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
109. 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.
110. 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 K-Means 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

111. 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.
112. 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.
113. P. Ganesan, Q. Sun, and H. Garcia-Molina, "Apocrypha: Making p2p overlays network-aware", 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.
114. [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 d-dimensional 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 multi-dimensional 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 GT-ITM, 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.
115. [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 light-weight 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 - ||Xi-Xj||)*u(xi-xj). 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 GT-ITM 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

116. Ellen W. Zegura, Ken Calvert and S. Bhattacharjee. How to Model an Internetwork. Proceedings of IEEE INFOCOM 1996, San Francisco, CA. (GT-ITM) ps.gz
     Download software
     Fixed compiling version for linux
117. C. Jin, Q. Chen, S. Jamin, Inet: Internet Topology Generator University of Michigan Technical Report CSE-TR-433-00. (INET) pdf
     Download v. 3
118. 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
119. "Medusa -- New Model of Internet Topology Using k-shell Decomposition," Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir. cond-mat/0601240
     Summary: present the Medusa model of Internet topology based on the DIMES project measurements.

     Error Correcting Codes, Source Coding and Network Coding

     1989

120. 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

121. G. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon limit error-correcting coding: Turbo codes, in Proc. 1993 Int. Conf. Commun., Geneva, Switzerland, May 1993, pp. 1064-1070.
     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 low-weight codewords by creating high-weight codewords by the other decoder. Gain performance of random block codes. Decoding is done using the alpha-beta algorithm which minimizes of the bit error rate (and not the word error rate as in Viterbi).

     1995

122. 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. 100-111. 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 N-K 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^-1|Cs]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.
123. J. Blomer, M. Kalfane, R. Karp, M. Karpinsky, M. Luby and D. Zukerman, An XOR-based ersure resilient coding scheme, Technical Report TR-95-048, 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

124. A. Albanese, J. Blonder, J. Edmonds, M. Luby and M. Sudan. Priority encoding transmission. IEEE Trans. Information Theory, 42:1737-1744, 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

125. John W. Byers, Michael Luby, Michael Mitzenmacher, and Ashutosh Rege, "A Digital-Fountain 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 2-4 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
126. 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

127. 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

128. 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 max-flow min-cut 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 non-negative 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 max-flow 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 max-flow 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

129. 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

130. 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 1-delta 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.
131. Weatherspoon, H., AND Kubiatowicz, J. Erasure coding vs. replication: A quantitative comparison. In Proc. of International Workshop on Peer-to-Peer 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

132. 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.
     
133. 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.
134. A. Shokrollahi, Raptor Codes, Technical Report, Digital Fountain, EPFL. pdf
     Summary: The paper presents raptor codes which is an extension of LT-codes with linear time encoding and decoding. The paper includes a very good overview of coding, digital fountain codes and LT-Codes.
     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. Digital-Fountain 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 LT-Codes. 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 pre-coding 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 LT-code 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 pre-coding to increase the number of input symbols.
135. 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 h-dimensional 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 (non-innovative 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 max-flow 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).
136. S.-Y. R. Li and R. W. Yeung and N. Cai "Linear Network Coding", IEEE Trans. on Information Theory, IT-49(2):371-381, Feb. 2003.
     Summary: show that it is sufficient of the network coding fucntions to be linear.

     2004

137. M. Krohn, M. Freedman, D. Mazieres, “On-the-Fly 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.
138. 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.
139. K. Jain, L. Lovasz and Philip A. Chou, Building Scalable and Robust Peer-tp-Peer Overlay Networks for Broadcasting using Network Coding Microsoft Research Technical Report MSR-TR-2004-135, 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

140. 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.
141. K. Jain, L. Lovasz and P. A. Chou, Building scalable and robust peer-to-peer 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.
142. R. W. Yeng, S. Robert Li, N. Cai and Z. Zhang: Theory of Network Coding.
     Summary: good overview of the network coding field.

     Searching

143. Efficient Content Location using Internet Based Locality in Peer-to-Peer 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.
144. 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.
145. Sarunas Girdzijauskas, Anwitaman Datta, Karl Aberer, Oscar: Small-world overlay for realistic key distributions, DBISP2P 2006, The Fourth International Workshop on Databases, Information Systems and Peer-to-Peer 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

146. M. R. Kuripolu, M. Dahlin, Coordinated Placement and Replacement for Large-Scale 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: non-cooperative and cooperative. Among the tested non-cooperative 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 level-i objects (objects in the i-th 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.
147. M. R. Korupolu, C. G. Plaxton and R. Rajaraman. Placemnt algorithms for hierarchical cooperative caching. In proc. of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 586-595, 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.
148. 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 654--663, 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.
149. 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

150. 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 sending-rate 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).
151. 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.
152. 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.
153. 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.
154. 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).
155. 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 high-end server environment when the bottleneck is not the bandwidth but server processing time.

     Parallel and Network Computation

156. Fast Tuning of Intra Cluster Collective Communications. Luiz Angelo Barchet-Estefanel., Gr´egory Mouni´e
157. P. Tvrdik. One-to-all 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 one-to-all broadcast in the SF (store and forward) model in Erew PRAM and hypercube using SBT (spanning binomial tress) to both 1-port and k-port 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 2-D tori T(5^k, 5^k) is the dilated digaonal based approach.
158. P. Tvrdik. Multicast, IRC, and one-to-all 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 all-port noncombining hc, where necklaces are created in order to create disjoint spanning trees.
159. P. Tvrdik. All-to-all broadcast algorithms. Lecture notes of topics in parallel computing course, University of Wisconsin Medison, 1999. ps
160. P. Tvrdik. All-to-all scatter algorithms. Lecture notes of topics in parallel computing course, University of Wisconsin Medison, 1999.. ps
161. Q. F. Stout and Bruve Wagar. Intensive Hypercube Communication: Prearranged Communication in Link-Bound Machines. In Journal of Parallel and Distributed Cmoputing 10 (1990), pp. 167-181.
162. A. Bar-Noy and Shlomo Kipnis. "Broadcasting multiple messages in simultaneous send/receive systems". In Discrete Applied Mathematics 55 (1994) pp. 95-105.
     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.
163. A. Bar-Noy and C. T. Ho. Broadcasting multiple messages in the multiport model. IEEE Trans on Parallel Dist. Sys. 10(5):500-508, 1999.
164. A. Bar-Noy, S. Kipnis, and B. Schieber. Optimal multiple message broadcasting in telephone-like communication systems. Discrete Applied mathematics, 100:1-15, 2000.
165. A. Bar-Noy, J. Brick, C.T. Ho, S. Kipnis, B. Schieber. Computing Global Combine Operations in the Multi-Port 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.
166. L. G. Valiant, A scheme for fast parallel communication. SIAM J. Comput. 11,2 (1982), 350-361.
167. Jehoshua Bruck, Ching-Tien Ho, Eli Upfal, Shlomo Kipnis and Derrick Weathersby, Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems,in IEEE Trans. Parallel Distrib. Syst. 8:11 1143-1156, 1997. Summary: proposed efficient algorithms for all-to-all 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 start-up 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

168. 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 best-effort, HHP (hop by hops naks), FEC and PRM. Did simulation using GT-ITM with 22K nodes.
169. P. Ganesan, M. Bawa, H. Garcia-Molina, "Online Balancing of Range Partitioned Data with Applications to Peer-to-Peer 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.
170. Stefan Birrer and Fabi?n E. Bustamante. Nemo -- Resilient Peer-to-Peer Multicast without the Cost. Technical Report NWU-CS-04-36, 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.
171. K. Aberer, A. Datta, M. Hauswirth and R. Schmidt. Indexing data-oreinted overlay networks. In VLDB 2005.
     Summary: present the P-Grid 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

172. J. Jordan and Yair Weiss, "Probabilistic inference in graphical models". ps
173. 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.
174. R. Vicente, D. Saad, Y. Kabashima, Low density parity check codes - a statistical physics perspective ps
     Summary: Another explanation of the BP algorithm (pp. 11-16), and good overview of LDPC codes.
175. Y. Weiss, Approximate inference using loopy belief propagation ps
     Summary: numeric example of BP calcaultions from some lecture.
176. Y. Weiss, Exact inference in tress using belief propagation pdf
     Summary: lecture notes
177. M. Jordan, Y. Weiss, Graphical models: probabablistic inference ps
     Summary: an overview of this field including exact and approximate inference, variational and sampling methods.
178. D. J. C. MacKey, Information Theory, Inference, and Learning Algorithms pdf
179. Webpage explaining junctions tree construction. html
180. M. Paskin, A short course of graphical models lecture 1 (pdf) lecture 2 (pdf) lecture 3 (pdf)
181. M. Paskin, Exploiting Locality in Porbablistic Inference, Ph. D. thesis, Univ. of Clifornia, Berkeley, Fall 2004. pdf
182. 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 mutli-dimensional sampling. A single iteration involves sampling one parameter at a time.
183. 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).
184. C. Yanover and Y. Weiss, Finding the M most probable configurations using Loopy Belief Propagation, in proc. of NIPS 2003.
185. iccv
186. Y. Weiss and W. T. Freeman, On the optimiality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory 47:2 pages 723-735. (2001). pdf
     Summary: Show that the max product algorithm acheives strong local maximum (which is a suboptimal solution) when it converges.
187. M. Wainwright, T. Jaakkola and A. Willsky, "Tree-based reparameterization framework for analysis of belief propagation and related algorithms," IEEE Trans. Information Theory, 2003
188. M. J. Wainwright, T. Jaakkola, A. S. Willsky. "Tree-based 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.
189. 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 tree-structured problems.
190. J. S. Yedidia, W. T. Freeman and Y. Weiss. Bethe free energy, Kikuchi approximations, and belief propagation algorithms. Mitsubishi Electric Research Labs, Technical Report TR-2001-16, May 2001.
     Summary: explain the derivation of the generalized BP algorithm from Kikuchi free enery approximation.
191. A. Braunstein, M. Mezard, M. Weight, R. Zecchina. Constraint Satisfsaction By Survey Propagation. cond-mat 0212451. Sept. 2003. pdf
192. A. Braunstein, M. Mezard, R. Zecchina. Survey Propagation: an Algorithm for Satisfiability. cond-mat 0212002, Nov. 2003
     Summary: Explain the Survey Propagation tehcnique used for solving random 3-SAT and q-coloring problems.
193. J. S. Yedidia, W. T. Freeman and Y. Weiss. Understanding Belief Propagation and its Generalization. Merl Tech Report TR-2001-22, 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.
194. T. Jaakola, Tutorial on variational approximation methods. ps
195. 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.
196. iJ. K. Johnson. Term Paper for 6.291 Graphical Modeling Seminar taught by S. Mitter: Walk-Summable Gauss-Markov 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.
197. Walk-Sum Interpretation and Analysis of Gaussian Belief Propagation Jason Johnson, Dmitry Malioutov, Alan Willsky. NIPS 05. pdf
198. 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.
199. 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.
200. 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(x|y). Using the Bayesian approach, p(x,y) = p(x) * prod(p(y_i|x)). 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.
201. T. Joachims, Making large-scale 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.
202. 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.
203. S. Vijayakumar and S. Wu: "Sequential support vector classifiers and regression", Int. Conf. Soft Computing, pp. 610--619 (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.
204. 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(theta|X). 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(theta|X) we assume the components t_i are indepenent and we get p(theta|x) = \pi t_i(theta) where t_i = p(theta|x_i). The strategy is to find a good approximation to each t_i and by that to find a global maximizer to p(theta|X). 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(theta|X). This method can be applied to arbitrary graphs assuming p(theta|X) 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(Theta|X) 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.
205. 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)(x-x0)^2 + O(x-x0)^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.
206. Laplace's Method - Mackey's book - chapter 27pdf
207. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods by Nello Cristianini and John Shawe-Taylor ISBN:0521780195 Cambridge University Press 2000 (190 pages)
     Summary: chapter 6 deals with SVMs.
208. WEKA software: html
209. Bruno A. Olshausen and David J. Field. Emergence of simple-cell 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
210. S. G. Mallat and Z. Zhang. Matching pursuits with time-frequency 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.
211. 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 >
212. "The Forgetron: A Kernel-Based Perceptron on a Fixed Budget" Ofer Dekel, Shai Shalev-Shwartz 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.
213. "A New Perspective on an Old Perceptron Algorithm" Shai Shalev-Shwartz 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

214. Nonparametric Belief Propagation for Self-Calibration 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 non-parametric 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 non-linear 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.
215. 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.
216. A Robust Architecture for Distributed Inference in Sensor Networks; Mark Paskin and Carlos Guestrin; In Intel Research Technical Report, IRB-TR-03-039, last updated April 2004. pdf
     Summary: extended technical report of the above paper.
217. 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.
218. Rui Castro, Mark Coates and Robert Nowak, "Likelihood Based Hierarchical Clustering", IEEE Transactions on Signal Processing, 52, no. 8, pp. 2308-2321, 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.
219. Mark Coates, Al Hero, Robert Nowak and Bin Yu, "Internet Tomography", in IEEE Signal Processing Magazine, May 2002 ps
220. M. Jain and C. Dovrolis, "End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput," ACM SIGCOMM, August 2002. ps
221. 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 max-product algorithm.
222. M. L. Littman, G. A. Keim and N. Shazeer. A probalistic approach to solving crosswords puzzles. Atificial Intelligence 134 (2002) 23-55.
     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.
223. V. padmanabhan, L. Qiu, and H. Wang. Server-based 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.
224. 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.
225. M. Alanyali, V. Saligrama, In-Network Decision Making via Local Message Passing, in Advances in Pervasive Computing and Networking, (Szymanski/Yener Editors) Kluwer 2004.
226. 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 non-symmtric 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.
227. 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 n-root 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.
228. 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.
229. 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 Sum-Product 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.
230. E.B. Ermis, V. Saligrama, Adaptive Satistical Sampling Methods for Decentralized Estimation and Detection of Localized Phenomena.
231. 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.
232. M. Bayati, D. Shah and M. Sharma, Maximum Weight Matching via Max-Product 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.
233. R. Schmidt and K. Aberer. Efficient Peer-to-Peer Belief Propagation. Fourteenth International Conference on Cooperative Information Systems (CoopIS), Montpellier, France, November 1-3, 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

234. A. Datta, S. Qouateroni and K. Aberer. Autonomous Gossiping: A Self-Organizing Epidemic Algorithm for Selective Information Dissemination in Wireless Mobile Ad-Hoc 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.
235. Y. Wu, P. A. Chou, and S.-Y. Kung, "Minimum-energy 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.
236. B. Xu, A. Ouksel, and O.Wolfson. Opportunistic resource exchange in inter-vehicle ad-hoc 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.
237. 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.
238. 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.
239. 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

240. 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 NP-complete 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 r-gathering problem to be a variant of the facility location problem where each facility should have at least r demand.
241. K. Munagala. Approximation Algorithms for Concave Cost Network Flow Problems. Ph. D. Dissertation. University of Stanford. May 2003.ps
242. A. Goel and D. Estrin. Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk. Preliminary version appeared in 14th ACM-SIAM 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.
243. M. Charikar and S. Guha. A constant-factor approximation algorithm for the k-median problem. In proc. 40th symposium on foundations of computer science, pp 378-388, 1999.
244. S. Guha, A. Meyerson and K. Mungala. Hieratchical placement and network design problems. In proc. 41st annyal symposium on foundations of computer science, 2000.
245. 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.
246. S. Khuller, B. Raghavachari and N. Young. Balancing minimum spanning and shortest path trees. Algorithmica 14(4):305-321, 1994.
247. P. Raghavan. Probablistic construction of deterministic algorithms: Approximating packing integer problems. Hournal of Comp. Sys. Sci. 37:130-43, 1988.
248. G. Robins and A. Zelikovsky, Improved Steiner Tree Approximation in Graphs, Proceedings of the 7th Annual ACM-SIAM 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 k-LCA. In a nutshell they construct a spanning tree, and in a loop find the k-restricted full componenet with max gain to loss ratio and attach it to the tree. The algorithm finishes when no such component is found.
249. R. Jothi, Approximation algorithm for single-sink edge instllation problems and other graph problems. Ph.D. Dissertation, the university of Texas at Dallas, 2004.
250. V. Arya, a. Meyerson and V. Pandit, Local Search Heuristics of k-median 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 3-approximation from the optimal solution.

     Gossip

251. 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.
252. 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.
253. H. Holbrook, S. Singhal, and D. Cheriton. Log-based receiver-reliable multicast for distributed interactive simulation. In SIGCOMM, 1995.
     Summary: Uses logger to provide storage and handle reliable transmission of missing messages.
254. 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.
255. A. M. Kermarrec, L. Massoulie and A. J. Ganesh. Probabilistic reliable dissemination in large-scale 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 GT-ITM topology to test in how many cases all nodes will get the gossiped message for fine tuning those parameters.
256. 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.
257. D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In Proc. of FOCS, 2003 (Push-Sum)
     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.
258. 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 Push-Sum algorithm to compute matrix eigenvalues using orthogonal iterations.
259. On Collaborative Content Distribution Using Multi-Message 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).
260. D. Most-Aoyama 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).
261. A. Montresor, M. Jelasity, and O. Babaoglu. Gossip-based Aggregation in Large Dynamic Networks. ACM Transactions on Computer Systems, vol. 23, no. 3, 219--252, August 2005.
     Summary: analyze the pairwise avergaing algorithm, which performs worser then the Push-Sum algorith.
262. Efficient Gossip-Based Aggregate Computation (with Supratim Deb, K.V.M. Naidu, Rajeev Rastogi and Anand Srinivasan). To appear in ACM SIGMOD-SIGACT-SIGART 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

263. 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 310--317, New York, November 5--10 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.
264. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. 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.
265. 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) co-citation (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 walk-sum 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.
266. Yehuda Koren, Stephen C. North, Chris Volinsky: Measuring and extracting proximity in networks. In KDD 2006. p. 245-255
     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.
267. Peer-to-Peer Rating by Danny Bickson, Dahlia Malkhi, Lidong Zhou. In the Seventh IEEE International Conference on P2P computing (2007).
268. Fast discovery of connection subgraphs by Christos Faloutsos, Kevin S Mccurley, Andrew Tomkins
269. A new status index derived from sociometric analysis Psychometrika, Vol. 18, No. 1. (27 March 1953), pp. 39-43. by Leo Katz
270. 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
271. Assortative mixing in networks (20 May 2002) by MEJ Newman
272. Centrality Measures Based on Current Flow STACS 2005 (2005), pp. 533-544. by Ulrik Brandes, Daniel Fleischer
273. Random Walks and Electric Networks by Peter G Doyle, Laurie J Snell
274. The structure and function of complex networks MEJ Newman
275. Mapping Small Worlds Peer-to-Peer Computing, 2007. P2P 2007. Seventh IEEE International Conference on (2007), pp. by Matteo Dell'amico 219-228.
276. Modeling relationships at multiple scales to improve accuracy of large recommender systems Robert Bell, Yehuda Koren, Chris Volinsky
277. Improved Circular Layouts Graph Drawing (2007), pp. 386-398. by Emden Gansner, Yehuda Koren

     T.B.D

278. Proc. 9th ACM-SIAM 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.
279. A. Langville and C. Meyer. Deeper inside pagerank. Internet Mathematics, 1(3):335--380, 2005.
     Summary: explain the pagerank algorithm.
280. K. Jain, M. Mahdian, and M. R. Salavatipour, "Packing Steiner Trees", Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 2003. ps
281. [26] M. Thimm, “On The Approximability Of The Steiner Tree Problem”, Mathematical Foundations of Computer Science 2001, Springer LNCS, 2001.
282. [28] G. Pandurangan, P. Raghavan and E. Upfal, “Building Low-diameter P2P Networks”, 42nd Annual Symposium on Foundations of Computer Science (FOCS01), pp. 492-499, 2001.
283. [30] E. Adar, B. Huberman, “Free Riding on Gnutella”, First Monday, Available at: http://www.firstmonday.dk/issues/issue5 10/adar/, 2000.
284. A. Ghodsi, L. O. Alima, S. Haridi, "Increasing Robustness and Minimizing Bandwidth Consumption in Strucured Peer-to-Peer Systems"
285. R. Koetter and M. Medard, "Beyond Routing: An Algebraic Approach to Network Coding", in Proc. of IEEE INFOCOM 2002.
286. 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).
287. 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
288. J. Byers, M. Luby, M. Mitzenmacher, "A Digital-Fountain Approach to Asynchronous Reliable Multicast," Journal on Selected Areas of Communication, Volume 20, Number 8, October 2002.
289. S. Banerjee, B. Bhattacharjee, and C. Kommareddy. Scalable application layer multicast. In ACM SIGCOMM 2002.
290. T. S. E. Ng and H. Zhang. Predicting internet network distance with coordinates-based approaches. In IEEE INFOCOM 2002.
291. R. Rejaie and A. Ortega. PALS: Peer-to-Peer Adaptive Layered Streaming. In NOSSDAV, 2003.
292. S. Saroiu, P. K. Gummadi, S. D. Gribble, “A Measurement Study of Peer-to-Peer File Sharing Systems”, Multimedia Computing and Networking 2002 (MMCN 2002).
293. J. Chu, K. Labonte, and B. Levine, “Availability and locality measurements of peer-topeer file systems”, ITCom: Scalability and Traffic Control in IP Networks, July 2002.
294. S. Sen and J. Wang, “Analyzing Peer-to-Peer Traffic Across Large Networks”, ACM/IEEE Transactions on Networking, Vol. 12, No. 2, April 2004, pp. 137–150.
295. C. Nieman, Digital Decoys”, IEEE Spectrum, May 2003, p. 27.
296. Y. Guo, K. Suh, J. Kurose, and D. Towsley, P2cast: peer-to-peer patching scheme for vod service," in Proceedings of the twelfth international conference on World Wide Web, 2003, pp. 301 - 309.
297. "A peer-to-peer on-demand streaming service and its performance evaluation," in Proceedings of 2003 IEEE International Conference on Multimedia & Expo, 2003.
298. M. Hefeeda, A. Habib, B. Botev, D. Xu, and D. B. Bhargava, Promise: Peer-to-peer media streaming using collectcast," Proc. of ACM Multimedia 2003, November 2003.
299. Gnustream: a p2p media streaming system proptoptype. Xuxian Jiang Yu Dong Dongyan Xu Bharat Bhargava. pdf
300. [9] S. M. Hedetniemi,T. Hedetniemi,an d A. L. Liestman. A Survey of Gossiping and Broadcasting in Communication Networks. NETWORKS,18, 1988.
301. [11] C. Huitema. The case for packet level FEC. In Proc. 5th International Workshop on Protocols for High Speed Networks, Oct. 1996.
302. [12] J. Leibeherr and M. Nahas. Application-layer Multicast with Delaunay Triangulations. In IEEE Globecom, Nov. 2001.
303. [13] B. Levine and J. Garcia-Luna-Aceves. A comparison of reliable multicast protocols. Multimedia Systems Journal,6( 5), Aug. 1998.
304. [14] B. Levine,D . Lavo,an d J. Garcia-Luna-Aceves. The case for concurrent reliable multicasting using shared ack trees. In Proc. ACM Multimedia, Nov. 1996.
305. [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.
306. [19] C. Papadopoulos,G. Parulkar, and G. Varghese. An error control scheme for large-scale multicast applications. In Proc. INFOCOM 1998.
307. 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.
308. X. Rex Xu, A. Myers,H . Zhang,an d R. Yavatkar. Resilient multicast support for continuous-media applications. In Proceedings of NOSSDAV 1997.
309. D. Rubenstein,S . Kasera, D. Towsley, and J. Kurose. Improving reliable multicast using active parity encoding services(APES). In Proc. INFOCOM 1999.
310. Z. Xiao and K. Birman. A randomized error recovery algorithm for reliable multicast. In Proc. INFOCOM 2001.
311. [27] B. Zhang,S . Jamin, and L. Zhang. Host multicast: A framework for delivering multicast to end users. In Proc. IEEE INFOCOM 2002.
312. Z. Wang and J. Crowcroft. Quality-of-Service Routing for Supporting Multimedia Applications. IEEE JSAC, 14(7):1288--1234, September 1996. pdf
313. D. Xu, M. Hefeeda, S. Hambrusch, and B. Bhargava. On Peer-to-Peer Media Streaming. Purdue Computer Science Technical Report, Apr. 2002. html
314. Schulzrinne, A., Casner, S., "RTP: A Transport Protocol for REAL--Time Applications ", Internet Engineering Task Force, Internet Draft, Oct. 20, 1993.(RTP) html
315. H. Schulzrinne, A. Rao, R. Lanphier, "Real Time Streaming Protocol(RTSP)," Internet RFC 2326, Apr. 1998.(RTSP) html
316. [CSW+2000] Freenet: A Distributed Anonymous Information Storage and Retrieval System, I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong, WDIAU 2000.
317. [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.
318. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek and Hari Balakrishnan, IEEE/ACM Transactions on Networking, Vol. 11, No. 1, pp. 17-32, February 2003.
319. [ZHS+2004] Tapestry: A Resilient Global-scale Overlay for Service Deployment, Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph, and John D. Kubiatowicz, IEEE JSAC 2004.
320. [DZD+2003] Towards a Common API for Structured P2P Overlays, Frank Dabek, Ben Zhao, Peter Druschel, John Kubiatowicz, and Ion Stoica, IPTPS 2003.
321. [CDG+2002] Secure Routing for Structured Peer-to-Peer Overlay Networks, Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron, and Dan S. Wallach, OSDI 2002.
322. [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
323. [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
324. [VYW+2002] Scalability and Accuracy in a Large-Scale Network Emulator, Amin Vahdat, Ken Yocum, Kevin Walsh, Priya Mahadevan, Dejan Kostic, Jeff Chase, and David Becker, OSDI 2002 pdf
325. [REG+2003] Pond: the OceanStore Prototype, Sean Rhea, Patrick Eaton, Dennis Geels, Hakim Weatherspoon, Ben Zhao, and John Kubiatowicz, FAST'03.
326. [RD2001] Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Antony Rowstron and Peter Druschel,SOSP 2001.
327. [MRG+2002] Ivy: A Read/Write Peer-to-peer File System, A. Muthitacharoen, R. Morris, T. Gil, and B. Chen, OSDI 2002.
328. [HHL+2003] Querying the Internet with PIER, Ryan Huebsch, Joseph M. Hellerstein, Nick Lanham, Boon Thau Loo, Scott Shenker, Ion Stoica, VLDB'03.
329. [ABKM2001] Resilient Overlay Networks, David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris,SOSP 2001.
330. [RS2002] The Design and Implementation of a Next Generation Name Service for the Internet, Venugopalan Ramasubramanian, Emin Gun Sirer, SIGCOMM 2004.
331. [NPB2004] A Routing Underlay for Overlay Networks, Akihiro Nakao, Larry Peterson, Andy Bavier, SIGCOMM 2004.
332. [Br2001] Lessons from Giant-Scale Services, Eric Brewer, IEEE Internet Computing 2001.
333. [FGC+1997] Scalable Network Services, Armando Fox, Steven D. Gribble, Yatin Chawathe, Eric A. Brewer, and Paul Gauthier,SOSP 1997.
334. [WDB2001] SEDA: An Architecture for Well-Conditioned, Scalable Internet Services, Matt Welsh, David Culler, and Eric Brewer,SOSP 2001.
335. [BCZ+2003] Capriccio: Scalable Threads for Internet Services, Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, Eric Brewer, SOSP 2003.
336. [GBHC2000] Scalable, Distributed Data Structures for Internet Service Construction, Steven D. Gribble, Eric A. Brewer, Joseph M. Hellerstein, and David Culler, OSDI 2000.
337. [SBL2000] Manageability, Availability, and Performance in Porcupine: A Highly Scalable, Cluster-Based Mail Service, Yasushi Saito, Brian N. Bershad, and Henry M. Levy, TOCS '00.
338. 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.
339. T. S. E. Ng and H. Zhang. Predicting internet network distance with coordinates-based approaches. In IEEE INFOCOM 2002, June 2002.(GNP) GNP software
     Summary: GNP (Global network positioning) relies on a small number (5-20) 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.
340. 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.
341. Y. Shavitt and T. Tankel. Big-bang simulation for embedding network distances in Euclidean space. In Proc. of IEEE INFOCOM 2003, April 2003. (BigBang)
     Summary: simulates a potential field.
342. 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.
343. 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.
344. M. Castro, M. Costra, and A. Rawstron, Performance and dependebability of structured peer-to-peer overlays. Technical report MSR-TR-2003-94, Microsoft Research, Dec. 2003. Pastry.ps">ps
345. J. Rosenberg, R. Mahy, C. Huitema. TURN: traversal using relay NAT. Internet draft, Internet Engineering Task Force, July 2004. Work in progress. pdf
346. 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.
347. A. El Gamal and T. M. Cover, “Achievable rates for multiple descriptions,” IEEE Trans. Inform. Theory, vol. IT–28, pp. 851–857, Nov. 1982.
348. D. Slepian and J. K. Wolf, “Noiseless coding of correlated information sources,” IEEE Trans. Inform. Theory, vol. IT-19, pp. 471–480, July 1973.
349. R.W. Yeung, “Multilevel diversity coding with distortion,” IEEE Trans. Inform. Theory, vol. 41, pp. 412–422, Mar. 1995.
350. 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.
351. I. Chawate, S. Rantasamy, L. Breslau, N. Lanham, S. Shenker, Making Gnutella like P2P systems scalable, In proc. of the ACM SIGCOMM 2003.
352. 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. 654-663, 1997.
353. "Pixie: A Jukebox Architecture to Support Efficient Peer Content Exchange", S. Rollins and K. Almeroth, ACM Multimedia 2002, Juan Les Pins, France, December, 2002.
354. SRM"> J. Gemmell, “E SRM – Erasure Correcting Scalable Reliable Multicast,” Microsoft Research Technical Report MS-TR-97-20, June 1997.
355. M. Luby, M. Mitzenmacher, and A. Shokrollahi, “Analysis of Random Processes via And-Or Tree Evaluation.” In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1998.
356. N. F. Maxemchuk, “Dispersity Routing.” In Proc. of the International Conference on Communications, pp. 41-10 – 41-13, 1975.
357. J. Nonnenmacher, E.W. Biersack, and D. Towsley, “Parity-Based Loss Recovery for Reliable Multicast Transmission.” In Proc. of ACM SIGCOMM ’97, 1997.
358. L. Rizzo, “Effective Erasure Codes for Reliable Computer Communication Protocols.” In Computer Communication Review, April 1997.
359. E. Schooler and J. Gemmell, “Using multicast FEC to solve the midnight madness problem,” Microsoft Research Technical Report MS-TR-97-25, September 1997.
360. A. T.-S. Ip, J. Liu, and J. C.-S. Lui, COPACC: A Cooperative Proxy-Client Caching System for On-Demand Media Streaming, Technical Report, July 2004. pdf
361. J. Liu, B. Li, and Y.-Q. Zhang, Optimal Stream Replication for Video Simulcasting, to appear in IEEE Transactions on Multimedia, 2005.
362. "Scalability in Adaptive Multi-Metric Overlays," Adolfo Rodriguez, Dejan Kostic, and Amin Vahdat, Proceedings of the International Conference on Distributed Computing Systems, March 2004. pdf
363. LoDN: Logistical Distribution Network Micah Beck, Jean-Patrick Gelas, Dustin Parr, James S. Plank, Stephen Soltesz Workshop on Advanced Collaborative Environments, Nice, France, September, 2004 pdf
364. G. Kortuem, J. Schneider, D. Preuitt, T. G. C. Thompson, S. Fickas, Z. Segall. When Peer to- Peer comes Face-to-Face: Collaborative Peer-to-Peer Computing in Mobile Ad hoc Networks. In Proc. 1st International Conference on Peer-to-Peer Computing (P2P 2001), Linkoping, Sweden, August 2001.
365. D. S. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins, Z. Xu. Peer-to-Peer Computing. Technical Report HPL-2002-57, HP Labs.
366. L. Yan and K. Sere. Stepwise Development of Peer-to-Peer Systems. In Proc. 6th International Workshop in Formal Methods (IWFM'03). Dublin, Ireland, July 2003.
367. Z. Ge, D. Figueiredo, S. Jaiswal, J. F. Kurose, D. Towsley. Modeling peer-to-peer file sharing systems. In Proc. IEEE Infocom, 2003.
368. F. L. Piccolo, G. Neglia. The Effect of Heterogeneous Link Capacities in BitTorrent-Like File Sharing Systems. In Proc. Intl. Workshop on Hot Topics in Peer-to-Peer Systems (HOT-P2P'04), Oct, 2004.
369. M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, \Errorcient erasure correcting codes," IEEE Trans. Inform. Theory, vol. 47, pp. 569{584, 2001.
370. R. G. Gallager, Low Density Parity-Check Codes, MIT Press, Cambridge, MA, 1963.
371. P. Maymounkov, \Online codes," Preprint, 2002.
372. H. Jin, A. Khandekar, and R. McEliece, \Irregular repeat-accumulate codes," in Proc. 2nd International Symposium on Turbo Codes, 2000, pp. 1{8.
373. C. Di, D. Proietti, E. Telatar, T. Richardson, and R. Urbanke, \Finite-length analysis of lowdensity parity-check codes on the binary erasure channel," IEEE Trans. Inform. Theory, vol. 48, pp. 1570{1579, 2002.
374. Francesca Lo Piccolo, Giovanni Neglia, The Effect of Heterogeneous Link Capacities in BitTorrent-Like File Sharing Systems 2004 International Workshop on Hot Topics in Peer-to-Peer Systems (HOT-P2P'04) October 08 - 08, 2004, Volendam, The Netherlands html
375. S. Banerjee, C. Kommareddy, K. Kar, S. Bhattacharjee, and S. Khuller. Construction of an efficient overlay multicast infrastructure for real-time applications. In INFOCOM, 2003.
376. C. Borcea, C. Intanagonwiwat, A. Saxena, and L. Iftode. Self-routing 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.
377. 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, Jan-Feb 2003.
378. O. Dousse, P. Thiran, and M. Hasler. Connectivity in ad-hoc and hybrid networks. In Proc. IEEE Infocom, June 2002.
379. 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.
380. 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.
381. 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.
382. 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.
383. L. Ji and M. S. Corson. Differential destination multicast - a manet multicast routing protocol for small groups. In Proceedings of Infocom, 2001.
384. Y. B. Ko and N. H. Vaidya. Flooding-based geocasting protocols for mobile ad hoc networks. Mobile Networks and Applications, 7(6):471–480, 2002.
385. M. Papadopouli and H. Schulzrinne. A Performance Analysis of 7DS, A Peer-to- Peer Data Dissemination and Prefetching Tool for Mobile Users. In Advances in wired and wireless communications, IEEE Sarnoff Symposium Digest, March 2001.
386. S. Ratnasamy, B. Karp, Y. Li, F. Yu, R. Govindan, S. Shenker, and D. Estrin. GHT: A Geographic Hash Table for Data-Centric 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.
387. 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.
388. J.E. Wieselthier, G.D. Nguyen, and A. Ephremides. On the construction of energyefficient broadcast and multicast trees in wireless networks. In Infocom, 2000.
389. N. Sprintg, R. Mahajan and D. Wterall. Measuring ISP topologies with Rocketfuel. In proc. SIGCOMM 2002, Pittsburg, PA, Aug. 20002.
390. J. S. Plank, S. Atchley, Y. Ding, and M. Beck. Algorithms for high performance, wide-area distributed file downloads. Parallel Processing Letters, 13(2):207-224, June 2003. 15(5):757-768, October 1999. pdf
391. J. Li, "Embedded audio coding with implicit psychoacoustic masking", ACM Multimedia 2002, Nice, France, Dec.1-6, 2001.
392. D. Eager, M. Vernon, and J. Zahorjan, “Minimizing bandwidth requirements for on-demand data delivery,” IEEE Trans. Knowl. Data Eng., vol. 13, pp. 742–757, Sept.–Oct. 2001.
393. S. Jin and A. Bestavros, “Scalability of multicast delivery for nonsequential streaming access,” presented at the ACM SIGMETRICS, Marina Del Rey, CA, 2002.
394. S. Sheu, K. Hua, and W. Tavanapong, “Chaining: A Generalized batching technique for video-on-demand systems,” in Proc. IEEE ICMCS, June 1997, pp. 110–117.
395. 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.
396. M.-J. Lin, K. Marzullo, and S. Masini. Gossip versus deterministic flooding: Low message overhead and high-reliability for broadcasting on small networks. In 14th International Symposium on Distributed Computing, pages 253–267, 2000.
397. 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.
398. 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.
399. 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. User-optimal 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.
400. L. Qiu, Y. R. Zhang and S. Shenker, On selfish routing in Internet-like envorinments, In proc. of ACM SIGCOMM 2003, Germany, Aug. 2003.
401. D. Kempe, A. Dobra and J. Gehrke. Gossip based computation of a ggregate information. In Proc. Conference on Foundations of Computer Science, IEEE 2003.
402. W. Wei, and A. Zakhor, “Multipath unicast and multicast video communication over wireless ad hoc networks,” Proc. Int. Conf. Broadband Networks, Broadnets, pp. 496-505, 2002.
403. E. Setton, T. Yoo, X. Zhu, A. Goldsmith, and B. Girod, “Cross-layer design of ad hoc networks for real-time video streaming,” IEEE Wireless Communications Mag., vol. 12, no. 4, pp. 59-65, Aug. 2005.
404. 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.
405. S. Shenker, “Efficient network allocations with selfish users,” in Proc. Perform. ’90. Edinburgh, Scotland, pp. 279–285, September 1990.
406. J. MacKie-Mason and H. Varian, “Pricing Congestable Network Resources,” IEEE J. on Select. Areas in Commun., vol. 13, no.7, pp. 1141-1149, September 1995.
407. R. La and V. Anantharam, “Optimal Routing Control: Repeated Game Approach,” IEEE Trans. Automatic Control, Vol. 47, No. 3, pp. 437 -450, March 2002.
408. Y. Guo, K. Suh, J. Kurose, and D. Towsley, “A Peer-to-Peer On-Demand Streaming Service and Its Performance Evaluation,” Proc. International Conference on Multimedia and Expo (ICME '03), 6-9 July 2003, vol.2, pp.649-52.
409. S. Annapureddy, M. J. Freedman and D. Mazieres. Shark: Scaling file servers via cooperative caching. In NSDI 2005.
410. K. Park and V. S. Pai. Deploying large file transfer on an HTTP conetent distribution network. In WORLDS 04'. (CoBlitz)
411. 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)
412. S. Iyer, A. Rowstron, and P. Druschel. Squirrel: A decentralized peer-to-peer web cache. In Proc. 21st ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2002.",
413. 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 Peer-to-Peer Systems, Berkeley, California, June 2003.
414. 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,
415. KARMA: A secure economic framework for P2P resource sharing,” in Workshop on Economics of Peer-to-Peer Systems, Berkeley, California, June 2003.
416. 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.
417. J. Kangasharju, “Internet content distribution,” Ph.D. dissertation, Dept. Comput. Sci., Univ. Nice, Nice, France, Apr. 2002.
418. 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.
419. E. Cohen and S. Shenker, “Replication strategies in unstructured peer-topeer networks,” in Proc. ACM SIGCOMM, Pittsburgh, PA, Aug. 2002, pp. 177–190.
420. Gerard Salton and Chris Buckley. Term weighting approaches in automatic text retrieval. Technical report, Ithaca, NY, USA, 1987.
421. 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.
422. 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
423. Dina Katabi, Mark Handley, and Charles Rohrs, "Internet Congestion Control for Future High Bandwidth-Delay Product Environments." ACM Sigcomm 2002, August 2002.
424. 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).
425. 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 multi-level peer index. Instead of routing to a fixed geographical location, the routing is done to a spatial erea.
426. 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.
427. 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

428. Analysis of BitTorrent and its use for the Design of a P2P based streaming Protocol for a Hybrid CDN - Skevik, Goebel, Plgemann
429. 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.
430. Speedup of Data Access using Error Correcting code in P2P Networks
431. 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.
432. 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.
433. Optimal Unconditional Information Diffusion - Malkhi, Pavlov, Sella
434. Circus: Oppotunistic Block Reordering for Scalable Content Servers - Anastasiadis, Wickremesignhe, Chase
435. B. J. Frey, H. A. Loeliger, F. R. Kschichang, N. Wiberg. Factor graphs and algorithms.
436. P. Oude and B. Ottens and G. Pavlin. Information Fusion with Distributed Probabalistic Networks.
     
437. C. Borcea, C. Intanagonwiat, A. Saxena and L. Iftode, Self-routing in pervasive computing environment using smart messages.
438. 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.
439. J. Li. The efficient implementation of high rate Reed-Solomon erasure resilient code. In ICASSP 2005.
     Summary: good overview of RS codes. Proposes two optimization for speeding up the coding implementation.
440. H. Ma, K. G. Shin and W. Wu. Best-Effort 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 Best-Effot 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.
441. George Pallis, Athena Vakali. Insight and perspectives for content delivery networks. Commun. ACM 49 (1): 101-106 (2006)
442. Athena Vakali George Pallis: Content Delivery Networks: Status and Trends. IEEE Internet Computing 7 (6): 68-74 (2003)
443. Konstantinos Stamos George Pallis, Athena Vakali: Integrating Caching Techniques on a Content Distribution Network. ADBIS 2006 : 200-215
444. George Pallis, Konsta$ntinos Stamos. Replication Based on Objects Load under a Content Distribution Network. ICDE Workshops 2006: 53

Original site design by Pegasus Web Design Resources, modified by David Rabinowitz