Service sharing for streaming video multicast
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal
Related Research Unit(s)
|Journal / Publication||IEEE Transactions on Multimedia|
|Publication status||Published - Nov 2008|
|Link to Scopus||https://www.scopus.com/record/display.uri?eid=2-s2.0-56549114590&origin=recordpage|
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.
- Greedy algorithm, NP-hard, Service cost optimization, Service invocation order, Service-oriented architecture