TL;DR
This paper tackles the challenge of understanding and utilizing the dynamic availability of millions of internet-connected computers for distributed systems. By analyzing availability patterns across over 110,000 hosts, they developed a clustering method to identify groups of resources with correlated availability, demonstrating significant performance improvements for parallel applications.
What Problem Does This Paper Address?
The rise of distributed systems like P2P networks, volunteer computing, and Grids has opened up vast computational resources across the internet. However, a clear understanding of how these resources become available and unavailable over time is crucial for designing efficient and reliable systems. Existing research often focuses on smaller scales or different types of availability (e.g., host vs. CPU). This paper aims to characterize the time dynamics of CPU availability across a massive, diverse set of internet-connected hosts, specifically focusing on identifying correlated availability patterns that can be exploited for better resource management. This is particularly important for applications with task dependencies or those requiring synchronization, where the availability of multiple resources at specific times can significantly impact performance.
Methods
The authors instrumented the BOINC client to record CPU availability intervals, defining an interval as a period of uninterrupted CPU availability. They collected data from over 112,000 hosts over seven months. To identify patterns, they employed a k-means clustering algorithm.
Key methodological choices include:
- Data Representation: Each host's availability was represented by a 24x7 bit vector, where each bit corresponds to an hour in the week, indicating whether the CPU was available (1) or not (0). A threshold of 0.75 was used to define availability, focusing on repetitive patterns over longer terms.
- Distance Metric: The Hamming distance was chosen to measure the similarity between host availability traces. This metric is sensitive to differences in binary vectors, making it suitable for comparing availability patterns.
- Clustering: K-means was used to group hosts with similar availability patterns. The authors explored different values of 'k' (number of clusters) and visually and quantitatively evaluated cluster quality.
Datasets
The primary dataset used in this study was collected from the BOINC server for SETI@home. This dataset comprises availability traces from 112,268 hosts over a period of approximately seven months (April 1, 2007, to February 12, 2008). The logs collectively represent 16,293 years of CPU availability. The data was categorized by host location: 81% at home, 17% at work, and 2% at school.
Key Insights and Ideas
- Internet Availability is Skewed and Diverse: While some hosts are highly available (90%+), a significant portion exhibits more sporadic availability, making simple availability-based prioritization insufficient.
- Time Zone Matters: Availability patterns show variations across different time zones, suggesting cultural or behavioral differences in how people use their computers. For instance, European users might turn off machines more at night than users in the US.
- Correlated Availability is Key: The most significant insight is that identifying groups of hosts with correlated availability (either positively or negatively) is more valuable than looking at individual host availability. This allows for more sophisticated resource management.
- Clustering Uncovers Hidden Patterns: Automated clustering, using Hamming distance on weekly availability patterns, successfully revealed distinct groups of resources with similar, often periodic, availability behaviors that were not apparent through simple visualization.
- Dedicated Resources Aren't Always Dominant: Surprisingly, hosts with 100% availability contributed less than 5% of the total compute power, highlighting the importance of considering less consistently available resources.
Key Results
- Availability Metrics: Mean availability interval length was 20 hours (median 8 hours), significantly longer than in enterprise environments. About 60% of hosts had mean interval lengths less than 24 hours. The mean fraction of time a CPU was available was 62% (median 67%).
- Clustering Performance: The k-means clustering algorithm, with k=5, identified distinct clusters of hosts. The two largest clusters were "cl_low_av" (0% availability) and "cl_high_av" (90-100% availability). The study found that inter-cluster distances were roughly twice the intra-cluster distances, indicating well-separated clusters.
- Application Performance Improvement: Through trace-driven simulations, a barrier synchronization application using the identified clusters for resource selection showed performance improvements of up to an order of magnitude or more compared to random selection or simple availability-prioritized methods. This was particularly evident when the number of hosts increased.
Limitations and Future Work
- Availability Definition: The study defines availability based on the BOINC client's idle state, assuming 100% or 0% availability. While justified by prior work, real-world scenarios might involve more nuanced availability levels.
- Trace Data Limitations: The availability patterns were derived from a specific two-month training period and used for coarse-grain predictions of time effects. The authors acknowledge that this might not perfectly capture all future availability dynamics.
- Future Work: The authors suggest exploring the use of these availability traces for modeling and simulation of resource management systems in unreliable environments. They also mention that in other recent work, they focus on the prediction of collective availability. The paper also hints at future work involving clustering based on host speed in addition to availability for applications that require both.
Summary updated