<title>Service composition for advanced multimedia applications</title>

Liang Jin, Klara NahrstedtProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2005 · DOI

TL;DR

This paper tackles the challenge of dynamically composing distributed services to deliver advanced multimedia experiences, especially those involving multiple sources and destinations. They introduce a novel heuristic algorithm that efficiently finds cost-effective service compositions while allowing a trade-off between computation and solution quality, proving effective even in resource-constrained environments.

What Problem Does This Paper Address?

The internet is increasingly built on distributed, autonomous services. Dynamically composing these services offers a powerful way to create new functionalities, particularly for advanced multimedia applications. Think of scenarios where video streams from multiple sources are combined, translated, and then delivered to various devices with different capabilities. Previous research often focused on simpler, single-source-to-single-destination scenarios. This paper addresses the more complex problem of composing services for advanced multimedia applications that involve multiple content sources, aggregation of data flows, and delivery to multiple, potentially heterogeneous, destinations. The core challenge is to select the right service instances and route data flows through them to satisfy Quality of Service (QoS) requirements while minimizing the overall cost of the composed service.

Methods

The authors formally define the service composition problem for advanced multimedia applications, proving it to be NP-hard. To address this complexity, they propose a greedy heuristic algorithm, inspired by Dijkstra's shortest path algorithm. This algorithm iteratively "grows" partial service compositions (paths or trees) by selecting the lowest-cost option at each step. A key innovation is the introduction of a parameter, nc, which controls the number of candidate partial solutions maintained for each (node, flow) pair. This allows the algorithm to trade off computation overhead for potentially better results, especially when network resources are scarce. The algorithm is designed to handle three types of service specification graphs: Single Source Single Destination (SSSD), Multiple Source Single Destination (MSSD), and Multiple Source Multiple Destination (MSMD).

Datasets

Not discussed in the paper. The authors generated synthetic network topologies and service specification graphs for their experiments.

Key Insights and Ideas

  • The NP-hardness of advanced composition: The paper formally demonstrates that composing services for complex multimedia scenarios (multiple sources/destinations) is computationally challenging, necessitating heuristic approaches.
  • The nc parameter for trade-offs: The introduction of nc is a crucial insight, providing a tunable knob to balance computational cost with the quality of the service composition. This is particularly valuable in real-world scenarios where resources might be limited.
  • "Growing" partial solutions: The algorithm's iterative approach of extending partial compositions, rather than trying to find a complete solution at once, is an effective strategy for navigating the complex search space.
  • Subpath suboptimality: The paper highlights that unlike standard shortest path problems, a locally optimal partial path doesn't guarantee a globally optimal solution. This justifies the need to keep multiple candidate partial paths, as managed by the nc parameter.

Key Results

The heuristic algorithm demonstrated strong performance across various network topologies and service specification graph types (SSSD, MSSD, MSMD).

  • Cost Efficiency: In lightly loaded networks, the heuristic solutions were very close to a computed lower bound, with the average cost being within 1% of the lower bound even with nc=1. Increasing nc further improved the results.
  • Resource Scarcity Performance: In resource-constrained environments, the algorithm's effectiveness was more pronounced. With nc=1, solutions could be up to 8% worse than the lower bound, but increasing nc significantly improved both cost and success ratio (probability of finding a solution). For instance, increasing nc from 1 to 2 improved the success ratio from 94% to 98% in low-resource scenarios.
  • Scalability: The algorithm showed good scaling properties, capable of computing solutions for requests with over 10 flows in a network of 500 nodes within seconds. The authors suggest that using a min-heap data structure for active labels could further improve performance.

Limitations and Future Work

  • Suboptimality: While the algorithm performs well, it is a heuristic and does not guarantee the absolute optimal solution. The paper acknowledges that a non-optimal partial path might sometimes lead to a better overall solution.
  • Centralized vs. Decentralized: The current algorithm is presented in a centralized manner. The authors suggest that it can be decentralized using techniques similar to the GHS distributed spanning tree algorithm.
  • Synthetic Data: Experiments were conducted on synthetically generated network topologies and service graphs. Evaluating on real-world network traces could provide further validation.
  • QoS Metrics: The paper focuses on resource requirements (bandwidth) as the primary QoS metric. Future work could explore incorporating a wider range of QoS parameters.

Summary updated

Abstract

By composing distributed, autonomous services dynamically to provide new functionalities, service composition provides an attractive way for customized multimedia content production and delivery. Previous research work has addressed various aspects of service composition such as composibility, QoS-awareness, and load balancing. However, most of the work has focused on applications where data flow from a single source is processed by intermediate services and then delivered to a single destination. In this paper, we address the service composition problem for advanced multimedia applications where data flows from multiple content sources are processed and aggregated into a composite flow, which is then delivered to one or more destinations, possibly after being customized for each receiver. We formally define the problem and prove its NP hardness. We also design a heuristic algorithm to solve the problem. Our algorithm has the following attractive features: (1) it is effective at finding low cost composition solutions; (2) it has the ability to trade off computation overhead for better results; (3) it is efficient and can scale to relatively large number of network nodes and component services.
BibTeX
@inproceedings{jin2005lt,
  author = {Liang Jin and Klara Nahrstedt},
  title = {{\<title\>Service composition for advanced multimedia applications\</title\>}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2005},
  doi = {10.1117/12.592307},
}
Figure