Bandwidth-efficient network monitoring algorithms based on segment routing

Abstract

<p>We study the bandwidth-efficient network monitoring algorithms using segment routing on topologies that can be modelled as a symmetric <a href="https://www.sciencedirect.com/topics/computer-science/directed-graphs" title="Learn more about directed graph from ScienceDirect's AI-generated Topic Pages">directed graph</a>. 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 <a href="https://www.sciencedirect.com/topics/engineering/construction-process" title="Learn more about construction process from ScienceDirect's AI-generated Topic Pages">construction process</a>. 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.<br></p>