© 2021 IEEE.Network monitoring is one of the key aspects to ensure communication reliability in case of failures and malicious activities and has several design issues depending on the system characteristics. As traditional monitoring solutions usually rely on periodic updates between the network controller and ordinary nodes, scalability remains a challenge, especially for complex systems. A recent solution, the In-Band Network Telemetry (INT) framework, allows data packets to probe the nodes while traversing the network reducing the overhead between the controller and other nodes. Accordingly, effective use of the INT framework is now a design problem to (i) minimize the control overhead, (ii) guarantee the freshness of telemetry information, and (iii) minimize redundancy. In this paper, we propose a heuristic, Graph Partitioned INT (GPINT), to find balanced paths to forward in-band telemetry information to satisfy these three requirements. We present an extensive analysis of our approach and compare it with a recent study that uses Euler's method for path generation. Our numerical results show that GPINT outperforms its opponent in terms of all three requirements.