Service sharing for streaming video multicast

J. Wang, D.K.W. Chiu, Qing Li, M. Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)


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 languageEnglish
Article number4668491
Pages (from-to)1393-1405
Number of pages13
JournalIEEE Transactions on Multimedia
Issue number7
Publication statusPublished - 1 Nov 2008
Externally publishedYes


  • 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


Dive into the research topics of 'Service sharing for streaming video multicast'. Together they form a unique fingerprint.

Cite this