Innovative Method of the Evaluation of Multicriterial Multicast Routing Algorithms

Authors

DOI:

https://doi.org/10.26636/jtit.2013.1.1201

Keywords:

evaluation, graph algorithms, multicast, QoS, resource drainage, routing

Abstract

Theoretical considerations of the multicast Quality of Service (QoS) routing have been a rapidly developing and dynamic research area for years. Several algorithms derived from different approaches have been proposed, while the pool of valid solutions to the problem is steadily growing. When new solutions are compared with their predecessors, as much information as possible about their characteristics and differences is needed. Both the graph theory and the optimization theory provide robust and objective means of comparing not only algorithms, but also the results they produce. However, any possible extension to the comparison methods is vital and can bring interesting new information that would eventually lead to innovative conclusions. This article presents a method, derived from practice and experience, that simulates the drainage of resources accumulated by consecutive communication allocations. The nature of this comparison is an extension to the classical measurement of the success ratio and this creates a context of the continuous measure of a success rather than a simple binary value. In this article such a method with regard to algorithms optimizing multicast problems for more than two criteria is used for the first time and leads to an interesting conclusion about the influence of the number of the criteria on the result.

Downloads

Download data is not yet available.

References

[1] S. Chen and K. Nahrstedt, „An overview of quality of service routing for next-generation high-speed networks: problems and solutions”, IEEE Netw., vol. 12, pp. 64-79, 1998.
View in Google Scholar

[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: theory, algorithms, and applications. Upper Saddle River: Prentice-Hall, 1993.
View in Google Scholar

[3] G. Feng, „A multi-constrained multicast QoS routing algorithm”, Comp. Commun., vol. 29, no. 10, pp. 1811-1822, 2006.
View in Google Scholar

[4] H. Jiang, P. Yan, J. Zhou, L. Chen, and M. Wu, „Multi-constrained least cost QoS routing algorithm”, in Int. Conf. Telecommun. ICT 2004, J. de Souza, P. Dini, and P. Lorenz, Eds. LNCS, Berlin-Heidelberg: Springer, 2004, vol. 3124, pp. 704-710.
View in Google Scholar

[5] Q. Zhu, M. Parsa, and J. J. Garcia-Luna-Aceves, „A source-based algorithm for delay-constrained minimum-cost multicasting”, in Proc. 14th Ann. Joint Conf. IEEE Comp. Commun. Soc. INFOCOM’95, Washington, DC, USA, 1995, pp. 377-386 [Online]. Available: http://dl.acm.org/citation.cfm?id=850956.854068
View in Google Scholar

[6] T. Korkmaz and M. Krunz, „Multi-constrained optimal path selection”, in Proc. IEEE INFOCOM 2001, Anchorage, Alaska, USA, 2001, pp. 834-843.
View in Google Scholar

[7] G. Feng, K. Makki, and N. Pissinou, „Efficient implementations of a delay-constrained least-cost multicast algorithm”, J. Commun. Netw., vol. 4, no. 3, pp. 246-255, 2002.
View in Google Scholar

[8] G. Feng, „The revisit of QoS routing based on non-linear lagrange relaxation: research articles”, Int. J. Commun. Syst., vol. 20, pp. 9-22, January 2007 [Online]. Available: http://dl.acm.org/citation.cfm?id=1189026.1189028
View in Google Scholar

[9] K. Stachowiak, M. Piechowiak, and P. Zwierzykowski, „The effectiveness of multicast trees with delay constraints”, in Proc. 31st Int. Conf. Inform. Syst. Architec. Technol. ISAT 2010, Szklarska Poręba, Poland, 2010, pp. 199-209.
View in Google Scholar

[10] A. Medina, A. Lakhina, I. Matta, and J. Byers, „BRITE: An approach to universal topology generation”, in Proc. 9th Int. Worksh. Model. Anal. Simul. Comput. Telecommun. Syst. MASCOTS 2001, Cincinnati, OH, USA, 2001, pp. 346-356.
View in Google Scholar

[11] C. Jin, Q. Chen, and S. Jamin, „Inet: Internet topology generator”, University of Michigan at Ann Arbor, Tech. Rep. CSE-TR-433-00, 2000.
View in Google Scholar

[12] E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, „How to Model an Internetwork”, in Proc. IEEE INFOCOM 1996, San Francisco, CA, USA, 1996, pp. 594-602.
View in Google Scholar

[13] E. W. Zegura, M. J. Donahoo, and K. L. Calvert, „A quantitative comparison of graph-based models for internet topology”, IEEE/ACM Trans. Netw., vol. 5, pp. 770-783, 1997.
View in Google Scholar

[14] M. Piechowiak and P. Zwierzykowski, „Efficiency analysis of multicast routing algorithms in large networks”, in Proc. 3rd Int. Conf. Netw. Serv. ICNS 2007, Athens, Greece, 2007, pp. 101-106.
View in Google Scholar

[15] M. Newman, A.-L. Barabási, and D. J. Watts, The Structure and Dynamics of Networks (Princeton Studies in Complexity). Princeton: Princeton University Press, 2006.
View in Google Scholar

[16] R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach. New York: Cambridge University Press, 2004.
View in Google Scholar

[17] K. Stachowiak, J. Weissenberg, and P. Zwierzykowski, „Lagrangian relaxation in the multicriterial routing”, in Proc. IEEE AFRICON 2011, Livingstone, Zambia, 2011, pp. 1-6.
View in Google Scholar

[18] M. Piechowiak, P. Zwierzykowski, and M. Stasiak, „Multicast routing algorithm for packet networks with the application of the lagrange relaxation”, in Proc. 14th Int. Telecommun. Netw. Strategy Plan. Symp. NETWORKS 2010, Warsaw, Poland, 2010, pp. 197-202.
View in Google Scholar

[19] M. Piechowiak, M. Stasiak, and P. Zwierzykowski, „The application of k-shortest path algorithm in multicast routing”, Theoret. Appl. Informat., vol. 21, no. 2, pp. 69-82, 2009.
View in Google Scholar

[20] M. Piechowiak and P. Zwierzykowski, „A new delay-constrained multicast routing algorithm for packet networks”, in Proc. IEEE AFRICON 2009, Nairobi, Kenya, 2009, pp. 1-5.
View in Google Scholar

[21] J. Moy, „OSPF Version 2”, RFC 2328 (Standard), Internet Engineering Task Force, Apr. 1998, updated by RFC 5709 [Online]. Available: http://www.ietf.org/rfc/rfc2328.txt
View in Google Scholar

[22] B. Waxman, „Routing of multipoint connections”, IEEE J. Select. Areas Commun., vol. 6, no. 9, pp. 1617-1622, 1988.
View in Google Scholar

[23] A.-L. Barabási and R. Albert, „Emergence of scaling in random networks”, Science, vol. 286, pp. 509-512, 1999 [Online]. Available: http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/9910332
View in Google Scholar

[24] A. Jüttner, B. Szviatovszki, I. Mécs, and Z. Rajkó, „Lagrange relaxation based method for the QoS routing problem”, in Proc. IEEE INFOCOM 2001, Anchorage, Alaska, USA, 2001, vol. 2, pp. 859-868.
View in Google Scholar

[25] A. H. Land and A. G. Doig, „An automatic method of solving discrete programming problems”, Econometrica, vol. 28, no. 3, pp. 497-520, 1960 [Online]. Available: http://jmvidal.cse.sc.edu/library/land60a.pdf
View in Google Scholar

Downloads

Published

2013-03-30

Issue

Section

RESEARCH ARTICLES

How to Cite

[1]
K. Stachowiak and P. Zwierzykowski, “Innovative Method of the Evaluation of Multicriterial Multicast Routing Algorithms”, JTIT, vol. 51, no. 1, pp. 49–55, Mar. 2013, doi: 10.26636/jtit.2013.1.1201.

Most read articles by the same author(s)