Small-world characteristics of the Internet and multicast scaling

Recent work has shown that the physical connectivity of the Internet exhibits small-world behavior. Characterizing such behavior is important not only for generating realistic Internet topologies, but also for the proper evaluation of network algorithms and protocols. Along this line, this paper tries to answer how small-world behavior arises in the Internet topologies and how it impacts the performance of multicast techniques. First, we attribute small-world behavior to two possible causes: the variability of vertex degree and the preference of vertices to have local connections. We found that both factors contribute with different relative degrees to the small-world behavior of the AS-level and router-level Internet topologies. For the AS-level topology, we have observed that extremely high variability of vertex degree is sufficient to cause small-world behavior, but for the router-level topology, preference for local connectivity plays a more important role. Second, we propose simple models to generate more realistic small-world Internet topologies. Our models consider both causes of small-world behavior. Third, we demonstrate the significance of our work by studying the scaling behavior of IP multicast tree size. We show that if topology generators capture only the variability of vertex degree, they are likely to underestimate the efficacy of multicast techniques.