Monitoring Trail Design based on Segment Routing

Abstract

<p>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.<br></p>