LAPGN: Accomplishing information consistency under OSPF in General Networks (an extension)

Abstract Open Shortest Path First (OSPF) protocol is a link-state routing protocol which requires the link-state information to be synchronous, and it needs to achieve a fast convergence when the network topology changes. In this paper, we extend the Limitation Arrangement Principle (LAP) algorithm to General Networks (GN) and design an LAP-based routing algorithm in GN (LAPGN) to solve the information consistency problem of the full network under OSPF with the following operations: (i) decomposing GN into one or more Single-link Networks (SNs) with the approach of depth-first walk; (ii) re-composting the SNs to a network with regular topology structure by connecting networks and adding links; (iii) searching the undirected complete graph of three nodes round by round until it converges to a simple network topology based on region binding; and (iv) processing different converged network topologies with different LAP-based routing algorithms. We compare the proposed algorithm with the well-known OSPF algorithm over some random network topologies and six backbone topologies. The simulation results reveal that LAPGN can solve the information consistency problem and has better performance than OSPF algorithm.