1 of 14Abstract We have designed and implemented three multicast path finding algorithms for networkswith directed links: an optimal algorithm based on the dynamic programming technique, aheuristic algorithm with the assumption that all vertices have the multicast capability, and aheuristic algorithm for networks where some vertices do not have the multicast capability.Computation results show that the heuristic algorithms can find multicast paths whose costsare close to optimal and can operate with reasonable response time for large networks. Wediscuss applications of these path finding algorithms to set up multipoint connections.1. IntroductionWith the recent advance in terminal, high-speed transmission and switching technology, it isnow feasible to provide multimedia, multiparty communication services. In order to support theseservices, networks need to have the capability to setup/modify the following five basic types ofconnections: point-to-point, point-to-multipoint (also called Multicast), multipoint-to-point (alsocalled Concast), multipoint-to-multipoint, and point-to-allpoint (also called Broadcast). Since thevideo connections and the high speed switching and transmission components implement uni-directional paths [Bus89], in this paper we are considering directed networks with uni-directionallinks. In directed networks, the shortest path algorithm proposed by Dijkstra can be used to set uppoint-to-point connections. It is a polynomial algorithm with time complexity where is thenumber of vertices in the network [Dij59]. The minimum spanning tree algorithm can be used to setup broadcast connections and is also a polynomial algorithm with time complexity where is the number of edges in the network [Kru56]. Ov2()vOe elog()ePublished in Proceedings of INFOCOM ‘91, pp. 1274-1283, Miami, Florida, April 7-11, 1991.On Multicast Path Finding AlgorithmsChing-Hua ChowBell Communications Research445 South Street, MRE 2Q231Morristown, NJ 07960-1910Phone: (201) 829-4534Email: [email protected] of 14In a given directed graph , with a vertex set , and an edge set , a vertexwhich has the multicast capability is called a multicast vertex. A multicast path is a treerooted at vertex , with all branching vertices to be multicast vertices, and with its leaf verticesconstitute , . is called the source of the multicast path and is called the destinationsof the multicast path. The multicast path finding problem can be defined as follows: Given a directed graph , with a cost function c: , find a minimumcost multicast path . The algorithms for finding a multicast path are called multicast path finding algorithms. Theyare similar to those for the Steiner tree problem which is defined as follows:Given an undirected graph together with a cost function , and, the Steiner tree problem for in G is to find a minimum cost, connectedsubgraph of G which contains all the vertices (and possibly some other vertices,which are called Steiner vertices).The Steiner tree problem was shown to be NP-hard [Karp 72] and a good survey of algorithms is in[Win 87]. Among the optimal algorithms, the dynamic programming algorithm of Dreyfus andWagner [DRE 72] seems to outperform others. For heuristic algorithms, the algorithm proposed byTakahashi and Matsuyama [TAK 80] and that by Rayward-Smith [RAY 86] perform quite well. Theformer is based on the shortest path to a subset of vertices. The later is based on a heuristic function toselect Steiner vertices. Waxman further considered optimizing a sequence of multicast connectionrequests [WAX 88]. Tu and Leung gave a sketchy description of a source-based spanning treealgorithm used in setting up multicast connections in a wide-area multicast packet switching network[Tu90].In this paper we only discuss centralized multicast path finding algorithms. Research resultshave been reported on distributed versions. Deering and Cheriton’s paper provides a good survey onmulticast routing in Datagram Internetworks and Extended LANs [Dee90]. However, the multimediamultipoint connections which we are considering are much more dynamic and complex. It is notrestricted to the group address scheme, and involves reservation of resources such as conferencebridges and protocol converters.The rest of the paper is organized as follows: Section 2 describes an optimal multicast pathfinding algorithm. Section 3 describes a heuristic multicast path finding algorithm which performswell for networks where almost all vertices are multicast vertices. Section 4 presents a heuristicalgorithm which perform well for networks with small number of multicast vertices. Section 5presents computation results of our implementations of these three algorithms, showing that the twoheuristic algorithms provide comparable performance at much lower complexity. Section 6 illustrateshow other multipoint connections can be solved by the combination of the shortest path algorithm andthe multicast path finding algorithm. Section 7 discusses related research issues.GVE,()=VEsD→sV∈DDV⊂sDGVE,()=Eℜ+→sD→GVE,()=c:E ℜ+→V' V⊂V'V'3 of 142. An Optimal Multicast Path Finding AlgorithmHere we present an optimal multicast path finding algorithm based on the dynamicprogramming technique proposed by Dreyfus and Wagner [DRE 72]. Intuitively, for an optimalmulticast path, , the technique starts by first finding all the optimal multicast paths to smallsubsets of . It then finds all the optimal multicast paths to larger subsets of by merging previousobtained optimal multicast paths. To facilitate the presentation, first let us define some of the termsused in the algorithm.Given a directed graph , is an optimal multicast path . Thecost of a multicast path , , is the sum of all edge costs in . is a multicastpath which is the minimum cost union of two multicast paths, say and , whichspan multicast vertex and with their destinations being the non-empty disjoint subsets of . The -vertex set of is the set of all vertex sets, such that and . For example, the 2-vertex set of is and has elements.The optimal multicast path finding algorithm for is as follows:for do = shortest path from to donefor do {for -vertex set of and do find wheredone if ( ) break; // we do not need where .for -vertex set of D and dofind wheredone}find where In terms of the time complexity, the inner loop that calculates the will tryall possible non-empty vertex sets of