Monitoring Trail Design Based on Segment Routing

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.