Group multicast routing algorithms satisfying quality of service requirements of real-time applications are essential for high-speed networks. A heuristic algorithm was presented for group multicast routing with bandw...Group multicast routing algorithms satisfying quality of service requirements of real-time applications are essential for high-speed networks. A heuristic algorithm was presented for group multicast routing with bandwidth and delay constrained. A new metric was designed as a function of available bandwidth and delay of link. And source-specific routing trees for each member were generated in the algorithm by using the metric, which satisfy member′s bandwidth and end-to-end delay requirements. Simulations over random network were carried out to compare the performance of the proposed algorithm with that from literature.Experimental results show that the algorithm performs better in terms of network cost and ability in constructing feasible multicast trees for group members. Moreover,the algorithm can avoid link blocking and enhance the network behavior efficiently.展开更多
A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictio...A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.展开更多
基金Supported by China Postdoctoral Science Foundation (No.20030056007).
文摘Group multicast routing algorithms satisfying quality of service requirements of real-time applications are essential for high-speed networks. A heuristic algorithm was presented for group multicast routing with bandwidth and delay constrained. A new metric was designed as a function of available bandwidth and delay of link. And source-specific routing trees for each member were generated in the algorithm by using the metric, which satisfy member′s bandwidth and end-to-end delay requirements. Simulations over random network were carried out to compare the performance of the proposed algorithm with that from literature.Experimental results show that the algorithm performs better in terms of network cost and ability in constructing feasible multicast trees for group members. Moreover,the algorithm can avoid link blocking and enhance the network behavior efficiently.
文摘A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.
