08-07-2014, 11:38 AM
PROFIT-DRIVEN SERVICE REQUEST SCHEDULING IN CLOUDS TECHNICAL REPORT 646
School of IT.pdf (Size: 355.94 KB / Downloads: 20)
Abstract
A primary driving force of the recent cloud
computing paradigm is its inherent cost effectiveness.
As in many basic utilities, such as electricity and
water, consumers/clients in cloud computing
environments are charged based on their service
usage; hence the term ‘pay-per-use’. While this pricing
model is very appealing for both service providers and
consumers, fluctuating service request volume and
conflicting objectives (e.g., profit vs. response time)
between providers and consumers hinder its effective
application to cloud computing environments. In this
paper, we address the problem of service request
scheduling in cloud computing systems. We consider a
three-tier cloud structure, which consists of
infrastructure vendors, service providers and
consumers, the latter two parties are particular
interest to us. Clearly, scheduling strategies in this
scenario should satisfy the objectives of both parties.
Our contributions include the development of a pricing
model—using processor-sharing—for clouds, the
application of this pricing model to composite services
with dependency consideration (to the best of our
knowledge, the work in this study is the first attempt),
and the development of two sets of profit-driven
scheduling algorithms
Introduction
In the past few years, cloud computing has emerged
as an enabling technology and it has been increasingly
adopted in many areas including science and
engineering not to mention business due to its inherent
flexibility, scalability and cost-effectiveness [1], [17].
A cloud is an aggregation of resources/services—
possibly distributed and heterogeneous—provided and
operated by an autonomous administrative body (e.g.,
Amazon, Google or Microsoft). Resources in a cloud
are not restricted to hardware, such as processors and
storage devices, but can also be software stacks and
Web service instances. Although the notion of a cloud
has existed in one form or another for some time now
(its roots can be traced back to the mainframe era [12]),
recent advances in virtualization technologies and the
business trend of reducing the total cost of ownership
(TCO) in particular have made it much more appealing
compared to when it was first introduced.
Cloud system model
A cloud computing system in this study consists of
a set of physical resources (server computers) in each
of which there are one or more processing
elements/cores; these resources are fully
interconnected in the sense that a route exists between
any two individual resources. We assume resources are
homogeneous in terms of their computing capability
and capacity; this can be justified using virtualization
technologies. Nowadays, as many-core processors and
virtualization tools (e.g., Linux KVM, VMware
Workstation, Xen, Parallels Desktop, VirtualBox) are
commonplace, the number of concurrent tasks on a
single physical resource is loosely bounded. Although
a cloud can span across multiple geographical
locations (i.e., distributed), the cloud model in our
study is assumed to be confined to a particular physical
location
Application model
Services offered in the cloud system can be
classified into software as a service (SaaS), platform as
a service (PaaS) and infrastructure as a service (IaaS).
Since this study’s main interest is in the economic
relationship between service providers and consumers,
services in this work can be understood as either of the
first two types
Scheduling model
The service request scheduling problem addressed
in this study is how to assign interdependent services,
part of one or more consumer applications, to service
instances—that may dynamically be created on
demand by providers—aiming to maximize the (net)
profit for providers without violating time constraints
associated with consumer applications. The scheduling
model in this study focuses on multiple service
requests from a number of consumers and a set of
services offered by a particular provider. The revenue
of a provider for a particular time frame is defined as
the total of values charged to consumers for processing
their applications (service requests) during that time
frame. The net profit is then defined as the remainder
of the revenue after paying the rental costs—which are
associated with the resources on which the service
instances of the provider have run and which the
provider has had to pay to its cloud infrastructure
vendor(s). Since a service instance runs constantly
once it is created, the provider needs to strike a balance
between the number of service instances it creates (and
provides), and the service request volume/pattern to
ensure its net profit is maximized. The effectiveness of
this balancing should be reflected in the average
utilization of those service instances.
Characterization of allowable delay
A consumer application in this study is associated
with two types of allowable delay in its processing,
i.e., application-wise allowable delay and service-wise
allowable delay. For a given consumer application Ai,
there is a certain additional amount of time that the
service provider can afford when processing the
application; this application-wise allowable delay is
possible due to the fact that the provider will gain
some profit as long as Ai is processed within the
maximum acceptable mean response time TMAXi. Note
that response time and processing time in our work are
interchangeable since the PS scheduling policy
adopted in our pricing model does not incur any
queuing delay. The minimum/base processing time
TMINi of application Ai is the summation of processing
times of services along the CP of that application. The
application-wise allowable delay aadi of application Ai
is therefore:
Maximum profit algorithm
MaxProfit (Figure 6) takes into account not only the
profit achievable from the current service, but also the
profit from other services being processed on the same
service instance. Specifically, the service is assigned
only if the assignment of that service onto the service
instance yields some additional profit. Note that each
service is associated with a decay rate and therefore,
the assignment of a service to a service instance on
which some other services of the same kind are being
processed may result in a certain degree of profit loss.
A scheduling event takes place either at the time
that a new service request (application) arrives or at
the time that a scheduled service completes its
processing and its successor service is ready to start by
the completion (Step 3). MaxProfit maintains a service
queue containing yet-to-be-dispatched services
according to their precedence constraints; that is, when
a new application arrives, its entry service is the only
one to be processed. MaxProfit checks all service
instances (the outer for loop; Steps 4–25) of service sj
(Ij)—for the current ready service ( *
j s )—and selects
the best instance based on additional profit incurred by
*
j s (Step 19). At core, for each service running the
current service instance (Step 7), the profit difference
Performance evaluation
In this section, we present and discuss performance
evaluation results obtained from an extensive set of
simulations. Our evaluation study is conducted on the
basis of comparisons between two sets of our
algorithms (MaxProfit and MaxProfitcsad, and MaxUtil
and MaxUtilcsad) and a non PS-based algorithm (called
earliest finish time with profit taken into account or
EFTprofit).
We have implemented and used EFTprofit as a
reference algorithm for our evaluation study, since
none of the existing algorithms can be directly
comparable to our algorithms. As the name (EFTprofit)
implies, for a given service, the algorithm selects the
service instance that can finish the processing of that
service the earliest with a certain amount of profit. If
none of the current service instances is able to process
Conclusion
As cloud computing is primarily driven by its cost
effectiveness and as the scheduling of compositeservice
applications, particularly in cloud systems, has
not been intensively studied, we have addressed this
scheduling problem with the explicit consideration of
profit, and presented two sets of profit-driven service
request scheduling algorithms. These algorithms are
devised incorporating a pricing model using PS and
two allowable delay metrics (asad and csad). We have
demonstrated the efficacy of such an incorporation for
consumer applications with interdependent services. It
is identified that those two allowable delay metrics
enable effective exploitation of characteristics of
precedence-constrained applications. Our evaluation
results confidently confirm these claims together with
the promising performance of our algorithms