Proof of NP-Hardness, new mathematical formulation and constructive heuristic for In-band network monitoring optimization

Abstract

The increasing usage of distributed and cloud-driven network ecosystems have rendered legacy network monitoring obsolete, as they are unable to provide granular visibility to huge amounts of network traffic data exchanged each day. In-Band Network Telemetry (INT) is showing itself to be a promising alternative to these legacy solutions, by allowing active packets to report their metrics within the network system. This new approach can provide the much needed accurate real-time granular network monitoring solution, yet it may cause network performance degradation if applied aimlessly. Work has been done to formalize an optimization problem, namely the Network Monitoring Optimization problem (NEMO), in the search to find an optimum way for a network to report its current state using INT. We build on top of that work. We introduce a generalization of NEMO and proof that such problem is NP-Hard. Then, we propose a new mathematical formulation and a heuristic algorithm for the problem. In our experiments using real-world network configurations, we observed that the proposed heuristic was able to find high-quality solutions to all networks under 1:7 seconds.