Reducing routing table computation cost in OSPF

In a link state protocol, every router has complete topology information about the network. We argue that with such information, divide-and-conquer schemes can be used to make the protocol processing more efficient. As an example, we present a simple approach for a router running the Open Shortest Path First (OSPF) protocol to automatically detect if its interfaces lead to multiple disjoint regions within an OSPF Area. If such disjoint regions exist, this approach can make the routing table computation more efficient. Compared to OSPF, this approach can reduce the computation work by more than n times in ideal cases, where n is the number of disjoint Within Area Routing Regions (WARRs). Furthermore, route computations in different WARRs are independent and can be done in parallel to give an additional speedup of min(n-1, m), where m is the number of CPUs in the router. The correctness of the algorithm is illustrated. The implementation of this approach is very simple and requires no change to OSPF. This approach is especially suitable for routers in corporate networks and can be immediately applied to current routers.