ILP Formulations for Monitoring-Cycle Design based on Segment Routing

Abstract

<p>The <em>minimum cycle cover problem</em> in segment routing is to find a set of monitoring cycles such that (a) they originate from the same vantage point, (b) cover every directed link in the network, (c) each cycle can be encoded by a segment list smaller than a given maximum size, and (d) the total length of all cycles is minimized. To solve the problem using <a href="https://www.sciencedirect.com/topics/computer-science/integer-linear-programming" title="Learn more about Integer Linear Programming from ScienceDirect's AI-generated Topic Pages">Integer Linear Programming</a> (ILP), the key challenge is how to capture all the subtle features of segment routing using <a href="https://www.sciencedirect.com/topics/computer-science/linear-constraint" title="Learn more about linear constraints from ScienceDirect's AI-generated Topic Pages">linear constraints</a>. In this paper, five original ILP formulations, numbered from ILP1 to ILP5, are designed. In ILP1, the classic flow-based approach is adopted for constructing cycles. In ILP2, a more efficient voltage-based approach is adopted. We then extend ILP2 to ILP3 to jointly minimize the total segment list size. Since the time required to detect a network failure is determined by the longest cycle, we also extend ILP2 to ILP4 to jointly minimize the length of the longest cycle. As finding optimal solutions for large-sized topologies is time-consuming, we propose to limit the set of candidate segments for constructing cycles. Although the resulting ILP5 cannot guarantee optimal solutions, we show that it always outperforms the best <a href="https://www.sciencedirect.com/topics/computer-science/heuristic-algorithm" title="Learn more about heuristic algorithm from ScienceDirect's AI-generated Topic Pages">heuristic algorithm</a>. Finally, the performance gain of using a dedicated monitoring topology for probe packets, as adopted by all existing heuristic algorithms, is studied.<br></p>