Monitoring Trail Design Based on Segment Routing

被引:4
作者
Li, Xiaoqian [1 ]
Yeung, Kwan L. [1 ]
机构
[1] Univ Hong Kong, Dept Elect & Elect Engn, Hong Kong, Peoples R China
来源
IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT | 2020年 / 17卷 / 04期
关键词
Monitoring cycle; monitoring trail; network management; network monitoring; segment routing; LOCALIZATION;
D O I
10.1109/TNSM.2020.3017222
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Segment routing is an emerging networking technology, where an arbitrary forwarding path can be identified using a list of segments. In this article, we study network monitoring in segment routing based on monitoring trails. Unlike the existing monitoring cycle, a trail is more flexible because it can be either open or closed (i.e., a cycle). Consider a network with a given set of k monitors, which are devices responsible for network monitoring. A monitoring trail must start and end at a monitor. The k-monitor cover problem is to cover every link in the network using trails such that each trail has no more than K segments and the total length of all trails is minimized. In this article, we prove that the k-monitor cover problem is NP-hard. To solve it, the first ILP is formulated and an efficient heuristic algorithm (k-MCA) is designed.
引用
收藏
页码:2648 / 2661
页数:14
相关论文
共 30 条
[1]   Segment Routing in Software Defined Networks: A Survey [J].
Abdullah, Zahraa N. ;
Ahmad, Imtiaz ;
Hussain, Iftekhar .
IEEE COMMUNICATIONS SURVEYS AND TUTORIALS, 2019, 21 (01) :464-486
[2]  
[Anonymous], 2010, 5880 RFC IETF
[3]  
[Anonymous], 1998, Modern Graph Theory, DOI 10.1007/978-1-4612-0619-4
[4]  
Aubry F., 2016, IEEE INFOCOM SER, P1, DOI 10.1109/INFOCOM.2016.7524410
[5]  
Avramopoulos I., 2006, ATEC 06 P ANN C USEN, P25
[6]   A study of prefix hijacking and interception in the Internet [J].
Ballani, Hitesh ;
Francis, Paul ;
Zhang, Xinyang .
ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2007, 37 (04) :265-276
[7]  
Dijkstra EW, 1959, NUMER MATH, V1, P269, DOI [10.1007/BF01386390, DOI 10.1007/BF01386390]
[8]  
Filsfils C., 2018, 8420 IETF RFC
[9]  
Filsfils C., 2020, RFC 8754
[10]  
Filsfils C., 2019, 8660 IETF RFC