Maximum-Revenue Multicast Routing and Partial Admission Control for Multimedia Distribution

Abstract

In this paper, we intend to solve the problem of maximum-revenue multicast routing with a partial admission control mechanism. Specifically, for a given network topology, a given link capacity, the destinations of a multicast group, and the bandwidth requirement of each multicast group, we attempt to find a feasible routing solution to maximize the revenue of the multicast trees. The partial admission control mechanism means that the admission policy of the multicast group will not be based on a traditional “all or none” strategy. Instead it considers accepting of partial portions of destinations for the requested multicast group. Firstly, we model this problem as an optimization problem. Then, we propose a simple heuristic algorithm and an optimization based heuristic to solve this problem. The methodology taken for solving the problem is Lagrangean relaxation. Computational experiments have been performed on regular networks, random networks, and scale-free networks.