Date Added: Oct 2009
Probing is a promising approach for network monitoring. An important problem that needs to be addressed while developing probing-based solutions is the selection of probe station nodes. Probe station nodes are the nodes that are instrumented with the functionality of sending probes and analyzing probe results. The placement of probe stations affects the diagnosis capability of the probes sent by the probe stations. The probe station placement also involves the overhead of instrumentation. Thus it is important to minimize the required number of probe stations without compromising on the required diagnosis capability of the probes. This paper presents a novel reduction of the Minimum Probe Station Selection problem to the Minimum Hitting Set problem.