Research On Network Automat IC Test Based On Set Cover Theory

The rapidly expanding network scale and increasing user requirements in recent years has brought great opportunities as well as more and more severe challenges to the network management. The need to gurantee net-work QoS has prompted Internet Service Providers(ISP) to draw a great deal of interest to set up a large scale network monitoring system to au-tomatically obtain the whole network real-time performance information by taking advantages of active test technologies through active probes. In order to realize network automatic performace monitoring, we have to solve one key issue, how to optimize probe station placement and probe assignment to get optimum test strategy. Until now, most previous re-search models the probe placement problem as minimum set cover prob-lem. In order to minimize the number of probe stations, different greedy algorithms based on shortest routing tree are proposed. Obviously, short-est routing tree based greedy algorithms will not guarantee best test strategy with minimum test cost as they don't take minimizing the total number of probe assignments into consideration.Thus, in our work we propose a network connectivity automatic test framework with a novel algorithm based on set cover theory to efficiently solve the probe station placement and probe assignment problems. We take more operational constraints into account: minimizing the total number of probe stations to reduce the placement cost as well as mini-mizing the total number of probe assignments to reduce test impact on network itself. Then we firstly propose an optimized algorithm SP-OGSA by introducing space parameter d and node/path priority to gain a balance between reducing the number of probe stations and reducing the total number of probes. Furthermore, in oder to avoid the local optimality of greedy algorithm, we propose another optimized global heuristic algo-rithm SP-GRASP which can obtain even better solutions. The main idea of our optimization is that in our work when building a solution we don't choose shortest router tree but a single path will dramatically reduce the total number of probes and finally result in a lower cost test strategy.Then we set up a whole network connectivity automatic test simula-tion system by using topology generator BRITE and network simulator NS-2 to evaluate our work and previous work. Experiment results show that our proposed algorithm SP-OGSA is much more effective than per-vious work, with almost the same number of probe stations and less probe assignments when setting space parameter d to 4. For example, when network has 500 nodes and d is 4, compared to previous work SP-OGSA can reduce about 30% of total probe assignments and about 40% of test times resulting in great reduction of test traffic and test time at the cost of increasing only less than 0.5% of probe stations. Experiment results also show that our SP-GRASP algorithm shows even significant performace than SP-OGSA at the cost of computation time. For example, when net- work has 500 nodes, compared to previous work SP-GRASP can further reduce about 6% of probe stations, about 50% of total probe assignments and about 85% of test times. Therefore, we have amply proved that com-pared to prior work, our optimized algorithms can adapt to more different network test environments with more superior performance.