From victoria@cs.hmc.edu Wed Mar 29 21:54:47 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from turing.cs.hmc.edu (turing.cs.hmc.edu [134.173.42.99]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2U2slY27690 for ; Wed, 29 Mar 2006 21:54:47 -0500 (EST) Received: by turing.cs.hmc.edu (Postfix, from userid 34382) id D01C65325F; Wed, 29 Mar 2006 18:54:40 -0800 (PST) Date: Wed, 29 Mar 2006 18:54:40 -0800 From: Victoria Krafft To: egs+summary@cs.cornell.edu Subject: PAPER 17 Message-ID: <20060330025440.GA28672@cs.hmc.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.2.1i These three papers all examine the problem of distributing data from one node to many nodes, while trying to maximize the speed that data is distributed at. The naive solution to this is simply to have the source send the data to each receiver, but this is horribly inefficient. Many packets containing the exact same data will travel over the same links. For some time, there have been proposals to set up IP multicasting, where this functionality - sending from one node to many nodes - would be built into the Internet. However, this approach has several problems, and is unlikely that IP multicast will be running on the entire Internet in the near future. As a result, a variety of systems for creating overlay networks have been developed. The basic forms for these are distribution trees, where the nodes assemble in a tree with the data source at the root, and distribution meshes, where nodes assemble into a mesh, and then create a tree on top of that. Bullet is a system which extends the concept of a distribution tree, creating a distribution mesh. It starts off with a tree architecture, but extends this by having nodes obtain some of their data from points in the tree other than their immediate parent, depending on available bandwidth. To accomplish this, the data to be broadcast is broken up into disjoint sets. The root node sends some of these sets to each of its children, and they do the same for their children. A node then obtains the missing sets from other points in the tree. To find locations which have those missing sets, Bullet uses RanSub, a scalable scheme which provides nodes in a tree with information about random subsets of participating nodes. Experimental data shows that Bullet performs at least as well as the optimal tree distribution system, and may achieve up to a 100% performance increase on highly constrained networks. Because a node obtains data from multiple peers as well as its direct parent, the failure of a single node does not cause a temporary outage for all of its children. SplitStream tries to distribute the workload among all nodes in the network evenly, unlike tree-based multicast protocols. SplitStream does this by splitting the data stream up into k stripes, similar to the disjoint sets in Bullet, although the stripes can overlap to allow for error correction, or the loss of a single stripe. Each of these stripes is multicast to all the nodes in the network, using a normal tree-based multicast structure. Each node in the network will be an interior node in one of these trees, and a leaf node in all the others. This approach splits the load for ingoing and outgoing bandwidth evenly among all the nodes in the network. However, it requires the construction of several multicast trees, which SplitStream accomplishes using Scribe. All the nodes share the underlying Pastry network, and a separate Scribe tree is constructed for each of the k stripes. Setting k=2^b, and using some other features of Scribe and Pastry, allows for efficient construction of multiple trees. Because it places an even load on each node in the network, performance in SplitStream may suffer if a reasonable portion of the network has a slow network connection. The Pastry network underneath Scribe may also slow SplitStream down, since it does not minimize link latency, or maximize link bandwidth. BitTorrent focuses exclusively on file downloads, while Bullet and SplitStream provided a more general multicast framework. Each file distributed through BitTorrent is broken up into fixed-size chunks, and requires a tracker. That tracker keeps a list of which BitTorrent clients have downloaded some or all of the file, and which pieces they have. Clients who wish to obtain the file download all the chunks they don't have from anyone who already has them. In order to prevent this from overloading the network, and in an attempt to avoid the free rider problem, BitTorrent clients which are still in the process of downloading a file only upload to a couple of their peers; those peers which are providing the best current download rates are preferred. All three of these networks improve their performance by splitting the data to be transmitted into multiple fragments. By offloading a relatively small portion of the work to a central tracker, BitTorrent does not need to create an overlay network, which will eliminate some overhead. However, attempts to use BitTorrent for real-time streaming applications, such as TV broadcasts or conferencing, would have some problems. BitTorrent assumes that the data to be passed around is stored on the computer, and can be re-uploaded at any point in time. In addition, the lack of a well-defined overlay networks makes it difficult broadcast data to everyone who wishes to have it in a timely fashion, since nodes are constantly choking each other off, and switching the source of their data. -- Victoria Krafft From lackhand@gmail.com Thu Mar 30 01:05:25 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-0.4 required=5.0 tests=AWL,BAYES_00,HTML_00_10, HTML_MESSAGE,RCVD_IN_BL_SPAMCOP_NET autolearn=no version=3.1.0 X-Spam-Level: Received: from pproxy.gmail.com (pproxy.gmail.com [64.233.166.176]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2U65OY07561 for ; Thu, 30 Mar 2006 01:05:25 -0500 (EST) Received: by pproxy.gmail.com with SMTP id i75so389865pye for ; Wed, 29 Mar 2006 22:05:24 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type; b=esfLewLjjYWXtSgj8gLISnb5rxmgWWl1JfuLQsx6e02+u8lOvk54m2dSRHp8Oc5rGawTV4+F7pSzHxWqyYBC+cfNWhVORLllXPK6kV0/Jr2hRmwmQbrY1DgilCMieZDF7avxQq9qQw1+4m/83Z7DYU0lj11u//70EuHZaZpL6no= Received: by 10.35.49.4 with SMTP id b4mr412016pyk; Wed, 29 Mar 2006 22:05:24 -0800 (PST) Received: by 10.35.125.16 with HTTP; Wed, 29 Mar 2006 22:05:24 -0800 (PST) Message-ID: <9aa7a97d0603292205o579e8647we6e147d9e03c767d@mail.gmail.com> Date: Thu, 30 Mar 2006 01:05:24 -0500 From: "Andrew Cunningham" To: egs+summary@cs.cornell.edu Subject: PAPER 17 MIME-Version: 1.0 X-Security: message sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.148 $Date: 2004-12-19 11:59:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_Part_121_24846656.1143698724329" ------=_Part_121_24846656.1143698724329 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable I think I may have screwed up in sending my last few papers! Sorry! Would you like them to be resent? Or something? (I believe I got the paper #s wrong) Andrew Cunningham arc39 Incentives Build Robustness in BitTorrent Bram Cohen In classical peer-to-peer fashion, BitTorrent takes the classical client-server model and subverts it. What is more obvious in this domain than most is how shady the legality can become; by making certain services available only via bit-torrent, a provider may essentially dodge out on their entire upload bill, causing ISPs to essentially foot the bill for their content distribution. Thus, BitTorrent introduces stronger quality of service guarantees and much better qualities for introducing new content, and permits economic measurement of client behavior in order to discover freeloaders. It does this by slicing each object to be transfered into blocks of bits and then carefully downloading them "optimally" from all those offering them, while simultaneously advertising, and offering, the block-just-downloaded. It is a deployed technology. What BitTorrent does not do is ensure good behavior after a file has been downloaded. A file must be seeded to be shared on this system, and after downloaded a peer should remain online and offering it, in order to help with the cost of upload. However, there is no incentive to do this, because this will create congestion on a peer's network to no personal benefit; a useful expansion might be to measure the performance of BitTorrent peers over time, and integrate the shorter term, per-object rules, to a peer whenever they're encountered. Also, it is something of a hybrid scheme (due to its real world deployment), and thus not purely peer-to-peer. This is relevant to the performance of BitTorrent in that it creates a single point of failure; while it is no longer necessary for the object to remain hosted by its author, it becomes necessary for the author to maintain the tracker; the cost is significantly lower but there exists a clear link between tracker and responsibility (legal, mostly!) of objects. SplitStream: High Bandwidth Multicast in Cooperative Environments Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, Animesh Nandi, Antony Rowstron, Atul Singh Solving a slightly different problem, SplitStream attempts to maximize not personal download while minimizing some central server's upload amounts= , but instead to maximize multicast throughput while minimizing reliance on fallible broadcast trees and attempting to enforce fairness. However, it uses a similar concept, splitting each object into stripes and to multicast each stripe along a separate broadcast tree whose interior points are disjoint with each other tree. The topology information is maintained by means of a Pastry ring, with groups treated much as objects around the ring= ; membership broadcast trees can then be cheaply and easily built by routing = a response to the unit on the ring corresponding to the arbitrary point chose= n to represent a group. Splitstream's algorithm is quite elegant, though requiring an amount of organizational overhead proportional to the size of the message being sent, in that it is related directly to the number of stripes being sent concurrently. This is not a problem, as it is done through pastry, which otherwise requires little overhead, but represents something of a stumbling block for other-than-longstanding connections, because since this setup and teardown work must be done per stripe to be sent, the model cannot easily b= e adapted (as BitTorrent) to include one-time downloads, but is instead bette= r suited for streaming video and so forth. Bullet: High Bandwidth Data Dissemination Using an Overlay Mesh Dejan Kostic, Adolfo Rodriguez, Jeannie Albrecht, and Amin Vahdat Similar in some ways to Bittorrent's model, Bullet uses a broadcast tre= e to seed data into the network and then lateral links to ensure good coverag= e of all portions of a given file. The important operation here is to locate = a peer with slices of content we do not posess; the RanSub algorithm attempts to do this via collect and distribute messages over a tree in an epoch based, cyclical system. Each node thus receives a parent stream of data fro= m the broadcast tree, and some lateral perpendicular streams of data from other peers. The improvements of this paper are an improvement over strict broadcast trees, and thus SplitStream in fact answers many of the flaws in this paper= ; the most obvious of which is that it is somewhat unstructured, and thus suffers from higher coordination requirements; the problem of locating peer= s in possesion of new data is essentially one of serving all the nodes 'in th= e correct order' in this model, since it is intended for arbitrary broadcast, and so scales very well, but also must manage throughput more efficiently than strict trees. The unstructured nature hinders in this goal. ------=_Part_121_24846656.1143698724329 Content-Type: text/html; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable I think I may have screwed up in sending my last few papers! Sorry! Would you like them to be resent? Or something? (I believe I got the paper #s wrong)

Andrew Cunningham
arc39

    Incentives Build Robustness in BitTorrent
    Bram Cohen
   
    In classical peer-to-peer fashion, BitTorrent takes the classical client-server model and subverts it. What is more obvious in this domain than most is how shady the legality can become; by making certain services available only via bit-torrent, a provider may essentially dodge out on their entire upload bill, causing ISPs to essentially foot the bill for their content distribution. Thus, BitTorrent introduces stronger quality of service guarantees and much better qualities for introducing new content, and permits economic measurement of client behavior in order to discover freeloaders. It does this by slicing each object to be transfered into blocks of bits and then carefully downloading them "optimally" from all those of= fering them, while simultaneously advertising, and offering, the block-just-downloaded. It is a deployed technology.
    What BitTorrent does not do is ensure good behavior after a file has been downloaded. A file must be seeded to be shared on this system, and after downloaded a peer should remain online and offering it, in order to help with the cost of upload. However, there is no incentive to do this, because this will create congestion on a peer's network to no personal benefit; a useful expansion might be to measure the performance of BitTorrent peers over time, and integrate the shorter term, per-object rules, to a peer whenever they're encountered. Also, it is something of a hybrid scheme (due to its real world deployment), and thus not purely peer-to-peer. This is relevant to the performance of BitTorrent in that it creates a single point of failure; while it is no longer necessary for the object to remain hosted by its author, it becomes necessary for the author to maintain the tracker; the cost is significantly lower but there exists a clear link between tracker and responsibility (legal, mostly!) of objects.
   
    SplitStream: High Bandwidth Multicast in Cooperative Env= ironments
    Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, Ani= mesh Nandi, Antony Rowstron, Atul Singh
   
    Solving a slightly different problem, SplitStream attempts to maximize not personal download while minimizing some central server's upload amounts, but instead to maximize multicast throughput while minimizing reliance on fallible broadcast trees and attempting to enforce fairness. However, it uses a similar concept, splitting each object into stripes and to multicast each stripe along a separate broadcast tree whose interior points are disjoint with each other tree. The topology information is maintained by means of a Pastry ring, with groups treated much as objects around the ring; membership broadcast trees can then be cheaply and easily built by routing a response to the unit on the ring corresponding to the arbitrary point chosen to represent a group.
    Splitstream's algorithm is quite elegant, though requiring an amount of organizational overhead proportional to the size of the message being sent, in that it is related directly to the number of stripes being sent concurrently. This is not a problem, as it is done through pastry, which otherwise requires little overhead, but represents something of a stumbling block for other-than-longstanding connections, because since this setup and teardown work must be done per stripe to be sent, the model cannot easily be adapted (as BitTorrent) to include one-time downloads, but is instead better suited for streaming video and so forth.
   
    Bullet: High Bandwidth Data Dissemination Using an Overl= ay Mesh
    Dejan Kostic, Adolfo Rodriguez, Jeannie Albrecht, and Am= in Vahdat
   
    Similar in some ways to Bittorrent's model, Bullet uses a broadcast tree to seed data into the network and then lateral links to ensure good coverage of all portions of a given file. The important operation here is to locate a peer with slices of content we do not posess; the RanSub algorithm attempts to do this via collect and distribute messages over a tree in an epoch based, cyclical system. Each node thus receives a parent stream of data from the broadcast tree, and some lateral perpendicular streams of data from other peers.
    The improvements of this paper are an improvement over strict broadcast trees, and thus SplitStream in fact answers many of the flaws in this paper; the most obvious of which is that it is somewhat unstructured, and thus suffers from higher coordination requirements; the problem of locating peers in possesion of new data is essentially one of serving all the nodes 'in the correct order' in this model, since it is intended for arbitrary broadcast, and so scales very well, but also must manage throughput more efficiently than strict trees. The unstructured nature hinders in this goal.
------=_Part_121_24846656.1143698724329-- From ns253@cornell.edu Thu Mar 30 01:13:30 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2U6DUY09300 for ; Thu, 30 Mar 2006 01:13:30 -0500 (EST) Received: from localhost (cpe-69-207-49-126.twcny.res.rr.com [69.207.49.126]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2U6DRm4026348 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Thu, 30 Mar 2006 01:13:29 -0500 (EST) Date: Thu, 30 Mar 2006 01:13:27 -0500 From: Niranjan Sivakumar To: egs+summary@cs.cornell.edu Subject: PAPER 17 Message-Id: <20060330011327.8ae92581.ns253@cornell.edu> Organization: Cornell Law School X-Mailer: Sylpheed version 2.2.3 (GTK+ 2.8.13; i686-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Niranjan Sivakumar Incentives Build Robustness in BitTorrent Bullet: High Bandwidth Data Dissemination Using an Overlay Mesh SplitStream: High-Bandwidth Multicast in Cooperative Environments BitTorrent presents a system where files are split into pieces and sent to a number of downloaders such that they can share the pieces that they have, and eventually the entire file, with other nodes in the system to relieve stress on the origin of the file. A central system, called a tracker, is used to coordinate and maintain information about nodes that are connected to the system and the pieces that they maintain. Hashes of pieces are maintained to allow for verification as the download progresses. Peers try to match up such that they have disjoint sets of pieces such that they can provide maximum benefit to each other. Furthermore, some incentives are built into the system by having nodes prefer to upload to nodes that provide good speed in return. Pieces of files are distributed randomly at first, and then rarest first once peers are established in order to reduce the risk of a file becoming unavailable due to a small number of missing pieces. BitTorrent provides! an optional choking mechanism to improve overall performance. Bullet, much like BitTorrent, also breaks files into pieces and tries to match peers with disjoint sets of pieces to help each other finish downloads. Bullet is based on a tree structure for the underlying network, but augments this by allowing for cross-links that ultimately form a mesh that is based on a tree. This mesh allows for parallel perpendicular downloads that increase resilience against failure. Bullet employs a technique called RanSub to coordinate information about nodes within the system. Rounds in RanSub are known as epochs and alternate between collection and distribution. Participants in the system collect data about a random set of descendants and send it up the tree. This is followed by the distribution phase, where the collected data is used to distribute uniformly random sets of nodes down the tree. A TCP friendly rate control scheme is employed to avoid congestion. SplitStream also attempts to leverage tree based structure and dividing data that is being transmitted over the network. SplitStream divides data into stripes and sets up a tree for each stripe. By having a number of trees, the inherent load imbalance of each tree is distributed to even out the aggregate load. SplitStream requires that the tree-based multicast is provided externally. The example provided is to rely on Scribe, and in turn Pastry, to provide this functionality. The most prominent issue with BitTorrent is the reliance on a centralized tracker system. Although the tracker provides for a performance increase, it makes the system somewhat fragile. Bullet and SplitStream do not have a centralized weakpoint. However, although both Bullet and SplitStream seem to be more versatile than BitTorrent in terms of the content that they can be used to deliver, each node in their system is required to shoulder some of the burden that would otherwise be centralized. SplitStream and Bullet also do not seem to have the same incentives, or a matching system, like in BitTorrent perhaps allowing freeloaders or misbehaving nodes to take advantage of them. From asr32@cornell.edu Thu Mar 30 02:06:25 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2U76PY23300 for ; Thu, 30 Mar 2006 02:06:25 -0500 (EST) Received: from dreadnought.cornell.edu (r253240123.resnet.cornell.edu [128.253.240.123]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2U76OE3028977 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Thu, 30 Mar 2006 02:06:25 -0500 (EST) Message-Id: <6.2.1.2.2.20060328204555.03192e18@postoffice8.mail.cornell.edu> X-Mailer: QUALCOMM Windows Eudora Version 6.2.1.2 Date: Thu, 30 Mar 2006 02:07:12 -0500 To: egs+summary@cs.cornell.edu From: Ari Rabkin Subject: PAPER 17 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed BitTorrent: Bittorrent is a system for efficient file download. The key motivations were to produce a system that worked efficiently in the presence of churn, and that forced nodes to contribute resources, to upload. BitTorrent relies on peers that want a file each swapping chunks; if a peer does not upload, it will be choked. In this way, the system enforces fairness; further, since chunks of the file are grabbed from many different peers, the system is robust against failures, slow peers, and even against peers whose connection speed changes in mid-download. The BitTorrent design is fairly ad-hoc, without any correctness proofs. The system tries to enforce fairness with respect to downloads of a single file, and does not allow exchanges across different files. The system relies on a centralized tracker, and on a single altruistic "seed" for a given file. Since nodes primarily download from other downloaders, the system may fail to acquire a file even if (complete) copies of it are held by nodes connected to the system. SplitStream: In a tree-based multicast, there are typically many more "leaves" receiving the multicast than there are interior nodes sending traffic; as a result, the interior nodes are heavily laden. This is awkward in a peer-to-peer system where nodes are neither able nor willing to bear disproportionate burden. SplitStream attempts to solve the problem by having many trees in parallel, with files striped between them. Nodes hopefully will be "leaves" in most of the trees, and interior nodes in a few. SplitStream builds its trees on top of some existing multicast system, such as Scribe/Pastry. A group of nodes with spare capacity is maintained, and is key for adding flexibility to the tree. SplitStream relies on the locality and efficiency properties of the underlying Pastry system in order to build the tree efficiently; in contexts where Pastry performs poorly, SplitStream would be expected to as well. SplitStream tries to make each node act as both an interior and leaf node; this is a poor choice when there are clients with very small bandwidth resources. Bullet: Bullet has the same central insight as BitTorrent and SplitStream: that multicast performance can be improved by having nodes trying to receive a broadcast share data amongst themselves instead of just downloading from the source. Bullet takes an existing multicast tree, and turns it into a mesh, using a number of specialized tricks: custom protocols are proposed for picking random subsets of nodes, for quickly comparing content, and for reliably and efficiently streaming data in a TCP-friendly way. Bullet relies on a number of highly tuned protocols, and it's not clear how weIt's not clear how well Bullet would work in a highly heterogenous network, where some nodes have very little upstream bandwidth. Also, it seems like Bullet is ignoring non-local information about the topology of the broadcast mesh that ought to be useful. Ari Rabkin asr32@cornell.edu Risley Hall 454 3-2842 The resources of civilization are not yet exhausted. --William Gladstone From sh366@cornell.edu Thu Mar 30 02:29:22 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2U7TMY28252 for ; Thu, 30 Mar 2006 02:29:22 -0500 (EST) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2U7TLd2019702 for ; Thu, 30 Mar 2006 02:29:21 -0500 (EST) Message-ID: <795335277.1143703759874.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Thu, 30 Mar 2006 02:29:20 -0500 (EST) From: Huang Shiang-Jia To: egs+summary@cs.cornell.edu Subject: PAPER 17 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: uPortal WEB email client 3.0 Today's three papers present efficient data distribution schemes in peer-to-peer / overlay network systems with the concerns of load balance, fault tolerance and bandwidth utilization. The trackers in BitTorrent, which direct peers to find each other, act as single points of failure and carry load in proportion to the number of peers in the system. * BitTorrent distributes the cost of upload to downloaders. It does so by dividing files into pieces; when multiple people are downloading a file, they upload the pieces of that file to each other. * Trackers play an important role in BitTorrent. They track which peers have what data and gather statistics to help downloaders find and connect to each other. * The principle of piece selections for file download in BitTorrent is: (a) When the download just starts, users get a complete piece as quickly as possible. (b) Once a sub-piece is requested, the remaining sub-pieces of that piece are requested before other pieces. (c) The fewest pieces available are requested before popular ones. (This is called rarest first in the paper.) * SplitStream solves two problems of traditional tree-based multicast systems: (a) Interior node carry the loads to forward data while no forwarding is required by leaf nodes. It's unfair. (b) Peers who act as interior nodes may be unable to handle high-bandwidth applications due to network capacity limitations. * To solve the first problem, SplitStream works by splitting the stream into multiple stripes which uses separate multicast trees (a forest) to distribute each stripe to the peers. The goal is to ensure that vast majority of peers are interior nodes in only one tree and are leaf nodes in all other trees. * To solve the second problem, peers in SplitStream choose to join a subset of the stripes to control their inbound bandwidths. On the other hand, they opt to limit the number of children nodes they adopt to control their outbound bandwidths. Therefore the split stream system accommodates peers with different bandwidths. * Bullet constructs an overlay mesh over the distribution tree. It aims to make data items available uniformly across the system. * The basic idea of Bullet is: as a parent, each participant transmits disjoint sets of its data to its children; as children, they receive objects from their parents but are responsible for locating peers that hold missing objects. * Bullet and SplitStream can be complementary to each other. Bullet may run on each of the stripes in SplitStream to maximize the bandwidth delivered to each node along each stripe. From nsg7@cornell.edu Thu Mar 30 11:43:05 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2UGh4Y15040 for ; Thu, 30 Mar 2006 11:43:05 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2UGh3H1014314 for ; Thu, 30 Mar 2006 11:43:03 -0500 (EST) Received: from 132.236.227.119 by webmail.cornell.edu with HTTP; Thu, 30 Mar 2006 11:43:04 -0500 (EST) Message-ID: <1788.132.236.227.119.1143736984.squirrel@webmail.cornell.edu> Date: Thu, 30 Mar 2006 11:43:04 -0500 (EST) Subject: PAPER 17 From: "Nicholas S Gerner" To: egs+summary@cs.cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal BitTorrent is a distributed file distribution protocol where downloaders of files ("leechers") also upload parts of the file to other peers as the file is retrieved. A torrent is described in a (small) .torrent file which enumerates "peices" of the file (the file being broken into fixed sized chunks and each piece identifying a chunk) along with a hash of the piece, "sub-pieces" of each piece and a "tracker" which coordinates the specific torrent. In addition an initial "seeder" node must have all the pieces described in the .torrent file and must be known to the tracker. As new peers participate in the torrent they identify themselves to the tracker and select peers from which to download pieces and sub-pieces. Once a whole piece is downloaded and verified (via its hash) the leecher must notify the tracker which can publish the peer as a potential site from which to download the piece. Pieces to download are selected to retrieve the pieces held by the fewest peers first (to ensure that the rarest pieces will be available at many peers). The tracker provides random subsets of peers from which to download the piece constructing a random overlay. Peers additionally use a "choking" algorithm where they refuse to upload to peers in order to saturate the connections. This algorithm does a local search for the best connections and provides a tit-for-tat mechanism so peers with poor upload performance are "choked", incentivizing good behavior. The tracker is a single point of failure and is needed to coordinate the downloads and uploads of every peer in the torrent. While the coordination protocol is lightweight, if the tracker goes down, new peers are not able to join the torrent and existing peers won't be able to find new pieces not available on the peers they are currently connected to. Bullet builds a mesh over a multicast tree in order to maximize bandwidth usage at each node in the network. The root of the tree holds the original content. The multicast tree is used to distribute the content to all nodes in the tree. However, this model guarantees that the bandwidth available will monotonically decrease as you descend the tree. Bullet overlays a mesh on top of this tree to overcome this problem. A network state dissemination protocol is used to provide a fixed-sized random subset of network state information to each node in the network using the tree. Information is collected up the tree and distributed down the tree. Each node can use this subset to identify potential peers which are likely to have packets which were dropped from the parent (since the transmission from the parent is unreliable and potentially out of order). Also this enables the children to achieve more incoming bandwidth than the parent can provide. Because Bullet is layered over a tree, the tree must be constructed and maintained requiring overhead which isn't directly used to maintain the content delivery system which Bullet could provide. It seems that this is an artificial constraint on the system and limits its application and performance. If a node high up in the tree goes offline, the whole subtree will be partitioned and this requires repair by some protocol not discussed. Also leaf nodes will not contribute as much as nodes interior to the tree. SplitStream is also targeted at multimedia streaming and uses multicast trees. SplitStream assumes several stripes of data (potentially coming from different source nodes). Each node specifies a desired number of streams to receive (its indegree) and the maximum number of children (its outdegree). A Scribe multicast tree is built for each stripe. Each stripe is identified by an id on for a Pastry ring. Each node sourcing the stripe acquires that id. Each strip id has a different leading digit guaranteeing that each node will be an interior node in only strip tree (since stripe trees are the union of the pastry routing paths of nodes in the tree). Node outdegrees are maintained by building an additional extra capacity tree and having nodes reject children if having such a child would exceed its outdegree. The extra capacity tree can be used to find a node receiving the desired stripe and with extra outdegree. This construction mechanism seems heavy duty (compared to something like BitTorrent) and also incurs significant delay, especially for some real-time application like video conferencing. Experimentation on PlanetLab show that nearly 40% of nodes experience a delay exceeding 400ms which may be too high for a realtime experience. From asg46@cornell.edu Thu Mar 30 11:59:44 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2UGxhY19144 for ; Thu, 30 Mar 2006 11:59:43 -0500 (EST) Received: from webmail.cornell.edu (hermes21.mail.cornell.edu [132.236.56.20]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2UGxgcT025374 for ; Thu, 30 Mar 2006 11:59:42 -0500 (EST) Received: from 128.84.98.90 by webmail.cornell.edu with HTTP; Thu, 30 Mar 2006 11:59:43 -0500 (EST) Message-ID: <4740.128.84.98.90.1143737983.squirrel@webmail.cornell.edu> Date: Thu, 30 Mar 2006 11:59:43 -0500 (EST) Subject: paper 17 - MULTICASTING From: "Abhishek Santosh Gupta" To: egs+summary@cs.cornell.edu User-Agent: SquirrelMail/1.4.5 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Priority: 3 (Normal) Importance: Normal these set of papers target high-bandwidth data distribution from a single source to a number of receivers. BASIC IDEA: split content into smaller sized chunks and distribute disjoint data sets for better recovery. BIT-TORRENT it breaks contents into sub-pieces typically 16Kb in size. the torrent file contains SHA1 hashes of all pieces and the peers dont report that they have a piece until the hash is checked against. a set of trackers help nodes in finding each other. a number of requests kept pending to avoid delay b/w pieces being sent. the order of downloading pieces depends upon the strategy being used. the authors discuss that a rarest first strategy serves the necessary purpose except when downloading starts(random first used). "endgame-mode": cancels have to be sent for pieces arrived to prevent bandwidth from being wasted on redundant sends. OPTIMISTIC UNCHOKING: allows upload to peers with download rates slower than the best download rate. this allows to test the bandwidth of unused connections. ANTI-SNUBBING: when over a minute goes by without getting a single piece from a particular peer, the requesting node does not upload to that peer ( assuming it is getting snubbed) - tit-for-tat strategy. this can reduce free-riding. BULLET basic idea: instead of sending the same data stream to all nodes in a tree and then designing scalable mechanisms for recovering from loss, the sender transmits disjoint data sets to various points in the network. the sender splits the data into sequential blocks. blocks are further subdivided into individual objects which are transmitted over the network. nodes receive a subset of the entire data objects from their parents but they are responsible for locating peers that hold the missing data objects. locating peers requires storage of state information that has to be updated using periodic dissemination of changing, uniformly random subsets of global state. RanSub achieves this purpose using collect and distribute messages. objects may be encoded to make data recovery more efficient. each node receiving a packet will optionally forward it to each of its children depending on factors related to the child's bandwidth and relative position in the tree. for this purpose it maintains a sending factor and a limiting factor. the sending factor is based on the number of descendants a node has while the limiting factor represents the proportion of the parent rate beyond the sending factor that each child can handle. calculating the sending factor requires knowledge of number of descendants of each node that is a child of the current node. each node maintains a working set of packets it has received ( indexed by sequence numbers). improving mesh: each node keeps a trial slot in its sender list which helps in elimination of senders that send greater amounts of duplicate packets. similarly a sender keeps a trial receiver. SPLITSTREAM the content is split into k stripes and each stripe is multicast using a separate tree. in a tree based multicast system, the burden of duplicating and forwarding multicast traffic is carried out by the interior nodes of the tree. the main goal is to balance across all nodes. this raises the challenge of constructing a forest of trees such that an interior node in a tree is a leaf in the remaining trees. the authors use scribe ( an application level group communication system) interior-node disjoint trees are created using a different msb for the group-id. a node's outdegree is limited by a "push-down" mechanism - if a node has reached its maximum outdegree capacity, it asks the requesting node to communicate with its children. SPARE CAPACITY GROUP : this is a special scribe group which consists of nodes who have not reached their outdegree capacity. this group can be used by a node to find a parent. cycles need to be taken care of in this mechanism. POSSIBLE FLAWS: splitting the content into same number of stripes, irrespective of the content size, does not seem a good idea. From km266@cornell.edu Thu Mar 30 12:01:23 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.7 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2UH1MY19546 for ; Thu, 30 Mar 2006 12:01:22 -0500 (EST) Received: from KEVSTOY (cpe-69-207-37-246.twcny.res.rr.com [69.207.37.246]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2UH1L4X019974 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for ; Thu, 30 Mar 2006 12:01:22 -0500 (EST) Message-ID: <000e01c6541b$ab98b600$f625cf45@KEVSTOY> Reply-To: "Kevin" From: "Kevin" To: Subject: PAPER 17 Date: Thu, 30 Mar 2006 12:02:03 -0500 MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=original Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.2527 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2527 BitTorrent is a centralized file distribution system. It is reminiscent of Napster in the way it does its routing, but far more specific per file. A tracker is stored on a server, for simplicity it is accessible through the HTTP protocol on port 80, and keeps track of the current peers downloading and uploading only one file. When a client connects to the tracker, the tracker sends back a random subset of the currently available peers who are also downloading (or are done downloading) the file. A client connects to many peers and downloads subsets of the file which it does not currently have in a rarest-available scheme. In the mean time, the client is uploading the parts of the file that it previously downloaded to other peers...in this way, clients can self monitor other peers and only upload to those that are allowing them to downloading, trying to making the communication symmetric. The problem with BitTorrent is that is has a central non-scalable point of failure. The tracker requires a fair amount of bandwidth and with very high numbers of clients (10^5 or higher), it would be non-performant. Furthermore, it is subject to legal attacks and other out-of-network attacks that Napster suffered from. It is, on the other hand, harder to go after than Napster because trackers and torrents can be stored on anyone's server, not just napster.com. The other problem with BT is that is seems to derive all of its conclusions by what was already implemented instead of experimentation and mathematics. Bullet is slightly more general than BT. It allows streaming video and other mutable file types to be shared between peers. The central idea behind bullet is similar to that of BT: once a peer has (part of) a file, it can start transferring it to other peers. To achieve this, Bullet organizes itself into a distribution tree and overlays a mesh on top. The authors argue that a distribution tree is not performant when any nodes, especially a node close the root, has a slow connection or disconnects. To alleviate this issue, the overlayed mesh connects peers that are not directly connected in the tree. The examples the authors gives are a root node, r, and two children: a and b. If the connections between all nodes is 1mpbs and the root node sends a the file, b can receive it at 2mpbs (instead of 1) because it can download from a and from r at the same time (as long as the mesh has that connection). In their experiments, Bullet achieved, on average, twice the bandwidth per node than a distribution tree. It is also less susceptible to random disconnections and low bandwidth nodes. The problem with Bullet seems to be the small amount of overhead bandwidth that is used to propagate node information that builds the mesh. The authors are quick to argue that 30kpbs is not significant enough to slow down the expected high-bandwidth connections that are expected to use it, but streaming video is not limited to high bandwidth connections. Currently, most websites have options of bandwidth between 50kpbs and 250kpbs (to satisfy modems up to decent quality broadband connections). This system would be unworkable with video bitrates of 50kpbs (or even 100kpbs) because a significant amount of bandwidth relative to the video quality would be required just as overhead. SplitStream is yet another system, once again more general than BitTorrent, that distributes data from a source to a bunch of clients/peers. SplitStream stripes data into overlapping segments (the overlap is for ECCs). Multiple distribution trees are created where each client is a leaf in every tree except one in which it is an interior node. The data that was cut into pieces is then sent along the trees and is received by all clients. In this way, SplitStream tries to achieve equal amounts of upload and download bandwidth between all peers. There are several problem with this approach. Bandwidth is often non-uniform and slower links can slow down the entire network. The other problem is the immense amount of resources needed to construct many distribution trees. In addition, when sending a larger file, the number of trees that are needed goes up. This seems like a serious flaw, especially in a system with large amounts of churn. From gp72@cornell.edu Thu Mar 30 12:19:57 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.9 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from postoffice10.mail.cornell.edu (postoffice10.mail.cornell.edu [132.236.56.14]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2UHJvY24150 for ; Thu, 30 Mar 2006 12:19:57 -0500 (EST) Received: from orpheus3.dataserver.cornell.edu (orpheus3.dataserver.cornell.edu [128.253.161.167]) by postoffice10.mail.cornell.edu (8.12.10/8.12.6) with ESMTP id k2UHJtTX008473; Thu, 30 Mar 2006 12:19:55 -0500 (EST) Message-ID: <1015850739.1143739194341.JavaMail.webber@orpheus3.dataserver.cornell.edu> Date: Thu, 30 Mar 2006 12:19:55 -0500 (EST) From: Gopal Parameswaran To: egs+summary@cs.cornell.edu Subject: PAPER 17 Cc: gp72@cornell.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: uPortal WEB email client 3.0 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k2UHJvY24150 Bittorrent The Bittorrent system is a peer-to-peer network that uses an economic mechanism based on the upload rate from the peer for downloading since real deployments experience high churn rates and this helps to correct the problems of fairness where peers disconnect after downloading their file. A Bittorrent is started with a user deploying a torrent file containing information about the file, its length, name, and hashing information and the url of a tracker that help downloaders find each other using a simple protocol layered on top of HTTP in which the downloader sends the information that specifies which file is being downloaded and the port it is listening on and the tracker responds with A list of contact information for peers which are downloading the same file and can be further used as a source for downloading the different portions of the file. Once the downloaders have this information they contact each other and download from each other. This method of peers to find other peers is done based on random graphs, which has good inherent robustness properties. Bittorrent cuts files into smaller pieces of fixed size of around a quarter mega byte and the SHA1 hash of all the pieces are included in the torrent file so that peers can report if they have a particular piece of the file or not after checking the hash of the pieces that they have. Bit torrent further breaks down the pieces into sub-pieces of typically 16 Kilo bytes and typically keeps five sub-pieces in the pipeline for transmission based on a value based on the threshold that would saturate the connection bandwidth. Bit torrent prevents choking by using a Pareto efficiency algorithm that that does local optimization by uploading to peers which upload to them, with the goal of at any time of having several connections which are actively transferring in both directions. Bullet This paper addresses bandwidth maximization in peer to peer networks and is a scalable distributed algorithm that enable nodes spread across a peer to peer network organize itself into an overlay mesh that would maximize bandwidth. It also helps nodes in recovering missing items and reduces the need to do expensive bandwidth probing in relation to a tree-based solution. It is based on spreading the uniform random subsets of a global state to all the nodes of the overlay tree as it changes over time called Ransub which works by using two types of messages called collect and distribute messages. The collect messages propagate up the tree and leaves the state information gathered from the underlying nodes at that node and the distribute message then traverses down from the root spreading uniform random subsets to all the underlying nodes. Bullet extends it by layering a mesh on the underlying overlay tree for Ransub. SplitStream SplitStream addresses the problem of application level multicast in peer to peer networks where a relatively small number of interior nodes carry the load of forwarding multicast messages by striping the content across a forest of interior-node-disjoint multicast trees that distributes the forwarding load among all participating peers. SplitStream thus distributes the forwarding load among all peers and can accommodate peers with different bandwidth capacities while imposing low overhead for forest construction and maintenance. SplitStream achieves this by splitting the multicast stream into multiple stripes, and using separate multicast trees to distribute each stripe. Split Stream only provided a generic infrastructure for high bandwidth content distribution and it would be the application that uses the framework that decides on how the content is to be divided into the stripes. From kelvinso@gmail.com Thu Mar 30 12:32:25 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-1.7 required=5.0 tests=AWL,BAYES_00, RCVD_IN_BL_SPAMCOP_NET autolearn=no version=3.1.0 X-Spam-Level: Received: from wproxy.gmail.com (wproxy.gmail.com [64.233.184.228]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2UHWOY27171 for ; Thu, 30 Mar 2006 12:32:24 -0500 (EST) Received: by wproxy.gmail.com with SMTP id i13so802996wra for ; Thu, 30 Mar 2006 09:32:24 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=j14oeokZNXgTtk2agDfvWjM7foBOk2alkg3sRhQT14z1c5GFkWssQTICF989S2x3Mv8ZBSSDghdOjfqgDt8lhvRZXah2ReBLwcGmmPL7ia6JJIfSbolZ50MoryoOiXOpSFIh1XwvwpozG0/4Uw9w+xfy1EX9nrjRY6BKDEZIoIk= Received: by 10.54.124.10 with SMTP id w10mr84682wrc; Thu, 30 Mar 2006 09:32:21 -0800 (PST) Received: by 10.54.78.5 with HTTP; Thu, 30 Mar 2006 09:32:21 -0800 (PST) Message-ID: <6e1ca4560603300932q5b5e34b1rde16767a7ed07b42@mail.gmail.com> Date: Thu, 30 Mar 2006 12:32:21 -0500 From: "Chiu Wah Kelvin So" To: egs+summary@cs.cornell.edu Subject: Paper 17 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id k2UHWOY27171 BitTorrent is a popular file distribution system. The general idea is to split the file into fixed-size segments. Bittorrent uses the tracker to gather statistic of each peers, such as upload rates, download rates, and also the segments of file they have. Whenever a peer wants to participate in download, the peer contacts the tracker to get a list of available peers. The peer individually requests segments using rarest first policy from anyone who has the segments. Although the tracker doesn't have a high load of communication, it is still a centralized approach and can suffer from scalability and single point of failure. The second paper, "Bullet: High Bandwidth Data Dissemination Using an Overlay Mesh," presents a general data dissemination protocol using an overlay mesh instead of multicast tree. This overlay mesh is based on a multicast tree with some number of cross links from other peers. Therefore, it is more fault-tolerance than multicast tree where a node only receives traffic only from its parent. Another advantage of such an approach is that the data dissemination rate doesn't limit by the bottleneck bandwidth of parent links. Bullet splits the object into fragments and sends disjoint set of the fragments to each of the children in the overlay mesh. It uses RanSub to collect information of the fragments each node has. Therefore, each node can finds its potential peers to download necessary fragments. The third paper, "SplitStream: High-Bandwidth Multicast in Cooperative Environments," uses multiple multicast tree to improve the efficiency. This paper identifies a problem in single multicast tree where the leaf in the tree doesn't contribute any bandwidth in the multicast. Therefore, it splits multicast stream into k stripes. Each stripe is served using a multicast tree built using Scribe. Therefore, the leaf in a tree can be an interior node of the other tree. Also, if a single node suddenly fails, the performance will not suffer since there are k-1 other multicast streams. All the techniques above can use some other data encoding, such as erasure coding, to improve performance. Although both Bullet and SplitStream require more bandwidth to maintain the underlying data dissemination structure, it can achieve a higher overall efficiency. From PJK25@cornell.edu Thu Mar 30 13:23:04 2006 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.0 (2005-09-13) on sundial.cs.cornell.edu X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.1.0 X-Spam-Level: Received: from authusersmtp.mail.cornell.edu (granite1.mail.cornell.edu [128.253.83.141]) by sundial.cs.cornell.edu (8.11.7-20031020/8.11.7/M-3.22) with ESMTP id k2UIN3Y10182 for ; Thu, 30 Mar 2006 13:23:03 -0500 (EST) Received: from [128.84.218.181] (rrdhcp216-693.redrover.cornell.edu [128.84.218.181]) (authenticated bits=0) by authusersmtp.mail.cornell.edu (8.13.1/8.12.10) with ESMTP id k2UIMwha001989 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for ; Thu, 30 Mar 2006 13:23:03 -0500 (EST) Mime-Version: 1.0 (Apple Message framework v746.3) Content-Transfer-Encoding: 7bit Message-Id: Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: egs+summary@cs.cornell.edu From: Philip Kuryloski Subject: PAPER 17 Date: Thu, 30 Mar 2006 13:22:57 -0500 X-Mailer: Apple Mail (2.746.3) BITTORRENT Bittorrent as outlined in this paper functions in a semi-centralized manner, using a tracker to locate peers who are actively sharing a desired file. All actual data sharing, however, takes place in a P2P manner. In general, peers try to enforce a "tit-for-tat" sharing scheme. In order to maximize global throughput, a variety of techniques are employed. Files are broken up into half megabyte blocks, with a file's name, size, and SHA1 hashes for each block posted in a torrent file in some well known place. Each block is broken up into smaller sub blocks, typically 16KB, and at all times 5 sub-blocks are on request from a peer. Initially a random block is requested, after that the rarest blocks are requested first to preserve the overall availability of a file. Upstream bandwidth to other peers is limited by the rate at which those peers provide data. At all times, one peer is allowed full upstream bandwidth, rotating through the peers, in order to detect a peer which will support higher reciprocating rates. BULLET Bullet is fully distributed and relies upon forming a P2P mesh of nodes. It does, however transmit disjoint data sets to nodes, in order to maximize the global spread of information. Rather than request the rarest packets, bullet uses erasure or multiple description coding and requests packets from any other node which is believed to have missing data. Periodically a message is sent up and down the overlay which produces a randomized global summary of the data each node has. These summaries are disseminated, thereby allowing nodes to locate appropriate peers. Rather than use a "tit- for-tat" choking scheme to control bandwidth, Bullet uses a modified TCP control algorithm called TFRC which attempts do maintain a steady data rate. It does not react to packet losses or search for bandwidth as aggressively as the standard TCP flow algorithm. Simulation demonstrates that bullet provides 5 times the transfer rate achieved by a random IP multicast tree. Other simulations show that Bullet is more effective than gossip protocols. Bullet seems to be designed not as a batch system like Bittorrent but as a multimedia streaming solution, esentially augmenting tree-based multicast with peer to peer multiple description coded enhancements. Bittorrent instead implements techniques to enforce upload/download fairness and minimize the likelihood that a file will become partially unavailable over the course of it's shared lifetime. SPLITSTREAM SplitStream, like Bittorrent, does not use erasure of multiple description codes, and instead attempts to spread slices or blocks of a file throughout the overlay (although the authors do suggest the use of such codes when multimedia content is to be distributed). Rather than request blocks in heuristic manner, however, SplitStream forms multiple multicast trees to distribute each slice of the file. The challenge is then maintaining that this forest of multicast trees remain even in the sense that a node is placed high on the hierarchy of one tree and low on all others. The overlay which is used as the foundation of SplitStream is Scribe and Pastry. Scribe is an application level group communication system built on Pastry, and Scribe groups, which have a natural routing tree, are used as members of a slice multicast tree. Since a scribe routing tree terminates at some arbitrary groupID in the Pastry identifier space, Scribe groups whose groupID differ in the most significant digit will remain disjoint in the sense that a node remains a leaf node in all but one tree. Bandwidth constraints limit the degree of nodes and the size of these trees.