UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Enhancing collaborative content delivery with helpers Wong, Joseph Hao Tan 2004

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2004-0692.pdf [ 2.29MB ]
Metadata
JSON: 831-1.0051633.json
JSON-LD: 831-1.0051633-ld.json
RDF/XML (Pretty): 831-1.0051633-rdf.xml
RDF/JSON: 831-1.0051633-rdf.json
Turtle: 831-1.0051633-turtle.txt
N-Triples: 831-1.0051633-rdf-ntriples.txt
Original Record: 831-1.0051633-source.json
Full Text
831-1.0051633-fulltext.txt
Citation
831-1.0051633.ris

Full Text

Enhancing Collaborative Content Delivery with Helpers by Joseph Hao Tan Wong B.Sc., University of  British Columbia, 2001 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of  Science in THE FACULTY OF GRADUATE STUDIES (Department of  Computer Science) We accept this thesis as conforming to the required standard The University of  British Columbia September 2004 © Joseph Hao Tan Wong, 2004 THE UNIVERSITY OF BRITISH COLUMBIA FACULTY OF GRADUATE STUDIES Library Authorization In presenting this thesis in partial fulfillment  of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference  and study. I further  agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Joseph Hao Tan Wong 30/09/2004 Name of Author (please  print) Date (dd/mm/yyyy) Title of Thesis: Enhancing Collaborative Content Delivery with Helpers Degree: Master of Science Year: 2004 Department of Computer Science The University of British Columbia Vancouver, BC Canada grad.ubc.ca/forms/?formlD=THS page 1 of 1 last  updated:  29-Sep-04 In the client-server model predominant in today's Internet, the load on a server has a significant  impact on the level of  service perceived by its clients. In particular, given that a server is connected to its clients via an access link of  finite capacity, the data transfer  rate to each of  its clients drops inversely as the number of clients served by the server. This limitation significantly  hampers the scalability of such a setup, especially when long-lived connections are involved in the transfer  of large files.  It is now commonplace for  a particular piece of  content on the Internet to experience a sudden spike in popularity and hence also in request rate. Such an occurrence, called a "flash  crowd" in Internet parlance, is difficult  to address via adjusting the provisioning level alone, as it may come and go so quickly for administrative actions to be taken. To mitigate the problem of  the flash  crowd, many solutions have been devel-oped. Some of  them involve setting up a load-balancing infrastructure,  while oth-ers rely upon the altruism of  clients to provide additional capacity to handle the in-creased load. In this thesis, we describe a novel hybrid approach, based on the tech-nique of  swarming, for  scaling up the delivery of  large files  to many clients. Our design allows machines on the Internet to contribute their bandwidth resources even when they are not interested in the content being disseminated. These peers, known as helpers, are specially tuned to maximize their upload rates while keep-ing their own download rates to a minimum. We evaluate our approach through simulation, testing it under a variety of  conditions involving different  bandwidth capacities and node arrival rates. Our results show that helpers are effective  in contributing their bandwidth resources under all circumstances, and are able to increase the aggregate upload capacity of  the whole system. Contents iii List of  Tables vi List of  Figures vii Acknowledgements ix Dedication x 1 Introduction 1 2 Related Work 4 2.1 Peer-to-Peer Web Caching 4 2.2 Collaborative Parallel-Download Systems 6 2.2.1 Multicasting Systems 7 2.2.2 Swarming Systems 9 2.2.3 Taxonomy 9 2.3 Swarming Performance  12 3 Design 14 3.1 Preliminaries 14 3.2 Operations 16 3.2.1 Ordering of  Block Requests 17 3.2.2 Connections between Peers 18 3.3 Helpers 20 3.3.1 Design Goals 20 3.3.2 Mechanism 21 4 Evaluation 27 4.1 Methodology 27 4.1.1 Simulation Framework 27 4.1.2 Evaluation Metrics 30 4.1.3 Baseline Test Cases 31 4.2 Experiments 32 4.2.1 Setup 32 4.2.2 A First Scenario: Instantaneous Flash Crowd with Broad-band Peers 33 4.2.3 Varying Arrival Rates 39 4.2.4 Varying Helpers' Bandwidth Characteristics 46 4.2.5 Varying the Number of  Helpers 49 4.2.6 Varying kthres 5 3 4.2.7 Varying kupioad 56 4.2.8 Summary 59 5 Conclusion and Future Work 61 5.1 Conclusion 61 5.2 Future Work 63 Bibliography 65 Appendix A Glossary 68 A.l Terms 68 A.2 Notations 69 List of  Tables 2.1 Differences  between existing swarming and multicast streaming sys-tems 11 2.2 Taxonomy of  collaborative parallel-download systems 12 4.1 Evaluation Metrics 31 4.2 Default  simulation parameters 33 4.3 Simulation parameters for  the first  scenario 34 4.4 Average download times for  the first  scenario 37 4.5 Simulation parameters for  varying arrival rates 39 4.6 Simulation parameters for  varying the mix of  helpers 47 4.7 Simulation parameters for  the test suite 50 4.8 Simulation parameters for  varying the number of  helpers 50 4.9 Simulation parameters for  varying k t h r e s 53 4.10 Simulation parameters for  varying k u p io ad 56 List of  Figures 4.1 Pseudocode for  the maximum-share bandwidth allocation algorithm . 29 4.2 Total number of  blocks transferred  to regular peers 35 4.3 Useful  throughput levels 35 4.4 Cut flow  levels 36 4.5 Total number of  blocks transferred  to helpers 37 4.6 Aggregate helper download rate 38 4.7 Aggregate helper upload rate 38 4.8 Total number of  blocks transferred  to regular peers 40 4.9 Useful  throughput levels 40 4.10 Total number of  blocks transferred  to helpers 41 4.11 Aggregate download rates and total upload capacity 42 4.12 Time of  download completion vs. start time 42 4.13 Download time vs. start time 43 4.14 Total number of  blocks transferred  to regular peers 43 4.15 Useful  throughput levels 44 4.16 Cut flow  levels 45 4.17 Aggregate upload and download rates of  the helpers 45 4.18 System throughput results for  instantaneous arrival scenarios . . . . 47 4.19 System throughput results for  phased arrival scenarios 48 4.20 Helper efficiency  results for  instantaneous arrival scenarios 48 4.21 Helper efficiency  results for  phased arrival scenarios 49 4.22 Uplink utilization of  helpers 51 4.23 Downlink utilization of  regular peers 52 4.24 Useful  throughput levels for  scenarios with helpers on asymmetric links 53 4.25 Aggregate helper download rates for  scenarios with helpers on asym-metric links 54 4.26 Useful  throughput levels for  scenarios with helpers on symmetric links 55 4.27 Aggregate helper download rates for  scenarios with helpers on sym-metric links 55 4.28 Useful  throughput levels and aggreate helper download rates for scenarios with helpers on asymmetric links 57 4.29 Useful  throughput levels and aggreate helper download rates for scenarios with helpers on symmetric links 58 From the bottom of  my heart, I would like to express my sincere gratitude to Dr. Norman Hutchinson, my supervisor and mentor. This thesis could not have come to fruition  without the constant support, guidance, patience and inspiration he has shown me through the ups and downs of  my research. I would also like to thank Dr. Charles Krasic, for  his insights into the world of  content delivery and peer-to-peer systems, and for  the valuable feedback  he has given me on my research and this thesis. I am also very proud to have been a part of  the DSG, and I would like to thank Dima, Chamath, Geoffrey,  Ken and everybody in the DSG for  all their advice, tips and tricks, and for  cracking me up with laughter every day I come into the lab. The DSG has been a most cheerful  and comfortable  place to be my home away from  home. Finally, I would like to express my deepest gratitude to my parents for  their unwavering love, support and care through it all. I would not have been able to pull it off  without them. JOSEPH WONG The University of  British Columbia September 2004 To the memory of  my loving grandmother. Introduction A common occurrence in today's Internet is the phenomenon of  the flash  crowd, where in a short period of  time a server experiences a dramatic spike in its request rate due to a sudden increase in the popularity of  the content it hosts. Often,  this causes the server in question to grind to a halt, as it no longer has the computa-tional capacity to process the flood  of  connection attempts. The common solution to such a computational bottleneck is to deploy a load-balanced cluster of  servers to handle the incoming requests. In many circumstances, however, a flash  crowd's might lies not in its computational requirements, but its burden on the server's bandwidth [19]. This effect  is most apparent when the popular content in question is a set of  large files,  which magnifies  the total number of  bytes that needs to be delivered. While many servers are connected by links adequately provisioned for regular levels of  traffic,  the intensity of  hundreds of  requests per minute can easily cause even well-provisioned links to become congested. There are several solutions now in common use to mitigate the effects  of flash  crowds, all of  which are different  approaches in tackling the same problem, namely that of  how to add more bandwidth to the delivery mechanism. Mirroring is the use of  alternate servers to host replicas, or mirrors, of  the popular content. Clients are then redirected, either automatically, or through a set of  links on the main web site, to these mirror servers to fetch  the files.  The mirror system pos-sesses, in aggregate, the combined upload capacity of  all its constituent nodes in the network. While mirroring is widely adopted and often  effective,  a mirror server can only help take a share of  the load after  it has mirrored the content. This means that the copying of  content to mirror sites must occur before  the flash  crowd comes in order to be effective,  and hence such a setup must be planned in advance. Content distribution networks, or CDNs, are another commonly used plat-form  for  the delivery of  popular content [1,13, 27]. A CDN consists of  a network of  nodes scattered across the internet in different  geographical locations, each of which serves as a cache of  the popular content. The geographic diversity of  these nodes means that any particular client could be redirected to a CDN node close by, thus achieving low latency and minimizing network stress. However, as CDNs are usually commercially deployed, a site wishing to utilize a CDN to handle flash crowds must be willing and able to pay a commercial operation for  its services. Whereas both of  the preceding approaches operate on a file-by-file  basis, delivering data in a some-to-all pattern, cooperative distribution aims to aggregate the bandwidth resources of  individual client nodes to aid in the dissemination of files,  and operates at a granularity below that of  an entire file.  Such systems are often  touted as scalable, or self-scalable  [19,11], since the aggregate upload capac-ity of  the system increases in some proportion to the demand, represented as the aggregate download capacity of  the system. Among the various different  flavours of  cooperative distribution, swarming is a technique that has caught on in popu-larity in recent years [9, 26, 30], championed by its most famous  implementation BitTorrent. Simply put, in a swarming system such as BitTorrent, a large file  is di-vided into blocks, and clients, or peers, download these blocks from  each other in parallel. The key to its efficiency  lies in its mechanism for  evenly distributing the blocks to different  peers, so that any two peers coming into contact will have some blocks that are not in common to share with each other. In swarming systems, a fundamental  assumption is that all peers are inter-ested in the file  which they are delivering to one another, as ultimately each peer's main objective is to download the file  as fast  as it can, while uploading already collected blocks remains only a secondary concern - an entry fee  into the system, so to speak. As a consequence, the performance  of  the system depends heavily on the level of  altruism of  the participating peers. In this thesis, we explore an alternate, hybrid approach to the problem of providing additional bandwidth for  scaling up a content delivery service. Build-ing upon the foundation  of  a swarming system, we introduce the notion of  a helper, whose purpose is to serve as an on-demand cache in a swarm. The helper would aim to saturate its own upload capacity while keeping its own download rate to a minimum. Our design of  the helper is able to provide additional usable band-width to the system regardless of  the level of  altruism of  the clients, and for  any provisioning level of  the helper's link to the network - including symmetric and asymmetric links (e.g., DSL links). This means that helpers can be deployed on almost any node on the Internet and be able to contribute its bandwidth resources under any condition, and as such could serve as the basis of  an economical and more adaptive CDN. The rest of  this thesis is organized as follows.  In Chapter 2, we discuss previous research in the area of  flash-crowd  mitigation, and present a taxonomy on existing and potential collaborative parallel-download systems. We present the design of  our swarming framework  and our helpers mechanism in Chapter 3. In Chapter 4, we give a detailed account of  our evaluation methodology and setup, and evaluate our design with a diverse set of  experiments covering many opera-tion scenarios. We conclude this thesis and outline some areas of  future  work in Chapter 5. Related Work At the heart of  any flash-crowd  mitigation technique is a mechanism for  replicating content. In order to spread out the high load experienced by a server onto a set of other nodes, these nodes themselves must have either complete or partial replicas of  the content with which to serve the redirected requests. Traditional approaches for  tackling this problem include mirroring and utilizing commercial content dis-tribution networks (CDNs). Both of  these approaches are proactive in nature, as the decision to replicate the content needs to come in advance of  any flash  crowds. There is always a chance that the flood  of  requests for  a particular piece of  con-tent never materializes, and hence the effort  and resources spent in replicating the content to all the mirror servers or in contracting out to a CDN is wasted. 2.1 Peer-to-Peer Web Caching The widely-deployed technique of  web caching is another popular approach in addressing flash  crowds. Such systems tend to be more reactive with respect to their replication policy, as objects are replicated based on their demand. To achieve scalability, web caching systems employ collections of  cooperating nodes acting as caches. Early web caching systems include the hierarchical cache [8] and the summary cache [10]. In recent years, there has been much interest in peer-to-peer systems, and several caching schemes employing peer-to-peer techniques have emerged. They offer  the benefit  that every client can potentially act as a cache as well, thus allow-ing the system to scale with the number of  clients. A few  of  these systems rely on the construction of  structured overlay net-works in the form  of  distributed hash tables (DHTs). Squirrel [14] is a decentral-ized, cooperative web cache based on the Pastry [24] overlay network, while Back-slash [28] is a similar system currently implemented on top of  the CAN [23] overlay. In Backslash, nodes participating in the system are themselves web servers which would like to be protected from  flash  crowds. As such, a Backslash node would function  as a web server in normal operations, and would only redirect onto the overlay network when it becomes overloaded by high request rates. In contrast, Squirrel involves all clients in its overlay, and routes all requests through the over-lay. Nonetheless, these two caching overlays operate on almost identical principles. When an HTTP request is routed through the overlay in either Backslash or Squirrel, the URL is hashed into a key in the overlay's ID space. In their first  mode of  operation (called home-store in Squirrel and local diffusion  in Backslash), an object with URL i is cached on the node whose nodelD is closest to SHA-l(z) (called the home node for  i). When the request rate hits a predetermined threshold, the object is replicated onto the previous node on a requestor's route to the home node. By doing so, a node that locally observes a flood  of  requests creates a bubble of  caches around itself,  thus diffusing  the load. In their directory mode, both systems maintain on i's home node a directory of  pointers to nodes which have recently requested copies of  the object, some of  which may still have it available to be delivered to other requestors. PROOFS [29] is another peer-to-peer caching scheme. It differs  from  Back-slash and Squirrel in that it utilizes a randomized overlay of  client and server nodes for  caching web content. Clients send out queries for  objects on the overlay net-work, and at the same time can opt to cooperate by answering queries from  other nodes. Compared to the approaches using structured overlays, PROOFS has to solve the additional problem of  locating replicas in a network whose topology is random and constantly changing. While these systems have been demonstrated to be effective  for  handling high request rates, they do so without consideration for  bandwidth issues. For example, if  a large file  (e.g., a Linux distribution) is being popularly requested, none of  these systems would attempt to place replicas of  this file  on well-endowed nodes with high upload capacities, which would be required to sustain long-lived upload connections with the many requestors. Hence, these systems are not espe-cially suited to the job of  mitigating high demands for  large files. 2.2 Collaborative Parallel-Download Systems Many systems have been devised especially to handle the delivery of  large files. They overcome the difficulties  of  replicating large files  by breaking up a file  into smaller units of  replication and transfer  called blocks. Instead of  locating and downloading a replica of  a file  among many files  stored in a web caching system, a peer in one of  these systems would instead be locating and downloading a replica of  a block among the many blocks of  a file,  and would ultimately want to down-load every block of  the file.  The issue of  bootstrapping onto the right overlay for  a particular file  is now a separate problem. Since a file  is now broken into many blocks, and each peer would want to download every single block, these systems take advantage of  the opportunity to increase the throughput by letting peers download multiple blocks from  mul-tiple peers simultaneously. These collaborative parallel-download systems can be grouped into two general categories: multicasting systems and swarming systems. 2.2.1 Multicasting  Systems As shown in [4,3,17], it is feasible  to deliver a file  to a large number of  clients using multicast when the file  is encoded by an erasure encoding. Castro et al. advocated in [5] the use of  an application-level multicast system to deliver bulk data. In or-der to fully  utilize the upload capacity of  participating peers, their system, called SplitStream, organizes the peers into a forest  of  trees which share no interior nodes with high probability. SplitStream is built upon the Scribe multicast system [7, 6, 25], which in turn is based upon the Pastry DHT infrastructure.  Each SplitStream node therefore joins the system with a Pastry nodelD. The file  to be delivered is encoded as k = 2b distinct streams called stripes. Each stripe is identified  by a stripelD, which has the property that the stripelDs of  all stripes differ  in the b most significant  bits. These stripelDs serves as multicast group names in the Scribe layer. A peer subscribes to a multicast group for  a stripe by routing a message to the stripe's root, which is the peer whose nodelD is closest to the stripelD. An application-level multicast tree is formed  using reverse-path forwarding  from  the root through the overlay, and each stripe is streamed from  the source through its own stripe tree. Pastry's prefix routing mechanism entails that in a SplitStream system where all the trees are built this way, a peer will be an interior node for  at most one stripe tree, namely the one whose stripelD shares the b most significant  bits with the peer's nodelD. Through this mechanism, the majority of  peers in SplitStream participate as interior nodes, and so they each help to take a share of  the load away from  the original data source. This tree-building mechanism resorts to a fallback  plan, however, when a peer is not able to join a stripe tree because of  bandwidth constraints. SplitStream allows each peer to specify  its bandwidth constraints in terms of  the number of stripes it is able to receive and forward.  This is to guarantee that every interior node of  a stripe tree has the capacity to forward  that stripe. When a stripe tree runs out of  upload capacity, represented by free  children slots on interior nodes, SplitStream concedes by asking some other peer with excess upload capacity to join the stripe tree as an interior node. This other peer may in fact  be an interior node for  some other stripe tree. In such a case, the trees are no longer interior-node-disjoint. However, this does not affect  the link utilization of  the system, only its resilience to node failures. To enable parallel downloads, a peer joins as many stripe trees as it can. With the redundancy afforded  by an appropriate erasure encoding scheme, the peer will be able to reconstruct the file  even when it has not been receiving all stripes, or has missed some blocks within a stripe. Bullet [16] is another streaming system explicitly supporting the transfer  of large files.  Recognizing that the bandwidth of  a tree is guaranteed to be monoton-ically decreasing moving down the tree, every interior node in Bullet's only tree, called the backbone tree, may choose not to forward  the entire stream it receives to every one of  its children. Instead, the node can drop blocks when its outbound connections are congested. Bullet's algorithm is configured  such that in these sce-narios, a node will forward  sets of  blocks which are maximally disjoint to its chil-dren. This maximizes the ability of  siblings to use up any excess upload capacity they have by sharing blocks with each other through connections that exist out-side of  the backbone tree. A tree-based gossip mechanism allows peers to find  out about each other, so as to establish parallel download connections for  the sharing of  blocks. Other multicast streaming systems, while not designed specifically  for  the delivery of  files,  can similarly be used for  this purpose through the use of  an ap-propriate erasure encoding. The streaming protocol of  CoopNet [19, 20] is one such system. As with SplitStream, it uses a forest  of  interior-node-disjoint trees for  the delivery of  multiple stripes to peers. However, this protocol differs  from SplitStream in that there is no lower-level multicasting or DHT substrate. Instead, the responsibility of  maintaining the forest  topology lies with a central coordinator, which dictates to which tree a peer should join as an interior node. 2.2.2 Swarming  Systems BitTorrent [9] is perhaps the most well known of  the swarming systems. They differ from  the multicasting systems in that no explicit dissemination trees are formed. Instead, peers form  an ad-hoc mesh through which they transfer  data to one an-other. BitTorrent is popularly used to distribute large files  such as software  up-dates and releases. A file  is split into many smaller blocks in BitTorrent, and peers in the system download blocks from  one another, while at the same time upload-ing blocks they already have to others. BitTorrent motivates peers to upload by employing a choking technique, where a peer will preferentially  upload to those that upload to itself  the fastest.  Hence peers that do not upload much also tend to receive worse treatment from  other peers connected to them. All peers interested in a particular file  register with the central coordinator responsible for  the file  called a tracker, which keeps track of  the membership of  nodes in the system. Slurpie [26] is another cooperative protocol for  bulk data transfer  based on swarming. It differs  from  BitTorrent in that the technique of  gossip is used in place of  the centralized tracker to inform  peers in the system of  the arrival or departure of  other peers. It also attempts to achieve better performance  by dynamically ad-justing the number of  connections based on the bandwidth conditions at the time. 2.2.3 Taxonomy Swarming and multicast streaming are two current techniques which have the po-tential to satisfy  the needs of  file  distribution and bandwidth sharing. We have developed a taxonomy for  these collaborative parallel-download systems, allow-ing us to focus  upon the salient features  which distinguish each system from  the others. In SplitStream and CoopNet, the content to be delivered is divided into one or more stripes. Each of  these stripes is delivered at a fixed  rate, and peers subscribe to as many stripes as they can. The peers which subscribe to a particular stripe form a dissemination tree, and the stripe's content then flows  from  its source down the tree, at the specified  rate. Within a stripe, the content is subdivided into blocks or data packets, and these are delivered in sequential order. Depending on the underlying transport, the delivery of  blocks may be lossy, and erasure encoding may be employed to compensate. This same technique is used to handle node churn, where a node leaving the system causes otherwise non-lossy connections to become permanently lossy. In swarming systems, the pertinent content to be delivered is most often  a file,  which is subdivided into blocks. Peers form  connections with each other in an ad-hoc fashion  and deliver blocks to each other. Intrinsically, a peer connection does not have a specified  delivery rate associated with it, nor does it place a re-striction on which blocks must or must not be delivered through it. Moreover, to maximize the utilization of  bandwidth, blocks can be requested and delivered in any order desired, and peers do not need to have the content completely down-loaded before  it can upload blocks to others. Swarming deals with churn naturally since it is a block-based technique and there is no enforced  ordering of  the delivery of  blocks. Bullet sits somewhere in between the two, as its tree connections are not required to deliver data at any particular rate. In addition to having a tree, it also permits peers to form  ad-hoc connections for  sharing blocks, in much the same way as swarming systems. We summarize the differences  in characteristics between these systems in Table 2.1. Among different  streaming and swarming systems, we also find  other dis-tinguishing design choices which have a major impact on their modes of  operation. SplitStream/ CoopNet Swarming Bullet Topology trees ad-hoc mesh tree and ad-hoc mesh Delivery rate per connection fixed variable variable Blocks sent on a connection only those be-longing to the stripe any any Order of  delivery sequential order any any Handling of  miss-ing blocks erasure encoding reconciliatory transfers reconciliatory transfers Group management The management of  the group of  peers in both streaming and swarming could be centralized or decentralized. In CoopNet, there is a central coordinator that maintains the topology of  the multiple stripe trees, whereas in SplitStream, a de-centralized DHT is used for  the same purpose. In BitTorrent, a tracker serves as a central repository on group membership information,  while in Slurpie, a gossip mechanism is used to disseminate group membership information. Discovery of  content The search for  other peers to connect to may be guided by a peer's desire for  par-ticular portions of  the content. In essence, this is can be regarded as an extension of  the group management mechanism, where group memberships are maintained not at the file  granularity but at a lower granularity, e.g., a stripe or a block. A peer would query this mechanism in order to discover other peers with the content it is interested in downloading. In SplitStream and CoopNet, group membership is maintained at the stripe level. With Slurpie, the gossip messages passed between peers contain not only a list of  other peers, but also which blocks those peers have. Design Decision Choice 1 Choice 2 Explicit topology construction yes no Fixed delivery rate per connection yes no Restriction on the blocks sent on a connection yes no Sequential order of  delivery yes no Erasure encoding yes no Group management centralized decentralized Discovery of  content guided unguided Together with the characteristics distinguishing streaming from  swarming, we have just described seven design decisions that are fundamental  to the oper-ation of  the content distribution system (see Table 2.2). These choices are in fact orthogonal to one another: they could be mixed and matched to form  a whole spectrum of  content distribution systems. 2.3 Swarming Performance To date, two groups have performed  measurement studies on the performance  of swarming, in particular of  the BitTorrent protocol [15, 21]. Izal et al. [15] followed the lifetime  of  a torrent for  the 1.77GB Redhat 9 Linux distribution for  five  months, and analyzed the statistics of  the thousands of  peers involved. They conclude that BitTorrent is highly effective,  and is able achieve throughput levels that are capable of  sustaining large flash  crowds. In [21], Pouwelse et al. present detailed mea-surements of  BitTorrent taken over an eight-month period, including results on the popularity and availability of  files  and trackers, the download performance,  the lifetime  of  torrents, and the fraction  of  corrupted or wrong content. The performance  of  swarming has also been studied analytically. Biersack et al. [2] provide several analytic models which approximate the operations of both streaming and swarming systems. They offer  some insight into the choice of  system parameters such as bounds on node degrees and the number of  blocks a file  should be split into. Through the use of  linear programs, Mundinger and Weber [18] analytically show how to solve the problem of  minimizing the time it takes for  a source to distribute a file  to n other nodes. Both [2] and [18] assume that the upload capacity is uniform  across all peers. Qiu and Srikant [22] developed deterministic and stochastic fluid  models specifically  to study the performance  of BitTorrent. Through these models, they considered the scalability, performance  and efficiency  of  BitTorrent, as well as the effectiveness  of  its peer selection and choking mechanism in incentivizing the system. Design Our survey of  existing collaborative content delivery systems reveals that both streaming and swarming are good candidates upon which to build our augmented delivery framework.  For our work, we have chosen to utilize the swarming model as the foundational  technology, since it has proven itself  as an effective  method in the collaborative distribution of  large files.  In this chapter, we present the design of  an extension to swarming that allows peers to volunteer their upload capacity to the benefit  of  others. 3.1 Preliminaries We begin our exposition on the details of  swarming by outlining the entities in-volved and explaining some of  the terms and notations that we use. All of  the terms and notations introduced here and in subsequent sections are summarized in the Glossary (Appendix A) for  easy reference.  In the interest of  facilitating  com-munication, we adopt the terminology of  BitTorrent wherever appropriate. In order to facilitate  the use of  parallel download connections, a file  is split up into many smaller, equal-length fragments  called blocks. Each block within a file  is identified  by a block id. For every peer A, let BA denote the set of  blocks that A has. These file  blocks are transferred  on connections that are semantically unidi-rectional, even though the underlying transport, TCP, supports bidirectional con-nections. As such, we refer  to the sending and receiving ends of  a connection as the source and the sink respectively. Each peer is connected by an access link to the rest of  the network, and we denote by UCA  and DC A respectively the upload and download capacity of  the peer A's access link in bits per second (bps). We refer  to a set of  peers which are uploading and downloading the same file  via swarming as a swarm. Coordinating the membership of  the swarm is the tracker, a server process responsible for  handling peers joining and leaving the swarm. The tracker itself  could be hosted by any node, regardless of  whether it is in the swarm or not. As the scalability of  a centralized coordinator is not our primary concern, we contend that the use of  such a tracker is sufficient  for  our evaluation needs. Within the swarm, some of  the peers may possess all the blocks for  the file. We refer  to these peers as seeds. Since seeds do not need to download any blocks, their presence in the swarm is simply to serve blocks to others. Setting the seeds aside, the remaining peers in the swarm have only partial copies of  the file,  and are known as leechers. When a leecher has completely downloaded the file,  it changes status and becomes a seed. Looking at the bigger picture, besides the peers that are actively engaged in swarms, there may be other peers that express no interest in the content distributed by the swarms, but are nonetheless willing to contribute their bandwidth to the aid of  others. We call these peers candidates. If  a candidate then joins a swarm to offer its bandwidth resources, the peer then becomes a helper in that swarm. In addition, the term regular peer is used to refer  to a non-helper peer in the swarm. We note that a helper, just like a regular peer, can be classified  as a seed or a leecher depending on whether it has the entire file  or not. 3.2 Operations We now describe the basic operation of  our swarming protocol. First of  all, it should be noted that this protocol is our own design, and differs  from  existing swarming protocols like BitTorrent and Slurpie in several aspects. Throughout our explanation, we will point out the various design decisions involved and the choices that we made. To join the swarm for  a file,  a peer first  contacts the tracker and registers with it. The tracker would add the newly joined peer's identity into its records. If  the peer joins as a leecher, it would then request a list of  peers from  the tracker. In our design, the tracker returns a list that is uniformly  sampled from  its records for  all peers in the swarm. In particular, a new peer in the system is as likely to be picked as one that has been in the swarm for  a while. This makes sure that old peers in the swarm continue to be effectively  utilized. Also, the tracker makes no attempt to select peers that have the blocks that the requesting peer is interested in, since maintaining the additional bookkeeping information  about which peers have which blocks on a continuing basis necessitates a significant  amount of  additional communication overhead. Having received the list of  other peers, the leecher then contacts each one in turn to attempt to establish a unidirectional download connection. The connection request can be accepted or rejected by the other peer depending on several factors, which we describe in Section 3.2.2. If  a connection is established, the requestor acts as a sink and starts requesting for  blocks to be transferred.  A short queue, two blocks in length, is set up on the source to make sure that there is always something to send when the connection is ready. The ordering for  the block requests follows the rarest-first  policy, explained in Section 3.2.1. When it reaches the point where the sink has all the blocks that the source has, no blocks would be transferred  and the connection will go idle. An idle con-nection will start transferring  again when the source receives a new block that is also desired by the sink. If  a connection remains idle after  a timeout period, how-ever, the connection will be dropped. The sink then contacts the tracker again to request additional peers to contact if  the number of  download connections falls below a lower bound. This entire process continues for  a leecher until it has completely down-loaded the file,  block by block, and becomes a seed, at which point its remaining in the swarm is completely optional. A peer can also leave the swarm at any point in time voluntarily, whereupon it would deregister itself  with the tracker. Connec-tions would be broken as the peer departs, leaving partially transferred  blocks on its sinks that would then be discarded. The main effect  of  an abrupt node failure  in a swarming system such as ours is that stale information  would be distributed by the tracker. Since it would be easy for  a peer to notify  the tracker that the list of  peers it received contains stale data, we choose to model all peer departures as proper voluntary departures in our evaluation. 3.2.2 Ordering of  Block Requests When selecting which block to download next, a peer would request a block that the fewest  of  its sinks already have. Once the block is completely downloaded, the peer can then turn around and upload this block to those sinks which do not have this block. This approach is often  called the rarest-first  policy, since a peer chooses to download a block that it deems is the rarest among its sinks. We employ this approach as it maximizes a peer's potential of  having something useful  to upload by preferentially  downloading blocks that are most wanted by its sinks. To implement rarest-first,  a peer categorizes all block ids by their local avail-ability measure. The local availability of  a block i on a peer is defined  to be the number of  the peer's sinks which have block i. Therefore,  the measure of  local availability for  a block ranges from  0 up to the total number of  sinks. For each possible value of  local availability, we maintain a randomly permuted list of  the associated block ids. When it is time to choose the next block to download from  a source, a peer would scan these lists one by one, in availability order from  lowest to highest, until it finds  a block which is offered  by the source but has not been downloaded. These lists of  block ids are updated dynamically. Recording a change in availability of  a block involves removing the id from  its old list and inserting it into a random position in the new one. Every time a sink connects with or disconnects from  one of  its sources, the sink sends a record of  the blocks it has to the peer, and the availability levels on the peer are duly updated. In addition, a sink sends a status update to all its sources whenever it receives a new block. By doing so, each peer in the swarm has the most up-to-date record of  local availability levels at any moment in time. 3.2.2 Connections between Peers The connections in our base swarming system are semantically unidirectional, that is to say that a peer A downloading from  another peer B is not duty-bound to re-ciprocate and upload to peer B via the same connection. Peer A could in actuality be uploading to peer B, but this connection would be maintained separately. This represents a departure in design from  existing swarming systems such as BitTor-rent, where there is an emphasis on a per-connection notion of  fairness.  We choose to look at fairness  in a broader sense, since helpers will by definition  be uninter-ested in the content which they help to deliver, and there is no incentive for  helpers to help at all if  their only reward is blocks of  a file  they are not interested in. One of  the advantages of  having unidirectional connections is that the num-ber of  upload connections is decoupled from  the number of  download connections. For peers on asymmetric access links with more download than upload bandwidth capacity, they can have more download connections than upload connections, ren-dering it easier to saturate both directions of  their access links. Another benefit  of the decoupling is the added flexibility  for  a peer to be able to choose sources and sinks independently, according to different  criteria. We place an upper limit on the number of  incoming and outgoing connec-tions, since having too many active TCP connections would result in some of  them getting starved due to the ad-hoc nature of  bandwidth allocation in real TCP im-plementations. Moreoever, having more connections splitting the same amount of bandwidth on a peer's access link would also increase the time required to deliver the first  block on each connection. This would have the consequence of  slowing down the propagation of  blocks through the swarm during the ramp-up period. On a particular peer A, we set an upper limit for  the number of  incom-ing (download) connections, and an upper limit for  the number of  outgoing (upload) connections. Each limit is lower-bounded above zero so as to allow each peer to maintain a minimum level of  parallelism in its download /upload efforts. At the same time, the limit grows linearly as the download/upload bandwidth ca-pacity of  the peer, so that each additional connection represents a fixed  amount of additional capacity. By doing so, we bound the heterogeneity of  the capacities of the various connections within the swarm, thereby rendering it less important for a peer to evaluate existing or potential connections based on transfer  rates. This approach is similar to what is done in SplitStream and CoopNet, where the number of  outbound connections on a peer is simply the outbound bandwidth capacity divided by the bandwidth requirement of  one stripe. Where we differ from  these two systems is that the actual attained transfer  rate on each connection is not rigidly enforced,  but is rather attenuated by the underlying TCP flow  control mechanism. With the upper limit on the number of  outgoing connections in place, a peer A needs to make a decision whenever a connection request arrives and it has al-ready reached this upper limit. The peer has the choice to either reject this request, or to evict one of  its existing connections. As its first  step, the peer checks to see that it has some blocks to offer  which the potential sink does not have. If  it can find no such block, the request is rejected. Otherwise, the peer A computes for  each peer p E Sinks U {requestor}  the set difference  SP — Ba~ BP and a score sp = |<5P|. Here, the score sp represents the number of  blocks peer A could currently send to peer p. Since the main goal is to try and maximize the opportunity to upload blocks, the peer chooses to dissociate with peer pVictim whose score sPviclim is the smallest among allp e S ink sVJ  {requestor}.  If  pvictim is the requestor, the connection request is rejected. If  not, the request is accepted, and the existing connection to pVictim will be broken after  the current block in transit is completely transferred. To foster  stability in the topology, we slightly bias the system to prefer  ex-isting connections by additionally imposing a small penalty on the requestor. In particular, we set s r e q u e s t o r = kpenalty  '  \^requestor  |, where k p e n a i t y is a scaling factor < 1. 3.3 Helpers 3.3.2 Design Goals By itself,  swarming enables nodes interested in the same file  to cooperatively up-load parts of  the file  to each other. From the perspective of  the original content provider, its clients are collaborating to take a large share of  the load away from itself.  In extending the swarming model, we aim to satisfy  two related goals: 1) the mechanism should enable a content provider to invite additional nodes into the delivery network with the sole purpose of  providing additional bandwidth, and 2) the mechanism should enable nodes which are otherwise uninterested in the con-tent to volunteer their bandwidth resources and make a positive contribution to the delivery. With the first  goal, our motivation is to allow a content provider to have control in increasing the capacity of  its delivery network on an on-demand basis. In turn, this enables a variety of  cooperation arrangements. For example, a group of  content providers may form  a mutual cooperation pact, where the nodes of  each provider are willing to be called into action in carrying traffic  for  another provider swamped by a flash  crowd. In another scenario, there may be a collection of  nodes that are willing to handle redirected traffic  from  any content provider that asks, effectively  forming  a public service similar to that of  a CDN. Our second goal focuses  upon the ability of  an individual node to make a contribution without actually wanting the file  it is distributing. In many peer-to-peer file  distribution systems, there is often  an emphasis on a per-connection notion of  fairness,  where the speed at which a node is able to download is correlated to the amount of  upload bandwidth it gives back to the system. For example, a node connected to the Internet via an asymmetric broadband link may not be able to download at full  speed because its upload bandwidth capacity is only a fraction of  that amount. We propose to alleviate this problem by allowing nodes to accrue some form  of  payment by transferring  content which they otherwise do not want, so that they will be able to pay for  better performance  later on when download-ing the content which they do want. Our mechanism shall be able to serve as the technical underpinnings of  such an endeavour; however, the design of  the com-plementary economic or incentive system is beyond the scope of  this thesis, and represents one of  the directions of  our future  research. 3.3.2 Mechanism For the design of  our mechanism, we draw some insights from  the streaming model. Let us consider a streaming system whose content is divided into m > 1 stripes of equal bandwidth, and each stripe is delivered in its own dissemination tree. By looking at how many stripes a peer is receiving and how many children it has, it is straightforward  to gauge whether the peer is a net consumer or provider of  ca-parity to the system. In particular, if  a peer is receiving fewer  stripes than it has children, it is giving more than it consumes, and is thus "helpful"  to the system. Therefore,  it is easy to see that a peer that is strictly interested only in helping could do so by signing on to as few  stripes as possible while maintaining a full  comple-ment of  children. Every block received by such a helpful  peer is forwarded  to one or more receivers, and the peer always downloads blocks at a rate no greater than its total upload rate. In the swarming world, there is no notion of  stripes, nor fixed-bandwidth connections. A connection that is usefully  transferring  data between a source and a sink at one moment may go idle at the next when the source no longer has any blocks that the sink wants. Therefore,  it is not enough to simply look at the number of  incoming and outgoing connections of  a peer to judge whether it is a net con-sumer or provider of  bandwidth capacity to the system. Matters are much more dynamic in a swarming system. From the observation that a helpful  streaming peer downloads slower than it uploads, we employ an adaptive rate-limiting mechanism to achieve the same effect  in a swarming peer. It operates on the same simple premise: provide as much upload capacity as possible while consuming no more download capacity than it must. With streaming, one of  the properties of  a helpful  peer A is that every block it receives is forwarded  to at least one other peer, or more generally, U/A  other peers, where U/A  > 1 is called the upload factor  for  A. For our design of  a helper peer in a swarming system, we would want to simply enforce  this property as a policy. However, since a block must be downloaded before  it could be uploaded, a helper cannot guarantee that a block it is about to download will, in the future, be uploaded at least ufA  times. We have to settle with an approximation. While a helper cannot guarantee that a block will be uploaded in the future,  it can at least confirm  that U/A  or more of  its sinks are currently missing this block and would therefore  have the desire to download it when it becomes available. This check plays a crucial role in our rate-limiting mechanism as it prevents a helper from downloading blocks whose demand is low or non-existent among its sinks. Just as importantly, a helper needs to control its downloading of  blocks so that, on average, it consumes less than it provides. Here, we continue with the insight that each block downloaded by a helper A should be uploaded at least U/A  times. At any point in time, a helper may have some blocks which it has downloaded but has each been uploaded less than UJA  times. We refer  to these blocks as unfulfilled  blocks as their purpose of  being uploaded at least U/A  times has yet to be fulfilled.  For every block i,  the helper maintains the number of  times it has been uploaded, denoted UA(i)- Therefore,  the set of  unfulfilled  blocks for  a helper A is represented by 3>a = {i\uA{i) < u/a}, and we define  4>a = to be the number of  such unfulfilled  blocks. If  the helper is able to download faster  than it can upload, and it does not stop downloading, the number of  unfulfilled  blocks will grow. Therefore,  a natural way to limit the rate of  download is for  the helper A to refrain  from  requesting blocks while the number of  unfulfilled  blocks, 4>A, is above a certain threshold TA-Doing so gives the helper some time to upload the unfulfilled  blocks without hav-ing new blocks added to the unfulfilled  ranks. This arrangement has certain salient characteristics. First, as a helper A starts off  with no blocks, it behaves like a regular peer for  at least the first  Ta  blocks it downloads. This allows the helper to quickly obtain a few  blocks which it could upload to other peers. Also, an increase of  1 to 4>A requires the uploading of  UJA blocks worth of  data to offset.  In effect,  this limits the download rate of  the helper to at most I/U/A  of  its upload rate, averaged throughout the lifetime  of  the helper. For a helper peer A, we set u f A = Kpload  • NI,  ( 3 . 1 ) and TA  = kthres  ' UCA,  ( 3 . 2 ) where kupioa(i  and k thres are system-wide parameters. The setting for  the upload factor  can be interpreted as a wish for  a helper to upload each block to a certain fraction  of  its sinks, however many or few  there are. At the same time, we choose to set the threshold on a per-helper basis because a helper with a faster  uplink would want to have more blocks to offer  its sinks early on so as to keep the pipelines full and the uplink fully  utilized. Once a helper A downloads a particular block i, that block remains in the unfulfilled  state until it has been uploaded U/A  times. However, it is possible that since the time when the helper first  requested block i, the situation has changed. Let us denote by desireA(«) the number of  A's sinks which do not have the block i. While desirea{i)  > ufA  when the decision was made to download block i, it may now be the case that desireA(i)  < UJA•  If  so, we reevaluate the block, and artificially  modify  the upload count of  the block, UA.{i), as follows: ua{i)  <— max(uA(i),ufA  — desireA(i))  (3.3) This then allows the block i to be taken off  the unfulfilled  list after  it has been uploaded another desireA(I)  times, at which point all the current sinks will have downloaded block i. The helper performs  this reevaluation periodically with period T REEV AI  whenever 4>A > TA- By performing  this reevaluation, the helper makes sure that no blocks are stuck in the unfulfilled  state indefinitely,  which if  left untreated would obstruct the helper from  downloading further  blocks. A side benefit  of  the slow download rate of  helpers is that over the course of  the helpers' participation in the swarm, they tend to consume less local storage for  the caching of  blocks. This makes it possible for  helpers to aid in the delivery of  more swarms simultaneously. Inviting Helpers In order to be able to determine whether the aid of  helpers is necessary in the delivery of  a particular file,  we need to know whether the demands of  the regular peers are satisfied.  At any point in time, given the full  knowledge of  the peers in the swarm and their link capacities, we can calculate the aggregate upload and download capacities of  the swarm. We observe that in an ideal situation, where there is more aggregate upload capacity in the network than there is aggregate download capacity, there is no room for  further  improvements, as all the peers are downloading as fast  as they could. Therefore,  we use the demand/supply ratio (D/S),  calculated as V  DC D/S  — ~ ^ r e S u l a r P e e r s 1 (3.4) Abigail peers ^ to determine our utilization of  helpers. The use of  the D/S  ratio requires the system to keep additional bookkeep-ing information.  In particular, the tracker maintains the download and upload capacities of  every peer in the swarm in terms of  bits per second. We do not re-quire these estimates to be extremely accurate; information  statically supplied by the users from  their knowledge of  their access links (cable, ADSL, T-3, etc.) is suf-ficient.  In our accounting scheme, we count only the download capacity of  regular peers towards the aggregate download bandwidth. Helpers are excluded from  the tally because through the use of  our rate-limiting mechanism, helpers should exert very little demand on bandwidth. When the tracker notices, during the course of  its operations, that the D/S ratio exceeds an upper threshold r{nv; te, it invites candidates into the swarm as helpers to satisfy  the excess demand. These candidates register themselves with a central, well-known candidates coordinator. It is from  this coordinator that the tracker finds  out about the identities of  these candidates. Once it has obtained such a list of  peers, the tracker contacts the candidates one by one and requests that they join in the delivery of  the file  as a helper. The invitation process stops when the D/S ratio is restored to be below ri nvit e, or when the number of  helpers in the system hits an upper limit. We limit the number of  helpers to be no more than kheiper times the number of  regular peers in the swarm, so as to ensure a minimum representation by regular peers. Conversely, when the D/S ratio falls  below a lower threshold r u n i n v i l e , the tracker can request some of  the helpers already participating in the file  delivery to leave the swarm. While this may have the potential of  reducing the download performance  perceived by regular peers, this mechanism helps to conserve the uti-lization of  helpers, especially at times when they are not overwhelmingly needed. The end result is that the helpers can now offer  their service to other swarms in need. We have designed and conducted a set of  experiments to evaluate the effectiveness of  our helpers mechanism. These experiments were conducted in a simulation environment, and under a variety of  parameter settings and workloads. The results obtained from  these experiments support our hypothesis that helper peers of  our design do indeed make a beneficial  contribution to the performance  of  swarming systems. 4.1 Methodology 4.1.1 Simulation Framework In order to support the simulation of  a large number of  nodes and links under high loads, we developed a custom network simulator based on flow-level  modelling [12], and implemented it in 1500 lines of  C++ For our simulations, we use a simple star topology, with each peer node connected to a central hub via its access link. Our choice of  the star topology is based on the assumption that, in the Internet, the bottlenecks of  swarming are at the access links of  the peers, and not within the core. We refer  to the outgoing and incoming portions of  a node's access link as its uplink and downlink. The fundamental  construct of  our simulator is the notion of  a flow.  Semanti-cally, a flow  is a unidirectional data connection between a source and a destination, and corresponds to an approximation of  one half  of  a bidirectional TCP connec-tion. Packets are transferred  from  the source to the destination through the flow, and each flow  is equipped with a send queue for  packets waiting to be sent. A flow that has no packets in transit is said to be idle. At any particular moment in time, a non-idle flow  is transferring  data at a flow  rate equal to its bandwidth allocation. The bandwidth allocation for  a flow can change with time, and can even change multiple times during the transfer  of  a single packet. In existing flow-level  simulators, the technique of  minimum-share allocation is often  used to allocate bandwidth to flows.  Using this allocation scheme, a node's uplink bandwidth capacity is split into equal bandwidth shares among all the flows that originate at the node. Similarly, a node's downlink bandwidth capacity is split among all flows  terminating at the node. The bandwidth available to a flow  is then the minimum of  its bandwidth shares on the source's uplink and the sink's downlink. This allocation algorithm is run on all the flows  of  a link whenever a flow  is added or removed from  the link. While this allocation technique is adequate for  simulating many scenarios, it falls  short when it comes to simulating nodes with widely varying access link capacities. Let us consider a scenario with three nodes, A, B, and C. Node A has a downlink capacity of  4 Mbps. Node B has an uplink capacity of  1 Mbps, while node C has an uplink capacity of  4 Mbps. We set up two flows  for  this scenario, one running from  B to A, and the other from  C to A. Running the minimum-share allocation algorithm, the flow  from  B to A would receive an alloca-tion of  ^ l ) = 1 Mbps, and the flow  from  C to A would be allocated miniA4Mbjuj = 2Mbps. Note that 1 Mbps worth of  A's downlink capacity lays unused, when with real TCP the flow  from  C to A can comfortably  use that up and run at 3 Mbps. Since we are interested in simulating a heterogeneous mix of access link capacities, such a shortcoming may lead to simulation results that are unnecessarily pessimistic with regards to link utilizations and transfer  rates. function otherSide(flow, link) if (link == flow.sourceUplink) return flow.destDownlink else return flow.sourceUplink function allocateBandwidth(link) for each flow in link.flows otherLink = otherSide(flow, link) flowDetails[flow] = record( theFlow = flow, otherSideFair = otherLink.capacity / otherLink.numFlows, otherSideCurrentMax = flow.allocatedBandwidth + otherLink.unallocatedBandwidth, potential = max(otherSideCurrentMax, otherSideFair)) end sort flowDetails by potential in ascending order remainingCap = link.capacity for (i = 0; i < link.numFlows; i++) share = min(remainingCap / (link.numFlows - i), flowDetails[i].potential) flowDetails[i].theFlow.allocatedBandwidth = min(share, flowDetails[i].otherSideCurrentMax) remainingCap = remainingCap - share end Figure 4.1: Pseudocode for  the maximum-share bandwidth allocation algorithm To ameliorate this situation, we introduce a more refined  allocation algo-rithm, which we call maximum-share allocation. It picks up where minimum-share leaves off,  seeking to put into use any bandwidth capacity left  unallocated by minimum-share. Figure 4.1 lists the pseudocode for  this algorithm. The algorithm starts by calculating the bandwidth potential for  each flow, namely the maximum share that the flow  can obtain from  otherLink, i.e., the link on the other side for  the flow.  This is the maximum of  the equal-split share of  bandwidth on otherLink, and the sum of  the current allocation plus all of  the unallocated slack on otherLink. Then, starting with the flow  with the lowest potential, the algorithm iteratively sets aside a share which is the minimum of  the flow's  potential and the equal split of  the remaining capacity. However, rather than assigning this share directly to the flow,  we limit it to the maximum bandwidth currently achievable on the link on the other side. In the end, the algorithm may potentially leave some slack on the link. This is intentional, as the slack could then be taken up by the flow  later when otherLink runs the algorithm and discovers this usable but unallocated bandwidth on this link. If  we run the maximum-share algorithm on the preceding scenario, we will get the desired result, namely that the flow  from  C to A will be allocated 3 Mbps of bandwidth on both C's uplink and A's downlink. 4.1.2 Evaluation Metrics We summarize the metrics we use to evaluate the effectiveness  and performance  of our helpers mechanism in Table 4.1. As the main objective of  our design is the effective  utilization of  bandwidth resources, especially those provided by helpers, our primary metric for  measuring performance  is that of  aggregate network throughput. In particular, we are inter-ested in the rate at which blocks are delivered to regular peers, which we call useful throughput. In addition, we also record peers' download times, i.e., how long it takes for  a peer to completely download the file.  From the perspective of  peers in real peer-to-peer networks, this is in fact  the most important performance  metric. Moreover, we quantify  the helpers' contribution by measuring, over time, Table 4.1: Evaluation Metrics Metric Short Name Note 1) # blocks delivered to regular peers 2) aggregate download rate of regular peers useful  throughput time deriva-tive of  (1) 3) # blocks delivered to helpers 4) aggregate helper download rate time deriva-tive of  (3) 5) # blocks uploaded by helpers 6) aggregate helper upload rate time deriva-tive of  (5) 7) (# blocks transferred  from helpers to regular peers) - (# blocks transferred  from  regular peers to helpers) cut flow 8) download time for  regular peers q\ aggregate upload rate ' aggregate upload capacity uplink utilization 1 r\\ aggregate download rate ' aggregate download capacity downlink utilization the number of  blocks both downloaded and uploaded by helpers, the utilization levels of  links, as well as the net flow  of  blocks through the cut separating helpers from  regular peers (which we call the cut flow). 4.1.3 Baseline Test Cases In order to get a better sense of  the performance  gains achieved by the addition of  helpers, we set up three baseline cases for  comparison in each of  the scenarios presented. The first  baseline (denoted NoHelpers) is the case where there are no helper nodes in the system, leaving only the initial seed and the regular peers. This represents a base performance  level, upon which the addition of  helpers is expected to make an improvement. The second case (SeedHelpers) is where all the helper nodes join the sys-tem as seeds. This implies that the helpers are maximally equipped to provide blocks wanted by other regular peers. Results obtained for  this case will be a theo-retical limit to the effectiveness  of  the helper mechanism, as seeds are in fact  perfect helpers. The third and final  baseline (FakeHelpers) has regular nodes masquerad-ing as helpers. In other words, this test case is the same as the primary test case with real helpers (denoted Helpers) in all aspects, except with the rate-limiting mechanism turned off.  These fake  helpers will therefore  try to download blocks as fast  as they can. This represents an attempt to improve the performance  perceived by regular peers by simply throwing in more regular peers into the system. 4.2 Experiments 4.2.1 Setup Our swarming system and helpers mechanism are configured  by a number of  pa-rameters, as discussed in Chapter 3 and summarized in the Glossary (Appendix A). For the experiments presented in this section, we have a set of  default  settings for  these parameters, as presented in Table 4.2. These settings will be used for  a particular experiment unless explicitly overriden. The regular peers all connect via asymmetric access links. This makes it likely that the demand for  bandwidth resources will be greater than the supply, and hence making the deployment of helpers worthwhile. We choose to have all nodes complete their downloads, as premature departures would have different  impact on different  but related test cases, rendering it more difficult  to compare results across these cases. A similar motivation is behind the choice of  setting r u n i n v u e to 0. In all of  the experiments, we have configured  the setup such that all the available candidate peers end up being invited to join the swarm as helpers. There-Table 4.2: Default  simulation parameters File size: 128 MB Block size: 256KB Initial seed's link Capacity: Latency: 2Mbps  up, 2Mbps  down 10ms Regular peers' links Capacity: Latency: 200Kbps  up, 2Mbps  down Gaussian distributed, with \i = 50ms, o = 20ms N«: NI: kpenalty  • 0.875 kthres- 0.0001 kupload• 0.6 Treeval  • 30 seconds Duration of  a peer's stay: T minutes after  it completely downloads the file, T exponentially distributed, with A = s mjnntps f  invite • 1.25 "Tuninvite  • 0 khelper• 4 fore,  we talk about the number of  candidates and the number of  helpers inter-changeably. For each experiment in this section, five  separate trials are run with the sim-ulator. In the presentation of  the results, the numbers and data points shown rep-resent average values over the five  runs. An error bar associated with a data point represents the minimum and maximum values, over the five  runs, for  that data point. Error bars are omitted in graphs where the legibility would be reduced by their presence. 4.2.2 A First Scenario: Instantaneous Flash Crowd with Broadband Peers We begin our presentation of  experiments and results with a case study, through which we intend to demonstrate the effectiveness  of  helpers, and to take a closer look at the inner workings of  our helpers mechanism. In this first  scenario, we investigate the ability of  helpers in mitigating the effects  of  a large spike in the number of  requests for  a file  by having all peers join the system simultaneously. Listed in Table 4.3 are the simulation parameters for this scenario. Table 4.3: Simulation parameters for  the first  scenario Arrival of  regular peers instantaneous Number of  regular peers 1000 Number of  helpers 2000 Helpers' links Capacity: Latency: 200Kbps up, 2Mbps down Gaussian distributed, with p = 50ms, a = 20ms For this experiment, we have 1000 peers joining the swarm at t = Is. As well, we have 2000 helpers on hand ready to be added to the swarm. These helpers are connected by asymmetric access links, each with an upload capacity of  200Kbps and download capacity of  2Mbps. In total, they could provide up to an additional 400Mbps of  upload capacity to the swarm. Figures 4.2 and 4.3 respectively show the number of  blocks received by reg-ular peers over time and the corresponding useful  throughput. As we can see, the line for  our primary test case with real helpers, identified  as Helpers, falls  be-tween the lines for  NoHelpers and SeedHelpers in both graphs. This signifies  that the helpers indeed made a positive contribution to the swarm by allowing regular peers to download blocks at a faster  rate. Examining Figure 4.3 more closely, we find  that the useful  throughput achieved by Helpers is around 400Mbps, and is 200Mbps more than the useful  throughput in NoHelpers. Out of  the 400Mbps made available by the helpers, it turns out that half  of  it is contributed to the ben-efit  of  regular peers. The remaining 200Mbps goes to support the helpers' own acquisition of  blocks. Time (seconds) Figure 4.2: Total number of  blocks transferred  to regular peers Time (seconds) Figure 4.3: Useful  throughput levels We also note that the line for  FakeHelpers in both graphs falls  below that of  NoHelpers, confirming  our expectation that the addition of  untuned regular peers can potentially drain resources away from  serving those peers that actually Time (seconds) Figure 4.4: Cut flow  levels want the file.  To confirm  this, we plot the outflow  for  Helpers and FakeHelpers in Figure 4.4, where we define  the cut flow  to be the number of  blocks transferred from  helpers to regular peers, minus the number of  blocks transferred  from  regular peers to helpers. Whereas the cut flow  for  Helpers grows as time progresses, the cut flow  for  FakeHelpers remains in negative territory throughout the entire sim-ulation, and is in fact  decreasing for  the majority of  the time. That means there are more blocks transferred  from  regular peers to the fake  helpers than blocks trans-ferred  in the opposite direction, representing a net loss to the regular peers as a whole. From the end user's point of  view, perhaps nothing matters more than how long it takes for  the download to complete. In Table 4.4, we summarize the average download times obtained in the primary test case Helpers and in the baseline cases NoHelpers, SeedHelpers, and FakeHelpers. Through their participation, the helpers are able to reduce the average down-load time of  regular peers by 1997 seconds. On the other hand, the fake  helpers Table 4.4: Average download times for  the first  scenario Test case SeedHelpers Helpers NoHelpers FakeHelpers Average download time 1772s 3443s 5540s 5817s Speed-up relative to NoHelpers 3.126 1.609 1 0.952 Time (seconds) Figure 4.5: Total number of  blocks transferred  to helpers of  FakeHelpers worsened the performance  for  everyone, increasing the average download time by 277 seconds. We have seen thus far  that the rate limiting mechanism in helpers has differ-entiated them from  the fake  helpers of  FakeHelpers and has succeeded in making it possible for  helpers to truly help out. To better understand what this mecha-nism does, we plot the number of  blocks downloaded by helpers and fake  helpers over time and the corresponding throughput in Figures 4.5 and 4.6. In between the ramp-up and ramp-down periods of  the system, namely in the time interval t = 1500s — 2500s, the download rate of  helpers is a mere 40% of  the download rate of  the fake  helpers. 500 400 -E 300 3 0 •O m 1 200 100 3000 4000 Time (seconds) 5000 7000 Figure 4.6: Aggregate helper download rate -a m o ra ra 0) Helpers FakeHelpers SeedHelpers 3000 4000 Time (seconds) 5000 6000 7000 Figure 4.7: Aggregate helper upload rate Figure 4.7 shows the aggregate upload rate of  all the helpers in Helpers. Comparing this graph with the download rate shown in Figure 4.6, we observe that the download rate during the stable period of  t = 1500s — 2500s is about 40% of the upload rate. In other words, every block downloaded by a helper is uploaded 2.5 times on average, which is close to our target upload factor  of  ku p io ad • = 0.6 • 5 = 3. 4.2.3 Varying Arrival Rates Our first  scenario focussed  upon an instantaneous flash  crowd. In order to more closely model the dynamics of  a real flash  crowd, we have also conducted tests where peers join the swarm one at a time at particular arrival rates. We summarize the setup for  these simulations in Table 4.5. Table 4.5: Simulation parameters for  varying arrival rates Arrival of  regular peers governed by Poisson process Expected arrival rate 10/minute 20/minute 40/minute Time interval of  arrivals from  t = 0s to t = 10000s Number of  regular peers 1675 3341 6719 Number of  helpers 2000 Helpers' links Capacity: Latency: 200Kbps up, 2Mbps down Gaussian distributed, with p = 50ms, a = 20ms As in the previous section, we are interested in comparing the performance of  our helpers-enabled swarming system with the baseline cases. For this compari-son, we focus  our attention to the scenario where the arrival rate is 20 regular peers per minute. In Figure 4.8, we observe that our swarm with 2000 helpers (indicated by Helpers) is able to deliver close to the same number of  blocks to regular peers as the swarm with 2001 seeds (indicated by SeedHelpers), especially after  a warm-up period in the first  4000s. The useful  throughput graph in Figure 4.9 confirms that both swarms achieve virtually identical performance  after  t = 4000s. In contrast, FakeHelpers's swarm with fake  helpers performs  poorly in the CD 1.8e+06 1.6e+06 1,4e+06 1.2e+06 1e+06 800000 600000 400000 200000 0 Helpers FakeHelpers NoHelpers SeedHelpers 2000 4000 6000 8000 10000 12000 14000 Time (seconds) Figure 4.8: Total number of  blocks transferred  to regular peers Helpers FakeHelpers • NoHelpers ° SeedHelpers 4 2000 4000 6000 8000 10000 12000 14000 Time (seconds) Figure 4.9: Useful  throughput levels first  6000s, lagging behind the NoHelpers baseline in terms of  number of  blocks delivered to regular peers. Past t = 6000s, however, it starts to pick up the pace, and ultimately by t = 8000s, it is able to catch up to the SeedHelpers baseline and 1.2e+06 i Helpers « FakeHelpers o 1e+06 800000 o 600000 m * 400000 200000 0 0 2000 4000 6000 8000 10000 12000 Time (seconds) Figure 4.10: Total number of  blocks transferred  to helpers surpasses our helpers-enabled swarm. Looking at it in a different  perspective, we observe in Figure 4.9 that FakeHelpers is able to sustain a higher useful  through-put than the other three cases after  t = 6000s. To help see why this is the case, let us further  investigate the performance  characteristics of  the swarm in FakeHelpers. Figure 4.10 plots the number of  blocks delivered to the helpers of  Helpers and the fake  helpers of  FakeHelpers. In it, we can see that by t = 6000s, most of the fake  helpers of  FakeHelpers have downloaded the entire file  and have become seeds. The subsequent graph (Figure 4.11) then displays, for  FakeHelpers, the respective aggregate download rates for  regular peers and fake  helpers, as well as the total upload capacity of  the swarm. Indeed, past t = 6000s, the download rate of  the fake  helpers falls  off  rapidly, and the entire swarm's upload capacity is then devoted to serving regular peers. This accounts for  the spike in performance originally observed in Figure 4.8. Coming to the metric of  download times, we see from  the graphs in Fig-ures 4.12 and 4.13 that helpers are able to lower the download time for  the peers Time (seconds) Figure 4.11: Aggregate download rates and total upload capacity Start Time (seconds) Figure 4.12: Time of  download completion vs. start time that join the swarm early. The first  completions occur just before  t = 4000s, and after  that peers complete their downloads in about 1500s. On the other hand, while the fake  helpers do contribute to lower download times, the first  download com-10000 9000 8000 7000 6000 5000 4000 3000 2000 1000 0 Helpers + FakeHelpers x NoHelpers * V SeedHelpers • / " " " " " - • u " L, B ) 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Start Time (seconds) Figure 4.13: Download time vs. start time pletions occur only after  t = 6000s, and not until t = 8000s do peers begin to complete in 1500s. Thus, we have shown that our rate-limiting mechanism is suc-cessful  in enabling helpers to mitigate the effects  of  flash  crowds early on. o m * 3.5e+06 3e+06 -2.5e+06 -2e+06 1.5e+06 -1e+06 -500000 • x 10 peers/min - Helpers • 10 peers/min - FakeHelpers o 20 peers/min - Helpers 4 20 peers/min - FakeHelpers v 40 peers/min - Helpers « 40 peers/min - FakeHelpers 4000 6000 8000 Time (seconds) 10000 12000 Figure 4.14: Total number of  blocks transferred  to regular peers Time (seconds) Figure 4.15: Useful  throughput levels To study the effects  of  different  arrival rates, we also ran our experiments for the arrival rates of  10 and 40 peers per minute (in addition to the aforementioned case of  20 peers per minute). Our plots of  the throughput levels in Figures 4.14 and 4.15 show that our helpers mechanism behaves consistently across different  arrival rates, modulo a scaling factor  due to the difference  in the number of  peers in the swarm. As with the instantaneous arrival scenario of  the previous section, we see in Figure 4.16 that our helpers (on asymmetric access links) are able to attain good levels of  cut flow,  while the fake  helpers of  FakeHelpers trail behind substantially for  all arrival rates. Figure 4.17 presents the aggregate upload and download rates of  the helpers in the three scenarios. As the arrival rate increases, the aggregate upload rate of  the 2000 helpers also increases, while the aggregate download rate decreases. To see why this is the case, we note that each helper halts downloading further  blocks as long as its has a certain number of  unfulfilled  blocks. With a higher arrival rate comes a higher connection request rate for  each helper. In turn, due to the Time (seconds) Figure 4.16: Cut flow  levels 5 to 2? •o id o c S o •o a o CL Z} V Time (seconds) Figure 4.17: Aggregate upload and download rates of  the helpers connection selection algorithm, each helper is more likely to be connected more often  to peers with very few  blocks in common with the helper. First of  all, this means that the helper would have more to offer  to its sinks, reducing connection idle times. At the same time, the helper would be able to upload more fulfilled blocks to its sinks, slowing down the delisting of unfulfilled blocks, and ultimately reducing the rate at which the helper downloads new blocks. Therefore, a higher arrival rate actually improves the operational efficiency of the helpers mechanism. 4.2.4 Varying Helpers' Bandwidth Characteristics Having shown that our helpers mechanism is effective in enabling peers on asym-metric access links to lend help to a swarm, we now explore the implications of having well-endowed helpers connected to the network via fast, symmetric access links. In particular, it remains to be seen whether the rate-limiting nature of our mechanism is suitable for these symmetric links, where there is less of a need to throttle a helper's download rate to be no higher than its upload rate. The configu-rations of our experiments are listed in Table 4.6. Here, we use scenarios involving instantaneous as well as phased arrivals. With regards to the helpers, the three cases are: 1) all on asymmetric links, 2) all on symmetric links, and 3) half asym-metric, half symmetric links. In all these scenarios, the number of helpers is chosen such that the helpers' aggregate upload capacity is fixed at 400Mbps. As the relative proportion of helpers on symmetric links increases, the through-put levels of the FakeHelpers baseline come closer to those of the helpers-enabled Helpers. This result is shown in Figures 4.18(a) and 4.18(b) for the simultaneous arrival scenarios, and in Figures 4.19(a) and 4.19(b) for the phased arrival scenarios. At the extreme of having all helpers on symmetric links, the fake helpers of Fake-Helpers can perform just as well as the helpers, but never significantly exceeding the performance of real helpers. Even though the rate-limiting mechanism may seem restrictive for symmetric links, it nonetheless does not hamper the helpers on such links from effectively utilizing their upload capacities in serving other peers. Indeed, as Figures 4.20 and 4.21 show, the rate-limiting mechanism con-tinues to function according to its design, slowing down the helpers' download Table 4.6: Simulation parameters for varying the mix of helpers Arrival of regular peers governed by Poisson process instantaneous Expected arrival rate 20/ minute — Time interval of arrivals from t = 0s to t = 10000s — Number of regular peers 3341 1000 Number of helpers 2000 asym. 200 sym. 1000 asym., 100 sym. 2000 asym. 200 sym. 1000 asym., 100 sym. Helpers' links Asymmetric Capacity: Latency: Symmetric Capacity: Latency: 200Kbps  up, 2Mbps  down Gaussian distributed, with p, = 50ms, a = 20ms 2Mbps  up, 2Mbps  down Gaussian distributed, with p, = 50ms, a = 20ms 800000 700000 600000 500000 W O 400000 m * 300000 200000 100000 -1 1 1 1 . all asym. links - Helpers all asym. links - FakeHelpers ® half sym./asym. - Helpers » half sym./asym. - FakeHelpers » all sym. links - Helpers all sym. links - FakeHelpers o. si CD D O (D ui 800 700 600 500 400 300 200 100 —i 1 1 1 1— all asym. links - Helpers i all asym. links - FakeHelpers half sym./asym. - Helpers half sym./asym. - FakeHelpers all sym. links - Helpers all sym. links - FakeHelpers 1000 2000 3000 4000 5000 6000 Time (seconds) 0 1000 2000 3000 4000 5000 6000 Time (seconds) (a) # blocks transferred  to regular peers (b) Useful  throughput levels Figure 4.18: System throughput results for instantaneous arrival scenarios o CD * 2e+06 1.5e+06 1e+06 500000 —i 1 1 1 1 : all asym. links - Helpers ' all asym. links - FakeHelpers > half sym./asym. - Helpers • half sym./asym. - FakeHelpers • all sym. links - Helpers • all sym. links - FakeHelpers 0 2000 4000 6000 80001000012000 Time (seconds) 200 1 1 1 1 1— x all asym. links - Helpers o all asym. links - FakeHelpers ° half sym./asym. - Helpers * half sym./asym. - FakeHelpers * all sym. links - Helpers * all sym. links - FakeHelpers •> 600 -400 0 2000 4000 6000 8000 1000012000 Time (seconds) (a) # blocks transferred  to regular peers (b) Useful  throughput levels Figure 4.19: System throughput results for phased arrival scenarios 1,4e+06 1.2e+06 1e+06 CO o o 800000 in » 600000 400000 200000 x all asym. links - Helpers a all asym. links - FakeHelpers ° half sym./asym. - Helpers » half sym./asym. - FakeHelpers-» all sym. links - Helpers • all sym. links - FakeHelpers •o <0 o c 3 o •o o ro o> £ a> 700 600 500 400 300 200 100 i i i i i all asym. links - Helpers all asym. links - FakeHelpers o half sym./asym. - Helpers . » half sym./asym. - FakeHelpers » all sym. links - Helpers all sym. links - FakeHelpers 1000 2000 3000 4000 5000 6000 Time (seconds) 0 1000 2000 3000 4000 5000 6000 Time (seconds) (a) # blocks transferred  to helpers (b) Aggregate helper download rate Figure 4.20: Helper efficiency results for instantaneous arrival scenarios 1.6e+06 1.4e+06 1,2e+06 1e+06 -o 800000 CD 600000 400000 » all asym. links - Helpers o all asym. links - FakeHelpers ° half sym./asym. - Helpers * half sym./asym. - FakeHelpers » all sym. links - Helpers ® all sym. links - FakeHelpers 2 0 0 0 0 0 -.o 5 5 o •D 600 500 400 • 300 200 100 1 1 1 1 1— x all asym. links - Helpers a all asym. links - FakeHelpers ° half sym./asym. - Helpers » half sym./asym. - FakeHelpers * all sym. links - Helpers • all sym. links - FakeHelpers 2000 4000 6000 80001000012000 Time (seconds) (a) # blocks transferred  to helpers 0 2000 4000 6000 8000 10000 12000 Time (seconds) (b) Aggregate helper download rate Figure 4.21: Helper efficiency results for phased arrival scenarios progress appropriately regardless of their link capacities. 4.2.5 Varying the Number of  Helpers In the previous sections, we have investigated the performance of our mechanism in settings with various arrival rates and different mixes of helper capabilities. From these scenarios, we pick four representatives, as listed in Table 4.7 to form a test suite. To facilitate communication, these scenarios will be referred to by their names, i.e., sym,2o, asym20, sym^ and asym^. We will be using this test suite to evaluate the effects of other simulation parameters. One parameter we are interested in is the number of helpers in the sys-tem. As we have seen in Section 4.2.3, an increase in the peer arrival rate makes the helpers function more efficiently by providing more blocks while download-ing less. We should note that the higher the arrival rate, the higher the number of active peers in the swarm. Therefore, there is potentially a more fundamental explanation to the increased helper efficiency, namely that there is a link between Table 4.7: Simulation parameters for the test suite Name syrn2 o asym2 o sym oo asyrrioo Arrival of regular peers governed by Poisson process instantaneous Expected arrival rate 20/minute — Time interval of arrivals from t = 0s to t = 10000s — Number of regular peers 3341 1000 Number of helpers 200 sym. 2000 asym. 200 sym. 2000 asym. Helpers' links Asymmetric Capacity: Latency: Symmetric Capacity: Latency: 200Kbps up, 2Mbps down Gaussian distributed, with p — 50ms, a = 20ms 2Mbps up, 2Mbps down Gaussian distributed, with p = 50ms, a = 20ms the relative proportions of helpers and regular peers in a swarm and the efficiency of the helpers. To validate this hypothesis, we ran the four scenarios in the test suite with fewer helpers, at levels that are 3/4, 1/2 and 1/4 of the original number of helpers (see Table 4.8). In other words, these experiments are run with aggregate helper upload capacities of 300, 200, and 100Mbps. Table 4.8: Simulation parameters for varying the number of helpers Test suite scenarios asym2o, asyrrioo sym20, syrrioo Number of helpers 500 1000 1500 50 10 150 In order to compare results across different experiments with varying num-bers of helpers, we examine the uplink and downlink utilization levels of helpers and regular peers. The uplink utilization of a set of peers is defined to be their ag-gregate upload throughput divided by their aggregate upload capacity, and the <0 O) <j> D> 2 asymM - 500 helpers asymM -1000 helpers asymM -1500 helpers asymM - 2000 helpers 1000 2000 3000 4000 Time (seconds) (a) asyrrioo 5000 1.4 1.2 1 0.8 0.6 0.4 0.2 • symM - 50 helpers x symM -100 helpers m symM -150 helpers a sym„ - 200 helpers 1000 2000 3000 4000 Time (seconds) (b) symoo 5000 Q. a> asym20 - 500 helpers asym20 - 1000 helpers asym20 - 1500 helpers asym20 - 2000 helpers 3000 6000 9000 12000 15000 Time (seconds) (c) asym20 * sym20 - 50 helpers x sym20 - 100 helpers » sym20 - 150 helpers • sym20 - 200 helpers 3000 6000 9000 12000 15000 Time (seconds) (d) sym2o Figure 4.22: Uplink utilization of helpers downlink utilization of a set of peers is defined likewise. From Figure 4.22, we see that while the helpers are able to achieve high levels of uplink utilization regardless of the number of helpers in the swarm, there is in fact a small decrease in uplink utilization as the number of helpers increases. asym, asym, asym, asym, asym, , - 500 helpers 1000 helpers , -1500 helpers , - 2000 helpers • 0 helpers T3 o 13 1000 2000 3000 4000 5000 6000 Time (seconds) 1.4 1.2 1 0.8 0.6 0.4 0.2 0 symc sym, sym, sym, sym. , - 50 helpers , -100 helpers , -150 helpers , - 200 helpers , - 0 helpers 1000 2000 3000 4000 5000 6000 Time (seconds) (a) asyrtioo (b) syrrioo 1.4 1.2 1 0.8 0.6 0.4 0.2 + asym20 - 5d0 helpers x asym20 - 1000 helpers » asym20 - 1500 helpers • asym20 - 2000 helpers • asym20 - 0 helpers c 5 o TJ 3000 6000 9000 12000 15000 Time (seconds) 3000 6000 9000 12000 15000 Time (seconds) (c) asym2o (d) sym2o Figure 4.23: Downlink utilization of regular peers Therefore, a small group of helpers in a big swarm can be just as effectively utilized as a larger group of helpers in a smaller swarm. At the same time, the benefit of having helpers grows with the number of helpers, as demonstrated in Figure 4.23 by the proportionate increase in the downlink utilization levels of regular peers in all four test-suite scenarios. 4.2.6 Varying kthres As outlined in Section 3.3.2, the helpers mechanism is configured by two main pa-rameters, namely kthres and kupioad. In order to better understand the effects each of these parameters have on the operation and performance of our mechanism, we simulated the four test-suite scenarios again with varying values for these param-eters. In the first set of experiments, we held the kupioad value fixed at our default value, and varied the value kthres (see Table 4.9). Table 4.9: Simulation parameters for varying kthres Test suite scenarios sym2o, asym2o, sym,asym kthres 0.0002 0.0001 0.00005 600 Q. JD 5 CL - C o> o ® W 1000 2000 3000 4000 5000 Time (seconds) 2000 4000 6000 8000 10000 12000 Time (seconds) (a) asyrrioo (b) asym20 Figure 4.24: Useful throughput levels for scenarios with helpers on asymmetric links The useful throughput levels for the scenarios asymand asym^o are shown in Figure 4.24. They show that, for both scenarios, the useful throughput levels in-crease as kthres decreases. This is in line with the intuition that limiting the down-load rates of helpers on asymmetric links is crucial to the efficiency of the helpers mechanism. The larger the value of k t h T e s , the longer a helper stays in its initial ramp-up mode where its download rate is unrestricted, and the more bandwidth resources the helper takes away from the rest of the swarm. Time (seconds) Time (seconds) (a) asyrrioo  (b) asym20 Figure 4.25: Aggregate helper download rates for scenarios with helpers on asym-metric links Figure 4.25 plots the aggregate download rate of the helpers. These results confirm that a lower kthres value translates to lower helper download rates. In the other two scenarios syru^ and sym20, the situation is reversed. From Figures 4.26 and 4.27, we learn that both the useful throughput levels and the cut flow levels decrease as kthres decreases. This is due to the fact that a lower kthres means that the helpers go into the rate-limiting mode sooner. For helpers on sym-metric links, overly restricting their download rates has the consequence of not allowing them to download a wide enough selection of blocks early on for their 500 1000 1500 2000 2500 3000 3500 Time (seconds) x k t h r e s = 0.0002 ° kthres = 0 0 0 0 1 » k , h „ . = 0.00005 0 2000 4000 6000 8000 10000 12000 Time (seconds) (a) syrrioo (b) sym20 Figure 4.26: Useful throughput levels for scenarios with helpers on symmetric links Q. •Q 5 <1 3 o •o <0 o> < 700 600 500 400 300 200 100 0 kthres = 0 0 ° 0 2 kthres = 0 0 0 0 1 kthres = °-°°005 t CL . Q 5 3 o •o <D 500 1000 1500 2000 2500 3000 3500 Time (seconds) (a) sym kthres ~ 9 "9 0 0 ^ kthres = 0 0 0 0 1 kthres = 0 0 0 0 ° 5 2000 4000 6000 8000 10000 12000 Time (seconds) (b) sym20 Figure 4.27: Aggregate helper download rates for scenarios with helpers on sym-metric links many sinks to request, causing many of the helpers' upload connections to unnec-essarily go idle. From these results, we conclude that there is room for improvement in our setting for the threshold value TA,  currently set to kthres • UCA•  In particular, the efficiency of helpers could be improved by further lowering TA  when the upload capacity UCA  is low, and further increasing TA  when UCA  is high. Potential so-lutions for achieving this include using a linear function in UCA with a negative y-intercept, and using a higher-order function. 4.2.7 Varying kupioad Having seen and analyzed the effects of changing the value of kthres, we com-plete our study on the rate-limiting equation by focussing on the effects of vary-ing kupioa(i. We conducted a set of experiments where we hold kthres constant at its default value, and let k u p i o a d  range from 0.2 to 0.8 (see Table 4.10). In other words, each block downloaded by a helper must be uploaded on 20% to 80% of its outgoing connections before being taken off the list of unfulfilled blocks. Table 4.10: Simulation parameters for varying k u p i o a d Test suite scenarios sym2o, asym2o, symasym^ kupioad 0.2 0.4 0.6 0.8 As the results in Figures 4.28 and 4.29 show, a higher value of kupioad has the effect of lowering the download rates on helpers. Therefore, for the scenarios where having lower helper download rates is important, namely those involving helpers on asymmetric links, the useful throughput levels do indeed increase with kupioad-On the other hand, varying the value of k u p i o a d  has a less pronounced effect on the useful throughput levels for the scenarios sym^ and sym2o involving helpers on symmetric links. 600 500 400 300 200 1 0 0 -1000 2000 3000 4000 Time (seconds) 5000 450 400 • 350 3 o "O x u^pload -° Upload = 0-4 0 u^pload = 0-° 1000 2000 3000 4000 Time (seconds) 5000 (a) asym00 - Useful  throughput (b) asynioo - Aggregate helper down-load rate 600 500 400 300 200 100 Kjpload ~ 0-2 u^pload ~ "upload = 0-6 Kupload ~ u a 300 250 200 u^pload -u^pload -u^pload : 0-O Kupload - u 0 0 2000 4000 6000 8000 10000 12000 Time (seconds) 0 2000 4000 6000 8000 10000 12000 Time (seconds) (c) asyrri2o - Useful  throughput (d) asym^o - Aggregate helper down-load rate Figure 4.28: Useful throughput levels and aggreate helper download rates for sce-narios with helpers on asymmetric links 700 6 0 0 • 500 400 300 200 100 140 120 100 0 500 1000 1500 2000 2500 3000 3500 Time (seconds) 0 500 1000 1500 2000 2500 3000 3500 Time (seconds) (a) syrrioo - Useful  throughput (b) syrrioo - Aggregate helper down-load rate Time (seconds) Time (seconds) (c) sym2o - Useful throughput (d) sym2o - Aggregate helper down-load rate Figure 4.29: Useful throughput levels and aggreate helper download rates for sce-narios with helpers on symmetric links 4.2.8 Summary We have now shown that our helpers mechanism succeeds in effectively utilizing the bandwidth resources of helpers in a wide variety of scenarios. In Section 4.2.2, we saw that helpers on asymmetric links are able to provide significant benefits in the case where a flash crowd arrives at an instant, by increasing useful through-put levels and lowering download times. On the other hand, the unregulated fake helpers of the corresponding FakeHelpers setup actually drain bandwidth re-sources away from regular peers, lowering the useful throughput levels and slow-ing down all downloads. As the only difference between the Helpers and Fake-Helpers setups is our adaptive rate-limiting mechanism, these contrasting results demonstrated the importance of this mechanism in making helpers work. We explored the effects of having peers arrive one at a time, with various arrival rates, in Section 4.2.3. In those scenarios, our helpers are able to increase the useful throughput levels early on, and very quickly get to a point where they are operating almost as efficiently as the fully-seeded helpers of SeedHelpers. Once again, the fake helpers take much longer to arrive at a comparable level of effi-ciency. We varied the bandwidth characteristics of helpers in Section 4.2.4. The sce-narios involved different mixes of helpers on symmetric and asymmetric access links. The results showed that our adaptive rate-limiting mechanism does not hin-der those helpers that are able to upload as fast as they can download. In Section 4.2.5, we varied the number of helpers in the swarms, and found that helpers are able to put their uplink capacities into good use regardless of the number of helpers. In fact, the helpers' efficiency increases slightly as the number of helpers decreases. For our final two sets of experiments, we configured our helpers mecha-nism with different values of the parameters kthres and kupioari. The results in Sec-tion 4.2.6 showed that a higher value of kthres is beneficial for helpers with well-endowed uplinks, while the reverse is true for helpers with slow uplinks. There-fore, there is room for improvement in our current setting of the threshold value TA  by the simple equation of TA  = KTHRES  • UCA•  In Section 4.2.7, we found that increasing the value of kupioad lowers the download rates of helpers while improv-ing the useful throughput levels. This measure is especially effective for helpers on asymmetric access links. Conclusion and Future Work 5.1 Conclusion In the client-server model predominant in today's Internet, the load on a server has a significant impact on the level of service perceived by its clients. In particu-lar, given that a server is connected to its clients via an access link of finite capacity, the data transfer rate to each of its clients drops inversely as the number of clients served by the server. This limitation significantly hampers the scalability of such a setup, especially when long-lived connections are involved in the transfer of large files. If such a high load can be anticipated in advance, it is possible to alleviate this problem by provisioning additional upload capacity. However, it is now common-place for a particular piece of content on the Internet to experience a sudden spike in popularity and hence also in request rate, only to have the number of requests returning to normal levels in a few hours or a few days' time. Such an occurrence, called a "flash crowd" in Internet parlance, is difficult to address via adjusting the provisioning level alone, as it may come and go so quickly for administrative ac-tions to be taken. Moreover, the operators of the server may not have the financial means to scale up the bandwidth of their access link. To mitigate the problem of the flash crowd, many solutions have been de-veloped, some involving the service provided by additional servers from around the world (mirrors and CDNs), while others involving the cooperation and collab-oration of the clients themselves. In this thesis, we explored the space of collabo-rative solutions, and found that existing systems, such as multicast streaming and swarming, are often able to adequately deliver large amounts of content to partic-ipating peers in a scalable way. However, these systems use a tit-fot-tat notion of fairness, and thus are not well-suited for harnessing the bandwidth resources of idle peers that are willing to contribute. Leveraging some insights in the helpful nature of interior nodes in multicast trees, we have developed a novel augmented swarming system that allows peers to contribute their bandwidth resources even when they are not interested in the content being disseminated in the swarm. Our design consists of a helpers mecha-nism which ensures that a helper's participation in a swarm is always to the benefit of others. It achieves this objective by employing an adaptive rate-limiting mecha-nism, so that the helper is able to maximize its uplink utilization while download-ing as little and as slowly as possible. For our evaluation, we have run a diverse set of experiments, testing the helpers mechanism under a variety of conditions, including varying arrival rates, varying numbers of and provisioning levels of helpers, and different parameter setttings of the mechanism itself. The experiments were run on a flow-level simu-lator of our own design, whose strength lies in its ability to deal with heterogeneous mixes of link capacities. Our results show that helpers are effective in contributing their bandwidth resources under all circumstances, and always perform at a level comparable to, and often much better than, the naive addition of untuned peers to the swarm. Using our framework, a content provider would be able to invite additional helpers into its swarm to aid in the handling the increased load from a flash crowd. At the same time, the flexibility of the helpers mechanism enables the development of a peer-to-peer content delivery infrastructure where the peers always have the ability and opportunity to contribute, regardless of whether or not these peers are actively downloading content of their own desires. 5.2 Future Work With regards to our helpers mechanism, we have identified four directions for fu-ture work. First, there is room to further improve the efficiency of helpers by fine-tuning the relevant parameters such as kthres and kupioafi.  In addition, it would be interesting to study how well the idea of rate-limited helpers would work in an existing system such as BitTorrent, where connection evaluations are made pri-marily based on the attained transfer rate on each connection. Thirdly, we would like to broaden our scope and investigate how our mechanism performs within other possible swarming systems as outlined in our taxonomy, such as ones where peers could be located based on which portions of the content they contain. For example, a group of helpers may each contain a different portion of a file, and the group management mechanism (e.g., a tracker or a DHT substrate) would then be able to direct a peer to the appropriate helpers depending on which blocks it is missing. Finally, we would like to perform our evaluations again in an emulation framework to obtain results which would better represent real-world performance. Our helpers, by definition, find no value in the content that they help to transfer. An interesting open issue related to this is the design of a suitable incen-tive mechanism or peer-to-peer economy for rewarding helpers for their contribu-tions. Such a mechanism must be able to resist attacks and cheating attempts from individual malicious nodes as well as nodes in collusion. Since a helper is often able to effectively utilize its upload capacity while having only slowly downloaded a few blocks, one may consider fixing a hard limit on the number of blocks a helper would cache at any point in time. Interesting issues arising from such a restriction includes the decision of which blocks to evict when the cache is full, and the corresponding effect on the helper's uplink uti-lization. Going further down this track, a helper handling multiple files simul-taneously could dynamically change the limits on the per-file caches to adapt to changes in the relative popularity of these files. Strategies for doing so must take into account the block-eviction policy adopted. Bibliography [1] Akamai, http://www.akamai.com. [2] Ernst W. Biersack, Pablo Rodriguez, and Pascal Felber. Performance analysis of peer-to-peer networks for file distribution. In Proceedings of  the Fifth  Inter-national Workshop  on Quality of  Future Internet Services (QofIS'04),  September 2004. [3] John Byers, Jeffrey Considine, Michael Mitzenmacher, and Stanislav Rost. In-formed content delivery across adaptive overlay networks. In Proceedings of the 2002 Conference  on Applications, Technologies,  Architectures, and Protocols for Computer Communications (ACM  SIGCOMM 2002), pages 47-60. ACM Press, 2002. [4] John W. Byers, Michael Luby, Michael Mitzenmacher, and Ashutosh Rege. A digital fountain approach to reliable distribution of bulk data. SIGCOMM Comput. Commun. Rev., 28(4):56-67,1998. [5] Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, Animesh Nandi, Antony Rowstron, and Atul Singh. SplitStream: high-bandwidth multicast in cooperative environments. In Proceedings of  the Nineteenth ACM Symposium on Operating Systems Principles (SOSP 2003), pages 298-313. ACM Press, Octo-ber 2003. [6] Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, and Antony Row-stron. Scribe: A large-scale and decentralized application-level multicast in-frastructure. IEEE Journal  on Selected Areas in Communication (JSAC),  20(8), October 2002. [7] Miguel Castro, Michael B. Jones, Anne-Marie Kermarrec, Antony Rowstron, Marvin Theimer, Helen Wang, and Alec Wolman. An evaluation of scalable application-level multicast built using peer-to-peer overlays. In Infocom'03, April 2003. [8] Anawat Chankhunthod, Peter B. Danzig, Chuck Neerdaels, Michael F. Schwartz, and Kurt J. Worrell. A hierarchical internet object cache. In USENIX Annual Technical Conference,  pages 153-164,1996. [9] Bram Cohen. Incentives build robustness in BitTorrent. In 1st Workshop  on Economics of  Peer-to-Peer Systems, June 2003. [10] Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. Summary cache: a scalable wide-area Web cache sharing protocol. IEEE/ACM  Transactions  on Networking,  8(3):281-293, 2000. [11] Pascal A. Felber and Ernst W. Biersack. Self-scaling networks for content dis-tribution. In Proceedings of  the International Workshop  on Self-*  Properties in Com-plex Information  Systems (Self-*),  May 2004. [12] TJ Giuli and Mary Baker. Narses: A scalable flow-based network simulator, 2003. [13] Digital Island, http://www.digitalisland.com. [14] Sitaram Iyer, Antony Rowstron, and Peter Druschel. Squirrel: A decentralized peer-to-peer web cache. In 12th ACM Symposium on Principles of  Distributed Computing (PODC 2002), July 2002. [15] M. Izal, G. Urvoy-Keller, E.W. Biersack, P. Felber, A. Al Hamra,, and L. Garces-Erice. Dissecting BitTorrent: Five months in a torrent's lifetime. In Proceedings of  Passive and Active Measurements 2004, April 2004. [16] Dejan Kostic, Adolfo Rodriguez, Jeannie Albrecht, and Amin Vahdat. Bullet: High bandwidth data dissemination using an overlay mesh. In Proceedings of  the Nineteenth ACM Symposium on Operating Systems Principles (SOSP 2003), pages 282-297. ACM Press, October 2003. [17] Petar Maymounkov and David Mazieres. Rateless codes and big downloads. In Proceedings of  the 2nd International Workshop  on Peer-to-Peer Systems (IPTPS 2003), 2003. [18] Jochen Mundinger and Richard R. Weber. Efficient file dissemination using peer-to-peer technology. Technical Report 2004-01, University of Cambridge Statistical Laboratory, 2004. [19] Venkata N. Padmanabhan and Kunwadee Sripanidkulchai. The case for co-operative networking. In Revised Papers from  the First International Workshop  on Peer-to-Peer Systems, pages 178-190. Springer-Verlag, 2002. [20] Venkata N. Padmanabhan, Helen J. Wang, and Philip A. Chou. Resilient peer-to-peer streaming. In Proceedings of  the 11th IEEE International Conference  on Network Protocols, page 16. IEEE Computer Society, 2003. [21] J. A. Pouwelse, P. Garbacki, D. H. J. Epema, and H. J. Sips. A measurement study of the BitTorrent peer-to-peer file-sharing system. Technical Report PDS-2004-007, Delft University of Technology, April 2004. [22] Dongyu Qiu and R. Srikant. Modeling and performance analysis of BitTorrent-like peer-to-peer networks. In Proceedings of  the 2004 Conference  on Applications, Technologies,  Architectures, and Protocols for  Computer Communica-tions (ACM  SIGCOMM 2004), pages 367-378. ACM Press, 2004. [23] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Schenker. A scalable content-addressable network. In Proceedings of  the 2001 Conference  on Applications, Technologies,  Architectures, and Protocols for  Computer Communications (ACM  SIGCOMM 2001), pages 161-172. ACM Press, 2001. [24] Antony Rowstron and Peter Druschel. Pastry: Scalable, distributed object lo-cation and routing for large-scale peer-to-peer systems. In IFIP/ACM  Interna-tional Conference  on Distributed Systems Platforms  (Middleware),  pages 329-350, November 2001. [25] Antony Rowstron, Anne-Marie Kermarrec, Miguel Castro, and Peter Dr-uschel. Scribe: The design of a large-scale event notification infrastructure. In Jon Crowcroft and Markus Hofmann, editors, Networked Group Communica-tion, Third  International COST264 Workshop  (NGC'2001),  volume 2233 of Lecture Notes in Computer Science, pages 30-43, November 2001. [26] Rob Sherwood, Ryan Braud, and Bobby Bhattacharjee. Slurpie: A cooperative bulk data transfer protocol. In Proceedings of  IEEE INFOCOM,  March 2004. [27] Speedera. http://www.speedera.com. [28] Tyron Stading, Petros Maniatis, and Mary Baker. Peer-to-peer caching schemes to address flash crowds. In 1st International Peer To Peer Systems Work-shop (IPTPS  2002), Cambridge, MA, USA, March 2002. [29] Angelos Stavrou, Dan Rubenstein, and Sambit Sahu. A lightweight, robust P2P system to handle flash crowds. In Proceedings of  the 10th IEEE International Conference  on Network Protocols, pages 226-235. IEEE Computer Society, 2002. [30] Swarmcast. http://sourceforge.net/projects/swarmcast/. Glossary A.l Terms Candidate : a peer that is willing to join a swarm to contribute its bandwidth re-sources to the aid of others. Helper: a peer that has joined a swarm only to contribute its bandwidth resources. A helper is not interested in the content that it helps to distribute. Leecher : a peer with only a partial copy of the file. Regular peer: a non-helper peer in the swarm (see Helper). Seed : a peer possessing all the blocks of the file. Swarm: a set of peers which are uploading and downloading the same file via swarming. Swarming : a content delivery technique where peers upload and download parts of the content to each other in parallel through multiple connections. Reevaluation (of  unfulfilled  blocks): a maintenance routine run periodically by our mechanism to make sure that unfulfilled blocks remain fulfillable, so that no blocks are stuck in the unfulfilled state indefinitely. Tracker: a server process responsible for coordinating the membership of the swarm. Unfulfilled  block (of  a helper peer A): a block possessed by A which has been uploaded less than U/A  times (see U/A). Upload factor:  the number of times a helper must upload each block it down-loads. A.2 Notations : the set of unfulfilled blocks possessed by peer A, defined as = {i\uA(i)  < u/A}-4>A • the number of unfulfilled blocks possessed by peer A, defined as 4>A — Treeval  : the time period between successive reevaluations (see Reevaluation). BA : the set of blocks possessed by peer A. DC a the download capacity of the peer A. Y^ DC-D/S  : the demand/supply  ratio of a swarm, calculated as D/S  = g ^ " 1 * * ^ '• It is used by our mechanism to determine whether additional helpers should be invited into the swarm, and whether existing helpers could be asked to leave. desireA(i)  • the number of A's sinks which do not have the block i. khelper  '•  a system-wide parameter dictating the maximum number of helpers al-lowable in a swarm. In our mechanism, we set the limit to be kheiper times the number of regular peers in the swarm. kpenalty  '•  a system-wide parameter between 0 and 1 used to bias our swarming system towards preferring existing connections over new ones. The bias in-creases as the value of kpenaity decreases towards 0. kthres  a system-wide parameter dictating the value of TA  for each helper peer A. In our mechanism, we set TA = hhres • UCA-kupload  '• a system-wide parameter dictating the value of UJA  for each helper peer A. In our mechanism, we set u/a = kupioad  • • the upper limit for the number of incoming (download) connections for peer A. : the upper limit for the number of outgoing (upload) connections for peer A. rinvite '•  an upper threshold for the value of D/S.  When D/S  > rinvite, the tracker attempts to invite additional helpers to join the swarm until either D/S  is restored to be below rin v i t e , or when the number of helpers in the system hits an upper limit. T%minvite  a lower threshold for the value of D/S.  When D/S  < runinvit e, the tracker can ask existing helpers in the swarm to leave. It may do so until D/S is restored to be above runinvite. TA  : an upper threshold for the value of 4>A- When 4>A > TA,  our mechanism halts the helper peer A from downloading further blocks. UA(i) • the number of times peer A has uploaded block i. This upload count can be modified artificially by the reevaluation routine (see Reevaluation). ufA  • the upload  factor  for a helper peer A, i.e., the number of times A must upload each block it downloads. UCA  • the upload capacity of the peer A. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051633/manifest

Comment

Related Items