ospf

OSPF Tutorial, or How OSPF Is Making The World A Better Place

The following are some of the most important OSPF knowledge gems, which I’ve condensed in a single tutorial.

Let us start first with looking into link state algorithms.

Link State Protocols: The Dijkstra Algorithm

Each router calculates the lowest cost path to each other router.

Routers exchange link states. They send information about their connected links to all the other routers by flooding their links.

Flooding means that whenever a router receives information on one interface, it sends it out of all the other interfaces. Flooding has the associated risk of creating loops.

When there is a link failure or a topology change, the information is flooded to all other routers. All routers re-run the Dijkstra algorithm.

How the Dijkstra algorithm works

To determine the shortest path from router R1 to all other routers, we do the following:

  • draw a table for R1, with the following rows: Shortest Path set, Candidate, Selected
    • Shortest Path Set: the shortest path we find after each iteration of the algorithm
    • Candidate: the potential new members of the shortest path set
    • Selected: the selected member of the shortest path set
  • iteration 1: beginning from R1, what are the paths that have a cost of 1? We add routers in the Candidate row. Then we choose one among them. Don’t worry if you have more than one router with the same link cost; that router will be added to the tree in a later iteration. Now the Shortest Path Set grew one router.
  • iteration 2: beginning from R1, are there still paths with cost of 1? if yes, add the router in the Candidate row then select one. The Shortest Path Set grows one more router
  • iteration 3: beginning from R1, are there still paths with cumulative cost of 2? repeat the steps
  • iteration 4: beginning from R1, are there still paths with cumulative cost of 3? repeat the steps
  • etc.
  • when the Candidate row becomes empty, then the algorithm is done.

The number of iterations of the link state algorithm is equal to the number of the routers participating in the algorithm.

Nb_iter = nb_routers

So if we have 5 routers, then to build a shortest path from any router to any other one we will iterate the algorithm 5 times.

A good example of how Dijkstra works is given by Professor Nick McKeown here.

Here is a sample trace I’ve done of the Dijkstra algorithm. Notice that with practice, you won’t need to constantly fill the Candidate row.

link-state-protocols-my-example

Figure: a sample trace of the Dijkstra algorithm

When the algorithm converges, each router in the shortest path to a destination X is the next hop of its precedent router for that same destination X. Using the trace above, starting from router R4, his next hop R5 is the router on the shortest path to reach R6.

OSPF DR and BDR

The Designated Router concept is a link-specific concept, not for the whole router. A router can be a DR on one link, a BDR on second link and a DROTHER on a third link.

DR and BDR elections

The router with the highest OSPF priority becomes the DR. The router with the second highest OSPF priority becomes the BDR.

If there is a tie, then the election is based on router IDs: the router which has the higher router ID wins and becomes the DR. The second router in this election becomes the BDR.

All routers, including the BDR, form full adjacency with the DR.

The BDR stays in standby. When it does not hear LSAs from the DR for the duration of the wait timer, it assumes the current DR has failed and promotes itself as a new DR.

All routers, except the DR and the BDR, form two-way adjacency with each other.

A DROTHER is a router that is neither DR nor BDR.

DR Operations

LSA exchange without DROTHERS

When a DR is elected, all routers send LSUs to it using multicast address 224.0.0.6. The DR sends back to each one of them an LSAck and assumes responsibility for multicasting the LSAs to all other routers. All non-DROTHER routers form a two-way adjacency with each other. In the diagram below, we concentrate only on router 3.

Router 3 sends its LSAs to the multicast address of 224.0.0.6. Router 5, which is the DR, is listening on that multicast address. Router 5 sends back a LSAck to Router 3, then multicasts Router 3’s LSA information at IP address 224.0.0.5.

LSA exchange with DROTHERS

OSPF Network Types

There are three types of networks that are known to our popular protocol:

  • point to point
  • broadcast
  • non broadcast multi-access NBMA

For each one of these network types, our link state protocol has an operational mode. The default operational modes are not always suitable for a specific network. So that’s why sometimes we need to change it.

To change the operational mode of OSPF on a particular network type:

(config-if)#ip ospf network {operational mode} 

Adjacency Behaviour on Point-to-point Network Types

  • This network type encompasses the following technologies
    OSPF-point-to-point-network-type
    OSPF point to point network type

     

    • physical serial interfaces
    • serial point-to-point sub-interfaces
  • No DR or BDR elections
  • Neighbors dynamically become adjacent
  • Hello timer = 10 sec
  • Dead Interval = 40 sec (4 times the Hello timer)

Adjacency Behaviour on Broadcast Network Types

OSPF-broadcast-network-type
OSPF broadcast network type
  • On each broadcast network a DR and a BDR are elected.
  • routers establish full adjacency with the DR only
  • routers communicate with the DR through the multicast address 224.0.0.6
  • DR communicate with routers through the multicast address 224.0.0.5
  • all routers have the same synchronized LSDB

Adjacency behavior on non-broadcast network types

ospf-non-broadcast-multiaccess-network-type
OSPF Non Broadcast MultiAccess network type

In this type of networks, OSPF provides 5 operational modes. Two of them are RFCs and the rest is Cisco-proprietary:

The RFC-based operational modes are:

  • Non Broadcast
  • Point to Multipoint

The Cisco-based operational modes are:

  • Point to Multipoint non Broadcast
  • Broadcast
  • Point to multipoint

In NBMA networks, a DR and a BDR are elected.

If there is a tie, then the router with highest Router ID wins.

Tables

  • Neighbor table
  • link state database (LSDB)

OSPF Timers

Hello timer

To discover neighbors and establish adjacency, OSPF routers exchange Hello packets at regular intervals called Hello timers. These Hello packets are sent to Multicast address group 224.0.0.5. Hello replies are unicast.

The Hello packet timer has some default values: in high speed links, the Hello timer is 5 sec. In Slow speed links, it is 60 sec (high speed links are ones that have greater or equal to the speed of a T1 circuit. And slow speed links are less than the speed of a T1 link.)

Neighbor routers can have different Hello timers, but their OSPF neighborship will be flapping.

The Hello protocol serves also as a keepalive mechanism between adjacent neighbors.

Hold-down timer

The Hold-down timer is usually equal to four times the value of the Hello timer:

Hold-down_timer =  4 * Hello_timer

Dead interval

When router 1 no longer hears Hello packets from a neighbor router 2 for the duration of the Dead Interval, then it believes that router 2 has failed and re convergence calculations occur.

Packet types

There are 5:

  • Hello
  • LSU
  • LSR: Link State Request
  • DBD: DataBase Descriptor: checks LSDB synchronization
  • LSAck

LSA

LSA: Link State Advertisement: information about one link. LSAs are included in packets called Link State Updates (LSU) or Link State Packets (LSP), and in Link State Acknowledgments (LSAck).

A router that receives an LSA forwards it to his neighbors -except the one from which the LSA came- in a flooding mechanism and he does not forget to store it in its link state database table.

LSAs in the LSDB have sequence numbers. Sequence numbers start with hex 0x800. when a router crafts an LSA, he inserts a sequence number. That same sequence number will be preserved in the whole flooding mechanism. Each receiving router will compare the sequence number against existing sequence numbers in its topology database:

  • if there is an LSA with an identical sequence number, the LSA is discarded
  • if not, a copy of the LSA is stored in the database and the LSA is flooded to all the OSPF neighbors, except the one from which the LSA came in the first place.

LSA age

Each LSA has an age. And it is recorded in the LSA header.

LSA MaxAge

The maximum age of an LSA defines the maximum time an LSA can exist in a link state database and it is called MaxAge. Once MaxAge is reached, the router floods the LSA to all its neighbors and flushes it from his link state database.

The default MaxAge value is 60 minutes.

LSA MaxAgeDiff

It is possible for an OSPF router to receive multiple copies of the same LSA with the same sequence number. But they will have different ages. To understand the behaviour of the router in this case, we examine the age difference between the LSA age and the received LSA age and compare it with a protocol-defined value called MaxAgeDiff:

  • if |received_LSA_age – stored_LSA_age| < MaxAgeDiff: the stored LSA is kept and the received LSA is discarded
  • otherwise, the stored LSA is received with the received LSA, and a copy of it is flooded.

The default MaxAgeDiff value is 15 mn.

LSRefreshTime

As its name implies, LSRefreshTime is the time at which a router refreshes a particular LSA.

At each occurrence of LSRefreshTime:

  • the correspondent LSA is flooded to neighbors,
  • the sending router resets the age of the LSA sent,
  • the receiving routers reset the age of the sending router’s LSA.

By default, LSRefreshTime value is 60 mn.

In a LSA, we must make the difference between LID (Link ID) andLSID (Link State ID).

OSPF LSA Types

LSA Type 1: Router LSA

  • flooded within the area
  • generated by each router
  • the Link State ID = the router ID of the sending router
  • provides information about directly connected networks

LSA Type 2: Network LSA

  • flooded within the area
  • Link State ID = the IP address of the interface of the network DR

LSA Type 3: Summary LSA

  • generated by ABRs
  • Link State ID = the IP address of the destination network
  • does not contain summary routes by default. Each subnet is, by default, advertised individually. So if we want to summarize routes, we should configure them manually on ABRs.

LSA Type 4: Summary LSA

  • generated by ABRs wen there is an ASBR within their area
  • Link State ID = the router ID of the described ASBR
  • some special bits to note here:
    • the e bit (external bit): set by ASBR when forwarding his LSA (Type 1)
    • the b bit (border bit): set by ABR

LSA Type 5

  • Link State ID = the IP address of the destination network
  • provides information about other Autonomous Systems

LSA Type 7

  • Link State ID = the IP address of the destination network

LSU

LSU: Link State Update, sent by an OSPF router to its neighbors as multicast. Note here that OSPF routers do not exchange routes; they exchange link states instead.

LSU packets are the vehicle for LSA. An LSU packet contains one or more LSAs.

Once a router receives a new link state information, it runs the Dijkstra Algorithm against its own link state database to generate routes.

OSPF neighbor relationship vs adjacency

There is a distinction between neighbors and adjacent neighbors in OSPF:

  • neighbors are routers running OSPF and have one or more common connected subnet,
  • adjacent neighbors, however, are routers that established adjacency by agreeing on specific OSPF parameters:
    • area type
    • area number
    • subnet number
    • subnet mask
    • Hello timer
    • Dead Interval
    • OSPF authentication type
    • OSPF authentication password (or digest)

Once neighbors become adjacent, their goal is to have a unique Link State database on all neighbors. This is called “synchronizing the link state database LSDB”. And it is done by the mechanism of exchanging LSAs.

OSPF Areas

To reduce convergence time and resource utilization (in terms of router CPU and memory), OSPF is segmented into areas. Area 0 is called the backbone area. All other areas must connect to the backbone area only.

SPF calculations in one area are confined to that area only. Also, flooding of LSAs impacts only the routers within the area.

All traffic from one area to another (called inter-area traffic) must cross the backbone area.

OSPF-tutorial-2

The area ID is the identifier of the area. The identifier of the backbone area is 0. The area ID can be in either decimal notation (area 0, area 6,…) or in dotted decimal notation (0.0.0.0, 0.0.0.6,…)

OSPF ABR

Area Border Routers ABRs:

  • connect multiple areas to the backbone area. They have at least one interface in the backbone area and one interface in a non-backbone area,
  • maintain separate link state databases, each for one area they connect to,
  • separate LSA floods,
  • receive and issue route summaries,
  • need sufficient CPU power and memory to handle bigger and bigger link state database tables and routing tables.

OSPF-tutorial-2-abr

OSPF cost

The metric in the OSPF protocol is called cost. It is either automatically calculated or manually configured.

Interface bandwidth

When left to the IOS, the OSPF cost is automatically calculated according to the following formula:

IP OSPF cost = Reference_bandwidth / Interface_bandwidth ( in bits per second)

With no intervention from your part, IOS has a default “manner” to perceive the bandwidth of a given OSPF interface. But the resulting OSPF cost might not suit your network environment.

So to “guide” IOS as to what is the real interface bandwidth, we configure the banwidth with the bandwidth command. The bandwidth command tells the IOS router  how to perceive the bandwidth of the interface, and its value is less or equal to the physical line speed:

Interface_bandwidth <= physical_line_speed

So instead of letting this IOS-generated Interface_bandwidth value, we can set it with the bandwidth command.

Reference bandwidth

The Reference_bandwidth value is 100 000 000, or 10^8, by default. So so to calculate the OSPF cost of a Fast Ethernet interface:

cost = Reference_bandwidth / Interface_bandwidth

= 100 000 000 / 100 000 000

= 1

–> OSPF cost of a FastEthernet interface equals 1, by default.

Let’s take another example. Suppose you have bought a 128kbps MPLS circuit from your service provider. The OSPF cost of the serial interface is:

cost = 100 000 000 / 128 000

= 781.25

–> The OSPF cost of your serial interface (at 128kbps speed) is 781, by default.

Note that the Reference bandwidth can also be changed in IOS with this command:

[box type=”shadow”] auto-cost reference-bandwidth {new value}[/box]

[box type=”info”] Although you can have fun changing the default value of the Reference bandwidth, it might not be fun to have different values on different OSPF routers. So keep the same value of the Reference Bandwidth on all OSPF routers [/box]

IP OSPF cost command

We can manually configure the cost of an OSPF interface in a much simpler way, without caring about Reference bandwidth calculations:

[box type=”shadow”] interface {xxx}

  ip ospf cost {value} [/box]

cost of the path

Each router’s interface participating in an OSPF process has an OSPF cost. From there the cost of a path is inferred. The cost of an OSPF path from one router X to a destination= the sum of all OSPF costs of the outgoing interfaces with router X being the root of the tree.

Here’s an example to understand that:
ospf-path-cost-1

RTA, RTB, RTC and RTD are four OSPF routers. And we have three network prefixes 128.213.0.0, 192.213.11.0 and 222.211.10.0. We will calculate the costs from RTA to prefixes 128.213.0.0 and 192.213.11.0. So we put RTA at the root of the tree.

Since we are going to sum the costs in the outgoing directions, we’ll add arrows. The arrows describe the interface costs we will consider in the calculations of the path cost:

  • The cost of the path to prefix 128.213.0.0 is the cost of the outgoing OSPF interface, which is attached to the LAN; so it’s 10
  • The cost of the path to prefix 192.213.11.0 = cost of the outgoing interface (10) + cost of RTB’s outgoing interface (5) –> 10+5 =15. Pay attention, the cost is not 10 + 8 + 5. The cost “8” is not calculated because it is an inbound interface. Remember, only consider the outbound interface when calculating OSPF costs.

The topology information learned by an OSPF router includes a cost associated with each link in the network. A routers sums up the cost associated with each link in each route to find the metric associated with the route

OSPF process ID

the Process ID identifies one instance of the routing protocol. We can have more than one instance of it on a single layer 3 device.

The process ID is written on 16 bits. Its value ranges from 1 to 65535. I’ve personally not seen any OSPF process ID whose value spans more than three digits.

Multicast group addresses used in OSPF

  • 224.0.0.5: means “all OSPF routers”
  • 224.0.0.6: means “all DRs”

IOS configuration

Basic configuration example:

[box type=”shadow”](config)#router ospf 11

(config-router)#network 10.0.0.0 0.255.255.255 area 0[/box]

Configuring OSPF on an interface level (optional):

[box type=”shadow”] interface xxxx

ip ospf {process} area {area ID}[/box]

configuring route redistribution into OSPF

[box type=”shadow”](config)#router ospf 11

(config-router)#redistribute {protocol} {metric value}[/box]

Configuring OSPF priority

This is done at the interface level:

[box type=”shadow”] (config-if)#ip ospf priority {value}[/box]

The priority value ranges from 0 to 255. If it is 0, the router no longer participates in the DR/BDR elections.

Router ID

Definition#1: Router ID is the highest IP address of any physical interface configured on the router when the OSPF process starts running, if no loopback interfaces were set.

Definition#2: Router ID is the highest IP address on a loopback interface – if one or more loopback interfaces is present on the router- even if there is a physical interface whose IP address is higher than the loopback interface’s address.

Definition#3: Router ID is set manually:

(config)#router-id {IP address}

When not manually set, it is better to use loopback interfaces than physical interfaces’ IP addresses:

  • a loopback interface never goes down (unless the router goes down of course).
  • with a loopback interface IP address, we have control as to what IP address is used for router ID. We are sure that even if a higher IP address is assigned to a physical interface the router ID value won’t change.

Redistribution into OSPF

When another AS routes are redistributed into OSPF, they are called OSPF external routes. There are two types of external routes:

  • Type 1 routes: their cost is the sum of all costs in the path
  • Type 2 routes: their cost is fixed

By default, the external routes have a cost of 20 for any protocol redistributed into OSPF, except for BGP where external routes have a metric of 1.

Redistributed routes that are coming from area 0 are not injected into NSSA (neither into stub areas).

Always check your OSPF neighbors. I had a problem injecting a default route into NSSA totally stub area, and I figured out it was a problem of OSPF network types.R3 and R4 were not already OSPF Neighbors. They are connected through Frame relay. R3 interface is “point-to-point” OSPF network type. R4 however, has interface ser0/0 in “NBMA” OSPF Network type.I corrected the network type under ser0/0 of R4 and it works

OSPF authentication

There are three types of authentication here:

  • Null
  • Clear text
  • Message Digest

OSPF authentication brings protection against OSPF DoS attacks and OSPF Reconnaissance attacks. It happens on a per OSPF interface basis.

When either clear text or message digest authentication is configured, and no key is configured, then a default key of 0 is automatically set.

Configuring OSPF clear text authentication

  • Define the authentication key

(config-if)#ip ospf authentication-key {key}

The key is 8 characters max.

  • Enable authentication

(config-if)#ip ospf authentication

OSPF load balancing

Occurs when there are multiple equal-cost routes, in the routing table, to the same network prefix. By default, there can be 4 possible equal-cost routes in the routing table. And it can be configured to be up to 16.

Load balancing occurs:

  • on a per packet basis,
  • on a per IP address basis.

OSPF Route Filtering

NSSA and Default Route 

The default behaviour in NSSA is: no default route is injected by the NSSA ABR. Routes are inserted normally. Use of “default-information-originate” on an NSSA ABR to inject a default route into NSSA.

Use of “no-summary” on NSSA ABR to inject a default route into NSSA

OSPF Show Commands in IOS

show ip ospf: gives the router ID, SPF algorithm statistics, LA timer information, area information…

show ip ospf database: displays the content of the topology database (links, neighboring router IDs,..)

show ip ospf interface: interface-related OSPF information such as the OSPF network type, the router ID, whether it is a DR or a BDR, OSPF process number

show ip ospf neighbor: neighbor ID, his IP address, whether it is a DR or a BDR, OSPF priority.

Troubleshooting OSPF

Here is an example of troubleshooting session.

We have two routers R2 and R3 configured as OSPF routers. The problem is that router R3 can not get routes that are redistributed into OSPF, from R2.
Let’s gather some information with the following debug commands:
 
debug ip ospf hello
debug ip ospf event

list of debug messages appears on the console screen. As we can see, R3 is not receiving Hello packets from R2:

Let’s read the OSPF neighbor table with:

show ip ospf neighbor


Let’s check the OSPF interfaces on both routers with :

show ip ospf interface

We see that serial0/0.203 subinterface is a passive interface. Thus it is not exhcnaging OSPF Hello packets, which is problematic because R3 is on the other end of se0/0.203.
The solution is then to make the subinterface actively particiapting in OSPF Hello exchange with:

router ospf 1
no passive-interface ser0/0.203


Now we see our routes in the routing table:

Passive-interface

Before the command, here’s R2 RIB:

After the command, R3 is no longer a neighbor -> no more routes from R3:

Configuring OSPFv3

Router-id
If we don’t configure one, OSPFv3 will choose a Router ID in the same fashion as OSPFv2.

After configuring basic OSPFv3, I see the following:

If we remember with OSPFv2 over NBMA networks, we must ensure that broadcasts are forwarded properly on interfaces. We generally use the “broadcast” keyword in “frame-relay map ip..” command.
Here, I added the static mapping command, with the “broadcast” keyword:

But it was not enough. I still do not see neighborship established. Something was missing:

What if it was a mismatched OSPF network type on both ends of the link?

Bingo. Now neighbors stand up!

What if we delete the “frame-relay map ipv6..” command? Neighbor state goes “init”:

OSPF Database
Intra area Prefix Link State is LSA9.
Inter area Prefix Link State is LSA3
R3 OSPF database:

On R1 and R4 e.g., we see OSPF routes:

R4 sees all routes (not a default route only).

OSPF neighborship does not form
. Let’s “debug ipv6 ospf hello”. From the following, we know that OSPFv3 uses link local addresses in its conversations, and that we have here mismatched Hello parameters. We know that, in order for OSPF neighborship to establish, these parameters must match (in the Hello packet):
– area ID
– authentication
– Hello timer, Dead timer
– stub area flag.
So if for example routers have different OSPF network types, that mean they have different values in one of the aforementioned parameters.

mismatched-hello-parameters

to solve it:

Sometimes, commands such as “debug ipv6 ospf hello” and “debug ipv6 ospf event” are not enough. Try “debug ipv6 packet” because the problem may be due to packet processing itself:

encapsulation failed

The “encapsulation failed” message on NBMA network can be solved with “frame-relay map ipv6..broadcast” command, like this:
“frame-relay map ipv6 {remoteLinkLocal here} {DLCI here} broadcast”

OSPFv3 configuration for TSHOOT lab, on R1

OSPF configuration for TSHOOT lab, on R2:

Route summarization
Beware not to do the conversion from decimal to binary! ipv6 addresses are in hex! so we should convert from hex to binary.

– if you configure OSPFv3 and there’s no IP address on router, then IOS will ask you to set Router-ID manually:

Redistributing connected routes into OSPFv3
we delete loopbacks from being advertised as OSPF internal routes (on R1) and we’ll redistribute their addresses into OSPF:

We chose 300 because it is greater than any internal route metric.
Let’s see R2 routing table:

Routes are learned as O E2, just like OSPFv2 :)

Redistributing RIPng into OSPFv3
Quite simple, if we already know redistribution in IPv4. By the way, knowledge is always useful. We either use it exactly as it is, or we do analogies between what we know and what we’re about to learn.

Let’s see what R3 has learned:

Where is the 2026::2:/122 network? it is supposed to be a RIPng route, so it should be redistributed.
I found the answer to it with “include-connected” keyword:

The redistributed RIP routes appear now on R3 routing table:

Leave a Comment