A multicast routing algorithm
Takayuki Yamagata, Akihiro Fujii, Yoshiaki Nemoto · Systems and Computers in Japan · 1999
With the advent of the multicast communication function, it is expected that a wide range of applications will be realized, such as the delivery of video information through networks. It is thus important from the viewpoint of communication cost to compose the optimum route for multicast communication. Some of the considered methods of routing are the method where the edges are weighted and the route is determined so that the total weight is minimized, and the method where the generation tree is constructed based on the shortest route to the destination. In multicast communication, the packet is copied at the switch and is transmitted. Thus, an overhead is produced due to the packet copying process. This paper proposes an algorithm to determine the route considering the number of copies at the switch, so that (1) the concentration of the packet copying process at a particular node is avoided and (2) the route to the farthest destination is guaranteed to be the shortest. The performance of the algorithm is evaluated from the viewpoint of computational complexity, and it is shown that the proposed algorithm is suited to multicast communication. © 1999 Scripta Technica, Syst Comp Jpn, 30(10): 69–75, 1999