Open Access

ARTICLE

Efficient Routing Protection Algorithm Based on Optimized Network Topology

by Haijun Geng^1,2, Zikun Jin¹, Jiangyuan Yao^3,*, Han Zhang⁴, Zhiguo Hu⁶, Bo Yang⁵, Yingije Guo⁷, Wei Wang¹, Qidong Zhang¹, Guoao Duan⁸

1 School of Computer and Information Technology, Shanxi University, Shanxi, 030006, China
2 School of Automation and Software Engineering, Shanxi University, Shanxi, 030006, China
3 School of Computer Science and Technology, Hainan University, Haikou, 570228, China
4 Department of Computer Science & Technology, Tsinghua University, Beijing, 100084, China
5 Department of Urban & Regional Planning San José State University, San José, CA, 95192, USA
6 Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, Shanghai, 201804, China
7 Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, Chengdu, 610054, China
8 Beijinng University of Technology, Beijing-Dublin International College, Beijing University of Technology, Beijing, 100124, China

* Corresponding Author: Jiangyuan Yao. Email:

Computers, Materials & Continua 2022, 72(3), 4525-4540. https://doi.org/10.32604/cmc.2022.027725

Received 24 January 2022; Accepted 08 March 2022; Issue published 21 April 2022

Abstract

Network failures are unavoidable and occur frequently. When the network fails, intra-domain routing protocols deploying on the Internet need to undergo a long convergence process. During this period, a large number of messages are discarded, which results in a decline in the user experience and severely affects the quality of service of Internet Service Providers (ISP). Therefore, improving the availability of intra-domain routing is a trending research question to be solved. Industry usually employs routing protection algorithms to improve intra-domain routing availability. However, existing routing protection schemes compute as many backup paths as possible to reduce message loss due to network failures, which increases the cost of the network and impedes the methods deployed in practice. To address the issues, this study proposes an efficient routing protection algorithm based on optimized network topology (ERPBONT). ERPBONT adopts the optimized network topology to calculate a backup path with the minimum path coincidence degree with the shortest path for all source purposes. Firstly, the backup path with the minimum path coincidence with the shortest path is described as an integer programming problem. Then the simulated annealing algorithm ERPBONT is used to find the optimal solution. Finally, the algorithm is tested on the simulated topology and the real topology. The experimental results show that ERPBONT effectively reduces the path coincidence between the shortest path and the backup path, and significantly improves the routing availability.

---

Keywords

---