An Efficient Technique for Message Flooding Based on Partial Shortest-Path Trees in Wired Networks

We propose a technique for reducing the number of message duplicates during message flooding in wired networks. The key feature of our proposal is that each node keeps the partial information of shortest path trees whose roots are in its neighborhood. When receiving the flooding message, each node generates its duplicates and forwards them to a subset of neighbors, which are on the partial shortest path tree rooted at the message source. The partial information on shortest path trees is stored in message forwarding table of each node. We show that the partial shortest path tree can be constructed in a fully-distributed manner by simply using dummy message flooding. Our proposal can largely reduce the number of message duplicates while it guarantees the full reachability and keeps the time to reach the same as that in the full flooding. Duplicate reduction effect of our proposal is theoretically evaluated and numerically examined by simulation experiments.