The complexity of RP selection in multicast channelization
Fei Che, Errol L. Lloyd · 2009
Rendezvous point (RP) selection for multicast groups is the problem of selecting a node to serve as the RP-host for a multicast group. We consider rendezvous point selection in the context of channelization where groups have been established based on user preferences for a set of available flows. Thus, each of the flows associated with a group will arrive at the node that serves as the RP-host for that group, from which those flows will be multicast to the group subscribers. We study the simultaneous assignment of RP-hosts for a collection of multi-cast groups with the dual goals of a) not overloading any single node serving as a host; and, b) minimizing the total network traffic. Toward those ends we consider two versions of the problem. For Bounded Host Assignment, we give a polynomial time algorithm for finding an optimal assignment. For Host Traffic Constrained Assignment, we establish that the problem is NP-complete and then study approximation algorithms. Simulation results are provided for the latter problem comparing the effectiveness of the solutions produced by our algorithms with optimal solutions.