Weighted Shortest Path Models: A Revisit to the Simulation of Internet Routing

Abstract

Understanding how packets are routed in Internet is significantly important to Internet measurement and modeling. The conventional solution for route simulation is based on the assumption of unweighted shortest path. However, it has been found and widely accepted that a packet in Internet is usually not transmitted along the unweighted shortest path between its source and destination. To better simulate the routing behavior of a packet, we thoroughly explore the real-world Internet routes and present a novel local information based simulation model, with a tuning parameter, which assigns weights to links based on local information and then simulates the Internet route with weighted shortest path. Comparisons with baseline approaches show its capability in well replicating the route length distribution and other structural properties of the Internet topology. Meanwhile, the optimal parameter of this model locates in the range of (0, 2), which implies that a packet inside the Internet inclines to move to nodes with small degrees. This behavior actually reflects the design philosophy of Internet routing, balancing between network efficiency and traffic congestion.

arXiv comment12 pages, 10 figures

References in corpus (5)

• Accuracy and Scaling Phenomena in Internet Mapping
• Traceroute sampling makes random graphs appear to have power law degree distributions
• Exploring networks with traceroute-like probes: theory and simulations
• Efficient routing on scale-free networks based on local information
• Network Inference from TraceRoute Measurements: Internet Topology `Species'