Efficient online algorithms for multicasting with bandwidth and delay guarantees

grantor: University of TorontoThis work proposes a novel paradigm for online multicasting with bandwidth and delay guarantees. We first address the issue of online maintenance of multicast tress, namely the case where the topology of the multicast network is confined to trees. Next, motivated by examples that demonstrate the inefficiency of tree-bead multicast graphs, we waive this requirement. Instead, multicast information is delivered to the participants by means of dedicated virtual circuits. Our solutions observe the following guidelines: (i) Satisfaction of bandwidth and delay requirements imposed by individual users; (ii) Feasibility with respect to constraints such as the capacity of links; (iii) Online handling of join/leave requests; (iv) Dual objectives, i.e., maximization of total admitted users while keeping the overall cost sufficiently small; (v) Performance guarantees related to the cost incurred by each admitted user; (vi) Provably low time-complexity; and (vii) Efficient reclaiming of resources. Previous research has failed to comply with several of the above specifications.M.Sc