Bandwidth-efficient network monitoring algorithms based on segment routing
Abstract We study the bandwidth-efficient network monitoring algorithms using segment routing on topologies that can be modelled as a symmetric directed graph. Aiming at directly minimizing the cycle cover length, four new two-phase algorithms, A, B, C and D, are proposed. Algorithm A is a simple extension of an existing algorithm. Algorithm B utilizes the notion of symmetric cycles. Algorithm C enhances B by adopting a new path metric. Algorithm D further improves C with a parallel and sequential cycle construction process. Since two-phase algorithms require a dedicated monitoring topology, the four two-phase algorithms are then enhanced to function without monitoring topology. Although the cycle cover length found is slightly increased, we argue that the cost saving in removing monitoring topology is far more significant.