Multiobjective optimization model and heuristic algorithm for dynamic multicast routing
Yezid Donoso, Ramón Fabregat, Jose Luis Marzo · 2004
We propose a multiobjective traffic engineering scheme using different distribution trees to dynamic multicast groups (i.e., in which egress nodes can change during the connection's lifetime). If a multicast tree is recomputed from scratch, it may consume a considerable amount of CPU time and all communication using the multicast tree will be temporarily interrupted. To alleviate these drawbacks we propose an optimization model (dynamic model MHDB-D) that makes use of a previously computed multicast tree (static model MHDB-S) in order to add new egress nodes. Using these two models, our aim is to combine into a single aggregated metric, the following weighting objectives: maximum link utilization, hop count, total bandwidth consumption and total end-to-end delay. Moreover, our proposal solves the traffic split ratio for multiple trees. The problem is NP-hard, therefore, a novel multicast multiobjective dynamic routing algorithm is proposed for optimizing the different objectives. We compare the dynamic multicast routing model with the algorithm proposed. The proposed approach can be applied in MPLS networks by allowing explicit routes to be established in multicast events. The main contributions of this paper are the optimization model for dynamic multicast routing; and the heuristic algorithm proposed with polynomial complexity.