In this work we investigate a new approach for detecting attacks which aim to degrade the network's Quality of Service (QoS). To this end, a new network-based intrusion detection system (NIDS) is proposed. Most contemporary NIDSs take a passive approach by solely monitoring the network's production traffic. This paper explores a complementary approach in which distributed agents actively send out periodic probes. The probes are continuously monitored to detect anomalous behavior of the network. The proposed approach takes away much of the variability of the network's production traffic that makes it so difficult to classify. This enables the NIDS to detect more subtle attacks which would not be detected using the passive approach alone. Furthermore, the active probing approach allows the NIDS to be effectively trained using only examples of the network's normal states, hence enabling an effective detection of zero-day attacks. Using realistic experiments, we show that an NIDS which also leverages the active approach is considerably more effective in detecting attacks which aim to degrade the network's QoS when compared to an NIDS which relies solely on the passive approach. Lastly, we show that the false positives rate remains very low even in the face of Byzantine faults.