Hybrid flooding and tree-based broadcasting for reliable and efficient link-state dissemination

Current link-state routing protocols (e.g., OSPF) use flooding to disseminate link-state information throughout the network. Despite its simplicity and reliability, flooding incurs unnecessary communications overhead since nodes may receive multiple copies of the same advertisement. This extra overhead becomes an issue in the context of quality-of-service (QoS) routing, where link state is dynamic and needs to be advertised frequently. The advertisement overhead can be significantly reduced by using tree-based broadcasting approaches. Although several of these approaches have been proposed in the literature, they are not used in practice because of their complexity and/or unreliability. We propose a new link-state dissemination approach that combines the best features of flooding and tree-based broadcasting. Our hybrid approach is particularly suited for "dynamic" link metrics (e.g., available bandwidth). It uses periodic flooding to advertise topology changes and first-time LSAs (link-state advertisements), and uses tree-based broadcasting to disseminate subsequent refresh LSAs. The broadcast trees in our approach are constructed dynamically during the flooding of the first LSA, without the need for the complex algorithms of previous tree-based approaches. Two versions of our dissemination approach are presented, with one being more suitable for networks with frequent topological changes. We prove the correctness of our approach and contrast its communications overhead with flooding and pure tree-based broadcasting. The results indicate that our hybrid approach has a significantly lower overhead than flooding; yet it enjoys the simplicity, reliability, and fast convergence of flooding. Finally, we outline how OSPF can be extended to support the proposed dissemination approach.