OMNI: 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 journalArticlepeer-review

50 Scopus citations


We consider an overlay architecture (called OMNI) 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 and 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 efficiently converges to near-optimal solutions.

Original languageEnglish (US)
Pages (from-to)826-841
Number of pages16
JournalComputer Networks
Issue number6
StatePublished - Apr 13 2006


  • Application-layer multicast
  • Minimum latency problem
  • Overlay multicast

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'OMNI: An efficient overlay multicast infrastructure for real-time applications'. Together they form a unique fingerprint.

Cite this