Innovative Method of the Evaluation of Multicriterial Multicast Routing Algorithms

• Autorzy: Stachowiak K. , Zwierzykowski P.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2013
• Tom: nr 1
• Strony: 49--55
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Stachowiak K.

autor

Zwierzykowski P.

• Chair of Communication and Computer Networks, Faculty of Electronics and Telecommunications, Poznań University of Technology, Pl. Marii Skłodowskiej-Curie 5, 60-965 Poznań, Poland,

Bibliografia

• [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.
• [2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: theory, algorithms, and applications. Upper Saddle River: Prentice-Hall, 1993.
• [3] F. Gang, “A multi-constrained multicast QoS routing algorithm”, Comp. Commun., vol. 29, no. 10, pp. 1811–1822, 2006.
• [4] H. Jiang, P. Yan, J. Zhou, L. Chen, and M. Wu, “Multi-constrained least cost QoS routing algorithm”, in Int. Conf. Telecom. ICT 2004, J. de Souza, P. Dini, and P. Lorenz, Eds. LNCS, Berlin-Heidelberg: Springer, 2004, vol. 3124, pp. 704–710.
• [5] Q. Zhu, M. Parsa, and J. J. Garcia-Luna-Aceves, “A source-based al- gorithm 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
• [6] T. Korkmaz and M. Krunz, “Multi-constrained optimal path selection”, in Proc. IEEE INFOCOM 2001, Anchorage, Alaska, USA, 2001, pp. 834–843.
• [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.
• [8] F. Gang, “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
• [9] K. Stachowiak, M. Piechowiak, and P. Zwierzykowski, “The effectiveness of multicast trees with delay constraints”, in Proc. 31th Int. Conf. Inform. Syst. Architec. Technol. ISAT 2010, Szklarska Poręba, Poland, 2010, pp. 199–209.
• [10] A. Medina, A. Lakhina, I. Matta, and J. Byers, “BRITE: An approach to universal topology generation”, in Proc. 9th Int. Worksh. Model. Analysis. Simul. Comp. Telecomm. Syst. MASCOTS 2001, Cincinnati, OH, USA, 2001, pp. 346–356.
• [11] C. Jin, Q. Chen, and S. Jamin, “Inet: Internet topology generator”, University of Michigan at Ann Arbor, Tech. Research Rep. CSE-TR-433-00, 2000.
• [12] E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, “How to Model an Internetwork”, Proc. IEEE INFOCOM 1996, San Francisco, CA, USA, 1996, pp. 594–602.
• [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.
• [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.
• [15] M. Newman, A.-L. Barabasi, and D. J. Watts, The Structure and Dynamics of Networks (Princeton Studies in Complexity). Princeton: Princeton University Press, 2006.
• [16] R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach. New York: Cambridge University Press, 2004.
• [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.
• [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. Telecom. Netw. Strat. Planning Symp. NETWORKS 2010, Warsaw, Poland, 2010, pp. 197–202.
• [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.
• [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.
• [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
• [22] B. Waxman, “Routing of multipoint connections”, IEEE J. Selec. Areas Commun., vol. 6, no. 9, pp. 1617–1622, 1988.
• [23] A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks”, Science, vol. 286, pp. 509–912, 1999 [Online]. Available: http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/9910332
• [24] A. Juttner, B. Szviatovski, I. Mecs, and Z. Rajko, “Lagrange relaxation based method for the QoS routing problem”, in Proc. IEEE INFOCOM 2001, Anchorage, Alaska, USA, 2001, vol. 2, pp. 859–868.
• [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