Online algorithms for selective multicast and maximal dense trees
Baruch Awerbuch, Tripurari Singh · 1997
Multicast routing and admission control can be defined as follows. Various network users issue online requests for a connection to certain multicast sources. The network either connects this request or rejects it (admission control decision). If request is connected, a path with sufficient bandwidth is established starting at the requesting user and ending either at the source or at one of the users previously connected to the same source (route selection decision). The goal of these admission control and route selection decisions is to maximize total number of users connected (i.e. total thruput) subject to the network capacity constraints. This problem can be reduced to the online maximal dense tree problem: Upon a service request from a node in a weighted graph with a distinguished source, the node is either rejected or connected to the tree of previously connected nodes. The goal is to maximize the total number of requests while keeping the density (ratio of accepted re...