Spanners and Message Distribution in Networks
Arthur Farley, Andrzej Proskurowski, Kurt Windisch
Committee:
Technical Report(Dec 1969)
Keywords:

We investigate the applicability of k-spanners as shared virtual topologies for intradomain broadcast and multicast on the Internet. A light-weight k-spanner is a spanning subgraph of a network that has both relatively small total edge weight and small multiplicative penalty (at most k) on all point-to-point distances. We define broadcasting and multicasting protocols based on flooding of a spanner, followed by pruning the distribution tree within the spanner and then joining in the network to form sender-based trees, if desired. We evaluate k-spanners (for 2 ≤ k ≤ 7) in terms of number of edges, diameter, and average distance on sets of randomly generated graphs having properties similar to intradomain networks. We compare values of these metrics for spanners with those for given graphs and single-source minimum-distance spanning trees. Results show that a 3- or 4-spanner could serve as a good virtual topology for message distribution, having fewer edges than the full network yet lower average distance and diameter than a single-source, minimum-distance spanning tree.