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

Turgay Korkmaz, Marwan Krunz

Research output: Contribution to conferencePaperpeer-review

7 Scopus citations


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.

Original languageEnglish (US)
Number of pages5
StatePublished - 2002
EventGLOBECOM'02 - IEEE Global Telecommunications Conference - Taipei, Taiwan, Province of China
Duration: Nov 17 2002Nov 21 2002


OtherGLOBECOM'02 - IEEE Global Telecommunications Conference
Country/TerritoryTaiwan, Province of China

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Global and Planetary Change


Dive into the research topics of 'Hybrid flooding and tree-based broadcasting for reliable and efficient link-state dissemination'. Together they form a unique fingerprint.

Cite this