An Approximation Scheme for Optimal Multicast Routing with Multiple QoS Constrains
Weijun Yang, Yun Zhang · International Journal of Future Generation Communication and Networking · 2016
This paper studies the problem of optimal multicast routing with multiple Quality-of-Service (QoS) constrains (OMRMC), which is regarded as a critical component in networks.However, it is not very efficient and effective for the existing algorithms.An undirected and connected graph G with m edges and n nodes is modeled to find a multicast routing tree from source to destination subset D in this paper, and a novel approximation algorithm called APP-OMRMC is proposed for OMRMC.The theoretical validations for the proposed method are presented to show its efficiency.After that, the different networks with different types of service are evaluated.Experimental results show that the proposed method APP-OMRMC is capable of finding the optimal (or minimum-cost) multicast routing tree with the approximation factor (1+ε) and time complexity of O(mτ K-1 ).