Cost-optimal multicast trees for mufti-source data flows in multimedia distribution Conference Paper uri icon

abstract

  • From a graph-theoretical perspective, the problem of constructing multicast distribution paths, modeled as 'steiner trees', is NP-complete. So, many heuristics-based algorithms are available to generate near-optimal trees. Typically, an algorithm first assigns the edge costs for all links, and then examines various candidate paths for interconnecting a given set of nodes. This strategy does not work well for the evolving multimedia application configurations (such as audio-video and image distributions) where it is often necessary to construct multiple distribution paths, viz., one per media data stream. This is because the overlapping of multiple tree segments over a common link forces the link cost to change, based on the delay and bandwidth characteristics of data streams flowing over these segments. Accordingly, algorithms that hitherto have assumed non-varying link costs during various phases of a run now need to take into account the variability of link costs as candidate trees with different levels of path overlapping are examined in a given run. In other words, as an algorithm runs by examining various paths, the link costs change. The paper embarks on a study of heuristics-based algorithms to tackle this 'modified steiner tree' problem. The algorithms allow more cost-efficient routing of data than feasible otherwise with a classical treatment of the 'steiner tree' problem.

published proceedings

  • IEEE INFOCOM 2001: THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-3, PROCEEDINGS

author list (cited authors)

  • Ravindran, K., Sabbir, A., Loguinov, D., & Bloom, G. S.

complete list of authors

  • Ravindran, K||Sabbir, A||Loguinov, D||Bloom, GS

publication date

  • January 2001