Construction of an efficient overlay multicast infrastructure for real-time applications

Suman Banerjee*, Christopher Kommareddy, Koushik Kar, Bobby Bhattacharjee, Samir Khuller

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

302 Scopus citations


We consider an overlay architecture where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs are organized into an overlay and act as application-layer multicast forwarding entities for a set of clients. We present a decentralized scheme that organizes the MSNs into an appropriate overlay structure that is particularly beneficial for real-time applications. We formulate our optimization criterion as a "degree-constrained minimum average-latency problem" which is known to be NP-Hard. A key feature of this formulation is that it gives a dynamic priority to different MSNs based on the size of its service set. Our proposed approach iteratively modifies the overlay tree using localized transformations to adapt with changing distribution of MSNs, clients, as well as network conditions. We show that a centralized greedy approach to this problem does not perform quite as well, while our distributed iterative scheme efficientlyconverges to near-optimal solutions.

Original languageEnglish (US)
Pages (from-to)1521-1531
Number of pages11
JournalProceedings - IEEE INFOCOM
StatePublished - 2003
Event22nd Annual Joint Conference on the IEEE Computer and Communications Societies - San Francisco, CA, United States
Duration: Mar 30 2003Apr 3 2003

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Construction of an efficient overlay multicast infrastructure for real-time applications'. Together they form a unique fingerprint.

Cite this