An Efficient Routing Mechanism in Network Simulation

Simulation is widely recognized as an essential tool to analyze large-scale networks. Routing is a key factor which impacts the scale and efficiency of simulation. This paper presents a new approach to routing calculation, storage and lookup, named MTree_Nix. It maintains variable number of spanning trees as the base routing table and uses well-known Nix-Vector routing to compute on demand the routing states that cannot be covered by any of the spanning trees. Theoretically, we obtain the constraint condition on the optimized trade-off between space and time in MTree_Nix routing. Integrated with the advantages of the current routing mechanisms, MTree_Nix comes to a better trade-off between the storage space for the routing tables and the CPU time for routing lookup. Experimental results show that, with an increasing storage space of only about 1% more than Nix-Vector, MTree_Nix can reduce the simulation time for about 85% compared with Nix-Vector.