OSPF -- Scalable Autonomous System Routing

Using Link State Routing Algorithms, OSPF supports complex autonomous system routing

Functionally more complex than RIP, as a link-state routing protocol as opposed to the vector-distance RIP, OSPF provides solutions to the primary deficiencies of RIP. Routing architectures can scale well beyond the maximum 16 hops supported by RIP. Rather than exchanging node (and network) reachability information, OSPF routers exchange link state information. Through the link state information, each router maintains its own copy of the network topology. From this link-state database, shortest path routing decisions can then be made. For those of you that are familiar with the OSI routing scheme, many of the features supported by OSPF are similar to the OSI IS-IS routing protocol. The original versions of OSPF are actually derivations of some of the earlier versions of the IS-IS protocol.

OSPF provides additional flexibility in managing complex networks. Some of its features include: Several concepts are involved in the OSPF algorithm. Where RIP treated an autonomous system as a monolithic collection of routes and subnets, OSPF introduces the concept of areas, that can be used to hide routing information within a OSPF routing domain (Internet autonomous system). With an autonomous system divided into a collection of logical areas, a number of types of OSPF routing nodes are supported, including internal routers, area border routers, backbone routers, and Autonomous System (AS) boundary routers. The protocols used to support OSPF routing include database broadcast packets and link state change broadcasts. A "Hello" protocol is used to detect changes in the availability of adjacent routers.

Link State versus Vector Distance

An understanding of link-state routing algorithms is fundamental in understanding OSPF. As opposed to the vector-distance protocols where adjacent routing nodes exchange only information describing their "distance" to destinations, link-state routing protocols are based on all nodes in the network maintaining a complete image of the links between routers within the router's routing domain. This information is transferred through initial database messages and link-state change messages. The routing algorithms run in parallel on all machines in the region. Each router maintains its own copy of a topological database. With a complete picture of the topology information within its area (or areas), each router can make routing decisions on the basis of traversing the route trees in the local tables. As datagrams are received, the shortest path through the local data base is identified. The datagram is then sent to the adjacent router that is the next hop in the shortest path to the packet destination.

The OSPF implementation of the link-state algorithms supports a hierarchical organization. At the highest level of the hierarchy is the AS. In the Internet routing scheme, the AS is a network or a group of networks that fall under a single administrative authority. With OSPF, the AS is divided into one or more areas. Routers can participate in one or more areas. Each router in an area maintains its own copy of the topological database for its own area. To limit the amount of information each router must maintain in an AS, the topological database contains only the routes within its designated area. Limiting the database through this abstraction helps to limit the amount of route management traffic that must be transferred throughout the AS. This form of routing abstraction leads to two types of routing, intra-area routing that handles traffic local to an area, and inter-area routing for routing information between nodes in separate routing areas.

OSPF Router Types

With the hierarchical organization, several types of routers are included in the OSPF architecture. The types of routers include: Through the use of several types of routers with different roles, the information hiding properties inherent to the concept of a hierarchical routing service are realized. This helps to limit the size and complexity of the routing databases maintained by each router. As a result, the amount of memory and processing capability required of each router can be controlled through judicious selection of a workable OSPF based AS architecture.

Maintaining the Topological Database

One of the critical services provided by OSPF is a set of messages that are used to define and control the topological database. These messages can be broken into three primary categories: These protocol exchange mechanisms represent the set of primitives used by the OSPF routing nodes. A good bit of the complexity in implementing OSPF is involved in management of the routing tables, along with the implementation of the routing algorithms. As a metric of the protocol's complexity, RFC 1583, OSPF Version numbers greater than 200 pages, much of which are examples of network topologies and routing strategies.

Types of Service Routing

One of the more attractive features of OSPF is its capability to support Types of Service (TOS) based routing. Through TOS routing, the IP service class selections are supported in routing decisions. In particular, the IP encodings of precedence, delay (the D bit represents low delay requested), and throughput (IP T bit represents a request for higher throughput) can be supported through OSPF identification of classes of service provided by the various links in the network. Routers in the network can advertise different route cost metrics for each TOS for each link state. Through varying the metrics used both for the links and the associated traffic TOS, TOS based routing is supported by OSPF.

Routing between nodes in different Areas (Inter-area routing)

Routing packets outside of the originator's local area is handled in a manner similar to the techniques applied to routing packets across the Internet. Three routes are managed in transferring the packet. First, the shortest path to the AS backbone is identified, and the packet is forwarded to the local area's nearest border router. Once the packet has reached the border router, the backbone routing determines the shortest path to the destination area. In effect, the backbone acts as an area that is the hub of a star routing topology. Once the backbone routes the packet to one of the destination node's area border routers, the third shortest path route is calculated, and the packet is delivered to its intended destination.

Extensive information is available on OSPF both in the RFCs and through documentation that can be found on the World-Wide-Web. In particular, the OSPF version 2 specification (RFC 1583) offers several examples of configurations that can be supported by OSPF, the database exchanges required and the algorithms that can be used in deriving the shortest path routing decisions. With the size and complexity of the Internet growing by the day, OSPF offers a rich set of routing features.


RFC 1583. J. Moy, OSPF Version 2. March 1994
Internetworking with TCP/IP Volume 1 Principles, Protocols, and Architecture. Douglas E. Comer, Prentice Hall