Bare conf dvi
Yüklə 182,13 Kb. Pdf görüntüsü
|
- Bu səhifədəki naviqasiya:
- Abstract —Resource discovery enables applications deployed in heterogeneous large-scale distributed systems to find resources
- Emulating Resource Discovery
- Resource Discovery Algorithms
- HiDRA
- Resource discovery accuracy
| HiDRA: Statistical Multi-dimensional Resource Discovery for Large-scale Systems Michael Cardosa and Abhishek Chandra Department of Computer Science and Engineering University of Minnesota, Minneapolis, MN 55455 {cardosa, chandra}@cs.umn.edu Abstract—Resource discovery enables applications deployed in heterogeneous large-scale distributed systems to find resources that meet QoS requirements. In particular, most applications need resource requirements to be satisfied simultaneously for multiple resources (such as CPU, memory and network band- width). Due to dynamism in many large-scale systems, providing statistical guarantees on such requirements is important to avoid application failures and overheads. However, existing techniques either provide guarantees only for individual resources, or take a static or memoryless approach along multiple dimensions. We present HiDRA, a scalable resource discovery technique providing statistical guarantees for resource requirements spanning mul- tiple dimensions simultaneously. Through trace analysis and a 307-node PlanetLab implementation, we show that HiDRA, while using over 1,400 times less data, performs nearly as well as a fully-informed algorithm, showing better precision and having recall within 3%. We demonstrate that HiDRA is a feasible, low-overhead approach to statistical resource discovery in a distributed system. I. I
NTRODUCTION Recent years have seen the increasing use of large-scale distributed systems such as open Grids [1], [2], distributed Clouds [3], and peer-to-peer systems [4], [5] for a wide range of applications such as scientific computing, file sharing and multimedia streaming. Most of these distributed platforms consist of large number of machines with heterogeneous re- sources, and many of them are also geographically distributed. In order to satisfy application QoS requirements such as throughput, latency, and jitter, resource discovery [6], [7], [5], [8] is often used in such systems to find suitable nodes for deploying application components, or to execute specific computational tasks. Most distributed applications rely on multiple interacting re- sources, such as processing, memory, and network bandwidth, in order to meet their execution requirements. For instance, a data-intensive bioinformatics application [9] might be running multiple computational tasks on different machines, each an- alyzing gene sequences. In this scenario, each computational task needs sufficient CPU capacity and memory for each indi- vidual task to run efficiently. If each node has enough CPU ca- pacity but insufficient memory, then the tasks may slow down considerably due to excessive swapping and disk accesses. In addition, these tasks may also need a minimum amount of network bandwidth for downloading the required genome data, This work was supported in part by NSF Grant CNS-0643505. and exchanging and communicating partial results. Similarly, a node participating in a peer-to-peer streaming application would require sufficient downstream bandwidth to download the required video frames along with enough buffer space and CPU capacity for storing and decoding the frames. At the same time, it should also have sufficient upstream bandwidth to share its frames with other peers in the system. In other words, most applications need to satisfy multiple resource requirements to avoid any single resource from becoming a bottleneck and affecting the performance of the application. Many existing resource discovery mechanisms [6], [10], [7] have incorporated the need for multiple resources. However, many of these mechanisms either satisfy statically defined requirements, such as a node’s physical CPU clock speed or total amount of RAM, or at best, provide information about the recent values affecting some of these attributes, such as CPU load. However, such static or limited resource capacity information is insufficient for most large-scale plat- forms. Many of these systems have been shown to exhibit a large degree of dynamism [11], [12] in terms of the effective resource capacity they can provide at any given time. This dynamism is caused by several factors, such as varying loads, network congestion, churn, or varying application demands. To take such dynamic resource capacities into account, a recent approach has focused on providing statistical guarantees on meeting resource requirements [8]. However, this approach focuses on individual resource requirements, and is insufficient for providing statistical guarantees for multiple resources simultaneously. In this paper, we present a new technique for statistical multi-dimensional resource discovery called HiDRA (High- Dimensional Resource Allocation). This technique is designed to find nodes with desired resource capacities along multiple dimensions, and provide statistical guarantees on these capac- ities being satisfied over a time interval. An important aspect of this technique is that it can provide such guarantees on any combination of a number of resources (e.g., only CPU and memory, or CPU, memory and network bandwidth, etc.), and further, it provides guarantees for all the resource requirements
work is the novel use of multivariate normal distributions for the probabilistic modeling of resource capacity over multiple dimensions. We provide a heuristic for converting general dis- tributions (observed in real node data) to this representation, to
provide high accuracy for common resource discovery queries. We conduct a data analysis of a month-long PlanetLab trace, and our results show that HiDRA performs nearly as well as a fully-informed algorithm, showing better precision and having recall within 3% of this algorithm. We have deployed HiDRA on a 307-machine PlanetLab testbed, and our live experiments on this testbed demonstrate that HiDRA is a feasible, low- overhead approach to statistical multi-dimensional resource discovery in a distributed system. II. B
ACKGROUND & S
YSTEM M ODEL Resource Discovery: Previous scalable approaches to resource discovery have taken place in a static-configuration context; that is, searching for nodes in a wide-area system such that hardware and software configurations meet specified require- ments. Since these components are quite static, there is no need to update this information on any regular basis and therefore the use of content-addressable networks [6] has been used for such matchmaking of applications with nodes in a distributed and scalable fashion. The focus of resource discovery techniques upon dynamic node-level characteristics [7] (e.g., CPU load, memory avail- able, network bandwidth) shared many similarities with the static-configuration approaches. In SWORD [7], a multi- attribute range query system [13] implemented over a DHT was used to store and index load values for several node- level resource metrics. However, due to scalability concerns and the inability of DHTs to store or index distributions, only one load value per metric per node was maintained. Due to high variability in distributed systems such as PlanetLab [11], such a memoryless approach is unable to provide node-level resource capacity guarantees to the application. Recent work has extended SWORD to address data staleness issues [14], but the resource discovery method still lacks statistical properties. Resource Bundles [8] introduced statistical guarantees for resource discovery for single node-level resource metrics. Historical resource usage measurements were presented as profiles in the form of histograms. For scalability in large- scale systems, aggregation was used in a hierarchical overlay topology wherein nodes with similar resource usage profiles were grouped together to form higher-level representatives. This accurately provided statistical guarantees for resource discovery, but only for one resource metric at a time (e.g. effective CPU capacity available). Other Related Work: Condor [15] used a centralized co- ordinator approach to finding idle workstations in grid en- vironments among machines under the same administrative domain. Cluster computing on the fly [5] is a decentralized cycle-sharing approach to resource discovery in peer-to-peer environments. This work is single-metric, as cycles were the primary resource sought after; no notion of resource usage profiles were used. Their goal was to find idle machines near the edge of the network. Network Weather Service [16] uses tournament predictors to accurately predict trends in resource usage levels. However, these predictions are limited to the next time instant, and our focus is on providing long-range statistical guarantees. SDIMS [17] and Astrolabe [18] provide distributed “control planes” as a monitoring backbones for large-scale distributed services. Such a distributed overlay can be useful for dissem- inating resource usage information in a distributed resource discovery framework. System Model: We assume our system is a large-scale, pos- sibly wide-area or planetary-scale system. Participant nodes may be geographically distributed and could span multiple administrative domains. Nodes are able to monitor their own resource usages and capacities over time. We assume the nodes are connected via some interconnection overlay which they use to disseminate and share their resource usage information. The focus of our paper is on the scalability of data representation in the system, and we make no assumptions about the type or structure of the overlay or a specific dissemination technique. Examples of data dissemination techniques that could be employed include gossiping and epidemic protocols. III. S TATISTICAL M ULTI
- DIMENSIONAL R ESOURCE
D ISCOVERY
A. Statistical Resource Requirements Existing multi-dimensional resource discovery techniques represent resource requirements as a tuple {[R
1 , . . . , R m ],
1 , . . . , c m ]} for m resources, such that each resource type R i satisfies a capacity value c i . For instance, an applica- tion might need n nodes with {CPU ≥ 1 GHz, RAM ≥ 1 GB, network b/w ≥ 1 Mbps}. This requirement can then be specified as {[CPU, RAM, network], [1GHz, 1GB, 1Mbps]}. As discussed in the previous section, these capacity require- ments can either be static values [6] or recent values [7]. However, due to dynamic variations in resource availability, for instance, due to load variations, failures, and competing applications, a statistical guarantee is desirable on these re- source requirements. Statistical resource requirements for a single resource have been defined [8] as a tuple {R, c, p, t}, where R is a resource type, c refers to a capacity level, p is a percentile value, and t is a time duration. This definition implies that a resource requirement can be specified as a resource type (e.g., CPU) satisfying an effective capacity c (e.g., 1 GHz) for at least p% (e.g., 95%) of a time duration t (e.g., 24 hrs). We extend this definition to incorporate multiple resource requirements, by allowing R and c to be vectors [R 1 , . . . , R m ] and [c 1 , . . . , c m ]
i satisfies
a capacity requirement c i , and all these requirements are satisfied simultaneously at least p% of the time 1 . Thus, for instance, the example requirement above can be specified as {[CPU, RAM, network], [1GHz, 1GB, 1Mbps], 95%}, where each capacity requirement corresponds to the effective capacity 1 We omit the time duration t for clarity of discussion; one could easily extend our techniques for each time period t of interest. (a) Negative correlation between CPU and Network usages (b) Positive correlation between CPU and Network usages Fig. 1. Two time series showing the same resource usage profiles for individual resources, but with substantially different correlations between the resources. of the corresponding resource, and all these requirements should be satisfied simultaneously 2 .
Based on the above definition of statistical resource require- ments, the resource discovery process then involves finding nodes based on the following criterion: Given a requirement {R, c, p}, which nodes satisfy ∀i(R i ≥ c
i ) (vector compari- son) 3
the resource usage information of multiple resources to enable such a query to be resolved easily. Let us begin by considering a few possible approaches, based on existing techniques and their extensions. One possible approach would be to use a key-based rep- resentation as used by several existing DHT-based resource discovery algorithms [6], [7]. These algorithms represent re- source capacity/usage information of individual nodes as DHT keys, where, each key incorporates information about each resource type as well as its capacity value. However, while such a representation is effective for representing points in a multi-dimensional space (e.g., static values or recent values), it is not suitable for representing distributions or for range queries (as required for statistical inference). Another possible approach could be to apply a statistical resource discovery technique such as Resource Bundles [8] to individual metrics and then to combine individual resource- level guarantees to derive multi-dimensional guarantees. For example, if a multi-dimensional requirement is {[CPU, net- work], [1 GHz, 10 Mbps], 90% }, then a node that can sustain 1 GHz effective CPU capacity for 90% of the time as well as 10 Mbps effective network bandwidth capacity for 90% of the time would be expected to satisfy the given requirement. 2 To capture the notion of meeting resource requirements for multiple metrics simultaneously, we will use the terms multi-dimensional, multi-metric, and multi-resource interchangeably in the rest of our paper. 3 We allow both ≥ and ≤ comparisons, but mention only one for clarity of discussion. −1 0 1 2 3 −3 −2 −1 0 1 0 0.2 0.4
0.6 0.8
1 Fig. 2.
MVN combines multiple normal distributions together with varying µ, σ
parameters and correlations between dimensions in the Σ matrix. Shown is an example 2-dimensional requirement space. However, this approach does not capture the simultaneous occurrence of the two requirements, which depends on the correlation between the two resource usages. Figure 1 illus- trates this time-dependence of the resource usage behavior of multiple resources. Therefore in order to derive multi- dimensional resource requirement guarantees directly from single-metric guarantees, all involved dimensions would either need to be completely correlated or completely independent of each other; in practice, neither of these conditions occur. For instance, in our study of PlanetLab traces, correlations between CPU and network bandwidth metrics were observed to vary between r = 0.13 and r = 0.96.
Based on our discussion above, the question is how can we model individual resource profiles accurately while also capturing the inter-resource correlations. In order to achieve these goals, we have the following key requirements for modeling resource capacity information: • A compact representation of the resource usage data over multiple resource types for each node. • An efficient means for characterizing the inter-resource correlations at each node. • A simple way to map the representation to the statistical requirement for resource discovery. Histograms or probability distributions can provide compact representations of individual dimensions, and are also easy to map to individual statistical requirements (by finding the cor- responding percentile values). However, as discussed above, they lose the time-dependent correlation among different di- mensions. One possibility could be to maintain histograms for individual dimensions along with inter-dimension cross- correlation values. However, as discussed above, there is no straightforward way of combining individual histograms with the correlation values to determine the corresponding percentile values across multiple dimensions (See Figure 1). A statistical distribution that satisfies the requirements men- tioned above is the Multivariate Normal (MVN) Distribution. This distribution is a generalization of the normal distribution to n dimensions. It can be represented as a set of n nor- mal distributions N (µ i , σ i ), i = 1, . . . n, each distribution corresponding to one dimension, and an n × n covariance matrix Σ capturing the correlation among the different di- mensions. The MVN distribution has the advantage of being a statistically “smooth” approach to finding the “volume” of an n-dimensional requirement plane. An example of a multi- dimensional requirement space generated by MVN is shown in Figure 2. Given desired ranges of values for each of the n normally distributed variables, and the covariances between each of the n variables, we can calculate the probability of these ranges co-occurring together. An MVN distribution meets each of the above-mentioned requirements as follows: • It provides a compact representation of individual re- source usage distributions: each distribution can essen- tially be represented by two numbers: (µ, σ), the mean and standard deviation of the normal distribution. • The covariance matrix captures the time-dependent cor- relation between different dimensions. • We can compute the probability of a multi-dimensional requirement being met by evaluating the parameterized MVN over the desired ranges along each of the resource dimensions. MVN would be a suitable representation to use if the actu- ally observed resource usage distributions could be accurately modeled as MVN distributions. However, we cannot assume resource capacities to be normally distributed 4 . The question is whether we can somehow exploit the nice properties of MVN for solving our problem, while accounting for the real resource usage behavior.
To solve the above problem, we observe that given a resource capacity distribution, there is likely to be only a small region of interest for resource discovery purposes. For example, an application is unlikely to request an effective
statistical guarantees are likely to lie in a high percentile range (such as 90-99 percentile). Therefore, since the critical values of the resource capacity distribution lie near the tail of the distribution, then a fair approximation would be to fit a normal distribution to more accurately capture that critical region of interest. Therefore, under the assumption of such a critical region of interest, we approximate a resource usage profile to the normal distribution. As seen in Figure 3, only two points in the resource usage profile are necessary in order to provide a normal approximation. We define these points to be the left and right boundaries of the critical region of the resource usage profile (e.g. 99th and 90th percentiles, respectively). Note that this normal curve need not be accurate for the shape of the distribution outside the critical region, but should capture the critical region with high accuracy. In addition, to capture the correlations among the different dimensions, we simply use 4 For instance, for PlanetLab data, we found that most resource usage distributions were not normally distributed. Fig. 3.
Construction of an approximation of a resource capacity profile (Actual) by a normal distribution (Normal), by defining the critical region between points A and B. the covariance matrix for the original distributions. This set of normal distributions along each dimension coupled with the covariance matrix provides us with an MVN representation of the resource usage profiles. The question is whether these normal approximations are adequate representations of their respective resource usage profiles? Furthermore, are the combination of these approx- imations into the MVN distribution sufficient for accurate ap- proximations of multi-dimensional resource requirements? We show empirically in Section IV-B that these approximations of single-metric resource usage profiles to normal distributions are, in fact, highly accurate approximations for their respective critical regions. Next, we show how the MVN model can be used for resource discovery.
An MVN-based multi-dimensional resource discovery tech- nique for n resource metrics, takes as its input an MVN model of n resource usage profiles in the form of normal distributions µ = (µ
1 , µ
2 , ..., µ
n ), σ = (σ 1 , σ
2 , ..., σ
n ), and
an n × n covariance matrix Σ capturing the correlations between resources. Also, it accepts a range of desired values for each metric. For example: for effective CPU available, [1.5 GHz, ∞], and for observed (node-level) network transmission rates, [ −∞, 1 Mbps]. Notice we must use −∞ instead of zero (even for nonnegative metrics) due to the use of normal approximations. As its output, this resource discovery technique uses the MVN distribution CDF to compute the probability that all of the resource usage variables will fall within their respective given ranges simultaneously. Thus, if the resulting probability is greater than or equal to the desired guaranteed level of service for the given requirement, then that node will be deemed suitable for the application. At a high level, each node in the system would analyze its own traces to determine the correlation values between all resource metrics, and perform approximations to the normal distribution for all such metrics. In order to represent its aggregate multi-dimensional resource requirement capacities, only the normal distribution parameters (µ i , σ
i ) and covariance matrix ( Σ) need to be maintained, and propagated to other nodes in the system as required (e.g., a central manager, or neighbors in an overlay). Overlays appropriate for this such data dissemination for resource discovery are presented in
our previous work [8] which makes use of a hierarchical overlay [17]. IV. E VALUATION We next present an evaluation of HiDRA: our MVN distribution-based resource discovery technique. We carry out this evaluation using a data analysis of PlanetLab traces, as well as through a live deployment on PlanetLab. As part of the evaluation, we first validate the accuracy of approxi- mating individual resource usage distributions using normal distributions. Then we evaluate the accuracy of HiDRA for multi-dimensional resource discovery. Finally, we evaluate the performance of this technique through a live deployment on PlanetLab. We begin by describing our data analysis method- ology for evaluating resource discovery techniques.
We used a month-long PlanetLab trace of 427 nodes ob- tained by CoMon [19] from February 2007 for our experi- ments. This trace provided resource usage values at 5 minute intervals for various resources for each node: CPU, memory, network bandwidth, etc. In particular, we considered resource usage metrics such as effective CPU (calculated from the CPU
transmission rate (NetTx), observed receive rate (NetRx) 5 and 5-minute load average (5LoadAvg). We did not consider memory usage, as PlanetLab has a stringent memory usage policy, which renders memory usage data useless for our purposes.
discovery techniques through data analysis, we emulate the resource discovery process as follows. This process from the client-side perspective begins as a query (specifying a requirement), receives an answer from the resource discovery algorithm (consisting of a selection of nodes on which to deploy), and then ends by evaluating the goodness of the node selections, determining which nodes were acceptable, i.e., which nodes satisfied the requirement over the lifetime of the deployment. We execute each resource discovery algorithm over a 24 hour trace of data for making its decisions (for node-level statistical guarantees over the next 24 hours), and then evaluate the goodness of the selection by observing the resource usage data for the selected nodes for the following 24 hours. We perform this evaluation for each successive day in the month- long trace. Each baseline algorithm (described next) may use all or part of the 24 hours of data to make its decisions. The MVN distribution-based algorithm (HiDRA) uses the 24 hours of data to construct single-metric normal approximations and cross-metric correlations which are then used for multi-metric approximations. Evaluation Metrics: The goodness of choice between dif- ferent resource discovery algorithms can be evaluated in several ways. Resource discovery algorithms return a set of 5 Note that NetTx and NetRx should not be confused with network transmit or receive capacity. nodes to the client application, indicating their best efforts at finding the most accurate set of acceptable nodes. To quantify the accuracy of resource discovery algorithms, we define the following evaluation metrics that take into account the proportion of acceptable nodes—nodes that actually meet the requirements—with respect to the selected nodes as well as the total number of nodes in the system. • Precision is the proportion of nodes selected that were actually acceptable. A precision value of 1 indicates that every node selected by the resource discovery algorithm fulfilled its given requirements. However, precision by itself is not enough, since it could still mean that the algorithm may have missed many acceptable nodes in the system. • Recall is the proportion of acceptable nodes that were chosen by the resource discovery algorithm of those that existed in the whole system. A low recall value means that the algorithm fails to find many acceptable nodes. However, one cannot consider recall alone, since a trivial algorithm that selects every node in the system will always have a recall of 1. Resource Discovery Algorithms: We will compare the fol- lowing resource discovery algorithms: • Memoryless: This algorithm uses the last data point for each metric on each node to estimate its expected capacity over the next day. This algorithm emulates resource discovery algo- rithms that use recent resource usage information to determine the suitability of a node to meet a minimum requirement, and does not incorporate statistical resource usage patterns into its decisions. • History: This is a centralized algorithm with global historical knowledge of the entire system. It maintains complete 24-hour traces for each node. This provides a baseline to determine the effect of data loss due to approximation/aggregation on the accuracy of resource discovery. • Resource Bundles: This algorithm is used for single- metric resource discovery results only. This uses Resource Bundles [8] to aggregate the resource usage histograms of groups of nodes into resource bundles. Note this technique is able to maintain the overall shape of the single-resource distributions, whereas the NormApprox method below sacri- fices all but the critical region of the distributions. It must be noted, however, that the Resource Bundles algorithm performs aggregation at a more complex group-level granularity (instead of node-level granularity), supporting more functionality than merely resource discovery. In our experiments, nodes are bundled based on histogram similarity. For each bundle, if its representative meets the desired statistical requirement, all its members are considered acceptable. • HiDRA: This algorithm uses the MVN-based resource discovery described in the previous section. Our single- dimensional version of HiDRA is called NormApprox.
In order to justify our modeling of resource usage profiles as normal distributions, we first show that these approximations are accurate models. Note that an important assumption we have is that the main area of interest for resource usage profiles
1 0.9
0.8 0.7
0.6 0.5
0.4 0.3
0.2 0.1
MeanCPU 1020 MHz
680 MHz 340 MHz
Precision Memoryless History
NormApprox ResourceBundles (a) Precision 1 0.9 0.8 0.7
0.6 0.5
0.4 0.3
0.2 0.1
MeanCPU 1020 MHz
680 MHz 340 MHz
Recall CPU Capacity Requirement Memoryless History
NormApprox ResourceBundles (b) Recall Fig. 4.
Normal Approximations (NormApprox) compared against baseline resource discovery algorithms along with Resource Bundles. (p = 95 th percentile for NormApprox, Cluster and History.) 420 PlanetLab node traces from Feb 2007 were used. is the critical region. If we assume that applications will infrequently ask for percentiles less than the 90th percentile, then it is reasonable to choose the critical region endpoints to be the 90th and 99th percentiles. But is this still accurate for resource discovery requirements between the 90th and 99th percentiles? In Figure 4 we show the accuracy in terms of precision and recall for 95th percentile CPU requirements. NormApprox shows more precision than History itself, similar to Resource Bundles. We explain this be- havior as the algorithms being conservative about their choice of nodes; it finds fewer nodes than History, but is slightly more precise in its choice of nodes. This most likely is a result of the approximation and “smoothing” of the distributions so that fewer nodes are chosen. However, NormApprox has recall nearly as high as that of History; Resource Bundles lags behind in this regard since the accuracy of its aggregation technique depends on other “similar” node resource usage profiles, whereas our approximation technique is independent of other node distributions. Thus, NormApprox is a highly accurate means for approx- imating node resource usage profiles using normal approx- imations, even though the distributions themselves may not entirely be normal. This is sufficient since we wish to model only the most important critical regions of the distribution. As we discussed in Section III-D, this normal approximation is crucial for the MVN approach to work, and we next show the benefit of this approach for multi-dimensional resource discovery.
We now evaluate HiDRA over multi-dimensional resource requirements. In our evaluation of HiDRA, we ask the follow- ing questions: •
set of resource requirements, varying of the number and combination of metrics selected. •
ment percentiles inside the critical region? Given the requirement metric values and critical region, if we vary the requirement percentile, we want to see how accurate HiDRA is inside the critical region, and investigate its accuracy for percentiles outside of the critical region. •
of HiDRA? As we hold constant the requirement metric values and the requirement percentile, we want to inves- tigate the changes on accuracy as we vary the boundaries of the critical region. 1) Performance Across Different Requirements: In our analysis we used five multi-dimensional resource requirements for
our evaluations, defined below.
Req EffCPU
NetTx NetRx
5Load 15Load
(≥ MHz) (≤ Kbps)
(≤ Kbps) (≤)
(≤) 1 500 1000 1000
5.00 2 500 1000 5.00
3 1000
8.00 4 1000 5000 5 300 2000 2000
These requirements were chosen to represent a wide variety of applications having a different multi-metric requirements. Also notice that there may be varying amounts of correlations between various metrics chosen above, e.g., while some of these metrics may be highly correlated, (e.g., effective CPU and the 5-minute Load Average), others may be largely independent of each other (e.g., Load Average and NetTx). The results of applying these requirements (with p = 95 percentile) can be seen in Figure 5. For each of the five requirements, HiDRA consistently performs very close to the fully-informed History technique (that uses complete node traces). The number of acceptable nodes chosen between the History and HiDRA algorithms is extremely close. As in the previous results, HiDRA selects slightly fewer nodes, showing a slightly better precision but slightly worse recall. These results show that under a wide variety of resource requirements, also among varied configurations and metrics chosen under these requirements, HiDRA is a highly accurate 0 20
40 60
80 100
120 140
Req 5 Req 4
Req3 Req 2
Req 1 Nodes Chosen Requirement History-Unacceptable History-Acceptable HIDRA-Unacceptable HIDRA-Acceptable Total Actual Acceptable Fig. 5. Number of nodes chosen as acceptable nodes for five different requirements under the 95th percentile and critical region of 90-99. 0.7
0.75 0.8
0.85 0.9
0.95 1 75 80 85
90 95
100 Accuracy
Percentile History-Precision HiDRA-Precision History-Recall HiDRA-Recall Fig. 6. Varying requirement percentiles from 75 to 99, for Req 2 and critical region of 90-99. algorithm for resource discovery, performing on par with a fully-informed algorithm.
show HiDRA’s performance as we vary the requirement percentile itself (for Requirement 2 above) with a critical region of 90-99. The results can be seen in Figure 6. First notice how both the precision and recall of History decline as the percentile value increases; this indicates that it is more difficult to accurately predict a selection of nodes for higher requirement percentiles. The precision and recall of HiDRA approaches the goodness of History as the percentile approaches the left boundary of the critical region, the 90th percentile. This is happening because the modeled normal distribution more accurately approximates the actual resource profile within the critical region, with an exact overlap at the endpoints of the critical region. Thus, we expect HiDRA’s performance to follow History more closely within the critical region. In particular, it can be seen by how the precision and recall of History and HiDRA both match exactly at the 90th and 99th percentile points, the critical region boundaries. Inside the critical region, the precision of HiDRA is slightly 0.7
0.75 0.8
0.85 0.9
0.95 1 74 76 78
80 82
84 86
88 90
Accuracy Left Boundary to Critical Region (in percentile) History-Precision HiDRA-Precision History-Recall HiDRA-Recall Fig. 7. 95th percentile for Req 2, Varying critical region left boundary from 75 to 90; right boundary is 99. 0.7
0.75 0.8
0.85 0.9
0.95 1 74 76 78
80 82
84 86
88 90
Accuracy Left Boundary to Critical Region (in percentile) History-Precision HiDRA-Precision History-Recall HiDRA-Recall Fig. 8. 75th percentile for Req 2, Varying critical region left-boundary from 75 to 90; right boundary is 99. better than that of History, while recall lags slightly behind. This indicates that, in the critical region, HiDRA tends to select slightly fewer nodes than History, but its selection is slightly more accurate than that of History. These results show that HiDRA is highly accurate when the requirement percentile falls inside the critical region.
tigate the sensitivity of HiDRA’s performance when we vary the critical region left boundary under two different percentile choices (for Requirement 2 above). Note that the accuracy measures for History will not change as it does not depend on the critical region of HiDRA. We set the percentile of the requirement to 95 and vary the left boundary of the critical region, keeping its right boundary fixed at 99 percentile. The results can be seen in Figure 7. In this example, the requirement is always inside the critical region, and the measures of accuracy, both precision and recall, show signs of improvement as the critical region is bound tighter to the percentile, as expected. Next we set the percentile to 75 and again vary the left boundary of the critical region in Figure 8. This time, the
requirement starts on the left boundary of the critical region, and moves outside of the region as we move the boundary of the critical region to the right. Not surprisingly, both precision and recall decline as the critical region moves away from the percentile of interest. However, the deviations from the History algorithm are not too severe (precision within 11%), showing that even with a misconfigured critical region, the results are still fairly accurate. 4) Selecting The Critical Region: Our results provide some guiding principles for the choice of critical region boundaries. First, we observe that tighter critical regions surrounding the requirement percentile result in higher accuracy. Second, when the requirement percentile falls outside the critical region, there is a dropoff in accuracy. These two observations highlight a tradeoff concerning critical region selection. If the critical region is too wide, several percentiles would likely fall inside the region, but accuracy would suffer from approximating such a wide region. On the other hand, if the critical region is too small, the accuracy would be high inside the region, but many percentiles are likely to fall outside of the critical region. This tradeoff suggests that the width of the critical region can be fine- tuned and dynamically adapted based on the frequently desired percentile values. For instance, even if the initial critical region was chosen as [90-99], if most queries are for 95 percentile requirements, then the critical region can be tightened to [95- 99]. Similarly, if many percentiles appear to fall outside the critical region, then, it can be expanded or the range moved to include the desired values.
We deployed our HiDRA algorithm on 307 nodes in Plan- etLab. Our primary goal was to validate the results we saw in our analysis, through an online deployment of HiDRA in a real system and also to measure the overhead of HiDRA. We chose three simple multi-dimensional requirements to inject into our implementation: Req
EffCPU (≥ MHz) NetTx (≤ Mbps) NetRx (≤ Mbps) 1 500 10 10 2 1000 10 10 3 1500
8 8 Nodes monitored their own resource usage time series via their own access to their local CoMon daemon process. We limited our monitoring to the three resource metrics of interest: effective CPU, network transmit bandwidth observed and network receive bandwidth observed. From this time series, the nodes computed their own normal approximations to individual metrics and also the covariance (i.e., correlation) matrix. This functionality was implemented using a Perl script. Then these normal distribution and correlation data were sent to a centralized query manager node, which executed the HiDRA algorithm using a Fortran implementation of the MVN distribution function [20]. The critical region was defined between the 90th and 99th percentile values for each of the resource metrics. Also, the History and Memoryless algorithms were employed in this system by each node sending a historical trace of its resource usage. For clarity, we refer to 0 50 100 150
200 250
Req 3 Req 2
Req 1 Nodes Chosen Memoryless-Unacceptable Memoryless-Acceptable History-Unacceptable History-Acceptable HiDRA-Unacceptable HiDRA-Acceptable Total Actual Acceptable Fig. 9. Node selection for three different requirements under the 95th percentile in our PlanetLab implementation the node-level resource profile MVN distribution parameters maintained by HiDRA as resource descriptors. In our resource discovery framework, we chose to utilize a centralized query manager because PlanetLab is a relatively small system. Here we place less focus on the actual means of data propagation in the system 6 , and rather pay attention to the amount of data, and provide results on the data transfer overhead “per update” as a result. We propagated updates every 10 minutes of the resource descriptors at each node to the centralized query manager. Note that if the centralized query manager goes offline, its complete data store of resource descriptors will be completely replenished within 10 minutes of coming back online by receiving the usual amount of data from each node every 10 minutes. Also note that the size of the resource descriptors is independent of the size of the trace from which it originated; it is of fixed size dependent only on how many resource dimensions are being measured. We chose a time window of 24 hours for application deploy- ment which is also used for resource descriptor construction. We submitted our query for the three multi-resource require- ments to the central query manager and received responses from each of the algorithms. Then to evaluate this response of the resource discovery algorithms, we analyzed the future traces of the nodes chosen for deployment to measure the goodness of choice of nodes for a pseudo-application 7 . A
node chosen by an algorithm that satisfied its requirements is hereby called “acceptable”, and a node that does not satisfy its requirements is labeled “unacceptable” in the evaluation that follows. Resource discovery accuracy: We evaluated our results over three different percentiles for each of the three multi-resource requirements. The results are shown in Figures 9 and 10. 6 Forms of propagation (in structured or unstructured systems) include gossiping and flooding, as well as communication in systems that assume some super-node or hierarchical based overlay such as [17]. 7 PlanetLab has stringent rules for network bandwidth and memory con- sumption that are prohibitive to extensive multi-metric experimentation, which led us to use a pseudo-application, instead of a real application. 0 50
100 150
200 250
300 Req 3
Req 2 Req 1
Nodes Chosen Memoryless-Unacceptable Memoryless-Acceptable History-Unacceptable History-Acceptable HiDRA-Unacceptable HiDRA-Acceptable Total Actual Acceptable Fig. 10.
Node selection for three different requirements under the 75th percentile in our PlanetLab implementation As seen above in section IV-C, HiDRA’s selection of nodes shows precision on-par with (or better than) History along each of the three requirements. Also, HiDRA has a recall slightly lower than that of History, which we also saw in the previous analysis. Even in the 75th percentile experiment that does not lie in the critical region, the precision and recall of HiDRA is remarkably close to History, showing again that HiDRA is robust to an improperly configured critical region. Our evaluation of this live implementation confirms our results in the data analysis section above that HiDRA is a highly accurate means for multi-dimensional resource discovery.
at the central node was 70 KB. A fully-informed history- based algorithm would need about 99 MB of full traces from all nodes, which is 1,458 times more overhead than using our resource descriptors. The memoryless approach would have a data transfer size of 6 KB per update, but we have shown it is highly inaccurate. Again, note that our resource descriptors describe the whole trace, so we feel this is a fair comparison, especially in systems that may use flooding or gossiping of the resource descriptors. An impressive property of HiDRA is its data size independence from the trace length. Additionally, we can also be flexible in how often we send data in HiDRA because resource usage distributions are unlikely to change over the short run, and hence HiDRA can send updates less frequently than a history-based or memoryless algorithm, reducing the network transmission overhead further. V. C ONCLUSION Statistical resource discovery is critical for applications to find suitable resources in dynamic and heterogeneous large- scale distributed systems. A key problem is achieving such statistical resource discovery for multiple resources simul- taneously. In this paper, we presented HiDRA, a scalable multi-dimensional resource discovery algorithm that employs multivariate normal distribution for the probabilistic modeling of resource capacity over multiple dimensions. Our PlanetLab trace-based analysis showed that HiDRA performs nearly as well as the fully-informed History technique (with better precision than History and recall within 3% of History). Since HiDRA has such a compact representation of node behavior on multiple metrics simultaneously, it becomes a very attractive solution for large-scale systems that need a scalable resource discovery mechanism. Also, HiDRA provides statistical guar- antees to applications that allow deployments to be more stable and reliable, not subject to frequent failures or migration scenarios. Our live implementation in the PlanetLab testbed shows our system to be a feasible, low-overhead method in finding acceptable nodes for applications. In future work, we will investigate an integration with our previous work [8]. R EFERENCES [1] I. Foster and C. Kesselman, Eds., Grid2: Blueprint for a New Computing Infrastructure. Morgan Kauffman, CA, USA, 2004. [2] D. Anderson, J. Cobb, E. Korpela, M. Lebofsky, and D. Werthimer, “SETI@home: An Experiment in Public-Resource Computing,” Com- munications of the ACM, vol. 45, no. 11, 2002. [3] K. Church, A. Greenberg, and J. Hamilton, “On delivering embarrass- ingly distributed cloud services,” in Seventh ACM Workshop on Hot
[4] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, “Making Gnutella-like P2P Systems Scalable,” in Proceedings of ACM
[5] V. Lo, D. Zappala, D. Zhou, Y. Liu, and S. Zhao, “Cluster Computing on the Fly: P2P Scheduling of Idle Cycles in the Internet,” in Proc. of
[6] J.-S. Kim, P. Keleher, M. Marsh, B. Bhattacharjee, and A. Sussman, “Using Content-Addressable Networks for Load Balancing in Desktop Grids,” in HPDC’07, Jun. 2007. [7] D. Oppenheimer, J. Albrecht, D. Patterson, and A. Vahdat, “Distributed resource discovery on PlanetLab with SWORD,” in WORLDS’04, Dec. 2004. [8] M. Cardosa and A. Chandra, “Resource bundles: Using aggregation for statistical wide-area resource discovery and allocation,” in ICDCS’08, Jun. 2008, pp. 760–768. [9] Y. J. Kim, A. Boyd, B. D. Athey, and J. M. Patel, “miblast: scalable evaluation of a batch of nucleotide sequence queries with blast,” Nucleic Acids Res, vol. 33, pp. 4335–4344, 2005. [10] R. Raman, M. Livny, and M. Solomon, “Matchmaking: Distributed Resource Management for High Throughput Computing,” in HPDC’98, Jul. 1998. [11] D. Oppenheimer, B. Chun, D. Patterson, A. C. Snoeren, and A. Vahdat, “Service Placement in a Shared Wide-Area Platform,” in Usenix Annual Technical Conference, Jun. 2006. [12] J. W. Mickens and B. D. Noble, “Predicting node availability in peer-to- peer networks,” in Proceedings of the ACM SIGMETRICS Conference, 2005, pp. 378–379. [13] A. R. Bharambe, M. Agrawal, and S. Seshan, “Mercury: supporting scalable multi-attribute range queries,” SIGCOMM Comput. Commun. Rev., vol. 34, no. 4, pp. 353–366, 2004. [14] I. Chang-Yen, D. Smith, and N.-F. Tzeng, “Structured peer-to-peer resource discovery for computational grids,” in Proceedings of the 15th
[15] M. Litzkow, M. Livny, and M. Mutka, “Condor - a hunter of idle workstations,” in Proceedings of the 8th International Conference of
[16] R. Wolski, “Experiences with predicting resource performance on-line in computational grid settings,” SIGMETRICS Perform. Eval. Rev., vol. 30, no. 4, pp. 41–49, 2003. [17] P. Yalagandula and M. Dahlin, “A Scalable Distributed Information Management System,” in SIGCOMM’04, 2004. [18] R. V. Renesse, K. P. Birman, and W. Vogels, “Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining,” ACM Tr Comp Sys, vol. 21, no. 2, pp. 164–206, 2003. [19] K. Park and V. S. Pai, “Comon: a mostly-scalable monitoring system for planetlab,” SIGOPS Oper. Syst. Rev., vol. 40, no. 1, 2006. [20] A.
Genz, “http://www.math.wsu.edu/faculty/genz/software/software. html.” Yüklə 182,13 Kb. Dostları ilə paylaş:
|