# Presentation: 886418

## Robust Grid Computing Using Peer-to-Peer Services  

**Robust Grid Computing Using ****Peer-to-Peer Services  **

- Alan Sussman
- Department of Computer Science

## Desktop Grids and P2P Systems

**Notes:**
 Desktop Grid computing has achieved tremendous computing power with low cost

 Opportunistic sharing to exploit large collections of personal computers and workstations across the Internet

## P2P Desktop Grid System

- Executing applications on a (widely) distributed set of resources
*Decentralized*, *Robust*, *Highly available* and *Scalable*
- Goal is to enable resource sharing
- create ad-hoc grids within (research) communities
- Applications
- Large computational requirements and relatively low I/O requirements
- Physical simulations and data analysis related to astronomy, physics, other scientific disciplines - parameter sweeps
- binary asteroid formation (co-I Richardson)
- comet composition (Deep Impact, co-I Wellnitz)
- Monte Carlo simulations
- Bioinformatics applications

## Hard Problems / Issues

- Job Submission
- Submit a job into the *decentralized* P2P system
**Matchmaking**
- Find a resource that can *meet* the minimum resource requirements of a job
**Load balance**
- Distribute the load (jobs) across the nodes in the system
- And no node has too much overhead (messages)
- Resilience to failure
- Overall system must not lose jobs from failures, and allow nodes to join and leave (or fail) dynamically

## System Architecture

**Clients**

**Job *****J***

**Assign GUID **
**to Job *****J***

**Peer-to-Peer**
**Network**
**(DHT)**

## Goals of Matchmaking Algorithm

*Expressiveness*
- Allow users to specify any type of resource requirements
*Load balance*
- Distribute load across multiple capable candidates
*Parsimony*
- Resources should not be wasted
*Completeness*
- A valid assignment of a job to a node must be found if such an assignment exists
*Low overhead*
- Routing must not add significant overhead

**Notes:**
 Low overhead can be challenging, given that the routing/matching is done in a completely decentralized fashion.

 Precision: A job should not be assigned to a node that is over-provisioned with respect to that job.

## Basic Assumptions

- Underlying *Distributed Hash Table* (DHT)
- Object location and routing in P2P network
- Reformulate the problem of matchmaking to one of routing
*Job* in the system
- Data and associated profile (requirements)
- All jobs are *independent*
- Optimization criterion
- Minimize time to complete all jobs (combination of throughput and response time)
- Queuing time used as proxy for response time

**Notes:**
 What the DHT does?
 Providing a lookup operation in decentralized P2P network
 Object location and routing

## Modified Content-Addressable Network

- Basic CAN
- Logical *d*-dimensional space
- zone, neighbors, greedy forwarding
- Formulate the matchmaking problem as a routing problem in CAN space
- Each *resource type* is a CAN dimension
- Map nodes and jobs into the CAN space
- Resource capabilities and requirements, respectively
- Search for *a node whose coordinates in all dimensions meet or exceed the job’s requirements*

**Notes:**
 The Basic CAN is the existing research work and we just used it and modified it

## CAN-based Algorithm

- Employ dynamic aggregated resource information for load balancing

***CPU***** Dimension**

***Memory***** **
**Dimension**

**Node A**

**Routing**

**Aggregate Resource ****Information**

**Job**

**Choose the least ****loaded direction**

**Push a job into under-loaded region**

**Stop pushing**

**Choose the best run ****node**

## Different Resource Types

- Categorical Resources
- Architecture, Operating system type (version), etc.
*Exact* match
- Continuous Resources
- CPU speed, Memory amount, Disk space, etc.
*Minimum* match
- Until recently, our work considered *only* continuous resource types

## Integrating Categorical Resources

- How to integrate all types of resources in CAN?
- Could add new CAN dimensions for categorical resource types
- Could create a distinct CAN space for each *combination* of categorical resource types
- Our Approach
*Virtual Peers* + *1-dimensional transformation*

## Virtual Peer+1-D Transformation

- 1-dimensional Transformation
- Transform all categorical resource dimensions into a *single* dimension
- To make virtual peer management and failure recovery simple, and re-use our existing algorithms
- Use Hilbert Space-Filling Curve
- Virtual peers cover the *unoccupied* parts of the CAN space in the categorical dimension
- Effectively divide the CAN space into multiple disjoint sub-CANs and *connect* them

## Memory

***Memory***

***C- Dim***

**B**

**A**

**C**

**V****BE**

**E**

**F**

**V****EH**

**V****H**

**H**

**D**

**Linux**
**& Intel**

**OSX**
**& PPC**

**Windows**
**& Intel**

**AIX**
**& Power**

**Solaris**
**& Sparc**

**M****J**

**I**

**G**

## Improving Overall Scalability

- Partial Updates
- Limit the size of a single update message
- Probabilistic Heartbeat Messaging
- Limit the number of outgoing update messages
- Specialized Routing along T-dimension
- Balance the load of processing routing messages from a sub-CAN to another sub-CAN
*All without affecting correctness of CAN algorithms*
- Must quantify performance and reliability effects

## Experimental Results

## Current Status

- Resource discovery algorithms thoroughly simulated and verified
- CAN-based implementation complete and being tested
- All CAN services working – node join, node leave/fail, job assignment, load aggregation
- Basic authentication mechanism in place, based on certificates and public-key authentication
- Job management and client interface completed
- Categorical resource types still being implemented
- Large-scale deployment and measurement in process
- binary asteroid formation application (Richardson)

## Ongoing Work

- Deploying the prototype system for real workloads and real machines
- practical issues, such as firewalls, user interface for job submission
- with serious logging for measuring system behavior
- Dealing with multicore and multiprocessor machines
- Better characterization of real workloads
- via consultation with Astronomy collaborators, logging behavior of the peer, and mining of Condor system logs
- High quality peer software, with good user tools

## The Project Team

- Faculty members
- Alan Sussman, Pete Keleher, Bobby Bhattacharjee, Derek Richardson (Astronomy), Dennis Wellnitz (Astronomy)
- Matchmaking algorithms and simulations
- Jik-Soo Kim (RA)
- Jaehwan Lee (RA)
- Peer implementation and other tools
- Michael Marsh (research scientist), Beomseok Nam (postdoc)
- Sukhyun Song, San Ratanasanya (RAs)

## End of Talk