A New Approach to Internet Route Simulation

A system simulation imitates the workings or operations of a real system so that it can be studied and improved upon. The paper "Describing and Simulating Internet Routes" by J. Leguay, T. Friedman, and K. Salamatian [1] adds a new approach to simulating Internet routes. The authors argue that the present models of Internet routes are still far from being a realistic representation of the actual system. They believe that their new model presents a closer representation of the statistical properties of the Internet.

According to the paper [1], there are three approaches to simulating routes: The first is the use of the shortest path model. A second approach is to explicitly model the actual network and separately simulate the public networks (WAN) and the intra network (LAN). The third approach is to use the actual route maps generated by network softwares like traceroute or skitter. The paper cites the study of Paxton [2] to show that actual network routing does not use really use the shortest path method most of the time. Another study [3] cited by the paper shows that routing policies at the autonomous systems level may have priorities other than the shortest path. The second approach is also limited by man's ability to obtain all the characteristics of the system, and that simulating inter and intra networks is, at best, a very difficult task. The third approach is also inapplicable if a large number of sources or nodes are to be simulated. As of now, the current tracing softwares can only employ a few hundred sources. For example, the skitter program can only map the route of thirty sources. Given the limitations of the three approaches, most prefer to use the shortest path model despite its limitations.

The new approach proposed by the paper [1] suggests using actual measured graphs of the network topology. Sources and destinations can be chosen at random. A model produces artificial routes that closely resemble statistically the actual routes. The two models tested are the random deviation model and the node degree model. According to the paper [2], the random deviation model is based on the notion that the router usually follows the shortest path method, but might at times deviate from it . The node degree model uses the node degrees from the source and destination to determine the shortest path.

Another contribution of the paper is an update of familiar statistical properties of actual routes which are the path length and hop direction. Path length is the sum of the paths from the source to the destination node. The proposed model aims to produce routes of the same length as the real routes Hop direction refers to the direction and distance taken by a packet as it travels from one router to another (hop). It may hop closer or farther from the source, but in general, the packet should increase the distance from the source and shorten the distance towards its destination.

Lastly, the paper introduces a new statistical property called the evolution of degree along the route. This refer to the probabilities of passing from a lower to a higher degree node or vice-versa as the packet passes to the next on the way to its destination. The evolution of degree and path length are utilized in the generation of artificial routes to produce a one that is closest to the real route that a packet actually goes through in the real network.

The paper impressed me by its methodology. In a situation where it is impossible to know the actual route that will be taken by packets in an a real network, the authors employ probability and statistics to predict the actual route thereby providing a better simulation of the system.

References:

[1] J. Leguay, T. Friedman, K. Salmatian. Describing and Simulating Internet Routes, 2004

[2] V. Paxton. "End-to-End Routing Behavior in the Internet", In Proc. ACM SIGCOMM, 1996

[3] H. Tangmumarunkit, et al. " Network Topology generators: Degree-based vs. structural", In Proc. ACM SIGCOMM, 2002