On the Construction of Low Cost Multicast Trees with Bandwidth Reservation
Dirceu Cavendish, Aiguo Fei, Mário Gerla, Raphaël Rom · 1998
. This paper addresses the problem of routing many-to-many multicast connections with bandwidth reservation. We devise a routing algorithm which provides not only connectivity but also bandwidth among multicast members at a low cost. After briefly addressing the problem complexity (NP-Complete), we move on to design polynomial time algorithms, for scalability purposes, some of which with worst case bounds on performance. A simulation study is used to illustrate the algorithms ' performance and trade offs. 1 Introduction In a QOS environment, routing algorithms must provide routes which conform with users end-to-end requirements while minimizing the cost of a connection. A connection cost is defined as the sum of the costs of individual links participating in the connection. Link costs are assigned so as to reflect the desirability of using a given link as part of a connection path. QOS requirements translate into path constraints for a routing algorithm, and impact its computation co...