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:

Type of Service routing. Multiple routes can be configured to support differing type of service requirements. For example, high-throughput can be selected for one class of service, while minimal delivery delay is more critical for some other application.
Load Balancing. When multiple routes are available, traffic can be evenly distributed over the routes. More efficient network utilization results.
Subdivision of Autonomous Systems - management of large autonomous systems can be enhanced by further dividing the system into logical areas.
Security - exchanges are authenticated. Inadvertent or malicious transmission from foreign routing nodes are discarded. Only those hosts intended for the routing network are included. The network isn't vulnerable to the threat of having routing tables corrupted by faulty route information.
Host-specific, network and subnetwork routing are supported.
Special features are provided to support LAN environments. Although the relationships between routers are maintained on a logical link basis, link state transmissions are minimized by the architecture. Designated gateways are responsible for transmitting the link state information for all information in their local area.
OSPF is an open specification - published as an RFC rather than defined as a defacto standard such as RIP, anyone can implement the standard, without paying royalties. The intent is to encourage many vendors to use it rather than requiring users to lock into a single vendor's equipment.

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:

Internal routers - Connected to only networks internal to single area. Routers that connect to only the backbone interfaces are also internal routers. Internal routers run only one copy of the OSPF routing algorithm and maintain a topological database for only their local area.
Area border routers - Connect to more than one area. These routers run multiple copies of the basic algorithm, with one copy of the topological database for each area to which they are connected, and one copy for the AS backbone. To limit the amount of routing traffic (and routing complexity), area border routers condense the topological information of their attached areas for distribution to the backbone. Other routers attached to the backbone forward the routing information to other areas.
Backbone routers - A router that has an interface to the backbone. This includes all routers that interface to more than one area (i.e., area border routers). However, backbone routers do not have to be area border routers. Routers with all interfaces connected to the backbone are considered to be internal routers.
AS boundary routers - A router that exchanges routing information with routers belonging to other AS. Boundary routers have external routes that are advertised throughout the AS. Every router in the AS maintains a path to each AS boundary router. AS boundary routers may be internal or area border routers, and may or may not participate in the backbone.

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:

Hello Messages - that are periodically sent to validate neighbor reachibility. Each router maintains a list of timers that are used to determine the presence of neighbor routers. As OSPF hello messages are received, the router resets its timer. Failure to receive the hello messages from neighbor routers is used to determine the loss of a link to a router.
Database Description Messages - transferred to initialize the topology data base. These messages are sent on the request of a router entering the network. These messages are used to define the topology of the network. The topology information includes the types of links, the routers involved in the links, along with link identification information.
Link State Advertisements - Once the topology databases have been exchanged, routers may determine that some of the information in the database is no longer accurate. To resolve these changes, the router will send a link status request message to its neighbor. The reply message is the link status update message that contains a list of link status advertisements.

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.

References:

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