Abstract
In a general context, the sharing of intermediate service results among different processes is seldom feasible because parameters are often different and there may be transactional and side effects. However, in a streaming video multicast environment, a large number of users often request various similar processing on the same stream. Therefore, service sharing is feasible, with a large potential of savings in processing cost. In this paper, we study the problem of determining the service invocation orders for multiple service composition requests in a streaming video multicast with the aim of maximizing the service sharing. We first formally define the problem. After proving the problem is NP-Complete, we develop an optimal algorithm for the base case of two requests. Then for the general case, we develop two heuristic algorithms, namely, a global greedy algorithm and a local greedy algorithm using the optimal algorithm for the base case as the building block. The global greedy algorithm is designed for a system where the existing service composition requests can be recomposed with the arrival of a new request. The local greedy algorithm can be used in a system where the existing service composition requests do not change their service composition solutions with the arrival of a new request. We prove that the global greedy algorithm is a 2-approximation algorithm in terms of maximizing service sharing. Simulation results show that the greedy algorithms can save more service costs compared with a naive algorithm, and are effective compared with the cost lower bound. © 2008 IEEE.
Original language | English |
---|---|
Article number | 4668491 |
Pages (from-to) | 1393-1405 |
Number of pages | 13 |
Journal | IEEE Transactions on Multimedia |
Volume | 10 |
Issue number | 7 |
DOIs | |
Publication status | Published - 1 Nov 2008 |
Externally published | Yes |
Keywords
- Greedy algorithm
- NP-hard
- Service cost optimization
- Service invocation order
- Service-oriented architecture
ASJC Scopus subject areas
- Signal Processing
- Media Technology
- Computer Science Applications
- Electrical and Electronic Engineering