OSPF Open Shortest Path Firs

OSPF designated router (DR)

2012-04-13T06:37:00.000-07:00

The OSPF protocol elects a designated router that is responsible for keeping
all routers updated on shortest routes. Instead of exchanging route infor-mation with ever other router in the network, routers only communicate
their routes to the designated router. The designated router then updates
everyone on the routes available. Consolidating the exchange of information
about routes to the designated router improves the efficiency of the network
because less bandwidth is consumed by having each router communicate its
routes only to the designated router, instead of communicating with every
other router in their area.
Routers send their LSA packets to a multicast address (224.0.0.6). The DR lis-tens to this multicast IP address. The DR relays routing information back to the routers by sending route updates to the multicast address 224.0.0.5. All
routers running OSPF are listening to the 224.0.0.5 multicast IP address.
Selecting a designated router
The designated router is elected based on the OSPF priority. The OSPF prior-ity is a value between 0 and 255 assigned to a router interface using the ip
ospf priority value Cisco IOS command. The default OPSF priority is
set to 1.
The router with the highest OPSF priority becomes the designated router.
If two routers have the same OPSF priority, the router ID (RID) is used to
decide which one becomes the DR.

It is best practice to configure a core router — or the largest, most highly avail-able, and most powerful router — in your network to be the designated router.
You can control which router is elected DR using either of the following:
✦ Loopback interfaces: Create loopback interfaces on each router in your
network, and set the highest IP address on the one you want to become
the DR.
✦ OSPF priority: Set the highest OPSF priority on the router and interface
you want to become the DR.

OSPF Routing Hierarchy

2012-04-13T06:32:00.000-07:00

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.

OSPF Cost metric

2012-04-13T06:30:00.000-07:00

OSPF uses the cost metric to evaluate the quality of each link.
Route cost is a metric calculated based on the bandwidth of each link. Cisco
routers calculate the cost by dividing a default bandwidth of 100 Mbps (100
million bits per second) by the actual bandwidth of the link.
For example, the following list illustrates the default OSPF cost calculated by
Cisco routers for various bandwidths:
✦ 64-Kbps (64,536-bits-per-second) link: 100,000,000 / 64,536 = 1,562
✦ 1.544-Mbps (T1) link: 100,000,000 / 1,544,000 = 64
✦ 10-Mbps link: 100,000,000 / 10,000,000 = 10
✦ 100-Mbps link: 100,000,000 / 100,000,000 = 1
✦ 1-Gbps link: 100,000,000 / 1,000,000,000 = 0.1
✦ 10-Gbps link: 100,000,000 / 10,000,000,000 = 0.01
OSPF chooses the route with the lowest cost. You can modify the default
reference bandwidth used to calculate the OSPF cost using the auto-cost
reference-bandwidth Cisco IOS command in global configuration mode.
It is very important to set the same reference bandwidth on all routers in
your network.
For example, if most links in your network are 1 Gbps, you set the reference
bandwidth to 1 Gbps instead of 100 Mbps using the following commands:
RT6751>enable (or en)
RT6751#configure terminal (or config t)
RT6751(config)#auto-cost reference-bandwidth 1000000000
RT6751(config)#exit
RT6751#disable
RT6751>

OSPF Route updates

2012-04-13T06:29:00.000-07:00

OSPF continues to update routers about available routes after they have
converged. These route updates are sent in the form of link-state advertise-ment (LSA) packets. Routers exchange LSA packets to maintain their link-state tables . After they have built their neighbor and link-state tables, routers
know the following:
✦ Their neighbors
✦ The network topology in their immediate vicinity
✦ The network topology in the vicinity of their neighbors
Next, each router evaluates the quality of each route registered in the link-state table.

OSPF Convergence

2012-04-13T06:28:00.000-07:00

The OSPF routing protocol converges within seconds because neighbor
routers only exchange “Hello” messages initially. During the convergence
process, routers get to know each other, exchanging communication param-eters and setting up their neighbor table.
Routers can only become neighbors if the following things occur:
✦ They have successfully exchanged “Hello” messages
✦ They have interfaces in the same routing domain (that is, in the same
autonomous system)
✦ They have their hello timers set to the same values. Hello timers define
the following:
• The frequency at which routers send each “Hello” message to each
other
• How long neighbors wait before they consider a router out of network
Hello messages are not only sent during the convergence process but also
afterward to keep track of which routers are still in the network. If a router
becomes unavailable and stops sending Hello messages, one of the hello
timers defines how long neighbor routers wait for a Hello message before
they consider the unavailable router out of the network

Characteristics of OSPF

2012-04-12T06:14:00.002-07:00

Here are the main characteristics of the OPSF protocol:
✦ Route updates are only sent when routes change. Each router sends a
link-state advertisement (LSA) whenever a change occurs in one of the
routes known to the router.
✦ LSAs contain information about the route that changed only.
✦ Routers exchange “Hello” messages during the convergence process to
build their neighbor tables.
✦ OSPF, like RIP, is supported on non-Cisco routers.
✦ OSPF supports variable-length subnet masking (VLSM).
✦ OSPF supports an unlimited number of network hops.
✦ OSPF scales out very well because
• It divides the routing domain (autonomous system) into areas.
• It classifies routers hierarchically.

• It converges very quickly.
• It sends routes updates (LSAs) only when routes change, minimizing
route change traffic.
• LSA packets have a small footprint.
• LSA traffic is consolidated to the designated router.
• LSA traffic is minimized when routes are summarized.

Routing tables of OSPF

2012-04-12T06:12:00.001-07:00

OSPF maintains these routing tables:
✦ Neighbor table: This table keeps track of the neighbors of a router.
Each router running OSPF maintains its own neighbor table. Thus, each
router has a clear picture of its peer routers, and each router has a
clear picture of the network topology in its immediate vicinity.
✦ Link-state table: This table keeps track of the state of the links on neigh-bor routers. In other words, this table keeps track of the state of the
routes on neighbor routers. Each router running OSPF maintains its own
link-state table. Thus:
• Each router has a clear picture of the topology in the immediate
vicinity of its neighbors.
• Using the neighbor table and the link state, each router has a two-level knowledge of the network topology: the topology in its immedi-ate vicinity and the topology in the vicinity of its neighbors.
✦ Routing table: This table keeps track of the metrics of each link tracked
by the link-state table. Hence, whereas the neighbor and link-state
tables are used to quantify routes, the routing table is used to qualify
each route.

Introducing Open Shortest Path First (OSPF)

2012-04-12T06:04:00.000-07:00

Link-state routing protocols build their routing tables independently based
on route updates they receive from their neighbors. Link-state protocols
do not merge the routing tables of neighbor routers. Link-state protocols
enable routers to have a clear image of neighbors, network topology, and
routes to their neighbors and beyond by maintaining not just routing tables
but also topology and neighbor tables.
OSPF complies with all these link-state routing protocol characteristics

Open Shortest Path First (OSPF) Protocol

2012-04-12T06:01:00.002-07:00

OSPF is a link-state routing protocol. OSPF was developed based on an
open standard and is supported by several router manufacturers.
OSPF is widely used as an interior gateway protocol (IGP), especially in large
network environments. Interior gateway protocols, including OSPF, route
within a single routing domain. A single routing domain, also known as an
autonomous system (AS), is a group of routers and network addresses that
use a common routing system. For example, a network that uses OSPF on all
routers is an autonomous system. This network can be connected to a large
service provider network that is using another routing protocol such as IS-IS
(Intermediate System–to–Intermediate System). The service provider’s IS-IS
network is another autonomous system. The protocol used to route between
autonomous systems and between large Internet service providers is called
Border Gateway Protocol (BGP). It is not necessary to know all the details
about IGPs and BGPs, but it is important to know that OSPF is classified as
an interior gateway protocol.