SN0476 : Using constraint programming to resolve the multi-source / multi-site data movement paradigm on the Grid

Author(s):Michal Zerola, Jérôme Lauret, Roman Barták, Michal Šumbera
Date:Jan. 27, 2009
File(s): zerola_acat_2008.pdf

In order to achieve both fast and coordinated data transfer to collaborative sites as well as to create
a distribution of data over multiple sites, efficient data movement is one of the most essential as-
pects in distributed environment. With such capabilities at hand, truly distributed task scheduling
with minimal latencies would be reachable by internationally distributed collaborations (such as
ones in HENP) seeking for scavenging or maximizing on geographically spread computational
resources. But it is often not all clear (a) how to move data when available from multiple sources
or (b) how to move data to multiple compute resources to achieve an optimal usage of available
resources. Constraint programming (CP) is a technique from artificial intelligence and opera-
tions research allowing to find solutions in a multi-dimensional space of variables. We present a
method of creating a CP model consisting of sites, links and their attributes such as bandwidth
for grid network data transfer also considering user tasks as part of the objective function for an
optimal solution. We will explore and explain trade-off between schedule generation time and
divergence from the optimal solution and show how to improve and render viable the solution’s
finding time by using search tree time limit, approximations, restrictions such as symmetry break-
ing or grouping similar tasks together, or generating sequence of optimal schedules by splitting
the input problem. Results of data transfer simulation for each case will also include a well known
Peer-2-Peer model, and time taken to generate a schedule as well as time needed for a schedule
execution will be compared to a CP optimal solution. We will additionally present a possible im-
plementation aimed to bring a distributed datasets (multiple sources) to a given site in a minimal

Submited: ACAT2008
Status: Accepted, PoS(ACAT08)039 (see also arXiv:0901.0148v1)

Keywords:data transfers, scheduling