Abstract
The fulfilment of guaranteed multiple criteria based quality of service (QoS) for Multimedia applications servicing multiple subscribers is known to be a NP complete problem. Moreover, finding the multicast graph respecting the defined QoS requirements and minimizing network resources is also a NP-complete optimization task. The well-known greedy algorithm Mamcra, proposed in the literature, computes the set of shortest paths from a source to all destination, and then reduces this set to an efficient set of multicast routes, without compromising the requested level of QoS. A closer look at Mamcra shows that it does not exploit further simple but possible reductions of the multicast sub-graph. In this paper, we propose a taboo search algorithm, named TabooQMR, that is augmented by some meta-heuristics to improve the multicast sub-graph computed by the greedy algorithm Mamcra, and leading to a considerable improvement, as demonstrated by the simulation results.