• Krzysztof Stachowiak


QoS enabled multicast routing is known to be of non-polynominal complexity, which leads to the necessity of using heuristic algorithms to find sub-optimal solutions to the problems of this class.
  The evaluation of such algorithms requires the use of the simulation techniques as the heuristics' results are of stochastic nature.
  Because of the problem complexity the simulation times increase significantly in the function of the network size, therefore the results presented in the literature are often limited to only small models.
  In this article the results of the evaluation of different multicast QoS routing algorithms have been presented for a wide range of network sizes reaching thousands of nodes.


Ahuja R.K., Magnanti T.L., Orlin J.B. (1993). Network flows: theory, algorithms, and applications.

Prentice-Hall, Inc., Upper Saddle River, NJ, USA.

Barabasi A-L., Albert R. (1999). Emergence of Scaling in Random Networks. Science, 286:509–912.

Chen S., Nahrstedt K. (1998). An Overview of Quality of Service Routing for Next-generation Highspeed Networks: Problems and Solutions. IEEE Network, 12:64–79.

Gang F. (2006). A Multi-constrained Multicast QoS Routing Algorithm. Computer Communications, 29(10):1811–1822.

Ghaboosi N., Haghighat A. (2007). Tabu Search Based Algorithms for Bandwidth-delay-constrained Least-cost Multicast Routing. Telecommunication Systems, 34:147–166.

Jin C., Chen Q., Jamin S. (2000). Inet: Internet Topology Generator. Technical Research Report CSE-TR-433-00, University of Michigan at Ann Arbor.

Li X., Ning Q., Jun-Ya Z., Yang-Qian L. (2008, July). An Improved GA for QoS Multicast Routing Algorithm. In Control and Decision Conference, 2008. CCDC 2008. Chinese, page 393–396, july 2008.

Molna ˛ar M., Bellabas A., Lahoud S. (2012). The Cost Optimal Solution of the Multi-constrained Multicast Routing Problem. Computer Networks, 56(13):3136–3149.

Stachowiak K., Weissenberg J., Zwierzykowski P. (2011, September). Lagrangian Relaxation in The Multicriterial Routing. In IEEE AFRICON, page 1–6, Livingstone, Zambia.

Stachowiak K., Piechowiak M., Zwierzykowski P. (2010). The Effectiveness of Multicast Trees With Delay Constraints. In Information Systems Architecture and Technology ISAT 2010, pp. 199–209.

Stachowiak K., Zwierzykowski P. (2013). Lagrangian Relaxation and Linear Intersection Based

QoS Routing Algorithm. International Journal of Electronics and Telecommunications, 58(4):307–314.

Stachowiak K., Zwierzykowski P. (2014). Rendezvous Point Based Approach to the Multiconstrained Multicast Routing Problem. AEU - International Journal of Electronics and Communications, 68(6):561 – 564.

Van Mieghem P., De Neve H., Kuipers F. (2001, November). Hop-by-hop Quality of Service Routing. Comput. Netw., 37(3-4):407–423.

Wan S., Zhang Y. (2009). Research of MultiConstrained Multicast Routing Qos Using Heuristic

Algorithm. In Information Engineering and Computer Science, 2009. ICIECS 2009. International

Conference on, pp. 1–4.

Waxman B.M. (1988, December). Routing of Multipoint Connections. Selected Areas in Communications, IEEE Journal on, 6(9):1617–1622.

Yao R., Fei J. (2010, May). New Multicast Routing Algorithm for QoS Routing in Communication

Network. In Future Computer and Communication (ICFCC), 2010 2nd International Conference

on, volume 3, page V3–379–V3–382.






Most read articles by the same author(s)