On growth of limited scale-free overlay network topologies

Overlay network topologies provide different networking applications an abstraction over underlying network architecture. Therefore, their construction and the resulting topological characteristics play a crucial role in the performance of operations running in these applications. Thanks to their small diameters, scale-free (power-law) overlay network topologies are one of the structures that offer high performance for these networks. However, a key problem for such networks is the high connectivity (i.e., load) in only a small portion (i.e., hubs) of nodes. In fact, the nodes in such scale-free overlay networks may not want or be able to accomplish such high connectivity due to technical restrictions. Therefore, some hard cutoffs are often imposed on the number of edges that each node can have, making them limited scale-free networks. In this paper, we discuss and analyze the growth of such limited scale-free networks and propose an algorithm aiming to achieve perfect scale-free overlay network topologies with low communication overhead and without global information usage during its construction phase. Through extensive simulations, we also evaluate the proposed approach and show its superiority over the existing solutions.