Affiliations: College of Software Engineering, Graduate University of the Chinese Academy of Sciences, Beijing 100049, P.R. China | School of Information Technology and Engineering, University of Ottawa, Ottawa, ON, Canada, K1N 6N5 Tel.: +1 613 562 5800 Ext. 2173; Fax: +1 613 562 5664; E-mail: {bxzhang,mouftah}@site.uottawa.ca
Note: [] Corresponding author.
Abstract: Shortest Path Tree (SPT) is the most widely used type of tree for multicast provisioning due to its simplicity and low per-destination cost. An SPT minimizes the accumulated cost, individually, from the source of a group to each destination of the group. However, SPTs have not considered the overall resource utilization in their constructions. This work aims at building cost-effective SPTs by enhancing link sharing between destinations of a group. We achieve this goal by introducing destination-driven characteristic into SPT constructions. Specifically, each destination is connected with the source via a shortest path. When equal cost multiple paths are available, priority is given to the one biasing through a destination among all such routes. We accordingly present the design of an algorithm building destination-driven SPTs. To achieve further improved performance in resource utilization, we also present an algorithm, which is designed to further enhance link sharing among the destinations of a group while meeting a maximum path length constraint for each destination. Simulation results are used to demonstrate the high performance of the proposed algorithms.
