Lecture #10 - OSPF: Part 1

OSPF Overview

Open Shortest Path First (OSPF) is a link-state based routing protocol designed as a replacement for RIP. As its name implies, OSPF makes use of Dijkstra's Shortest Path First (SPF) algorithm in order to determine the best route to a given destination based on the information within its link-state or topological database.

OSPF is open - the standard was developed by the Internet Engineering Task Force (IETF) and is readily available for anyone to implement and use. The current version of OSPF for IPv4 is OSPF version 2 (or OSPFv2 for short) and is documented in RFC2328.

OSPF exhibits a number of advantages over distance vector protocols such as RIP and IGRP. Due to the fact that it is a link-state based protocol OSPF has faster convergence, better scalability and is less susceptible to faulty routing information (we are no longer routing by rumour!).

Other features of OSPF include:

Support for VLSM, classless routing and supernetting.
An arbitary and dimensionless metric.
Support for routing "areas" to reduce overhead and maintain network topology.
All routing protocol exchanges are authenticated.
Route tagging to track routes from external sources.

OSPF Operation - An Overview

The general operation of OSPF can be summarised as follows:

Hello messages are sent out on all OSPF-enabled interfaces. A router receiving the Hello message will become a neighbour if they have a matching configuration (same area, same authentication, etc).
Neighbouring routers may establish adjacencies (effectively a virtual point-to-point link), if deemed necessary.
Link State Advertisements (LSAs) are sent over all adjacencies. OSPF has multiple LSA types which identify the type of network which this link connects to.
When a router receives an LSA it stores a copy in its Link-State DataBase (LSDB), before sending it on to all of its neighbours (excluding the one from which it received the LSA). After flooding has completed all routers should have identical link-state databases.
Once the link-state database has been created, E. W. Dijkstra's Shortest Path First (SPF) algorithm is used to create a loop-free graph that identifies the shortest path to every known network. This is done separately for each area.
The router then constructs its routing table based on the resulting SPF graph.

The network traffic generated by OSPF is minimal. Once the initial exchange of LSAs has been completed, the only traffic will be small Hello packets sent every 10 seconds (for broadcast networks). Additionally, LSAs are readvertised every 30 minutes. Other than this no OSPF traffic should be required unless changes occur to the network topology or link-state.

Dijkstra's Shortest Path First Algorithm

Dijkstra's SPF algorithm allows us to construct a tree with the minimal distance between n nodes. Recall from lecture 1 that a tree is a minimally connected network, with only one path between every two nodes. By definition, a tree means that routing loops are impossible and routing decisions are simple since there is only one possible path.

In the case of a router we will work with three sets of data: the link-state database, a list of shortest paths and a working list of paths. To find the shortest path from a given router to all other routers:

Starting at the router in question (this becomes the "root node" of the tree), add to the working list paths for all directly connected routers.
Select the shortest path from the working list and mark the destination router as "done". We now remove this shortest path from the working list and add it to our shortest paths list (this will be the shortest path between the root node and the destination router).
Add to the working list paths from the "done" router to all other routers that it is directly connected to, providing that they are not already on the shortest path list. If a router already exists on the working list, only replace the entry if the new entry has a "distance" that is less than the current entry. The "distance" to these routers is calculated from the root node.
If there are still entries on the working list (ie. there are routers for which the minimum distance has not been found), go back to step 2.

In this example network the "distances" are to be found from router A to all others.

The end result (in order of discovery) is:
A-C 2
A-B 3
A-C-D 4

OSPF Notes

The running time for this algorithm increases in proportion to N log N, where N is the number of routers in the network. This doesn't scale too well (though there are worse ways of discovering the best path). For this reason, large OSPF networks are usually subdivided into smaller areas.
Often it is not necessary for every router to know the path to every other router. There may be only one path out of an area, no matter what the destination. Further, each router is concerned only with getting packets to the next router. Once delivered there, the packets become "someone elses problem" (or an SEP :)

RFC2328 does not specify how the "distance" metric is to be determined. Cisco define it to be:

^10⁸/_{interface speed
bps.}

This results in the following OSPF costs:

Media type	Default Bandwidth	Default OSPF cost
Ethernet	10Mbps	10
Fast Ethernet	100Mbps	1
FDDI	100Mbps	1
T1 (serial)	1544Kbps	64
56Kbps serial	1544Kbps	64
HSSI	45Mbps	2

OSPF Areas

An OSPF network (Autonomous System) can be divided into Areas. This has advantages from a network scalability perspective. Large OSPF areas have the following problems:

Large routing tables. There may be multiple paths between networks within an area. All these are kept in the topology database.
Frequent recalculation of the SPF algorithm. This happens every time there is a change in the area. Even an unstable link can cause frequent recalculation.
Slow synchronisation. It takes time for the topology information to propagate throughout an area. Some routers may have an inconsistent view of the network leading to temporary reachability problems.

Subdivision into areas reduces these problems and in addition, reduces route update overhead. Routers need only pass summary information between areas, not the full database.

It is rumoured [RFC 2328] that "all" communications between areas must pass through a backbone area, leading to the star topology below:

This means that the routers in the OSPF system need considerably more thought in their configuration as they may be called on to perform different routing functions.

Internal Routers: A router with all directly connected networks belonging to the same area. These routers run a single copy of the basic routing algorithm.
Area Border Routers (ABRs): A router that attaches to multiple areas. ABRs run multiple copies of the basic algorithm, one copy for each attached area. ABRs condense the topological information of their attached areas for distribution to the backbone. The backbone in turn distributes the information to the other areas.
Backbone Routers: A router that has an interface to the backbone area. This includes all routers that interface to more than one area (i.e. ABRs). However, backbone routers do not have to be ABRs. Routers with all interfaces connecting to the backbone area are supported.
AS Boundary Routers (ASBRs): A router that exchanges routing information with routers belonging to other Autonomous Systems. Such a router advertises AS external routing information throughout the Autonomous System. The paths to each ASBR is known by every router in the AS. This classification is completely independent of the previous classifications: ASBRs may be internal or ABRs, and may or may not participate in the backbone.

Forming OSPF Areas

All OSPF routers in an area have identical copies of the area topology database.

On a broadcast medium, OSPF routers elect a Designated Router (DR) and a Backup Designated Router (BDR). This reduces the amount of traffic that would otherwise occur when every router tried to exchange its database with every other router.

Routers exchange databases only with the the DR and the BDR, not with all other routers in the area.

In general communication between routers is addressed to the AllSPFRouter multicast group (224.0.0.5), whilst traffic addressed to the DRs is sent to the DRouters multicast group (224.0.0.6).

In order for an area to be formed, all routers must agree on:

Area Number
Netmask
Hello interval (see later)
Dead interval
Authentication type

Discovering Neighbours

Routers send out OSPF Hello packets every 10 seconds (30 seconds on non-broadcast media). Routers discover their neighbours by listening to these broadcasts.

Electing Designated Router and a Backup

When a network area comes up for the first time, routers examine Hello packets from their neighbours and compare priorities.

If two or more routers share the highest priority, they then compare their IDs (the numerically highest IP address of any of their interfaces or loopback addresses). The winner becomes the DR, the runner up becomes the BDR.

Following the initial election, the DR and the BDR retain their status, even if a higher priority router is added to the area. It's only when both DR and BDR fail that another router can take over as DR.

If the DR fails, the BDR is promoted and a new BDR is elected. If the BDR fails, a new BDR is elected.

Virtual Links

To ease the restriction that "all areas connect to the backbone", OSPF provides for Virtual Links.

These are point to point links joining ABRs so that the outlying area can be connected to the backbone via only one transit area.

It is rumoured that Virtual Links are not "good style" and should only ever be used as emergency fixes, not as an inherent part of the network design.

Route Summarisation

OSPF summarises routing tables only when manually configured on an ABR or ASBR. OSPF summarisation can be done on any bit boundary. For this to work efficiently, IP addresses in an area need to be carefully allocated (see later lecture).

For example, if an area contained network addresses 192.168.0.x through to 192.168.15.x (where x is a host number and 0...15 is the subnet number), then all 16 subnets could be described (summarised) as 192.168.0.0/20.

This means that if the first 20 bits of the IP address match the first 20 bits of 192.168.0.0, then the destination is within the summarised area. Note that OSPF does not describe route summaries quite this way. The intent is the same, but the syntax is different.

Route summarisation is an "obvious good thing"™: It reduces the size of the topology database and thereby reduces the number of rules a router has to use to determine where to send a packet.

Non-Broadcast Multiple Access (NBMA) Networks

Some transmission media are inherently not broadcast capable (ATM, X25, Frame Relay).

It may be necessary to manually force the election of a DR and BDR. Point-to-point links will then need to be configured to all routers in the area (without broadcasting, routers won't be able to find their neighbours).

Routers will have to replicate packets to simulate multicasting, which increases processing load on the routers.

Configuring OSPF (Single Area)

(Commands entered in Configuration Mode)

Configuring an Interface

R1(config)#
R1(config)#interface Ethernet0/0
R1(config-if)#ip address 192.168.1.254 255.255.255.0
R1(config-if)#no shutdown
R1(config-if)#bandwidth 1...10000000  Bandwidth in kilobits
R1(config-if)#exit
R1(config)#

Enabling Routing of IP

R1(config)#ip routing

Enabling Routing Protocol

R1(config)#
R1(config)#router ospf 100
R1(config-router)#network 192.168.1.0 0.0.0.255 area 0
R1(config-router)#network 192.168.4.0 0.0.0.255 area 1
R1(config-router)#exit
R1(config)#

Note that the 100 following the "router ospf" command identifies the specific routing process that we will be configuring.

Saving Configuration in NVRAM

copy running-config startup-config

Other Useful Commands

R1#show ip ospf neighbor
R1#show ip ospf database
R1#show ip ospf border-routers
R1#show ip ospf interface Ethernet0/0

References

Shortest Path First Algorithm Demystified

Wikipedia: Dijkstra's Algorithm

Cisco IOS: Configuring OSPF