Hierarchical networks and the LSA N-squared problem in OSPF routing
A. V. Aho, D. Lee · 2002
With N routers in a network running the open shortest path first (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 link state advertisements (LSA) 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(/sup 3//spl radic/(N/spl middot/N)).