Parallel Flow-Constrained Multicast Algorithms

Abstract

Multicast is an important operation in communication networks and its attainment relies on the performance of the underlying multicast routing algorithm. The multicast routing problem is well known to be NP-Hard and many heuristic algorithms have been developed . Moat heuristic algorithms take time to compute the MST (Minimum Spanning Tree) of some specified nodes. Thus, the heuristic performance can be improved by exploiting parallelism within the algorithms when executed in a network node. In this article we investigate efficient parallel implementations for four MST algorithms-the Esau-Williams’s Prim’s Kruskal’s and Sollin’s algorithms. The optimization goal of these algorithm is not only to construct a minimum cost spanning tree for a designated group of nodes, but also to satisfy the maximum flow constraint on each link. The corresponding parallel programs are implemented with message-passing mechanism in the Parallel Virtual Machine (PVM) environment.