High-bandwidth data dissemination in overlay networks

Data dissemination or multicast in overlay networks, in its various forms, is popular in the Internet because of its lack of infrastructure requirement and its flexibility. Availability of abundant capacity in the physical network and high demand for the exchange of increasingly large-sized data contents make data transfer rate or bandwidth a critical metric to improve.;We study application-layer data dissemination in overlay networks, with the aim of reliably maximizing the bandwidth. Our research was undertaken from mainly three fronts. (1) We applied the theoretic results of network coding, from the field of information theory, to overlay multicast. A distributed algorithm is designed to construct an overlay multicast topology conducive to network coding. On this topology, we then devised a practical method for generating specific linear codes to implement the encoding/decoding of data. The resulting overlay multicast topology, with the implementation of network coding, is able to achieve the improvement in bandwidth predicted by the theory. (2) To address practical issues of network dynamics and cross traffic fluctuations, we developed a distributed algorithm to adaptively and progressively build overlay multicast topologies of a multiple-tree structure. We not only conducted experiments in simulations, but also implemented the algorithm and deployed it in PlanetLab, a real wide-area overlay network test-bed. (3) Studying overlay networks from a more theoretical perspective, we made the simple observation that overlay links have hidden correlations in capacity, based on which we introduced a new model of overlay networks: overlay with linear capacity constraints (LCC). We investigated several classical network flow problems in the context of LCC-overlays. Using theory and techniques from the field of linear optimization, we formulated and solved these problems. We also studied LCC-overlays with simulated experiments, and discovered that even a highly restricted class of LCC would yield substantial increase in flow rates. Even more encouraging is that this particular restricted class of LCC is naturally distributed. Furthermore, we developed distributed algorithms both for constructing LCC-overlays and for doing overlay multicast in them.