Information Technology Reference
In-Depth Information
using the same criteria as before. Note that
cost
s
is the total cost of acquir-
ing all the instances in
C
S
according to a
bid price prediction method
(lines 6
and 7). Next paragraphs detail the strategy used for spot prices bidding used
in this work.
Both consumption vectors (
C
od
and
C
s
) represent the scaling plan generated
by SIAA. The algorithm then acquires the necessary instances considering the
number of instances already running (lines 10 to 12).
Spot Prices and Bidding.
Many strategies for bidding the spot prices have been
proposed relying on the use of historical data prices [1]. The performance of bid
price prediction methods have impact on the These prediction methods present
estimation errors that may affect the overall behavior of the autoscaling strategy.
If the method tends to underestimate the minimal bid price, instances may fail
earlier augmenting the number of interrupted tasks and reducing the size of the
infrastructure. Overestimation of the optimal bid price reduces the chances of
failure but may unnecessary increase the cost of execution if idle instances are not
terminated wisely. Because the aim of this work is not evaluating the performance
of bidding strategies, we simulate bid prediction methods as follows. The bid
is computed by sampling from a uniform distribution centered on the optimal
price for the next hour with bounds determined by a specified error percentage
of such optimal price. Prices used correspond to an existent databases [16]. This
bidding schema permits modeling a non-perfect bid-price estimation method by
just specifying the desired prediction error.
3.3 Phase 3: Heuristic Tasks Scheduling
At this point of the process, the infrastructure has been fitted to the needs
for the next hour of computation for an application. The scheduling algorithm
is now in charge of e
ciently execute the workflow application considering the
available instances. SIAA uses an heuristic scheduling algorithm which optimizes
the workflow makespan, i.e. the total running time of the workflow.
The objective of makespan minimization is accomplished keeping in mind two
premises: (
i
) execute the tasks as fast as possible, and (
ii
) minimize the negative
effects of instance failures. For such purpose, knowing which are the critical
tasks (slack times) plays a central role in the optimization process. Algorithm 2
describes the pseudocode of the scheduling strategy in SIAA.
The algorithm undertakes the minimization of workflow makespan reducing
the execution time of critical tasks. Tasks ready to execute are sorted prioritizing
those with the smaller slack times (line 3). Then, one by one, the tasks are
scheduled to the instance that offers the earliest completion time (ECT). This
process (lines 5 to 9) is repeated until there are no more ready tasks to schedule
or available instances (line 4). Please note that in all cases only waiting tasks
and available instances are considered. Tasks currently running continue their
execution on the instances they were previously assigned.
Although, the bid price prediction method (used during the scaling phase)
aims to reduce the number of task failures, out-of-bid errors are likely to occur.
