An efficient network-wide broadcasting based on hop-limited shortest-path trees

We propose a technique for reducing the number of message duplicates during network-wide broadcasting in wired networks. The key feature of our proposal is that each node keeps the information on hop-limited shortest path trees whose roots are within a certain number of hops from each node. When receiving the message, each node generates its duplicates and forwards them to a subset of neighbors, which are on the hop-limited shortest path tree rooted at the message source. The information on hop-limited shortest path trees is stored in message forwarding table of each node. We show that the hop-limited shortest path tree can be constructed in a fully-distributed manner by simply using dummy message flooding or exchanging distance vectors with poisoned reverse. Our proposal can largely reduce the number of message duplicates compared with the flooding while it is more scalable than the global-shortest-path-tree-based delivery. We also note that it guarantees the full reachability in static conditions and the time to reach of the proposal is the same as that of the flooding or the global-shortest-path-tree-based delivery. Duplicate reduction effect of our proposal is theoretically evaluated and numerically examined by simulation experiments.