Hierarchical Networks and the LSA N-Squared Problem in OSPF Routing

With N routers in a network running the OSPF routing protocol a network topology update can generate on the order of N sup 2 LSA packets. This phenomenon, known as the LSA N-Squared Problem, severely degrades network performance and scalability. Hierarchical OSPF network architectures have been proposed to reduce the number of LSAs that are generated by a network topology update. We show that equal-size areas minimize the number of LSAs. Then we derive the optimal number of areas and the size of areas to create the network producing the minimal number of LSAs. Finally, we show that the optimal network architecture reduces the number of LSAs from O(N sup 2 ) to O(N sup (1.33)).