The TCP/IP Guide - OSPF Route Determination Using SPF Trees

NOTE: Using software to mass-download the site degrades the server and is prohibited.
If you want to read The TCP/IP Guide offline, please consider licensing it. Thank you.

The Book is Here... and Now On Sale!

Searchable, convenient, complete TCP/IP information.

The TCP/IP Guide

The TCP/IP Guide
9 TCP/IP Lower-Layer (Interface, Internet and Transport) Protocols (OSI Layers 2, 3 and 4)
      9 TCP/IP Internet Layer (OSI Network Layer) Protocols
           9 TCP/IP Routing Protocols (Gateway Protocols)
                9 TCP/IP Interior Routing Protocols (RIP, OSPF, GGP, HELLO, IGRP, EIGRP)
                     9 Open Shortest Path First (OSPF)

OSPF Hierarchical Topology, Areas and Router Roles

OSPF General Operation and Message Types

OSPF Route Determination Using SPF Trees
(Page 2 of 4)

OSPF Route Determination Example

I can almost see your eyes glazing over, so let's go back again to the example we have been using in this section. I am going to assume we are looking at the whole AS as a whole in basic topology, for simplicity. In Table 124, I have repeated the LSDB for this AS, and I have taken the liberty of replacing the “[“s with cost metrics; these are shown in Figure 181 as well. Again, remember there is no cost to reach a router from a network, so those links have a non-zero cost only going from the router to the network.

**Table 124: Example OSPF Link State Database (LSDB) With Costs**
To Router / Network	From Router				From Network
To Router / Network	RA	RB	RC	RD	N1	N2	N3	N4
RA					0	0
RB			5			0	0
RC		5				0	0
RD							0	0
N1	2
N2	3	4	3
N3		5	6	1
N4				4

**Figure 181: Example OSPF Autonomous System With Costs**
This is the same sample AS that is shown in Figure 179, but with costs assigned to each of the links between routers and networks. Costs between routers and networks are applied only in the direction from the router to the network.

Now, let's construct the SPF tree for RC. We can do this in iterations, as follows (this is shown graphically in Figure 182 as well for your convenience):

**Figure 182: OSPF Route Determination Using The Shortest Path First Algorithm**
This diagram shows graphically how a router, in this case RC, determines the best path to various networks. The arrows here represent not the transfer of data but rather the examination of various links from a router to other routers or networks. In panel #1, RC examines its LSDB and determines the cost for each of its directly-linked devices. In #2, the second level of the SPF tree is constructed by adding to those numbers the costs of all routers/networks that connect to the routers/networks found in panel #1. (The red arrows represent “looking back” in the direction we came from in the prior step, which we don’t pursue.) In #3 the process continues, resulting in the determination of a cost of 5 for RC to reach N1 and 10 to reach N4.

First Level

To construct the first level of the tree, we look for all devices that RC can reach directly. We find:

RB, with a cost of 5.
N2, with a cost of 3.
N3, with a cost of 6.

OSPF Hierarchical Topology, Areas and Router Roles

OSPF General Operation and Message Types

If you find The TCP/IP Guide useful, please consider making a small Paypal donation to help the site, using one of the buttons below. You can also donate a custom amount using the far right button (not less than $1 please, or PayPal gets most/all of your money!) In lieu of a larger donation, you may wish to consider purchasing a download license of The TCP/IP Guide. Thanks for your support!

Home - Table Of Contents - Contact Us

The TCP/IP Guide (http://www.TCPIPGuide.com)
Version 3.0 - Version Date: September 20, 2005

© Copyright 2001-2005 Charles M. Kozierok. All Rights Reserved.
Not responsible for any loss resulting from the use of this site.