Cluster Computing on the Fly:P2P Scheduling of Idle Cycles in the InternetVirginia Lo, Dayi Zhou, Daniel Zappala, Yuhong Liu, and Shanyu ZhaoComputer and Information Science, University of Oregon, Eugene, Oregon 97403-1202flo, dayizhou, zappala, liuyh, [email protected]—Peer-to-peer computing, the harnessing ofidle compute cycles throughout the Internet, offersexciting new research challenges in the convergingdomains of networking and distributed computing. Oursystem, Cluster Computing on the Fly, seeks to harvestcycles from ordinary users in an open access, non-institutional environment.The CCOF cycle sharing system encompasses allactivities involved in the management of idle cycles:overlay construction for hosts donating cycles, resourcediscovery within the overlay, application-based schedul-ing, local scheduling on the host node, and meta-levelscheduling among a community of application-levelschedulers.We identify four important classes of cycle-sharingapplications, each with distinct requirements that callfor application-specific scheduling strategies. CCOF’sWave Scheduler exploits large blocks of idle time atnight, to provide higher quality of service for deadline-driven workpile jobs, using a geographic-based overlayto organize hosts by timezone. CCOF’s workpile sched-ulers use quizzes sent to host nodes to check the correct-ness of results computed by the hosts and to determinetrust ratings for the hosts. Our PoP Scheduler dispersestasks comprising a point-of-presence application, usingscalable protocols to discover strategically located hoststo meet application-specific requirements for location,topological distribution, and resources. Our work withCCOF reveals many of the critical challenges that lieahead for P2P computing systems.I. INTRODUCTIONPeer-to-peer computing, the harnessing of idle com-pute cycles throughout the Internet, offers an ex-citing new challenge for P2P networks beyond cur-rent information sharing applications. Experience hasshown that not only are idle cycles widely avail-able throughout the Internet, but in addition, manyusers are willing to share cycles [14], [7], [16]. Thiscompelling opportunity has not gone unnoticed andnumerous researchers are delving into this excitingnew juncture between the fields of networking anddistributed computing.Our research addresses the problem of peer-to-peer computing, which encompasses all of the activi-ties involved with utilizing idle cycles from ordinaryusers in a distributed, open environment. In contrastto Grid computing [10], [12] and other institution-based cycle-sharing systems [17], we are targetingan open environment, one that is accessible by theaverage citizen and does not require membership inany organization. Peer-to-peer computing representsthe next step in distributed computing, providingpotentially greater computing power than institutional-based projects while also empowering ordinary users.This view of P2P computing is the focus of severalother current research projects [13], [5], [4].P2P computing in an open environment gives rise toa new generation of resource management problemsthat are dramatically different from those addressedby traditional scheduling systems, including issues ofresource discovery, trust, incentives, fairness, security,and new criteria for evaluating performance. We usethe term “P2P scheduling system” to encompass allactivities involved in the management of idle cycles:overlay management for hosts donating cycles, re-source discovery within the overlay, application-basedscheduling, local scheduling on the host node, andmeta-level scheduling which involves coordinationof efforts among a community of application-basedschedulers.We believe that peer-to-peer scheduling solutionsmust be driven by the characteristics and goals of thespecific applications to be scheduled. We identify fourimportant classes of problems that are particularlywell-suited to capturing idle cycles in the Internet:infinite workpile, deadline-driven workpile, tree-basedsearch, and point-of-presence applications.Popular applications for harvesting idle cycles fromordinary users, such as SETI@home [8], are limitedto CPU-intensive workpile applications and requiredonors of cycles to manually coordinate through acentralized web site. More general cycle-sharing sys-tems, such as Condor [17], provide automatic schedul-ing but require a centralized matchmaking serviceand are limited to members of participating institu-tions. Our goal is the development of a schedulinginfrastructure that supports automatic scheduling ofthese four broad classes of applications in an openenvironment.In this paper, we discuss the problems faced byP2P scheduling systems that presume an open andlarge scale environment. In Section 2, we presenta taxonomy of P2P cycle sharing applications andtheir specific requirements. Section 3 presents theCluster Computing on the Fly architecture and dis-cusses issues and open problems involved in thedesign of an open P2P scheduling system. In Section4 we describe how CCOF addresses some of theseproblems. In particular, we introduce CCOF’s WaveScheduler which harvests night time idle cycles byusing geographic timezones to organize the hosts, andCCOF’s method for verification of results returnedby the hosts. We also describe our PoP Schedulerwhich utilizes scalable protocols to schedule point-of-presence applications by discovering strategically lo-cated hosts to meet application-specific requirementsfor location, topological distribution, and resources.II. P2P SCHEDULING SYSTEMSA. P2P Cycle-sharing ApplicationsWe organize P2P cycle-sharing applications intofive classes whose scheduling needs are starkly dis-tinct, calling for individualized scheduling servicesthat are tailored to those needs. Our research isfocused on the first four of these classes.1) Infinite workpile applications: These applica-tions consume huge amounts of compute time under amaster-slave model in which the master delivers codeto as many hosts as possible, over long periods oftime. Each host computes intensively, and then returnsthe results back to the master node. The workpileapplication is “embarrassingly parallel” in that thereis no communication at all between slave nodes.Examples of infinite workpile applications include thenow legendary SETI@home [7], the Stanford FoldingProject [11], and numerous mathematical applicationsranging from number theory to cryptography [14].Infinite workpile
View Full Document
Unlocking...