Pagoda: A Dynamic Overlay Network for Routing, DataManagement, and MulticastingAnkur Bhargava∗Kishore Kothapalli Chris Riley Christian Scheideler†Mark ThoberDepartment of Computer ScienceJohns Hopkins University3400 N. Charles StreetBaltimore, MD 21218, USA{ankur,kishore,chrisr,scheideler,mthober}@cs.jhu.eduABSTRACTThe tremendous growth of public interest in peer-to-peer systems inrecent years has initiated a lot of research work on how to design ef-ficient and robust overlay networks for these systems. While a largecollection of scalable peer-to-peer overlay networks has been pro-posed in recent years, many fundamental questions have remainedopen. Some of these are:• Is it possible to design deterministic peer-to-peer overlaynetworks with properties comparable to randomized peer-to-peer systems?• How can peers of non-uniform bandwidth be organized in anoverlay network?We propose a dynamic overlay network called Pagoda that pro-vides solutions to both of these problems. The Pagoda networkhas a constant degree, a logarithmic diameter, and a 1/logarithmicexpansion, and therefore matches the properties of the best ran-domized overlay networks known so far. However, in contrast tothese networks, the Pagoda is deterministic and therefore guaran-tees these properties. The Pagoda can be used to organize bothnodes with uniform bandwidth and nodes with non-uniform band-width. For nodes with uniform bandwidth, any node insertion ordeletion can be executed with logarithmic work, and for nodes withnon-uniform bandwidth, any node insertion and deletion can be ex-ecuted with polylogarithmic work. Moreover, the Pagoda overlaynetwork can route arbitrary multicast problems with a congestionthat is within a logarithmic factor of what a best possible overlaynetwork of logarithmic degree for that particular multicast problemcan achieve, even though the Pagoda is a constant degree network.This holds even for nodes of arbitrary non-uniform bandwidths.We also show that the Pagoda network can be used for efficientdata management.∗Supported by NSF Grant CCR-0311321.†Supported by NSF grant CCR-0311121 and NSF grant CCR-0311795.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SPAA’04, June 27–30, 2004, Barcelona, Spain.Copyright 2004 ACM 1-58113-840-7/04/0006 ...$5.00.Categories and Subject DescriptorsC.2.1 [Computer-Communication Networks]: Network Archi-tecture and Design—Distributed networks; F.2.8 [Analysis of Al-gorithms and Problem Complexity]: Non-numerical Algorithmsand Problems—Routing and layout; G.2.2 [Discrete Mathemat-ics]: Graph Theory—Network problemsGeneral TermsAlgorithms, TheoryKeywordspeer-to-peer networks, routing, multicasting1. INTRODUCTIONIn recent years, peer-to-peer overlay networks have become ex-tremely popular for a variety of reasons. For example, the fact thatpeer-to-peer systems do not need a central server means that indi-viduals can search for information or cooperate without fees or aninvestment in additional high-performance hardware. Also, peer-to-peer systems permit the sharing of resources (such as computa-tion and storage) that otherwise sit idle on individual computers.Therefore, it is not surprising that peer-to-peer systems have in-spired an enormous amount of research. Despite many advances,fundamental problems have remained open, such as:1. Is it possible to design deterministic peer-to-peer overlaynetworks with properties comparable to randomized peer-to-peer systems?2. How can peers of non-uniform bandwidth be organized in anoverlay network?Why are these problems important and non-trivial? An obviousadvantage of a deterministic over a randomized solution is the abil-ity to locally self-correct the overlay network so that it not onlyfulfills the given connectivity rules but also retains certain desir-able topological properties such as a high expansion. The propertyof self-stabilization was introduced by Dijkstra in his 1974 paper[8] and is considered an important property in existing peer-to-peersystems [29, 22, 25]. By definition, (pseudo-)random constructionscannot be self-correcting with regard to expansion because the sys-tems can be in a state with a poor expansion although all connec-tivity rules are fulfilled. Although this may be unlikely to happen ifeverybody is honest, adaptive adversarial attacks can make such asituation very likely (see also [10]). Designing scalable, determin-istic overlay networks with a high expansion is a highly non-trivial170problem. The first such construction just recently emerged, and theconstruction and its analysis is quite involved [4].Also, organizing peers of non-uniform bandwidth in a scalableway is an important and non-trivial problem. It is important be-cause in reality, peers have different connections to the Internetwith bandwidths that may be several orders of magnitude apart.Also, future peer-to-peer systems will have to allow peers to ad-just the bandwidth they want to contribute to it to be acceptablesince many peer-to-peer applications may run in a peer at the sametime. Thus, a system is needed that can organize peers of non-uniform bandwidth and that can adapt to changing bandwidths in ascalable way. DHT-based peer-to-peer approaches cannot (in theirbasic form) take advantage of high bandwidth peers, because theirapproach of giving every peer the same degree and randomly dis-tributing peers in the system will isolate high bandwidth peers,making them ineffective. A straight-forward solution would beto simply include multiple virtual peers for each high-bandwidthpeer into the system. This approach, however, does not work wellin general, because allowing a peer to have multiple virtual peersin the system reduces its scalability and increases its vulnerabil-ity. It reduces its scalability because frequent bandwidth changesmay create a high update cost when using virtual peers, and it in-creases its vulnerability because if a high-bandwidth peer leaves,many virtual peers will leave with it, potentially creating disruptionof service and high repair costs for the overlay network. It wouldtherefore be much better to give every peer just a
View Full Document