Lagrangian Relaxation and Linear Intersection Based QoS Routing Algorithm

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

Abstrakty

EN

Due to the process of network convergence, the variety of types of traffic transmitted over a single medium increases steeply. This phenomenon can be handled by the existing networking structure although the protocols that are used and, especially, the underlying routing protocols need to be improved. The problem of finding the shortest path on the Internet can no longer be easily defined as there is an increasing number of different characteristics to describe a point-to-point link. The definition of the shortest path may differ for different traffic types. Therefore, in the mathematical models used to solve the modern routing problems multiple criteria must be taken into account. One of the interesting classes of the optimization problem is the problem of finding the solution that is minimized against one of the criteria under certain constraints with regard to the others. In this paper, two algorithms solving this kind of problems are presented and compared with a new solution proposed by the authors.

Słowa kluczowe

EN

Lagrangian relaxation; quality of service; routing

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2012
• Tom: Vol. 58, No. 4
• Strony: 307--314
• Opis fizyczny: Bibliogr. 19 poz., wykr.

Twórcy

autor

Stachowiak K.

• Poznań University of Technology, Chair of Communication and Computer Networks, ul. Polanka 3, 60-965 Poznań, Poland

autor

Zwierzykowski P.

• Poznań University of Technology, Chair of Communication and Computer Networks, ul. Polanka 3, 60-965 Poznań, Poland

Bibliografia

• [1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: theory, algorithms, and applications. Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1993.
• [2] S. Chen and K. Nahrstedt, „An overview of quality of service routing for next-generation high-speed networks: problems and solutions”, IEEE Network, vol. 12, pp. 64-79, 1998, DOI: 10.1109/65.752646.
• [3] T. Korkmaz and M. Krunz, „Multi-Constrained Optimal Path Selection”, in Proceedings of IEEE International Conference on Computer Communications (INFOCOM), 2001, pp. 834-843.
• [4] 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, DOI: 10.1002/dac.v20:1. [Online]. Available: http://dl.acm.org/citation.cfm?id=1189026.1189028
• [5] H. Jiang, P. Yan, J. Zhou, L. Chen, and M. Wu, „Multi-constrained Least Cost QoS Routing Algorithm”, in International Conference on Telecommunications - ICT 2004, ser. Lecture Notes in Computer Science, J. de Souza, P. Dini, and P. Lorenz, Eds. Springer Berlin / Heidelberg, 2004, vol. 3124, pp. 704-710.
• [6] F. Gang, „A multi-constrained multicast QoS routing algorithm”, Computer Communications, vol. 29, no. 10, pp. 1811-1822, 2006.
• [7] C.-H. Chu, J. Gu, X. D. Hou, and Q. Gu, „A heuristic ant algorithm for solving QoS multicast routing problem”, in Proceedings of the 2002 Congress on Evolutionary Computation, vol. 2, 2002, pp. 1630-1635, DOI: 10.1109/CEC.2002.1004486.
• [8] X. Zhao, P. B. Luh, and J. Wang, „Surrogate gradient algorithm for lagrangian relaxation”, Journal of Optimization Theory and Applications, vol. 100, pp. 699-712, 1999.
• [9] Y. Xiao, K. Thulasiraman, and G. Xue, „The primal simplex approach to the QoS routing problem”, Quality of Service in Heterogeneous Wired/Wireless Networks, International Conference on, vol. 0, pp. 120-129, 2004, DOI: 10.1109/QSHINE.2004.51.
• [10] D. Bertsimas and J. B. Orlin, „A technique for speeding up the solution of the lagrangean dual”, Mathematical Programming 63, pp. 23-45, 1994.
• [11] A. Juttner, B. Szviatovski, I. Mecs, and Z. Rajko, „Lagrange relaxation based method for the QoS routing problem”, in Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, vol. 2, 2001, pp. 859-868, DOI: 10.1109/INFCOM.2001.916277.
• [12] E. W. Dijkstra, „A note on two problems in connexion with graphs”. Numerische Mathematik, vol. 1, pp. 269-271, 1959. [Online]. Available: http://gdzdoc.sub.uni-goettingen.de/sub/digbib/loader?did=D196313.
• [13] 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.
• [14] M. Piechowiak, M. Stasiak, and P. Zwierzykowski, „Multicast routing algorithm for packet networks with the application of the lagrange relaxation”, in Telecommunications Network Strategy and Planning Symposium (NETWORKS), 2010 14th International, sept. 2010, pp. 1-6, DOI: 10.1109/NETWKS.2010.5624921.
• [15] M. Piechowiak, „Evaluation of Heuristic Algorithms for Multicast Connections in Packet Networks”, Ph.D. dissertation, Poznan University of Technology, Poznan, Poland, 2010.
• [16] K. Stachowiak, J. Weissenberg, and P. Zwierzykowski, „Lagrangian relaxation in the multicriterial routing”, in AFRICON, 2011, sept. 2011, pp. 1-6, DOI: 10.1109/AFRCON.2011.6072070.
• [17] B. Waxman, „Routing of multipoint connections”, Selected Areas in Communications, IEEE Journal on, vol. 6, no. 9, pp. 1617-1622, dec 1988, DOI: 10.1109/49.12889.
• [18] L. Barolli, A. Koyama, H. Sawada, T. Suganuma, and N. Shiratori, „A New QoS Routing Approach for Multimedia Applications Based on Genetic Algorithms”, in Proceedings of the First International Symposium on Cyber Worlds (CW'02), ser. CW'02. Washington, DC, USA: IEEE Computer Society, 2002, pp. 289-296. [Online]. Available: http://dl.acm.org/citation.cfm?id=794192.794815.
• [19] M. Faloutsos, P. Faloutsos, and C. Faloutsos, „On power-law relationships of the internet topology”, in Proceedings of the Conference on Applications, technologies, architectures, and protocols for computer communication, ser. SIGCOMM'99. New York, NY, USA: ACM, 1999, pp. 251-262, DOI: 10.1145/316188.316229.