Open Shortest Path First is the dynamic
routing protocol based a link-state algorithm. In the upcoming few posts
I will attempt to explain the basics of OSPF operation. Cisco CCNA
level of expertise assumes that the candidates know how to implement it
in a single area. In my OSPF related posts I will go a bit beyond CCNA
requirements but not too much, just enough to help you appreciate this
fascinating solution and put OSPF into practice.
Link-state algorithm is faster and more accurate in selecting the best
path compared to distance vector approach. The latter algorithm allows
routers to know how far the destinations are (distance) and the next-hop
router(s) the packets should be sent to (vector). Thus, the routers do
not know the topology of the network.
Routers using link-state algorithm
create "a map" of the network which allows them to choose paths more
accurately. Even though they are more demanding hardware-wise (CPU and
RAM memory) they supersede distance vector based solutions.
OSPF Basic Operation
OSPF
is a very complex routing protocol but its fundamental operation is
quite simple. The steps of operation might be pictured as follows:
- Each router sends so called hello packets out
of all OSPF-enabled interfaces. This way, the OSPF-enabled router
discovers directly connected routers which also run OSPF. If certain
parameters in the hello packets match between the neighboring routers,
they form the relationship called the adjacency. It is a sort of virtual communication between them.
- Then, each router exchanges special packets called Link State Advertisements (LSAs) with its neighbors (adjacent routers). In OSPF terminology the word link is
the same as the interface. LSAs contain details such as:
addresses/network masks configured on the links (interfaces running OSPF
of course), the metric, the state of the link (which is its relation to
the rest of the network), list of neighbors connected to the link.
- Each router stores the LSAs in its Link State Database (LSDB). These LSAs are then flooded (advertised) to all OSPF neighbors. As a result of the LSA flooding, all routers in the area have
identical LSDBs. An analogy would be having the same road map of a
given country which all drivers use. Their journey's starting point is
different but the map is still the same.
- Each router runs Dijkstra's algorithm to
select the best path from this topological database (LSDB). This way,
each router creates loop free graph indicating the shortest (best) path
to each network/subnet advertised. The best paths end up in the routing
table.
OSPF Network Types
OSPF distinguishes between two major types of networks:
- Transit Networks - Networks which have two or more attached routers. The packets might be originated or passing through this type of network.
- Stub Networks - Networks which have only one router attached
(one exit point). Packets are either originated or destined to these
types of networks. A loopback interface is a type of stub network as
well. The loopbacks are by default advertised as /32 prefixes
(255.255.255.255). If you want to advertise loopbacks with their real
network mask length, you must change the OSPF mode of operation to
point-to-point (presented in the upcoming posts).
More specifically OSPF defines five different types of networks it can operate on. These are:
- Broadcast - such as Ethernet, Token-Ring
- Non Broadcast Multiple Access (NBMA) - such as Frame-Relay, ATM, X.25 (they may but do not have to be fully meshed)
- Point-To-Multipoint - such as Frame-Relay but treated as point-to-point links (Hub and Spoke)
- Point-to-Point - such as using PPP, HDLC protocols
- Virtual Links - used in special situations if the OSPF area 0
(backbone area) is partitioned or if an OSPF area cannot be connected
to the area 0 directly
There are some differences in OSPF operation, depending on
what type of network it runs on. I will explain the relevant details in
the upcoming posts.
OSPF routers will go through multiple states with their
neighbors before they are ready to route the packets. Some of them will
be used on all type of the networks but others only on specific types of
networks listed above.
OSPF Neighbor State Machine
All possible states between the neighbors are shown in pic. 1. They are also referred to as Neighbor State Machine.
Down
In this state, a router has not heard a hello packet from any OSPF neighbor yet.
Attempt
This state is applied only on NBMA
networks in which the neighbors are not discovered dynamically but must
be configured manually ('neighbor' statement in the config-router context).
Init
A router has heard a hello packet from
its neighbor(s), which among other parameters the Router IDs of all the
neighbors are listed (look at hello packet structure in the
next post).
2-Way
A router has seen its own Router ID in
the hello packet from the neighbor(s). This means that bidirectional
communication has been established between the routers.
ExStart
In this state the master/slave relationship is established necessary to exchange Database Description Packets.
Since all the packets have their sequence number allowing routers to
detect more recent information, initial numbers are negotiated in this
state. The router with the highest Router ID becomes the master.
Exchange
The routers will send Database Description packets (description of the LDSB). Link State Request packets to request more recent LSAs are also sent in this state.
Loading
The Link State Request packets are sent to neighbors in the loading state. They request more recent LSAs discovered in the Exchange state. Link State Updates are sent in response to LSRs.
Full
OSPF neighbors are fully adjacent. All information about networks/subnets have been exchanged and acknowledged.
OSPF Packet Types
In the Neighbor State
Machine description, a few types of OSPF packets were mentioned. OSPF
uses five types of packets for communication. Take a look at them (pic.
2)
Type 1 - Hello
This packet type is used to
discover neighbors and maintain the adjacencies between them. More
details regarding a hello packet will be presented in the next post.
Type 2 - Database Description
It is used to
describe the LSAs so that the receiving router (neighbor) can determine
if all LSAs have been synchronized between them (all routers in the area
must have the same LSDB). It is accomplished by exchanging the headers
of LSAs (Database Description packets aka DD packets) with
the neighbor(s). The receiving router will check if it has a match for
all LSAs in its local database. If not, LSR packets are sent to retrieve
the missing LSAs.
Type 3 - Link State Request
During the
exchange state the router creates a list of all missing or older LSAs in
the so called Link State Request List. Then, it sends one or more LSR
packets asking the neighbor for the copy of all these LSAs.
Type 4 - Link State Update
It is the
response to LSR packets. Contains one or more LSAs which are sent to the
neighbor which sent LSR. Upon receiving them the router is flooding
them to all its neighbors in order to maintain the same LSDB within the
OSPF area.
Type 5 - Link State Acknowledgment
Each LSA
the router receives must be acknowledged in order to synchronize the
LSDB with neighbors reliably. This packet is used to acknowledge the
reception of all LSAs.
This lesson's terminology should make it easier for you to
understand some details of OSPF operation presented in the upcoming
lessons.
