As mentioned above OSPF is a link-state routing protocol that can be used
within an Autonomous System. It uses Dijkstra's SPF
algorithm to find optimal route from source to destination. I won't go through
how SPF works, this has been done, better than I could, over at Dijkstra's
algorithm. It was developed by the IETF through a variety of RFCs as mentioned above, all written
by John Moy.
It should be noted that this write up is fairly Cisco-centric as that is what I have had to deal with. Hopefully most of this stuff is generic to all routers. This node is single area OSPF specific so, as usual, if anyone has any info on how this is done elsewhere (eg on Juniper routers or on Unix) or about multiarea OSPF, please message me and I'll add the info here.
The basic metaphor for OSPF is that a network consists of multiple hierarchical
areas which area each Autonomous System which requires another routing protocol
to route between them. Area 0 is generally reffered to as the backbone and routers
must be in the same area in order to share routing information. All information
from other areas must pass through area 0, other areas may not directly communicate.
OSPF works in four stages. These are worked through once two or more routers
are connected to each other. Depending on the network topology OSPF will do
different things to exchange routing information. OSPF defines five types of
topology that it can use. These are (with corresponding layer 2
technologies):
The first stage is called INIT or hello, it basically consists
of the routers sending Hello packets to each other. The diagram below illustrates
this simply.
hello 1.1.1.1
__ ----> __
|__|---------|__|
<----
hello 2.2.2.2
Hello packets contain very basic data regarding the router sending it. Once
two routers have exchanged Hello packets they are said to be neighbours. Hello
packets also serve to verify the link between routers is stable/bi-directional
and also as keepalives.
The next stage of OSPF is 2WAY and at this point there is a split between multi-access
topologies and non-multi-access systems. It is easier to describe the non-multi-access
first and then delve into multi-access systems.
In these systems routers develop adjacencies with each other and then enter
XSTART and XCHANGE phases. This is where the routers
exchange information about routes known to them (these can be directly connected
networks, static routes or routes redistributed from other protocols like RIP,
IGRP or IS-IS) in the form of LSAs (Link State Advertisements). LSAs are
sent multicast on the network (via the addresses 224.0.0.5 (AllSPFRouters)
and 224.0.0.6 (AllDRouters))These LSAs are stored in a database in RAM and
then forwarded to other OSPF neighbours as illustrated below:
LSA LSA
__ ----> __ ----> __
|__|---------|__|-------|__|
stored in
database
Once LSAs have been received from all adjacencies the SPF algorithm is run
on the database to find the optimum route from to a network. It is this process
which makes OSPF different from most other routing protocols; the way that each
router has a complete view of the entire network. From these optimised routes
the router can build it's routing table and from there start successfully
routing data across the network.
This method of creating adjacencies does not scale well on multi-access networks
like Ethernet. You can see this if you look at the number of LSAs needed to
exchange routing information with a little help from algebra. If n
is the number of routers in a network then there are n(n-1)/2
adjacencies needing to be made this would lead to n2 LSAs
from the network. This would lead to a lot of traffic on the network and a very
slow convergance time. We obviously don't want our network getting bogged
down in routing information; after all OSPF should be speeding us up not slowing
things down.
Rather than every router sending every other their routing table, routers develop
adjacencies with the a single router which stores all the information for
a network. This router is called the designated router (DR). Just incase the
DR goes down there is a backup designated router (BDR) that will take over.
Routers will only form adjacencies with the DR and BDR only and send all LSAs
to them. The DR and BDR also form an adjacency with each other but before they
can they must be decied upon. This is done via a process known as the election.
The election is not particuarly complicated and is usually done behind the
scenes, unless you want to make a particular router the D.R. or B.D.R you can
let the routers do their magic uninterrupted. Basically each router running
OSPF must have a Router ID. There are three ways a router can get a Router
ID on a Cisco router. These are checked through in the following order.
- First of all the router will check if there is any priority on a physical
interface, if this is set then it will choose this interface straight away.
On a Cisco router the priority may be set from 0 through to 255 (ie one
byte), 0 means that the router will never participate in an election, 255
means that it is certain to win.
- Secondly if there are any loopback interfaces on the router it will use
the highest loopback IP address as its router ID.
- Lastly it will use the highest address on a physical interface.
Once a Router ID has been decided upon it's time to start the election process.
The router with the highest Router ID will become the D.R. and the next highest
will become the B.D.R.
The election results will stand unless all (or all but one) of the routers
are unplugged/turned off/disconnected (however you like). Even if new routers
are added (maybe with higher Router IDs) there will be no change in the D.R.
and B.D.R. If the D.R. goes down then the B.D.R. becomes the D.R. and there
is a new election for the new B.D.R. only.
Routers will then go though EXSTART and EXCHANGE
as above but sending routing information to the DR and BDR only. The DR then
sends LSAs to the routers in the network (called DRothers, via the multicast
address ), then each can run Dijkstra's algorithm and populate their routing
tables.
If a new route becomes available then routers will exchange LSUs (Link State
Updates) and will adjust their routing tables accordingly. While routers have
formed an adjacency they will send Hello packets to each other periodically
(by default 10 seconds on a Cisco router) to verify connectivity.
It is also worth mentioning the data which is fed to Dijkstra's algorithm;
that being the cost of the link. Costs are related to the speed of the link,
a brief, incomplete and possibly wildly inaccurate list are in the following
table:
Technology Cost (x108/BW)
----------------------------------
FDDI, Fast Ethernet 1
HSSI 2
Token Ring (12 meg) 6
Ethernet 10
Token Ring (4 meg) 25
T1 64
DS0 1562
56K 1785
Tunnel 11111
BW is the bandwidth of the interface, on a Cisco router this may be set to
a certain value if necessary but is not generally recommended.
As for configuring OSPF on a Cisco router, I may as well cover the basics here
just incase you need a ready reference (this assumes you have a little knowledge
of IOS, of course)...
First go into enable, then configure terminal
Router# configure terminal
Then to configure OSPF, where <number> is a process ID, each different
OSPF process has different settings to remember the number or you'll bog down
your router.
Router(config)# router ospf <number>
Now to tell OSPF which networks to share and in which area (the wildcard mask
is the subnet mask NOTed)
Router(config-router)# network <IP> <wildcard mask> area <area
number>
That is all that needs to be done for a basic configuration of OSPF. You may
want to play around and tweak things (like DR elections etc) in which case
setting a priority can be done like this:
Router(config)# interface loopback <number>
Router(config-if)# ip address <IP> 255.255.255.255
Also you can set the OSPF priority (on a per interface basis) as follows:
Router(config-if)# ip ospf priority <number>
It is also possible to configure authentication on a per interface basis
(remember this must be done on both ends of the connection):
Router(config-if)# ip ospf authentication-key <password>
Router(config-router)# area <area> authentication
This sets a cleartext password, if you like you can try varying levels of
encryption (encryption type, 0 -7, 7 being the strongest) with:
Router(config-if)# ip ospf message-digest-key <key id (0-255)>
md5 <encryption type> <key>
Router(config-router)# area <area> authentication message-digest
Well that was a brief introduction to OSPF, I hope it made some sense and it
was usefull to you. If there is anything you can see please /msg me and I'll
try to sort it out.