@article {Simula.ND.102,
	title = {Evaluating Steiner Tree Heuristics and Diameter Variations for Application Layer Multicast},
	journal = {Computer Networks},
	volume = {52},
	number = {15},
	year = {2008},
	note = {Special issue on Complex Computer and Communication Networks, Elsevier},
	month = {October},
	pages = {2872-2893},
	abstract = {Latency reduction in distributed interactive applications has been studied intensively. Such applications may have stringent latency requirements and dynamic user groups. We focus on application-layer multicast with a centralized approach to the group management. The groups are organized in overlay networks that are created using graph algorithms that create a tree structure for the group. A tree has no cycles and uses a small routing table, as opposed to a connected overlay mesh. We investigate a group of spanning tree problems that are referred to as Steiner tree problems, and we have a particular focus on reducing the diameter of a tree, which is the maximum pairwise latency in a tree. In addition, we focus on reducing the time it takes to execute membership changes. In that context, we use core-selection heuristics to find well-placed client nodes, and edge-pruning algorithms to reduce the number of edges in an otherwise fully meshed overlay. Our edge-pruning algorithms strongly connect well-placed client nodes to the remaining group members, to create new and pruned group graphs. Consequently, when a tree algorithm is applied to a pruned group graph, it is manipulated into creating trees with a smaller diameter.We devised new Steiner-tree heuristics that reduced the diameter, and also proposed new edge-pruning algorithms to make the tree construction faster. These heuristics and algorithms were implemented and analyzed experimentally along with several spanning-tree and core-selection heuristics found in the literature. We found that a full-mesh of shortest paths makes it difficult for Steiner-tree heuristics to find better trees than spanning tree algorithms. The network seen from the application layer is in fact a full mesh of shortest paths. In addition, we found that faster Steiner-tree heuristics that do not explicitly optimize the diameter are able to compete with slower heuristics that do optimize it.},
	doi = {10.1016/j.comnet.2008.06.003},
	author = {Vik, Knut-Helge and Halvorsen, P{\r a}l and Griwodz, Carsten}
}
