ILP Formulation for Monitoring-Cycle Construction Using Segment Routing

摘要

A monitoring-cycle can be easily implemented using segment routing and subject to a given maximum segment list size. In this paper, we propose the first ILP formulation (ILP1) to optimally solve the problem of covering every link in the network using monitoring-cycles and with minimum cycle cover length. To further conserve network bandwidth, we extend ILP1 to jointly minimize the total segment list size needed (ILP2). Since the time required to detect a network failure is affected by the longest cycle, we also extend ILP1 to jointly minimize the length of the longest cycle (ILP3). Finally, since all the existing network monitoring algorithms need to maintain a dedicated monitoring topology, we evaluate the gain brought by the monitoring topology using our ILPs. We found that the gain is limited, therefore we argue that maintaining a dedicated monitoring topology for monitoring-cycle construction is unnecessary.