This paper studies the problem of constructing a minimum-cost multicast tree (or Steiner tree) in which each node is associated with a cost that is dependent on its degree in the multicast tree. The cost of a node may depend on its degree in the multicast tree due to a number of reasons. For example, a node may need to perform various processing for sending messages to each of its neighbors in the multicast tree. Thus, the overhead for processing the messages increases as the number of neighbors increases. This paper devises a novel technique to deal with the degree-dependent node costs and applies the technique to develop an approximation algorithm for the degree-dependent node-weighted Steiner tree problem. The bound on the cost of the tree constructed by the proposed approximation algorithm is derived to be (2lnk/2 +1)(WT*+B), where k is the size of the set of multicast members, WT*is the cost of a minimum-cost Steiner tree T*, and B is related to the degree-dependent node costs. Simulations are carried out to study the performance of the proposed algorithm. A distributed implementation of the proposed algorithm is presented. In addition, the proposed algorithm is generalized to solve the degree-dependent node-weighted constrained forest problem.

This paper studies the problem of constructing application-layer multicast trees for end-system based voice conferences in which voice mixing and replication are performed at end systems. This problem is formulated as a degree-constrained node-weighted Steiner tree problem with a degree-dependent cost associated with each node, which is a generalization of the degree-constrained node-weighted Steiner tree problem with a fixed cost associated with each node. This paper devises a novel technique to deal with degree-dependent nodal costs and develops a bicriteria approximation algorithm, with the degree of each node and the cost of the tree as two objectives, for this more general Steiner tree problem. The bound on the degree of each node and the bound on the cost of the tree constructed by the bicriteria approximation algorithm are derived. Two heuristic algorithms which construct multicast trees that obey the degree constraint on each node are obtained by modifying the bicriteria approximation algorithm. The performances of the two heuristic algorithms are studied via simulations.

This paper studies the problem of constructing a minimum-cost multicast tree (or Seiner tree) in which each node is associated with a cost that is dependent on the degree of the node on the multicast tree. The cost of a node may depend on its degree on the multicast tree due to a number of reasons. For example, a node may need to perform various processing for sending messages to each of its neighbors on the multicast tree. Thus, the overhead for processing the messages increases as the number of neighbors increases. This paper devises a novel technique to deal with the degree-dependent node costs and applies the technique to develop an approximation algorithm for the problem. The bound on the cost of the multicast tree constructed by the proposed approximation algorithm is derived.

This paper considers the problem of constructing minimum-delay multicast trees for message dissemination in overlay networks in which nodal delays for processing messages are taken into account in addition to communication delays. The objective is to find a multicast tree to deliver a message from a source to multiple destinations in minimum delay time. This paper introduces a new delay measure called reception-and-processing delay that takes nodal processing delays into account for constructing multicast trees. In the process of constructing a multicast tree, the branches of the multicast tree may intersect or overlap with each other. An efficient method is devised to avoid this undesirable phenomenon. Several heuristic algorithms are developed for constructing multicast trees. The performances of the heuristic algorithms are studied via simulation. Our simulation results show that constructing the multicast tree by iteratively attaching the destination node with the smallest reception-and-processing delay to the current multicast tree yields the lowest average multicast delay among the heuristic algorithms studied in this paper.