Service composition is a promising approach to multimedia service provisioning, due to its ability to dynamically produce new multimedia content, and to customize the content for individual client devices. 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 multimedia services that can be modeled as directed acyclic graphs (DAGs). We formally define the problem and prove its NP hardness. We also design a heuristic algorithm to solve the problem. Our simulation results show that the algorithm is effective at finding low-cost composition solutions, and can trade off computation overhead for better results. When compared with a hop-by-hop approach for service composition, our algorithm can find composition solutions that aress 10% smaller in cost, even when the hop-by-hop approach uses exhaustive searches.

Original languageEnglish (US)
Pages (from-to)568-581
Number of pages14
JournalMultimedia Systems
Issue number6
StatePublished - Jun 2006


  • Algorithm
  • Quality of service (QoS)
  • Service composition
  • Simulation

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Media Technology
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Service composition for generic service graphs'. Together they form a unique fingerprint.

Cite this