OSPF Routing Hierarchy

OSPF uses the Dijkstra shortest path first (SPF) routing algorithm to calculate
the shortest path from a router to each destination network.

The Dijkstra SPF routing algorithm does the following:
 ✦ Considers the router to be the root of a tree
 ✦ Considers each destination network (router) to be a branch or a leaf in
that tree
 ✦ Calculates the shortest route from the root of the tree (the router) to
each branch and to each leaf (to each destination network)
Effectively, the Dijkstra SPF algorithm calculates the shortest route from
each router to each network in the OSPF routing domain (or autonomous
system), b ecause each router is the root of its own tree. This creates a shortest-
path tree for each router.
However, OSPF does not need to calculate the shortest path from each router
to each destination if the network is designed in a hierarchical fashion.
Router trees overlap in a hierarchical design. This improves the efficiency of
OSPF because after the Dijkstra SPF algorithm calculates the shortest routes
for a branch of the tree, it doesn’t need to recalculate those routes as you
move up the tree to the root router.
Figure 6-1 shows the recommended network topology for OSPF.
Observe the following:
 ✦ One router is the root of the OSPF tree (although you can configure
more than one root router).
 ✦ The OSPF routing domain (or autonomous system) is divided into areas
with at least one designated router (DR) in each area. It is best practice
to have a  backup designated router (BDR) in each area as well.
In this example, the tree that starts at router 10-1, going down, is
 ✦ Part of the DR-10 router tree in area 10
 ✦ Part of the BDR-10 router tree in area 10
 ✦ Part of the root tree in the area 0
This is good, because after OSPF (the Dijkstra SPF algorithm) calculates the
shortest route from router 10-1 to each destination underneath, the DR-10
router, the BDR-10 router, and the root router can readily use those shortest
routes to destinations under the 10-1 router.

Figure 6-1:
OSPF routing hierarchy.

. . .
OSPF route summarization
The reuse of previously calculated shortest routes is leveraged by route sum-
marization. Route summarization allows routers to identify common network
IP address spaces and create a summarized route for the IP address space as
opposed to creating a route for each IP address individually. This improves
network throughput because routers sharing a summarized route send LSA
packets upstream only when the summarized route changes, as opposed to
sending LSA packets upstream for each of their (internal, or downstream)
routes. For example, in Figure 6-1:
 ✦ The tree underneath router DR-10 is one IP address space (subnet).
 ✦ The tree underneath router BDR-10 is another IP address space
(subnet).
 ✦ The tree underneath router 10-1 is one IP address space (subnet).
 ✦ The tree underneath router 10-2 is another IP address space (subnet).


However, the DR-10 tree includes the 10-1 and the 10-2 trees. Similarly, the
BDR-10 tree includes the 10-1 and the 10-2 trees.
Suppose that networks in area 10 have the following IP addresses:
 ✦ Router DR-10: 172.10.75.0
 ✦ Router BDR-10: 172.10.76.0
 ✦ Router 10-1: 172.10.77.0
 ✦ Router 10-2: 172.10.78.0
The first 2 bytes are the same for all subnets in area 10: 172.10. The third
byte is different. Table 6-1 examines these IP addresses in binary.
Table 6-1  Route Summarization
IP Address Byte 1 (172)Byte 2 (10)Byte 3 (75, 76, 77, 78)Byte 4 (0)
 172.10.75.0 1100 0000 0000 1010 0100 1011 0000 0000
172.10.76.0 1100 0000 0000 1010 0100 1100 0000 0000
172.10.77.0 1100 0000 0000 1010 0100 1101 0000 0000
172.10.78.0 1100 0000 0000 1010 0100 1110 0000 0000
Observe that the IP address of these networks is almost the same except for
byte 3. Now from the perspective of the root router in area 0, this difference
is irrelevant because the DR-10 and BDR-10 trees both include the 10-1 and
the 10-2 trees. Hence, if the root router in area 0 knows how to get to DR-10
and to BDR-10, it knows how to get to everyone underneath. So, it makes
sense to expose only one route up to the root router instead of exposing all
four. That is exactly what route summarization accomplishes.
So how do you summarize these routes? Table 6-1 shows that only byte 3
varies. Specifically, only the second nibble in byte 3 varies. Assume that
nibble 2 in byte 3 would be the same for all routers (for example, 0100
1011, which is 75). You would have IP address 172.10.75.0 for all networks.
However, you can only do this if you modify the subnet mask.
The subnet mask changes from 255.255.255.0 (/24) to 255.255.240.0 (/20),
because the variable part of the IP address now includes 4 more bits in
byte 3. Table 6-2 details the following:

✦ The original subnet mask, where bytes 1 and 2 represent the network IP
address and bytes 3 and 4 are used for variable intranetwork addresses.
 ✦ The new subnet mask for the summarized route, where byte 1 and the
first nibble in byte 2 represent the network IP address. The second
nibble of byte 2 and bytes 3 and 4 represent the variable intranetwork IP
addresses.
Table 6-2  Subnet Mask for Summarized Route
Mask               Byte 1         Byte 2        Byte 3       Byte 4
255.255.255.0 1111 1111 1111 1111 1111 1111 0000 0000
255.255.240.0 1111 1111 1111 1111 1111 0000 0000 0000
Now you can expose route 172.10.75.0/20 up to the root router in area 0. You
are telling the root router in area 0 to keep track of route 172.10.75.0/20 to
get to any of the networks in area 10.
In fact, you can have two summarized routes in this example, because both
DR-10 and BDR-10 connect to the root router in area 0:
 ✦ One route to reach the tree under router DR-10: 172.10.75.0/20
 ✦ One route to reach the tree under router BDR-10: 172.10.76.0/20
Now instead of exposing four routes up to the root router in area 0, you only
expose one (or two) summarized routes. This improves the efficiency of the
root router because it needs to maintain only one (or two) route(s) for area
10 instead of maintaining four routes.