Algorithms and trade-offs in multicast service overlay design

摘要

The Multicast Service Overlay Network (MSON) has been recently introduced to address some of the deployment and maintenance problems of IP multicast and application-level multicast. An MSON is essentially a backbone service overlay provisioned by an MSON provider and designed to "multiplex" multiple-user overlays. It consists of service nodes or proxies deployed by the provider. The proxies are strategically deployed to form a backbone overlay and provide multicasting functionalities for supporting many user groups simultaneously. The MSON provider designs the backbone overlay for a large user population and can therefore enjoy large-scale economies and benefits. Since the deployment of an MSON is a capital-intensive investment, it is very imperative to carefully design the MSON so that the provider can make the best revenue out of this investment. In this article, the authors formulate the MSON design problem by taking into account operational costs of the MSON provider. They then explore three subproblems: overlay proxy placement, overlay link selection, and bandwidth dimensioning. For each of these subproblems, the authors present several algorithms and discuss their design trade-offs. By simulations, they investigate the effectiveness of different overlay design algorithms, analyze their impact on multicast performance, and suggest some practical solutions for MSON design.