LMST-based searching and broadcasting algorithms over Internet graphs and peer-to-peer computing systems

In a broadcasting problem, a message is sent from a source to all the other nodes in the network. Blind flooding is a classical mechanism for broadcasting, where each node retransmits received message to all its neighbors. Despite its important advantages, an increase in the number of requests or the size of the routing area produces communication overheads that limit the scalability of blind flooding, especially in networks with dynamic topologies. Theoretically optimal solution is based on minimal spanning trees (MST), but its construction is expensive. Protocols based on local knowledge are recently proposed. In weighted RNG, messages are forwarded only on links which are not the ´longest´ in any triangle. In weighted RNGQ, messages are forwarded to links which are not the longest in any triangle or quadrangle. In this paper, we propose weighted LMST as the new graph structure, and apply it for broadcasting. Each node constructs weighted MST based on its 2-hop knowledge. Weighted LMST preserves only edges that are selected by both endpoints. Any available metric, such as delay, can be used as weight. weighted RNG was shown in a previous work to perform better than existing flooding and rumor mongering (or gossip) schemes. The new parameterless weighted LMST scheme is compared to the weighted MST, RNG and RNGQ methods, showing its superiority among localized schemes.