A Heuristic Algorithm for Multi-layer Network Optimization in Cloud Computing

Hadian, A.; Bagherian, M.; Fathi Vajargah, B.

doi:10.22044/jadm.2021.9955.2133

Document Type : Original/Review Paper

Authors

¹ Department of Applied Mathematics, University campus 2, University of Guilan, Rasht, Iran

² Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

³ Department of Statistics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

https://doi.org/10.22044/jadm.2021.9955.2133

Abstract

Background: One of the most important concepts in cloud computing is modeling the problem as a multi-layer optimization problem which leads to cost savings in designing and operating the networks. Previous researchers have modeled the two-layer network operating problem as an Integer Linear Programming (ILP) problem, and due to the computational complexity of solving it jointly, they suggested a two-stage procedure for solving it by considering one layer at each stage.
Aim: In this paper, considering the ILP model and using some properties of it, we propose a heuristic algorithm for solving the model jointly, considering unicast, multicast, and anycast flows simultaneously.
Method: We first sort demands in decreasing order and use a greedy method to realize demands in order. Due to the high computational complexity of ILP model, the proposed heuristic algorithm is suitable for networks with a large number of nodes; In this regard, various examples are solved by CPLEX and MATLAB soft wares.
Results: Our simulation results show that for small values of M and N CPLEX fails to find the optimal solution, while AGA finds a near-optimal solution quickly.
Conclusion: The proposed greedy algorithm could solve the large-scale networks approximately in polynomial time and its approximation is reasonable.

Keywords

20.1001.1.23225211.2021.9.3.9.4

References

[1]M. Pióro, and D. Medhi, Routing, flow, and capacity design in communication and computer networks. Elsevier, 2004.

[2] K. Walkowiak, Modeling and optimization of cloud-ready and content-oriented networks, Springer International Publishing, vol 56, 2016.

[3] G. Carofiglio, G. Morabito, L. Muscariello, I. Solis, and M. Varvello, From content delivery today to information centric networking. Computer Networks, vol 57(16), pp. 3116-3127, 2013.

[4] G. Tyson, E. Bodanese, J. Bigham, and A. Mauthe, Beyond content delivery: Can icns help emergency scenarios? IEEE Network, 28(3), pp. 44-49, 2014.

[5] J.M. Simmons, Optical network design and planning. Springer, 2014.

[6] I. Tomkos, S. Azodolmolky, J. Sole-Pareta, D. Careglio, and E. Palkopoulou, A tutorial on the flexible optical networking paradigm: State of the art, trends, and research challenges. Proceedings of the IEEE, 102(9), pp. 1317-1337, 2014.

[7] Y. Li, D. King, F. Zhang, and A. Farrel, Generalized Labels for the Flexi-Grid in Lambda Switch Capable (LSC) Label Switching Routers. IEEE, 2015.

[8] B. Mukherjee, WDM optical communication networks: progress and challenges. IEEE Journal on Selected Areas in communications, 18(10), pp. 1810-1824, 2000.

[9] Recommendation, I.T.U.T. Optical interfaces for multichannel systems with optical amplifiers. Vol. G, 692, 1998.

[10] O. Nevzorova, O. Lemeshko, A. Mersni, A.M. Hailan, A.S. Ali, and S. Harkusha, July. Improved Two-Level Method of Multicast Routing in MPLS-TE Network. IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON) (pp. 846-850). IEEE, 2019.

[11] I. Zhukovyts’kyy, V. Pakhomova, H. Domanskay, and A. Nechaiev, Distribution of information flows in the advanced network of MPLS of railway transport by means of a neural model. In MATEC Web of Conferences (Vol. 294, p. 04007). EDP Sciences. 2019.

[12] M. Masood, M.M. Fouad, R. Kamal, I. Glesk, and I.U. Khan, An improved particle swarm algorithm for multi-objective-based optimization in MPLS/GMPLS networks. IEEE Access, 7, pp. 137147-137162, 2019.

[13] M. Masood, M. Mosta Foyad, R. Kamak, I. Glesk, and I. Ullahkhan, An Improved Particle Swarm Algorithm for Multi-Objective-based Optimization in MPLS/GMPLS Networks, IEEE Access, 2019.

[14] A.R. Sharafat, S. Das, G. Parulkar, and N. McKeown, Mpls-te and mpls vpns with open-flow. In Proceedings of the ACM SIGCOMM, pp. 452-453, August 2011.‏

[15] MABHOOT, Nahid; MOMENI, Hossein. An Energy-aware Real-time Task Scheduling Approach in a Cloud Computing Environment. Journal of AI and Data Mining, 2021.‏

A Heuristic Algorithm for Multi-layer Network Optimization in Cloud Computing

References

References

Volume 9, Issue 3July 2021Pages 361-367

Volume 9, Issue 3
July 2021
Pages 361-367