Service composition for generic service graphs

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.