Introduction
Web Service Composition (WSC) is a fundamental process in service-oriented computing, enabling the creation of complex applications by aggregating individual software modules. As cloud computing and big data have evolved, a more challenging variant has emerged: Distributed Data-intensive Web Service Composition (DWSC). Unlike traditional WSC, which often assumes a centralized environment where data transfer costs are negligible, DWSC involves services and massive datasets scattered across geographically distributed nodes. In this context, the "Quality of Service" (QoS) is dominated by communication latency and the overhead of moving large volumes of data across the network. This paper presents a novel Memetic Algorithm (MA) specifically designed to optimize workflows in these distributed environments by targeting network bottlenecks through a flexible local search mechanism.
The Problem: Beyond Centralized Optimization
Most existing composition algorithms treat the network as a transparent layer, focusing primarily on the execution time of individual services. However, in data-intensive scenarios, the time required to transmit data between services often exceeds the actual processing time. If two services in a workflow are located on opposite sides of the globe, the resulting communication delay becomes a crippling bottleneck.
To address this, the authors frame DWSC as a global optimization problem where the physical location of services and data is a primary constraint. The goal is to find a service sequence that satisfies functional requirements while minimizing a fitness function composed of execution time, communication cost, and overall network latency.
Methodology: The MA-DWSC Approach
The researchers propose a Memetic Algorithm (MA), hybridizing the global exploration capabilities of a Genetic Algorithm (GA) with a specialized local search phase for fine-tuning solutions. The approach consists of several key innovations:
1. Indirect Representation and Decoding
Solutions are encoded as sequences of services. A dedicated decoding step transforms these sequences into a feasible Directed Acyclic Graph (DAG) workflow. This ensures that all functional dependencies are met while allowing the algorithm to operate on a simplified representation during the evolutionary process.
2. Distance-Guided LCS Crossover
Rather than employing random crossover operators, the algorithm utilizes the "Longest Common Subsequence" (LCS) between two parent solutions. This preserves high-quality segments of the workflow that have already been optimized. The crossover points are determined using service distance data, ensuring that the recombination process favors the preservation of geographically proximate service clusters.
3. Flexible Local Search (The Core Innovation)
The defining feature of this algorithm is its "surgical" approach to local refinement. Instead of applying local search randomly, the algorithm identifies the specific "bottleneck"—the link between two services with the highest communication delay. It then applies two distinct strategies:
- Type-I Search: Replaces a single service at one end of the bottleneck with a closer alternative from the repository.
- Type-II Search (Flexible): Replaces an entire segment or path of the workflow. This allows the algorithm to reroute data through a completely different set of nodes, effectively bypassing congested or distant network paths.
Experimental Setup
The approach was evaluated using the standard WSC-2008 and WSC-2009 benchmark datasets. Since these benchmarks lack geographic metadata, the authors integrated coordinate information from the WS-dream dataset. This integration allowed for the simulation of a realistic distributed network where communication costs are derived from the physical distance between servers.
Key Results and Insights
The proposed method, MA-DWSC(II), was compared against state-of-the-art memetic baselines. The findings highlight several critical aspects of distributed service composition:
- Superior Workflow Quality: In nearly all test cases, MA-DWSC(II) achieved the lowest (best) fitness scores. By specifically targeting bottlenecks, the algorithm consistently found workflows with a superior balance of execution time and communication cost.
- The Power of Path Replacement: One of the most significant findings was the efficacy of Type-II search. While Type-I (single service) replacement only improved solutions in 1-4% of cases, the flexible Type-II (path) replacement led to improvements in 40-50% of cases. This suggests that resolving network bottlenecks often requires structural rerouting rather than simple service swaps.
- Computational Efficiency: Despite the added complexity of the local search, MA-DWSC(II) demonstrated competitive execution times. In larger tasks, such as WSC09-04, the targeted nature of the search allowed the algorithm to converge on high-quality solutions faster than broader, less focused algorithms.
- Statistical Significance: ANOVA tests (p < 0.05) confirmed that the improvements provided by the flexible local search were statistically significant across various task complexities.
Conclusion and Future Work
This research demonstrates that in the era of distributed data-intensive computing, service location is a first-class citizen in optimization. By incorporating geographic awareness and flexible path-based local search, the MA-DWSC algorithm effectively mitigates the impact of network bottlenecks.
Future research directions include testing the algorithm in live, fluctuating wide-area networks where bandwidth changes dynamically, and exploring multi-objective optimization to allow users to define more nuanced trade-offs between cost, speed, and reliability. Additionally, as service repositories scale into the millions, further refinements to the local search efficiency will be necessary to maintain performance.
Summary updated