OSPF-based hybrid approach for scalable dissemination of QoS parameters

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 communication and processing overheads in control plane since nodes may receive multiple copies of the same advertisement. These overheads become significant in protocols that support quality-of-service (QoS) routing, where links are associated with dynamic metrics (e.g., available bandwidth) that need to be advertised frequently. The overheads can be significantly reduced using tree-based broadcasting approaches. Although a number of such approaches have been proposed in the literature, they have not been used in real networks because of their complexity and/or unreliability. In this paper, we propose a hybrid link-state dissemination approach that combines the best features of flooding and tree-based broadcasting. Our approach is particularly suited for the dissemination of "dynamic" link metrics (e.g., available bandwidth), which are often used in QoS-based path selection and traffic engineering. In our approach, topological changes and first-time LSAs (link-state advertisements) are flooded, whereas refresh LSAs (the ones that provide updated information on the dynamic metrics) are sent using tree-based broadcasting. The broadcast trees in our approach are constructed dynamically during the flooding of the first-time LSA, without the need for the complex algorithms of previously proposed tree-based approaches. Two versions of the proposed scheme are provided; one being more suitable for quasi-static topologies (i.e., link failure rate is low) while the other is aimed at highly dynamic networks. We show how both versions can be integrated into the OSPF protocol. We further provide a working implementation of both versions, obtained after modifying Moy's OSPF source code [OSPF: Complete Implementation (with CD-ROM), Addison Wesley, Reading, MA, 2000]. We contrast the communications and processing overheads of our scheme with those of flooding and pure tree-based broadcasting, using both analysis and simulations. Our results indicate that the hybrid approach has a significantly lower overhead than flooding; yet it enjoys the simplicity, reliability, and fast convergence of flooding.