Title :
Hierarchical networks and the LSA N-squared problem in OSPF routing
Author :
Aho, Alfred V. ; Lee, David
Author_Institution :
Lucent Technol. Bell Labs., Murray Hill, NJ, USA
Abstract :
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 N2 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(N2) to O(3√(N·N))
Keywords :
network topology; optimisation; packet switching; protocols; telecommunication network routing; LSA N-squared problem; LSA packets; OSPF routing protocol; equal-size areas; hierarchical OSPF network architectures; link state advertisements; network performance; network scalability; network topology update; open shortest path first routing; optimal network architecture; optimisation; Bandwidth; Degradation; Intelligent networks; Network topology; Routing protocols; Scalability;
Conference_Titel :
Global Telecommunications Conference, 2000. GLOBECOM '00. IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
0-7803-6451-1
DOI :
10.1109/GLOCOM.2000.892036