Minimizing routing state for light-weight network simulation

Abstract

We introduce an O(N) routing mechanism, referred to as algorithmic routing. It minimizes the memory consumption for routing states in network simulations. Our computation shows that for network simulations size of the Internet, algorithmic routing can potentially reduce memory requirement by three orders of magnitude to hirarchical routing in Internet-like hierarchy and an additional three orders of magnitude to flat shortest path routing. To evaluate the efficiency of algorithmic routing in practice, we implement the mechanism on ns-2. With network topologies randmly generated by GT-ITM, we compare the memory and run-time consumption of flat, hierarchical and algorithmic routing and confirm the expected performance improvement by algorithmic routing. We also quantify difference of the three mechanisms in route length (i.e., hop counts). We find the relative difference is below 10% for more than 80% of the routes. Nevertheless, we are cautious about the applicability of algorithmic routing to general network simulations, given that it is not clear to what extent the GT-ITM topologies capture the hierarchical structure of Internet and what impact the different routes may incur. Thus, we further rationalize distortions that algorithmic routing may introduce and recommend users to apply this technique only when suitable.