On approximating a multicast routing tree with multiple Quality-of-Service constraints

Jun Huang*, Yoshiaki Tanaka, Yan Ma

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


Multicast routing with Quality-of-Service (QoS) guarantees is the key to efficient content distribution and sharing. Developing QoS-aware multicast routing algorithm is an important open topic. This paper investigates QoS-aware multicast routing problem with K constraints where K > 2. The contributions made in this paper include a heuristic that employs the concept of nonlinear combination to extend the existing well-known algorithm for fast computation of a QoS multicast tree, and a Fully Polynomial Time Approximation Scheme (FPTAS) to approximate a multicast routing tree with QoS guarantees. The theoretical analyses and simulations conducted on both algorithms show that the algorithms developed in this paper are general and flexible, thus are applicable to the various networking systems.

Original languageEnglish
Pages (from-to)2005-2012
Number of pages8
JournalIEICE Transactions on Communications
Issue number6
Publication statusPublished - 2012 Jun


  • Approximation algorithm
  • Heuristic
  • Multicast tree
  • Nonlinear combination
  • QoS routing

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On approximating a multicast routing tree with multiple Quality-of-Service constraints'. Together they form a unique fingerprint.

Cite this