| The research and industrial communities have recently been striving to make the Internet capable of supporting unicast and multicast traffic sources with Quality of Service (QoS) guarantees. QoS parameters targeted are guaranteed throughput, end-to-end delay, and delay variation. A multicast tree for a given multicast source is a tree rooted at the source and all its leaves being members in the multicast group. Tree cost is measured by the utilization of tree links. Also tree cost is highly correlated with the number of Steiner tree nodes, i.e., nodes which are not members of the multicast group. In this thesis, a tabu search algorithm is proposed for three different multicast routing problems involving the above QoS parameters. Our proposed algorithms are then compared with other proposed techniques on numerous sample networks. On all tests, the proposed tabu search algorithms were able to find better multicast trees than those reported in the literature. Also, a greedy algorithm is proposed for multicast routing problem with dynamic membership. |
