Open Shortest Path First - (OSPF)

is a link-state routing protocol that was developed as a replacement for the distance vector routing protocol, RIP

Two implementations were written. One implementation was developed to run on routers and the other to run on UNIX workstations. The latter implementation became a widespread UNIX process known as GATED.

At the same time the OSPF was introduced, ISO was working on a link-state routing protocol of their own, Intermediate System-to-Intermediate System (IS-IS).

IETF chose OSPF as their recommended Interior Gateway Protocol (IGP).

Features of OSPF

1. Classless - It is classless by design; therefore, it supports VLSM and CIDR.

2. Efficient - Routing changes trigger routing updates (no periodic updates). It uses the SPF algorithm to choose the best path.

3. Fast convergence - It quickly propagates network changes

Administrative distance (AD) is the trustworthiness (or preference) of the route source.

OSPF has a default administrative distance of 110

Components of OSPF

Data Structures

OSPF creates and maintains "three databases": (see Figure)

These tables contain a list of neighboring routers to exchange routing information with and are kept and maintained in RAM.

Components of OSPF

B. Routing Protocol Messages

OSPF exchanges messages to convey routing information using five types of packets

Components of OSPF

C. Algorithm

The CPU processes the neighbor and topology tables using Dijkstra’s SPF algorithm. The SPF algorithm is based on the cumulative cost to reach a destination.

Link-State Operation

1. Establish Neighbor Adjacencies - OSPF-enabled routers must recognize each other on the network before they can share information.

"An OSPF-enabled router sends Hello packets out all OSPF-enabled interfaces" to determine if neighbors are present on those links.

If a neighbor is present, the OSPF-enabled router attempts to establish a neighbor adjacency with that neighbor.

Link-State Operation

2. Exchange Link-State Advertisements - After adjacencies are established, routers then exchange link-state advertisements (LSAs).

LSAs contain the state and cost of each directly connected link.

Routers flood their LSAs to adjacent neighbors. Adjacent neighbors receiving the LSA immediately flood the LSA to other directly connected neighbors, until all routers in the area have all LSAs.

Link-State Operation

3. Build the Topology Table - After LSAs are received, OSPF-enabled routers build the topology table (LSDB) based on the received LSAs.

This database eventually holds all the information about the topology of the network.

Link-State Operation

4. Execute the SPF Algorithm - Routers then execute the SPF algorithm.

The gears in the figure are used to indicate the execution of the SPF algorithm. The SPF algorithm creates the SPF tree.

OSPF can be implemented in one of two ways:

1. Single-Area OSPF - all routers are in one area called the backbone area (area 0).

OSPF can be implemented in one of two ways:

2. Multiarea OSPF - OSPF is implemented using multiple areas, in a hierarchal fashion.

All areas must connect to the backbone area (area 0). Routers interconnecting the areas are referred to as Area Border Routers (ABR).

The hierarchical-topology possibilities of multiarea OSPF have these advantages:

1. Smaller routing tables - Fewer routing table entries because network addresses can be summarized between areas.

Route summarization is not enabled by default.

* Link failure affects the local area only (area 51).

* The ABR (R2) isolates the fault to area 51 only.

* Routers in areas 0 and 1 do not need to run the SPF algorithm.

Encapsulating OSPF Messages

OSPF messages transmitted over an Ethernet link contain the following information:

Types of OSPF Packets

* Type 1: Hello packet - Used to establish and maintain adjacency with other OSPF routers.

* Type 2: Database Description (DBD) packet - Contains an abbreviated list of the sending router’s LSDB and is used by receiving routers to check against the local LSDB.

The LSDB must be identical on all link-state routers within an area to construct an accurate SPF tree.

Types of OSPF Packets

OSPF uses link-state packets (LSPs) to establish and maintain neighbor adjacencies and exchange routing updates.

The figure shows the five different types of LSPs used by OSPF.

Hello Packet

The OSPF Type 1 packet is the Hello packet. Hello packets are used to:

1. Discover OSPF neighbors and establish neighbor adjacencies.

2. Advertise parameters on which two routers must agree to become neighbors.

3. Elect the Designated Router (DR) and Backup Designated Router (BDR) on multiaccess networks like Ethernet and Frame Relay. Point-to-point links do not require DR or BDR.

Hello Packet

* Type - Identifies the type of packet. A one (1) indicates a Hello packet. A value 2 identifies a DBD packet, 3 an LSR packet, 4 an LSU packet, and 5 an LSAck packet.

* Router ID - A 32-bit value expressed in dotted decimal notation (an IPv4 address) used to uniquely identifying the originating router.

* Area ID - Area from which the packet originated.

* Network Mask - Subnet mask associated with the sending interface.

Hello Packet

* Hello Interval - Specifies the frequency, in seconds, at which a router sends Hello packets. The default Hello interval on multiaccess networks is " 10 seconds".
This timer must be the same on neighboring routers; otherwise, an adjacency is not established.

* Router Priority - Used in a DR/BDR election.

" The default priority for all OSPF routers is 1", but can be manually altered from 0 to 255. The higher the value, the more likely the router becomes the DR on the link.

Hello Packet

* Dead Interval - Is the time in seconds that a router waits to hear from a neighbor before declaring the neighboring router out of service. By default, the router Dead Interval is "four times the Hello interval."

This timer must be the same on neighboring routers; otherwise, an adjacency is not established.

* Designated Router (DR) - Router ID of the DR.

* Backup Designated Router (BDR) - Router ID of the BDR.

* List of Neighbors - List that identifies the router IDs of all adjacent routers.

Hello Packet Intervals

OSPF Hello packets are transmitted to multicast address 224.0.0.5 in IPv4 and FF02::5 in IPv6 (all OSPF routers) every:

* 10 seconds (default on multiaccess and point-to-point networks)

* 30 seconds (default on nonbroadcast multiaccess [NBMA] networks; for example, Frame Relay)

The Dead interval is the period that the router waits to receive a Hello packet before declaring the neighbor down

Link-State Updates

Routers initially exchange Type 2 DBD packets, which is an abbreviated list of the sending router’s LSDB and is used by receiving routers to check against the local LSDB.

A Type 3 LSR packet is used by the receiving routers to request more information about an entry in the DBD.

OSPF Operational States

When an OSPF router is initially connected to a network, it attempts to:

* Create adjacencies with neighbors

* Exchange routing information

* Calculate the best routes

* Reach convergence (Full State)

Establish Neighbor Adjacencies

1. When OSPF is enabled, the enabled Gigabit Ethernet 0/0 interface transitions from the Down state to the Init state.

R1 starts sending Hello packets out all OSPF-enabled interfaces to discover OSPF neighbors to develop adjacencies with.

Establish Neighbor Adjacencies

2. R2 receives the Hello packet from R1 and adds the R1 router ID to its neighbor list. R2 then sends a Hello packet to R1.

The packet contains the R2 Router ID and the R1 Router ID in its list of neighbors on the same interface.

Establish Neighbor Adjacencies

3. R1 receives the Hello and adds the R2 Router ID in its list of OSPF neighbors. It also notices its own Router ID in the Hello packet’s list of neighbors.

When a router receives a Hello packet with its Router ID listed in the list of neighbors, the router transitions from the Init state to the Two-Way state.

The action performed in Two-Way state depends on the type of inter-connection between the adjacent routers:

* If the two adjacent neighbors are interconnected over a point-to-point link, then they immediately transition from the Two-Way state to the database synchronization phase.

* If the routers are interconnected over a common Ethernet network, then a designated router DR and a BDR must be elected.

OSPF DR and BDR

Multiaccess networks can create two challenges for OSPF regarding the flooding of LSAs:

* Creation of multiple adjacencies - Ethernet networks could potentially interconnect many OSPF routers over a common link.

Creating adjacencies with every router is unnecessary and undesirable. It would lead to an excessive number of LSAs exchanged between routers on the same network.

Synchronizing OSPF Databases

After the Two-Way state, routers transition to database synchronization states. While the Hello packet was used to establish neighbor adjacencies, the other four types of OSPF packets are used during the process of exchanging and synchronizing LSDBs.

In the ExStart state, a master and slave relationship is created between each router and its adjacent DR and BDR. The router with the higher router ID acts as the master for the Exchange state

In the Exchange state, the master and slave routers exchange one or more DBD packets.

A DBD packet includes information about the LSA entry header that appears in the router’s LSDB. The entries can be about a link or about a network.

Each LSA entry header includes information about the link-state type, the address of the advertising router, the link’s cost, and the sequence number. The router uses the sequence number to determine the newness of the received link-state information.

R1 compares the information received with the information it has in its own LSDB. If the DBD packet has a more current link-state entry, the router transitions to the Loading state.

After all LSRs have been satisfied for a given router, the adjacent routers are considered synchronized and in a full state.

As long as the neighboring routers continue receiving Hello packets, the network in the transmitted LSAs remain in the topology database. After the topological databases are synchronized, updates (LSUs) are sent only to neighbors when:

* A change is perceived (incremental updates)

* Every 30 minutes

OSPFv2 is enabled using the:

" router ospf (process-id (1 - 65,535))" global configuration mode command.

The process-id value is locally significant, which means that it does not have to be the same value on the other OSPF routers to establish adjacencies with those neighbors.

Router Ids

The router ID is used by the OSPF-enabled router to:

1. Uniquely identify the router - The router ID is used by other routers to uniquely identify each router within the OSPF domain and all packets that originate from them.

Router IDs

If no loopback interfaces are configured, then the router chooses the highest active IPv4 address of any of its physical interfaces. This is the least recommended method because it makes it more difficult for administrators to distinguish between specific routers.

If the router uses the highest IPv4 address for the router ID, the interface does not need to be OSPF-enabled. This means that the interface address does not need to be included in one of the OSPF network commands for the router to use that IP address as the router ID. The only requirement is that the interface is active and in the up state.

Configuring an OSPF Router ID

Use the "router-id (rid)" router configuration mode command to manually assign a 32-bit value expressed as an IPv4 address to a router. An OSPF router identifies itself to other routers using this router ID

If the router ID is the same on two neighboring routers, the router displays an error message similar to the one below:

%OSPF-4-DUP_RTRID1: Detected router with duplicate router ID.

* Use the "show ip protocols" command to verify the router ID.

Modifying a Router ID

After a router selects a router ID, an active OSPF router does not allow the router ID to be changed until the router is reloaded or the OSPF process cleared.

Ej: the router ID 1.1.1.1 is being assigned to R1. Notice how an informational message appears stating that the OSPF process must be cleared or that the router must be reloaded. The reason is because R1 already has adjacencies with other neighbors using the router ID 192.168.10.5. Those adjacencies must be renegotiated using the new router IP 1.1.1.1.

Modifying a Router ID

The OSPF routing process is cleared using the clear ip ospf process privileged EXEC mode command. This forces OSPF on R1 to transition to the Down and Init states. Notice the adjacency change messages from full to down and then from loading to full.

Using a Loopback Interface as the Router ID

The IPv4 address of the loopback interface should be configured using a 32-bit subnet mask (255.255.255.255). This effectively creates a host route. A 32-bit host route does not get advertised as a route to other OSPF routers.

Note: Some older versions of the IOS do not recognize the router-id command; therefore, the best way to set the router ID on those routers is by using a loopback interface.

Enabling OSPF on Interfaces

The "network" command determines which interfaces participate in the routing process for an OSPF area. Any interfaces on a router that match the network address in the network command are enabled to send and receive OSPF packets. As a result, the network (or subnet) address for the interface is included in OSPF routing updates.

The basic command syntax is:

" network (network-address) (wildcard-mask) area (area-id)"

A wildcard mask is a string of 32 binary digits used by the router to determine which bits of the address to examine for a match. In a subnet mask, binary 1 is equal to a match and binary 0 is not a match. In a wildcard mask, the reverse is true:

* Wildcard mask bit 0 - Matches the corresponding bit value in the address.

* Wildcard mask bit 1 - Ignores the corresponding bit value in the address.

The network Command

Figure - displays the required commands to determine which interfaces on R1 participate in the OSPFv2 routing process for an area. Notice the use of wildcard masks to identify the respective interfaces based on their network addresses

Figure - provides an example of specifying the interface IPv4 address with a quad 0 wildcard mask. Entering network 172.16.3.1 0.0.0.0 area 0 on R1 tells the router to enable interface Serial0/0/0 for the routing process. As a result, the OSPFv2 process will advertise the network that is on this interface (172.16.3.0/30).

The advantage of specifying the interface is that the wildcard mask calculation is not necessary. OSPFv2 uses the interface address and subnet mask to determine the network to advertise.

Passive Interface

By default, OSPF messages are forwarded out all OSPF-enabled interfaces. However, these messages really only need to be sent out interfaces connecting to other OSPF-enabled routers.

OSPF messages are forwarded out of all three routers G0/0 interface even though no OSPF neighbor exists on that LAN. Sending out unneeded messages on a LAN affects the network in three ways

Note: OSPFv2 and OSPFv3 both support the passive-interface command.

As an alternative, all interfaces can be made passive using the "passive-interface default" command.

OSPF Metric = Cost

The cost of an interface is inversely proportional to the bandwidth of the interface.

Therefore, a higher bandwidth indicates a lower cost. More overhead and time delays equal a higher cost.

Therefore, a 10-Mb/s Ethernet line has a higher cost than a 100-Mb/s Ethernet line.

Adjusting the Reference Bandwidth

To adjust the reference bandwidth, use the:
"auto-cost reference-bandwidth (Mb/s)" router configuration command

* Gigabit Ethernet - auto-cost reference-bandwidth 1000

* 10 Gigabit Ethernet - auto-cost reference-bandwidth 10000

To return to the default reference bandwidth, use the: " auto-cost reference-bandwidth 100" command.

Adjusting the Reference Bandwidth

Use the show ip ospf interface s0/0/0 command to verify the current OSPF cost assigned to the R1 serial 0/0/0 interface

Ej: auto-cost reference-bandwidth 1000

Adjusting the Interface Bandwidths

Use the " bandwidth (kilobits)" interface configuration command

** Note: A common misconception for students who are new to networking and the Cisco IOS is to assume that the bandwidth command changes the physical bandwidth of the link.

** The command only modifies the bandwidth metric used by EIGRP and OSPF. The command does not modify the actual bandwidth on the link

Manually Setting the OSPF Cost

As an alternative to setting the default interface bandwidth, the cost can be manually configured on an interface using the: "ip ospf cost (value) " interface configuration command.

Ej: the interface bandwidth of serial 0/0/1 is reset to the default value and the OSPF cost is manually set to 15,625. Although the interface bandwidth is reset to the default value, the OSPF cost is set as if the bandwidth was still calculated.

Manually Setting the OSPF Cost

An advantage of configuring a cost over setting the interface bandwidth is that the router does not have to calculate the metric when the cost is manually configured. In contrast, when the interface bandwidth is configured, the router must calculate the OSPF cost based on the bandwidth.

The ip ospf cost command is useful in multi-vendor environments where non-Cisco routers may use a metric other than bandwidth to calculate the OSPF costs.

Verify OSPF Neighbors

Use the show ip ospf neighbor command to verify that the router has formed an adjacency with its neighboring routers. If the router ID of the neighboring router is not displayed, or if it does not show as being in a state of FULL, the two routers have not formed an OSPF adjacency.

If two routers do not establish adjacency, link-state information is not exchanged. Incomplete LSDBs can cause inaccurate SPF trees and routing tables. Routes to destination networks may not exist, or may not be the most optimum path.

Verify OSPF Neighbors

* State - The OSPF state of the interface. FULL state means that the router and its neighbor have identical OSPF LSDBs. On multiaccess networks, such as Ethernet, two routers that are adjacent may have their states displayed as 2WAY. The dash indicates that no DR or BDR is required because of the network type.

* Dead Time - The amount of time remaining that the router waits to receive an OSPF Hello packet from the neighbor before declaring the neighbor down. This value is reset when the interface receives a Hello packet.

Verify OSPF Protocol Settings

The "show ip protocols" command is a quick way to verify vital OSPF configuration information.

This includes the OSPF process ID, the router ID, networks the router is advertising, the neighbors the router is receiving updates from, and the default administrative distance, which is 110 for OSPF.

Verify OSPF Process Information

The "show ip ospf" command can also be used to examine the OSPF process ID and router ID

This command displays the OSPF area information and the last time the SPF algorithm was calculated.

Verify OSPF Interface Settings

The quickest way to verify OSPF interface settings is to use the "show ip ospf interface" command. This command provides a detailed list for every OSPF-enabled interface. The command is useful to determine whether the "network" statements were correctly composed.

To get a summary of OSPF-enabled interfaces, use the "show ip ospf interface brief" command

The "show ip ospf interface (serial 0/0/1)" command provides detailed OSPF information.

OSPFv3

Recall that in IPv6, the network address is referred to as the prefix and the subnet mask is called the prefix-length.

Similar to its IPv4 counterpart, OSPFv3 exchanges routing information to populate the IPv6 routing table with remote prefixes.

Similarities Between OSPFv2 to OSPFv3

* Neighbor discovery mechanism: in OSPFv3, there is no requirement for matching subnets to form neighbor adjacencies.

This is because neighbor adjacencies are formed using link-local addresses, not global unicast addresses.

Differences Between OSPFv2 and OSPFv3

* All OSPF router multicast addresses - OSPFv2 uses 224.0.0.5; whereas, OSPFv3 uses FF02::5.

* DR/BDR multicast address - OSPFv2 uses 224.0.0.6; whereas, OSPFv3 uses FF02::6.

* Authentication - OSPFv2 uses either plaintext authentication or MD5 authentication. OSPFv3 uses IPv6 authentication

Link-Local Addresses

An IPv6 link-local address enables a device to communicate with other IPv6-enabled devices on the same link and only on that link (subnet).

Packets with a source or destination link-local address cannot be routed beyond the link from where the packet originated.

A network with router interfaces configured with IPv4 and IPv6 addresses is referred to as dual-stacked. A dual-stacked network can have OSPFv2 and OSPFv3 simultaneously-enabled.
Ej: IPv6 unicast routing and the configuration of the global unicast addresses of R1

Steps to configure basic OSPFv3 in a single area.

Step 1: Enable IPv6 unicast routing: "ipv6 unicast-routing"

Step 2: (Optional) Configure link-local addresses.

Step 3: Configure a 32-bit router ID in OSPFv3 router configuration mode using the:

"router-id (rid)" command.

Link-Local Addresses

Link-local addresses are automatically created when an IPv6 global unicast address is assigned to the interface. Global unicast addresses are not required on an interface; however, IPv6 link-local addresses are.

Unless configured manually, Cisco routers create the link-local address using FE80::/10 prefix and the EUI-64 process. EUI-64 involves using the 48-bit Ethernet MAC address, inserting FFFE in the middle and flipping the seventh bit.

Assigning Link-Local Addresses

Link-local addresses can be configured manually using the same interface command used to create IPv6 global unicast addresses, but appending the:

"link-local" keyword to the ipv6 address command.

A link-local address has a prefix within the range "FE80 to FEBF". When an address begins with this hextet (16-bit segment) the link-local keyword must follow the address

Configuring the OSPFv3 Router ID

OSPFv3 requires a 32-bit router ID to be assigned before OSPF can be enabled on an interface.

Configuring the OSPFv3 Router ID

IPv6 routing protocols are enabled on an interface, and not from router configuration mode, like their IPv4 counterparts. The network IPv4 router configuration mode command does not exist in IPv6.

Adjusts the reference bandwidth to 1,000,000,000 bps (1 Gb/s), because there are Gigabit Ethernet links in the network. Notice the information console message that this command must be configured on all routers in the routing domain.

Modifying an OSPFv3 Router ID

However, after an OSPFv3 router establishes a router ID, that router ID cannot be changed until the router is reloaded or the OSPF process is cleared.

Ej: the OSPF routing process is cleared using the clear ipv6 ospf process privileged EXEC mode command. Doing this forces OSPF on R1 to renegotiate neighbor adjacencies using the new router ID.

Enabling OSPFv3 on Interfaces

To enable OSPFv3 on an interface, use the:

"ipv6 ospf (process-id) area (area-id)" interface configuration mode command.

The (process-id) value identifies the specific routing process and:

"must be the same as the process ID used to create the routing process in the:

"ipv6 router ospf (process-id)" command.

Verify the IPv6 Routing Table

The "show ipv6 route ospf" command provides specifics about OSPF routes in the routing table