Open Shortest Path First Protocol

November 21, 1998

Jing Liu
Computer Science Engineering Department
Helsinki University of Technology
jliu@cc.hut.fi

Abstract

This essay briefly describes the OSPF protocol used for routing purpose in Internet. Concepts like dynamic routing, link-state algorithm and routing protocol etc.are introduced and explained shortly. The advantages of OSPF over other routing protocols are also justified.

Table of Contents

• 1 Introduction
• 2 Dynamic Routing
• 3 OSPF Algorithm
• 4 OSPF Routing Protocol
• 5 Why OSPF protocol?
• References
• Further Information

1 Introduction

Many different routing protocols are used in big networks. The Internet as an example is divided to collection of autonomous systems (ASs), each of which uses its routing protocol to communicate between the routers in the same autonomous system. This is called an Interior Gateway Protocol (IGP). Among many other IGPs, Open Shortest Path First (OSPF) protocol is becoming the preferred one and is gradually replacing RIP. It is a link-state routing dynamic protocol. OSPF Version 2 is documented in RFC 1583 [4].

OSPF recalculates routes quickly in the face of topological changes, utilizing a minimum of routing protocol traffic. OSPF provides support for equal-cost multipath. Separate routes can be calculated for each IP Type of Service. An area routing capability is provided, enabling an additional level of routing protection and a reduction in routing protocol traffic. In addition, all OSPF routing protocol exchanges are authenticated. [6]

Back to the Table of Contents

2 Dynamic Routing

Routing is a key feature of the Internet because it enables messages to pass from one computer to another and eventually reach the target machine [6]. When the network is small, there is a single connection point to other networks, and there are no redundant routes, a static routing is enough. But if any of these tree conditions is false, dynamic routing is normally used. Dynamic routing occurs when routers talk to adjacent routers, informing each other of what network each router is currently connected to. The routers must communicate using a routing protocol. In Contrast to static protocol, the information placed into the routing tables - the routes, are added and deleted dynamically as routes change over time.

Back to the Table of Contents

3 OSPF Algorithm

Two main types of routing algorithm are link-state algorithm and distance vector algorithm [1]. OSPF is a link-state algorithm while RIP is a distance vector algorithm. The basic concept of link state algorithm is all nodes in the network have a copy of the network map, which is regularly updated. Instead of trying to compute "best routes" in a distributed fashion, all the nodes will maintain a complete copy of the network map and perform a complete computation of the best routes from this local map [2]. The network map is held in a database, where each record represents one link in the network.

The basic algorithm can be described as below:

• Least-cost criteria weights are assigned to the paths in the network.
• Each node is labeled (identified) with its least-cost criteria from the source along to a known path.
• Initially, no paths are known, so each node is labeled with infinity. However, updates to the values (once the weights are established) are the same as an initialization. Each node is examined in relation to all nodes adjacent to it. (The source node is the first node considered and becomes the working node).
• Least-cost criteria labels are assigned to each of the nodes adjacent to the working node. Labels change if a shorter path is found from this node to the source node. In OSPF, this would occur with the sending of link status messages on a broadcast basis to all other gateways.
• After the adjacent nodes are labeled, all other nodes in the network are checked. If one has a smaller value in its label, its label becomes permanent and it becomes the working node. If the sum of the node's label is less than the label on an adjacent node, the adjacent node's label is changed because a shorter path has been found to the source node. Another working node is selected and the process repeats itself until all possibilities have been searched. The final labels reveal the least-cost, end-to-end path between the source and the other nodes. These nodes are considered to be within a set N as it pertains to the source node.

Back to the Table of Contents

4. OSPF Routing Protocol

OSPF runs directly on top of IP. It routes IP packets based solely on the destination IP address and IP Type of Service found in the IP packet header. IP packets are routed "as is" -- they are not encapsulated in any further protocol headers as they transit the Autonomous System. OSPF is a dynamic routing protocol. It quickly detects topological changes in the AS and calculates new loop-free routes after a period of convergence. This period of convergence is short and involves a minimum of routing traffic. [3]

In this routing protocol, each router maintains a database describing the Autonomous System's topology. Each participating router has an identical database. Each individual piece of this database is a particular router's local state. The router distributes its local state throughout the Autonomous System by flooding.

OSPF allows sets of networks to be grouped together. Such a grouping is called an area. The topology of an area is hidden from the rest of the Autonomous System, which enables a significant reduction in routing traffic. Also, routing within the area is determined only by the area's own topology.

OSPF divides networks into several classes, including point-to-point, multi-access, and non-broadcast multi-access. A serial link connecting two routers together would be a point-to-point link, while an Ethernet or Token Ring segment would be a multi-access link. A Frame Relay or X.25 cloud would be classified as non-broadcast multi-access.

All OSPF protocol exchanges are authenticated. Only trusted routers can participate in the Autonomous System's routing. A variety of authentication schemes can be used; a single authentication scheme is configured for each area. This enables some areas to use much stricter authentication than others do.

Back to the Table of Contents

5 Why OSPF protocol?

OSPF is much more complex than for example RIP, but why it's becoming more and more popular and replacing RIF? The following are the main reasons:

OSPF is specifically designed to operate with larger networks so it has good scalability.

OSPF can fully support subnetting, including VLSM and non-contiguous subnets.

OSPF uses small "hello" packets to verify link operation without transferring large tables. In stable networks, large updates occur only once every 30 minutes.

OSPF can route packets by different criterion based on their Type Of Service (TOS) field [5]. For example, file transfers could be routed over a satellite link while terminal I/O could avoid such high delays. This requires cooperative applications on the end systems.

Routes can be tagged with arbitrary values, easing interoperation with EGPs, which can tag OSPF routes with AS numbers.

Back to the Table of Contents

References

Back to the Table of Contents

Further Information

Building large frame relay networks with OSPF

Recommendations for building large Frame Relay networks using OSPF

Cisco - OSPF design guide

How OSPF works and how to use it to design and build large and complicated networks.

Data communications, computer networks and open systems

Address all the main issues in data communications, computer networks and open systems. Both TCP/IP and OSI structure are discussed.

Introduction to IP multicast routing

Benefits of multicasting, operations of IGMP and algorithms deployed by multicasting routing protocols.

OSPF 2 protocol overview

OSPF protocol overview on its advantages, disadvantages and main features.

OSPF FAQs

FAQs and the answers about OSPF.

OSPF - PC webopedia definition and links

Short introduction on OSPF and some useful links to other documents.

OSPF white paper

Background information and an application guide to the Open Shortest Path First (OSPF) routing protocol

RFC1370

Statements on applicability of using OSPF as a common IGP in Internet.

RFC1403 BGP OSPF interaction

Defines the criteria for designing ASBR, which runs BGP with other ASBR and OSPF as its IGP.

Router level protocols

Introductions on different route level protocols including EGP and OSPF.

Back to the Table of Contents