Spanners and message distribution in networks Original Research Article

We investigate the applicability of spanners as substructures that offer both low cost and low delay for broadcast and multicast. A k-spanner has the potential to offer lower delay than shared multicast trees because it limits the distance between any two nodes in the network to a multiplicative factor k of the shortest-path distance. Using simulation over random topologies, we compare k-spanners to single-source minimum-distance spanning trees and show that a k-spanner can have similar cost and lower delay. We illustrate that by varying the value of k a spanner can be made to gradually favor cost over delay. These results indicate the spanner can reduce the cost of flooding, which is a basic mechanism used in multicast routing protocols.