Multicast server selection: Problems, complexity, and solutions

We formulate and investigate fundamental problems that arise when multicast servers, that deliver content to multiple clients simultaneously, are replicated to enhance scalability and performance. Our study consists of two parts. First, we consider the problem under the assumption that the multicast clients are static for the duration of the multicast content distribution session. In this context, we examine two models for server behavior: fixed-rate servers, which transmit at a constant rate, and rate-adaptive servers, which adapt their transmission rate based on network conditions and/or feedback from clients. In both cases, we show that general versions of the client assignment problems are NP-hard. We then develop and evaluate efficient algorithms for interesting special cases, as well as heuristics for general cases. Second, we consider the case in which the set of clients changes dynamically during the multicast content distribution session. We again consider both fixed-rate and rate-adaptive servers. We formulate the problem as a Markov decision process, capturing the costs associated with trees, as well as the transition costs to dynamically change the trees. We use the properties of optimal solutions for small examples to develop a set of dynamic server selection heuristics.