This dissertation focuses on scheduling strategies that achieve fast turnaround in open, dynamic, and large scale peer-based desktop grid. The challenges are two-fold: How does the scheduler quickly discover idle cycles in the absence of global information about host availability? And how can faster turnaround time be achieved within the opportunistic scheduling environment? Thus, our research is focused on two components of a peer-based desktop grid system: (1) fast scalable resource discovery and (2) application scheduling for fast turnaround.
We first describe a general peer-based desktop grid architecture, CCOF (Cluster Computing on the Fly). All of our research is based on this open, scalable, autonomous architecture.
Resource discovery is used to find available hosts in the peer-to-peer overlay network. We are the first to conduct a comprehensive study of generic resource discoverymethods in dynamic peer-based desktop grid systems. We found that the rendezvous point algorithm performs best under both light and heavy workloads because of its high success rate and consistently low message overhead.
We capitalized on the features of structured overlay networks to design two innovation rendezvous point selection schemes. SORPS (Structured Overlay Rendezvous Point Selection) selects a group of rendezvous points in a structured overlay network, with the goals of a balanced load among rendezvous points and low latency access from ordinary peers to rendezvous points. We then introduced virtual rendezvous points, which, in contrast to SORPS, do not utilize any physical nodes for resource discovery. Instead, we encode resource information in each node label, creating a RAON (resource-aware overlay network).
We designed a new peer-to-peer infrastructure called WaveGrid which uses a timezone-aware RAON for fast resource discovery and migration from heavily loaded host to lightly loaded host to improve throughput. We evaluated the performance of WaveGrid using a heterogeneous host CPU profile based on statistical data derived from the BOINC volunteer computing system. The simulation results show that WaveGrid outperforms other systems with respect to turnaround, stability and minimal impacts on hosts.
This dissertation includes both my previously published and my co-authored materials.