On Optimal File Distribution in Practical Mesh-Based Overlay Networks

Abstract

Distributing large video files or operating system images over the Internet requires file servers with high bandwidth and large storage capacity. Overlay networks, including content distribution networks (CDN) and peer-to-peer (P2P) systems, are promising network models for large file distributions. Both CDN and P2P leverage bandwidth and storage resources between content distribution servers and individual nodes, so that they can scale to a larger number of nodes easily. Previous work on large file distribution mainly focused on minimizing the distribution time of a fully connected overlay network. In a fully connected overlay network, each individual node is connected to every other node in the network. However, most practical CDN and P2P systems are based on a partially connected mesh topology, where nodes are typically connected to a subset of other nodes. In this paper, the distribution time of practical mesh-based overlay systems is analyzed and a lower bound on the file distribution time is established. Our algorithms consist of two steps. First, we decompose the mesh network into multiple spanning trees so that the load on each node is balanced. We show that the construction of balanced spanning trees is NP-complete and propose a few heuristics to tackle it. The second step, we derive the optimal system distribution time based on the multiple spanning tree topology, node bandwidths and file size. In this step, an optimal file segmentation algorithm is developed, in which a file is divided into unequal-sized pieces and allocated to individual nodes based on the available bandwidth. We validate our theoretical analysis via experiments and investigate how system design parameters, such as  node churning and implementation complexity, affect system distribution time.