SLA Negotiation Protocol for Grid-Based
Workflows
Dang Minh Quan and Odej Kao
Department of Computer Science, University of Paderborn, Germany
Abstract. Service Level Agreements (SLAs) are currently one of the
major research topics in Grid Computing. SLA negotiation protocol de-
fines a business relationship between consumer and provider and is thus a
necessary part of any commercial Grid application. In the Grid environ-
ment, an SLA negotiation protocol for a workflow becomes complicated
because of its structure which includes many dependent sub-jobs. The
complex workflow model leads to several constraints compared to single
jobs and requires advanced solutions. As a continuous effort in building
a full system supporting SLAs for Grid workflows, this paper presents
an SLA negotiation protocol for workflows and an initial system imple-
mentation.
1 Introduction
Service Level Agreements (SLAs) [8] are currently one of the major research
topics in Grid Computing, as they serve as foundation for a reliable and pre-
dictable job execution at remote Grid sites. The process of SLA composition
between consumer and provider is implemented by an SLA negotiation protocol.
Most of the existing SLA negotiation protocols [1,2,3,10] apply solely for Grid
jobs defined as monolithic entities, where the user sends the input data to a
service, computes the data  without dependencies  on this site and receives
the results. The complexity of the SLA negotiation protocol grows significantly
in case of workflows consisting of multiple, dependent sub-jobs. Figure 1 depicts
a common scenario where a workflow in a Grid environment is executed. The ex-
ecution of such a workflow differs from a single job execution in several aspects.
A workflow consists of many dependent sub-jobs, each of them with individual
requirements. Some sub-jobs have to run in parallel in order to fulfil the SLA
conditions, so certain resources are required simultaneously. Thus, it is necessary
to re-distribute the sub-jobs to different sites. Those differences lead to further
challenges for systems supporting SLAs for a Grid workflow compared to the
single job scenario. The challenges are found in the architecture, the language
description [4], the mapping algorithm [5], etc.
This paper presents the next step of building a full system supporting SLAs
for Grid workflows, which is an SLA negotiation protocol for workflows. It is
organized as follows: Section 2 describes the related work, Section 3 presents the
protocol and Section 4 describes the implementation architecture as well as the
deployment. Finally, Section 5 concludes the paper with a short summary.
L.T. Yang et al. (Eds.): HPCC 2005, LNCS 3726, pp. 505 510, 2005.
© Springer-Verlag Berlin Heidelberg 2005
506 D.M. Quan and O. Kao
2 Related Work
Czajkowski et al. introduced a general negotiation model called Service Negoti-
ation and Acquisition Protocol (SNAP) [3]. SNAP defines three types of SLAs
to manage resources across different administrative domains, which are Task
SLA (TSLA), Resource SLA (RSLA) and Bind SLA (BSLA). Those types of
SLAs can be used together in order to describe complex service requirements
in a distributed environment. The SNAP protocol is general and valid for many
cases. However, the application of the protocol to a specific problem needs fur-
ther extension to satisfy the requirements. A research contribution to express
a detailed SLA negotiation and implementation is presented in [1]. The GGF
Grid Resource Agreement and Allocation Protocol Working Group proposed a
draft on Agreement-based Grid Service Management (OGSI-Agreement), which
defines a set of OGSI-compatible portTypes through which management appli-
cations and services can negotiate.
Nassif et al. presented an agent-based SLA negotiation in Grids [10]. The
negotiation module includes different forms of negotiation called bilateral, multi-
issue and chaining negotiation. A bilateral negotiation occurs when only two
parts are involved. In a multi-issue negotiation, different aspects are negotiated
such as price, quality and time schedule. The negotiation between user agent
and network agent is called chaining negotiation. A chaining negotiation occurs
after the negotiation between user agent and server agent finished.
An initial work to design and implement a system supporting SLAs for Grid
jobs is described in [6,7,2]. However, solely monolithic jobs are considered and
supported. Shortcomings are mainly the underlying cost model and the missing
consideration of SLOs (Service Level Objectives).
3 SLA Negotiation for Workflow
As shown in Figure 1, an implementation of SLAs for workflows needs the partic-
ipation of three entities: a consumer, a broker and one or more providers. From
consumer s point of view, the broker is responsible for satisfying the published
SLA workflow broker
Provider 2
Subjob 1
Provider 1
Provider 3
Subjob 0
Subjob 3
Provider 4
Subjob 2
Fig. 1. Scenario of running a workflow in the grid environment
SLA Negotiation Protocol for Grid-Based Workflows 507
Local RMS
SLA data transfer
SLA subjob
SLA workflow
Grid resource
SLA subjob
Local RMS
broker
SLA subjob
SLA data transfer
Local RMS
Fig. 2. Interaction among participants in SLA for workflow negotiation process
requirements. However, the broker does not execute the workflow but manages
the workflow execution process. Components that run sub-jobs of the workflow
are computing services with their local Resource Management Systems (RMS).
The interaction among them in the negotiation process is depicted in Figure 2.
Figure 2 presents three different types of sub SLA negotiations. The User
- Broker negotiation focuses on the definition of the submitted SLA. Broker
- Provider negotiation considers the workflow s sub-jobs and uses the sub-job
SLAs. Provider - Provider negotiation deals with the data transfer between sub-
jobs (and also between providers) so the SLA part for data transfer is used.
In following, the each SLA part as well as the SLA negotiation procedures are
described in detail.
3.1 SLA Document Description
The SLA document defines the data transfers between two participants in the
negotiation process. All three types of the SLA text - including SLA workflow,
SLA sub-job, SLA data transfer - are compiled with the same SLA workflow
language [4]. The structure of the SLA text is presented in Figure 3, Figure 4,
and Figure 5.
3.2 Basic Negotiation Procedures
Although there are three types of SLA negotiation, the procedure remains the
same, only the service attributes differ. Figure 6 describes this basic procedure as
a Client/Server model. In the first step, the client creates a template SLA with
some preliminary service attributes and sends those to the server. The server
parses the text and checks the client requirements. In case of conflicts, a new
SLA version is compiled and sent back. Modified information can be start/stop
time, cost, maximal available CPUs etc. Additional information can be a new
SLO, FTP address, path etc. The client verifies the new SLA version and sends
it to server again. The process is repeated until the SLA is definitely accepted or
rejected. After acceptance, the signing phase is completed leading to an accepted
SLA, which cannot be modified.
3.3 An SLA for a Workflow Negotiation Process
Figure 7 describes the SLA negotiation for a Grid-based workflow as a time se-
quence. The customer sending an SLA template for workflows to the broker starts
the process. The broker determines a solution and negotiates with the customer.
508 D.M. Quan and O. Kao
SLA subjob
SLA workflow
General SLA description
General SLA description
Compute task description
Subjobs description
SLOs description
SLO description
Data transfer description
Data transfer description
Signature
Signature
Fig.3. SLA workflow structure Fig. 4. SLA sub-job structure
C S
SLA data transfer
1. Template SLA
l e
General SLA description
i r
Grid FTP 2. SLA negotiation
e v
File list
n e
3. SLA sign
Signature
t r
Fig. 5. SLA data transfer structure Fig.6. Basic SLA negotiation procedure
Template SLA workflow
C P P
SLA workflow negotiation
u B r r
Template SLA subjob
s r o o
SLA subjob negotiation
t o v v
SLA subjob signing
o k i Template SLA dat-tran i
m e d d
SLA dat-tran negotiation
e r e e
SLA dat-tran signing
SLA workflow signing
r r r
Phase 1 Phase 2 Phase 3
Fig.7. SLA for workflow negotiation process
Thereafter, the broker performs an SLA sub-job negotiation with providers for
all sub-jobs in the workflow. The SLA data transfer can be initiated after all
related SLA sub-job negotiations are completed. In case of conflicts, the broker
will find another solution and repeat phase 2 and phase 3. Following parts de-
scribe the negotiation steps with focus on the operation of each participant as
well as on the modified and additional information in the SLA text.
After the preliminary mapping decision (phase 1), the broker gains detailed
information on running the workflow, which is used for the negotiation (start/
stop time for each sub-job, data transfer SLA, etc.). Additional information can
be related for example to the SLO for workflows. However, in the SLA context,
consumers can also cause a Grid job failure for example by underestimating the
processing time. This will lead to job cancellation or job checkpointing after the
reserved time slot expired. Thus, it is necessary for the broker to add more SLOs
which impose the customer responsibility for the SLA text.
SLA Negotiation Protocol for Grid-Based Workflows 509
After receiving the SLA for a particular sub-job, the provider parses the
document and checks if it can fulfil the requirements (Phase 2). After successful
evaluation, the provider adds the FTP address and the storage path to the SLA
part defining the data transfer.
Phase 3 with provider - provider negotiation process increases further the
complexity. It can be done only when the two related SLA sub-job negotiations
finished. If this is not the case, the destination provider will conclude that the
submitted SLA data transfer belongs to none of the jobs and will discard it. In
order to solve this problem, the broker monitoring the state of each SLA sub-job,
plays the role of SLA transition. The template SLA from source provider is sent
to the broker and then to the destination provider when appropriate.
4 System Implementation
An implemented prototype fulfils the above constraints and provides basic fea-
tures, which allow any client to negotiate SLAs, monitor running workflows and
to receive the result. Based on standard components such as Globus Toolkit 3.2,
MySQL database, Maui ME for the local RMS, the system is compatible with
the existing Grid infrastructure. The overall architecture schema is depicted in
Figure 8. The online demonstration of the negotiation process as well as the
execution of a workflow consisting of seven sub-jobs in cooperation of three local
RMS can be found at http://pc-kao3.upb.de:9035/manual/test.html
Client console
Client
OGSI
SLA workflow broker service
Broker
Parser Database Mapping Monitoring Negotiation
OGSI
SLA local service
Local
SLA aware layer
RMS
Maui ME
Fig.8. System implementation architecture
5 Conclusion
An SLA negotiation process for workflow in the Grid environments is more
sophisticated than the mapping of monolithic jobs contained in the workflow.
This paper aims at defining that process and distinguishing the role as well as
the interaction of the components participating in the negotiation. The main
contribution of the paper is the definition of the components, the structure of
the SLA text and of the protocol which merges all components in the SLA
negotiation process. The process starts with negotiation on workflow between
510 D.M. Quan and O. Kao
the consumer and the broker using the SLA workflow text. Thereafter, a series
of negotiations between the workflow broker and the provider about each sub-
job is performed. Finally, the negotiation on data transfer between sub-jobs is
executed between providers according to the data transfer part in the SLA. The
process is implemented in a prototype using existing Grid middleware.
References
1. K. Czajkowski, A. Dan, J. Rofrano, S. Tuecke, and M. Xu.  Agreement-based Grid
service management (WS-Agreement), Global Grid Forum, 2003.
2. L. Burchard, M. Hovestadt, O. Kao, A. Keller, and B. Linnert. The Virtual Re-
source Manager: An Architecture for SLA-aware Resource Management. Proc.
IEEE CCGrid 2004, Chicago, US, 2004
3. K. Czajkowski and I. Foster and C. Kesselman and V. Sander and S. Tuecke.
SNAP: A Protocol for Negotiating Service Level Agreements and Coordinating Re-
source Management in Distributed Systems. Proc. 8th Workshop on Job Scheduling
Strategies for Parallel Processing, 2002.
4. D.M. Quan, O. Kao,  On Architecture for an SLA-aware Job Flows in Grid En-
vironments, Proc. 19th IEEE International Conference on Advanced Information
Networking and Applications (AINA 2005)., IEEE Press, 2005, pp. 287 292.
5. D.M. Quan, O. Kao,  Mapping Grid job flows to Grid resources within SLA con-
text, Proc. European Grid Conference,(EGC 2005), LNCS., Springer Verlag, 2005,
pp. 1107 1116.
6. R. Al-Ali, O. Rana, D. Walker, S. Jha, and S. Sohail. G-QoSM: Grid Service
Discovery using QoS Properties. Computing and Informatics Journal, Special Issue
on Grid Computing, 21(4):363-382, 2002
7. I. Foster, C. Kesselman, C. Lee, R. Lindell, K. Nahrstedt, and A. Roy. A dis-
tributed resource management architecture that supports advance reservation and
coallocation. In Proceedings of the International Workshop on Quality of Service,
pages 27-36, 1999.
8. A. Sahai and S. Graupner and V. Machiraju and A. Moorsel. Specifying and Mon-
itoring G)uarantees in Commercial Grids through SLA. Proceedings of the 3rd
IEEE/ACM CCGrid2003, 2003.
9. I. Foster, C. Kesselman, and S. Tuecke. The Anatomy of the Grid: Enabling Scal-
able Virtual Organizations. International Journal of Supercomputing Applications,
15(3), 2002.
10. L. Nassif, J. M. Nogueira, M. Ahmed, R. Impey, A. Karmouch. Agent-based Ne-
gotiation for Resource Allocation in Grid. 3rd Workshop on computational Grids
and applications, Summer program LNCC - 2005