Illustrated TCP/IP by Matthew G. Naugle Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471196568   Pub Date: 11/01/98

Chapter 118
OSPF Overview

There are two types of standardized IGPs: RIP (versions 1 or 2) and OSPF. Like RIP, OSPF is an IGP, which means that it is designed to run internally to a single autonomous system (AS). (An AS is described as those networks and routers grouped into a single domain under one authority.) It exchanges routing information within a single autonomous system. It can be used in small, medium, or large internetworks, but the most dramatic effects will be readily noticed on large IP networks. As opposed to RIP (a distance vector protocol), OSPF is a link-state protocol. It maintains the state of every link in the domain.

The following is a simple algorithm for OSPF:

•  Upon initialization, each router records information about all its interfaces.

•  Each router builds a packet known as the Link State Advertisement (LSA).

•  The packet contains a listing of all recently seen routers and their costs.

•  LSAs are restricted to being forwarded only in the originated area.

•  Received LSAs are flooded to all other routers.

•  Each router makes a copy of the most recently “seen” LSA.

•  Each router has complete knowledge of the topology of the area to which it belongs.

•  Adjacencies are formed between a designated router (and backup DR) and other routers on a network.

•  Shortest-path trees are constructed after routers exchange their databases.

•  Router algorithm updates only when changes occur (or every 30 minutes, whichever is shorter).

This information is “flooded” to all routers in the domain. Flooding is the process of receiving the information on one port and transmitting it to all other active ports on the router. In this way, all routers receive the same information and can compute their own routes. This information is stored in a database called the link-state database, which is identical on very router in the AS (or every area if the domain in split into multiple areas). Based on information in the link-state database, an algorithm known as the Dykstra algorithm runs and produces a shortest-path tree based on the metrics, using itself as the root of the tree. The information this produces is used to build the routing table.