Research On An Evaluation Model For Topology Partitioning Based On Network Simulation

With the rapid development of the Internet, the scale of network increasesrapidly, and the structure becomes more complicated, large-scale network hasbecome a hot topic of network research. Network simulation can do research intocomplex network behaviors and evaluate implemented network protocols. It hasseveral advantages, such as low cost, easy to use and high simulation authenticity,so it has been widely used. Large-scale network simulation requires hugecomputational overhead, because of hardware resource constraint, the singlesimulation has been unable to meet the needs of large-scale network simulation.Parallel discrete event simulation technology has become an important approach tolarge-scale network simulation. One of the significant research contents of parallelsimulation is how to distribute simulation task reasonably in order to guarantee loadbalance, to shorten the simulation running time, to reduce simulation resourceconsumption, and to increase the simulation performance.The task distribution of paralle l network simulation is usually realized bytopology partitioning. This paper dedicates to researching topology partitioning andits evaluation methods. The main research contents include the following three parts:Firstly, this paper start from the parallel discrete event simulation mechanism,analyzing a variety of factors which have influences on simulation performance,then we summarize and classify them. The factors inc lude simulating runningenvironment, simulating task and topology partitioning results. The factorsinfluenced by topology partitioning result are balanced load factors, remotecommunication overhead factors and synchronous cycle factors.Secondly, the current task partitioning methods start from considering merelyparts of the influence factors of the simulation performance, with the way of thegraph partitioning algorithm, but the simulation performance improves limitedlywhit lack of evaluation methods to assess the pros and cons of topology partitioningresult. Therefore, this paper considers simulation run time as the evaluationstandard of topology partitioning results, putting forward the methods of calculatingthe influence degrees of load balance, remote communication overhead andsynchronous cycle to simulation performance, and then sets up an evaluation modelfor topology partitioning based on simulation run time. This paper simulates DDoSin PDNS, comparing model calculations with experiment results, and then finds thattheir deviation is between5%and10%, which proves the accuracy of the model.By evaluating METIS algorithm and subnet elimination algorithm, the former algorithm has higher evaluation than the latter, and the rate is about13%. Theexpectations accord with experimental results, declaring the effectiveness of thismodel.Thirdly, because METIS and other graph partitioning tools are easy to fall intolocal optimum, this paper proposes and implements an optimization method fortopology partitioning, which based on time consumption evaluation. The methodconsiders the evaluation model as a guide, and solves METIS’ local optima l defectby optimizing its result, from three aspects, which including load balance,communication overhead and synchronous cycle. The experimental results showthat the method can effectively improve the perfo rmance of paralle l networksimulation, with an average of about20%.