Scalable and automated monitoring processes for testing, debugging, and operation of VNFs and service-chains are crucial components towards achieving the aims of network softwarization - i.e., cheaper, faster, and shorter service deployment and network management processes. In this paper we present a decentralized monitoring approach aimed at supporting automated deployment and operation of VNFs and service-chains. The approach is inspired by network tomography and is designed to address observability limitations and scalability issues that arise from performing measurements from an SDN controller. From successive end-to-end measurements link metrics are derived via in-network parameter estimation with no need of forwarding raw measurements to the controller, which significantly reduces the measurement overhead compared to when monitoring individual links explicitly from an SDN controller.