PaperlayerView exact revision on arXiv

Source-linked AI summary

A Time-driven Data Placement Strategy for a Scientific Workflow Combining Edge Computing and Cloud Computing

Bing Lin, Fangning Zhu, Jianshan Zhang, Jiaqing Chen, Xing Chen, Neal N. Xiong, Jaime Lloret Mauri

arXiv:1901.07216v2cs.DC

TL;DR

Scientific workflow data placement must reduce transmission delays while respecting limited edge storage and fixed private-dataset locations. The paper proposes GA-DPSO, combining self-adaptive discrete particle swarm optimization with genetic operators and hybrid-environment factors. Experiments report reduced transmission time during workflow execution, with preprocessing also reducing search effort for some workflows.

  • Problem

    Hybrid cloud-edge workflows face transmission delays because large datasets span datacenters, while edge storage is limited and private datasets have fixed locations.

  • Method

    GA-DPSO combines self-adaptive discrete particle swarm optimization with genetic operators and considers bandwidth, edge-datacenter count, and edge storage capacity.

  • Results

    GA-DPSO effectively reduced data transmission time during workflow execution combining edge computing and cloud computing.

  • Takeaways & Limitations

    Bandwidth-aware placement can reduce transmission time, while preprocessing reduces the dataset representation and search iterations for some workflows.

Abstract

from arXiv · show

Compared to traditional distributed computing environments such as grids, cloud computing provides a more cost-effective way to deploy scientific workflows. Each task of a scientific workflow requires several large datasets that are located in different datacenters from the cloud computing environment, resulting in serious data transmission delays. Edge computing reduces the data transmission delays and supports the fixed storing manner for scientific workflow private datasets, but there is a bottleneck in its storage capacity. It is a challenge to combine the advantages of both edge computing and cloud computing to rationalize the data placement of scientific workflow, and optimize the data transmission time across different datacenters. Traditional data placement strategies maintain load balancing with a given number of datacenters, which results in a large data transmission time. In this study, a self-adaptive discrete particle swarm optimization algorithm with genetic algorithm operators (GA-DPSO) was proposed to optimize the data transmission time when placing data for a scientific workflow. This approach considered the characteristics of data placement combining edge computing and cloud computing. In addition, it considered the impact factors impacting transmission delay, such as the band-width between datacenters, the number of edge datacenters, and the storage capacity of edge datacenters. The crossover operator and mutation operator of the genetic algorithm were adopted to avoid the premature convergence of the traditional particle swarm optimization algorithm, which enhanced the diversity of population evolution and effectively reduced the data transmission time. The experimental results show that the data placement strategy based on GA-DPSO can effectively reduce the data transmission time during workflow execution combining edge computing and cloud computing.

I. INTRODUCTION

Scientific workflows combine large datasets, complex dependencies, and distributed execution, creating data-transmission delays across cloud and edge datacenters. The study proposes GA-DPSO to place data while accounting for bandwidth, edge capacity, and privacy constraints.

  • Cloud resources reduce deployment cost but remote placement of large workflow datasets causes serious transmission delays.
  • Edge computing reduces transmission delays and protects private datasets, but its limited storage cannot hold all workflow datasets.
  • Fixed private-dataset placement, limited inter-datacenter bandwidth, and large data movement make hybrid cloud-edge placement difficult.
  • Effective placement should increase within-datacenter cohesion, reduce cross-datacenter coupling, and respect edge storage and privacy constraints.
  • GA-DPSO combines discrete particle swarm optimization with genetic operators to reduce transmission time during hybrid workflow execution.Crossover and mutation operators are used to avoid premature convergence and enhance population diversity.
  • The strategy explicitly considers bandwidth between datacenters, the number of edge datacenters, and edge-datacenter storage capacity.
  • Workflow preprocessing compresses the dataset representation to improve GA-DPSO execution efficiency.

III. PROBLEM DEFINITION AND ANALYSIS

The problem models data placement in a hybrid cloud-edge environment as minimizing total transmission time while satisfying datacenter storage and placement constraints. Workflow structure, dataset attributes, bandwidth, and execution prerequisites define the optimization setting.

  • The placement objective is minimum total data transmission time subject to each datacenter’s storage-capacity constraint.
  • The hybrid environment contains remote cloud datacenters and near-end edge datacenters, with the model focusing on storage capacity rather than computing capacity.
  • Cloud datacenters store public datasets, whereas edge datacenters can store both private and public datasets within their capacities.
  • A scientific workflow is represented as a directed acyclic graph whose tasks, dependencies, and datasets determine execution order and data requirements.A task cannot start until all precursor tasks have completed.
  • Tasks require input datasets to be present at their assigned datacenter, while dataset records track size, generating task, original location, and final placement.
  • Placement maps datasets from original to final datacenters, and binary variables indicate whether transmissions occur and where datasets are stored.
  • Transmission time is determined using dataset size and inter-datacenter bandwidth, with total time aggregating the transfers required by placement.

B. Problem Analysis

A workflow example shows that minimizing data movement does not necessarily minimize transmission time when bandwidth differs across datacenters. The proposed analysis therefore evaluates placement using bandwidth-aware transmission time.

  • The example contains five tasks, six datasets, private datasets fixed at edge datacenters, and task locations constrained by their private inputs.
  • 1953 s is the transmission time for the matrix-partitioning placement, which moves 27 GB across four data movements.
  • 1023 s is the transmission time for the optimal placement, despite five data movements totaling 30 GB.
  • Bandwidth-aware placement can outperform dependency-based placement even when it increases both the number and amount of data movement.
  • GA-DPSO places datasets while considering bandwidth, the number of edge datacenters, and edge-datacenter storage capacity.

IV. DATA PLACEMENT STRATEGY BASED ON GA-DPSO

The proposed strategy combines preprocessing with GA-DPSO to find data placements that minimize transmission time across edge and cloud datacenters.

  • GA-DPSO optimizes the mapping from datasets to datacenters to minimize total data transmission time.The strategy is designed for workflow execution combining edge computing and cloud computing.

A. Preprocessing for a scientific workflow

Preprocessing merges cut-edge datasets to compress the workflow representation before applying GA-DPSO. This reduces coding dimensionality but can constrain the final placement.

  • Preprocessing identifies cut-edge datasets and merges each into a new dataset.The procedure repeats until no cut-edge datasets remain.
  • Merging datasets reduces the number of datasets and improves GA-DPSO execution efficiency.The reduced dataset count lowers the algorithm's coding dimension.
  • Preprocessing may affect the final data placement result by forcing merged datasets to share a datacenter.For example, ds5 and ds6 must be stored together after preprocessing, whereas they may otherwise use different edge datacenters.

B. GA-DOSO

GA-DPSO uses discrete particles to represent data placements and adapts PSO with genetic operators for constrained edge-cloud optimization. Its adaptive search accounts for feasibility, transmission time, and exploration needs.

  • Problem encoding: Each particle dimension stores the datacenter number assigned to the corresponding dataset.This encoding satisfies non-redundancy and completeness, but some particles violate edge-datacenter capacity constraints.
  • Fitness function: A feasible particle satisfies edge-datacenter storage capacity, whereas an infeasible particle exceeds at least one such capacity.These feasibility conditions determine whether an encoded placement can be used as a candidate solution.
  • Fitness function: The fitness comparison prioritizes feasible particles and otherwise compares particles using data transmission time.When both particles are feasible, the smaller transmission time is preferred; when one is infeasible, the feasible particle is selected.
  • Update strategy: GA-DPSO replaces traditional PSO update components with crossover and mutation operators to reduce premature convergence.Crossover updates individual and social cognition components, while mutation updates the inertia component.
  • Update strategy: Crossover and mutation can change an encoded particle between feasible and infeasible states.Crossover exchanges particle segments with personal-best or global-best particles, while mutation changes a public-dataset position within the datacenter range.
  • Parameter adaptation: The adaptive inertia weight increases global search when the current particle differs substantially from the global best.When the difference is smaller, the strategy emphasizes local search and faster convergence.

V. EXPERIMENTAL RESULTS AND ANALYSIS

The experiments used a fixed computing environment and specified population, iteration, and parameter settings for evaluating GA-DPSO.

  • Experiments ran on Win8 64-bit with an Intel i7-7500U 2.90 GHz processor and 8GB of RAM.The reported setup provides the hardware and operating-system context for the simulations.
  • The acceleration coefficients were set as c1 start = 0.9, c1 end = 0.2, c2 start = 0.9, and c2 end = 0.4.These values define the reported coefficient schedule for the experiments.

A. Experimental setup

The experiments use five partly synthetic scientific-workflow types and vary workflow scale, bandwidth, and edge-storage conditions to evaluate data transmission time.

  • Workflow datasets: Experiments use CyberShake, Montage, SIPHT, Epigenomics, and LIGO workflows spanning earthquake science, astronomy, bioinformatics, biogenetics, and gravitational physics.Each workflow type has different dataset counts and dependency structures recorded in XML files.
  • Experimental parameters: The storage capacity of three edge datacenters is set to 2.6 times the benchmark capacity.This parameter belongs to the reported experimental configuration.
  • Basic experiment: The basic experiment evaluates data transmission time for small, medium, and large workflows across different placement strategies.The results are organized in Fig. 6 for the three workflow scales.
  • Experimental parameters: Private datasets comprise 25% of each workflow, while bandwidth across datacenters is specified in M/s.The setup also varies edge-datacenter storage capacity in the follow-up experiments.

B. Competitive algorithms

GA-DPSO is compared with adapted DCO-k-means and GA-based placement strategies, plus NGA-DPSO without preprocessing, using bandwidth-aware data-dependency modeling.

  • Comparison algorithms: DCO-k-means clusters datasets by dependency and partitions them into data blocks, but its dependency degree ignores bandwidth.The modified strategy is adapted to the time-driven edge–cloud setting.
  • Bandwidth-aware modeling: The revised dependency degree counts tasks accepting both datasets and incorporates pre-placement bandwidth between their datacenters.This definition adds bandwidth influence when optimizing transmission time.
  • Comparison algorithms: The GS strategy uses binary genetic-algorithm encoding to optimize data movements, moved-data volume, and transmission time.Its original cloud formulation ignored private datasets and placed all datasets in a cloud datacenter.
  • Preprocessing comparison: NGA-DPSO omits preprocessing and serves as a comparison algorithm for measuring preprocessing effects.GS, GA-DPSO, and NGA-DPSO terminate after retaining their original value for 80 iterations.

C. Experimental results and analysis

Across the experiments, GA-DPSO and NGA-DPSO generally achieve the lowest transmission times, while workflow scale, edge capacity, datacenter count, and bandwidth materially affect performance.

  • Basic results: GA-DPSO and NGA-DPSO generally perform best, while GS performs worse and DCO-k-means performs worst in the basic experiment.For Epigenomics and Montage, NGA-DPSO is slightly better than GA-DPSO, with average transmission time reduced by approximately 1.5%.
  • Basic results: 1.5%: NGA-DPSO reduces average data transmission time relative to GA-DPSO for Epigenomics and Montage.The difference is attributed to preprocessing affecting final placement.
  • Workflow scale: 47, 77, and 1501 datasets: LIGO small, medium, and large workflows transmit progressively more data as workflow scale increases.Their total dataset sizes are 2.47 TB, 4.08 TB, and 82.21 TB, respectively.
  • Preprocessing effects: Preprocessing reduces Epigenomics datasets from 77 to 50, exceeding a 35% compression rate and reducing GA-DPSO iterations by approximately 10% versus NGA-DPSO for selected workflows.The compressed encoding space improves GA-DPSO execution efficiency and reduces execution time for workflows with high compression ratios.
  • Number of edge datacenters: As edge-datacenter count increases, transmission time increases because fixed total edge storage is divided among more datacenters.Lower per-datacenter capacity leaves fewer or smaller datasets stored locally.
  • Edge storage capacity: More edge storage decreases transmission time by allowing more datasets to remain in edge datacenters; GA-DPSO and NGA-DPSO store all Epigenomics datasets at the edge above a capacity multiplier of 3.DCO-k-means requires a multiplier above 8 for the same Epigenomics placement outcome.
  • Bandwidth sensitivity: Increasing inter-datacenter bandwidth significantly decreases transmission time without changing the final placement produced by each strategy.The bandwidth sensitivity experiments use multipliers of 0.5, 0.8, 1.5, 3, and 5 relative to the basic experiment.

D. Industrial applications

The GA-DPSO placement strategy combines edge and cloud storage resources to reduce scientific-workflow transmission time in time-sensitive applications.

  • Application relevance: GA-DPSO can effectively reduce scientific-workflow data transmission time and improve augmented-reality application user experience.The paper frames data transmission time as decisive for time-sensitive applications.

VI. CONCLUSION

GA-DPSO reduced data transmission time for scientific workflows combining edge and cloud computing. Transmission time increased with more edge datacenters, decreased with greater bandwidth, and could reach zero when an edge datacenter stored all datasets.

  • GA-DPSO effectively reduced data transmission time during workflow execution across edge and cloud datacenters.The strategy was proposed to address serious transmission delays in combined edge-cloud data placement.
  • Increasing the number of edge datacenters increased data transmission time when their total storage capacity remained unchanged.More edge datacenters made data placement more decentralized.
  • Greater bandwidth across datacenters decreased data transmission time, while sufficient edge storage enabled zero transmission time for all datasets.The final placement for each workflow did not change with different strategies.
  • Future work will consider private-dataset proportions, heterogeneous edge storage capacities, and transmission cost alongside time.The authors note that transmitting data among edge and cloud datacenters costs both time and money.
Loading 1901.07216v2…