A Simple Efficient Policy to Reduce Broadcast Redundancy in Wired Networks

Broadcasting plays an important role in computer networks and is the base of link-state routing protocols. Flooding is the simplest approach to implement network-wide broadcasting, but it suffers from high overhead. Flooding-based variants like multi-point relay (MPR) and tree-based flooding can reduce the broadcast redundancy efficiently, with the demand of maintaining specific routing structure in a network. In this paper, we propose a simple and efficient policy to reduce the broadcast redundancy in flooding-based approaches. The policy eliminates the unnecessary forwarding operations to common neighbors. While the flooding approach has the communication complexity of
$\boldsymbol{O(m)}$
in wired networks, the policy can reduce the complexity to
$\boldsymbol{O(m-t^{*}n)}$
, where
$\boldsymbol{m}$
is the link number and
$\boldsymbol{n}$
is the node number of a network, and
$\boldsymbol{t}$
is the average common neighbor degree which is a newly-proposed metric in this paper. Simulation results on different networks have verified the effectiveness of the proposed policy which reduces the broadcast redundancy of all flooding-based approaches. The application of the policy to link-state routing protocols is also discussed.