Open Shortest Path First

See also: OSPF for IPv6

Open Shortest Path First (OSPF) is one of the two nonproprietary and highly scalable interior routing protocols of the Internet, the other being Intermediate System-Intermediate System (ISIS). Its principal specification is RFC 2328. While it uses multicast addresses for some of its internal functions, it only sets up routes for unicast definitions.

OSPF is designed for hierarchical routing, from a set of nonzero "edge" areas, to a backbone area, forming a routing domain. Contrary to some misperceptions, there is absolutely no reason not to have multiple OSPF domains (i.e., a backbone area 0.0.0.0 and some number of nonzero areas), connected by a backbone of backbones. Examples of such networks, include, for example, the OSPF domains are continental, and the backbone of backbones is BGP when the policies are complex and static routing when the network is fundamentally hierarchical with 3 or more levels of hierarchy.

OSPF History and Relationships

While the conceptual background for both OSPF and IS-IS came from research on the theory of link state routing, the serious specification and standards efforts that made them real involve technical, market, and even personality factors. Some of the reasons why OSPF and IS-IS differentiated are in the link state routing section, and some of the history is here and in IS-IS

One of the historical drivers for OSPF is that Internet Protocol, still in its early days of significant deployment, had principally been using the Routing Information Protocol (RIP). RIP is a simple and straightforward protocol, and, especially with enhancements, still occasionally has a niche role.

The industry, as a whole, looked for an interior routing protocol that would overcome some of the disadvantages of RIP. Cisco Systems created the first viable second-generation interior routing protocol, the Interior Gateway Routing Protocol (IGRP). While IGRP is obsolete today, it had significant advantages over RIP. It is probably appropriate to note that Cisco's proprietary Enhanced Interior Gateway Routing Protocol is a proprietary third-generation protocol, but radically different in architecture than IGRP; the simularity in name is all they really have in common.

OSPF, IS-IS and EIGRP all can be considered third-generation. In particular, the Internet Engineering Task Force (IETF), while as neutral as standards bodies can get, had a number of vendors cooperating on what was hoped to be a superior protocol, which, among other things, would use link state theory rather than the second-generation distance vector model of IGRP. It can be observed that some truly multivendor standards emerge when one proprietary standard truly scares the competition. IS-IS, while sharing age and algorithm with OSPF, developed in a different standards body, when not only the Open Systems Interconnection Reference Model but the OSI protocols still were considered a potential competitor for the Internet Protocol Suite (IPS) and IETF; the original IS-IS (actually an open derivative of the routing protocol in Digital Equipment Corporatio's DECnet Phase V, was undertaken under the auspices of the International Organization for Standardization (ISO).

OSPF and ISIS, therefore, are contemporaries, but not only had different drivers, but different lead architects, John Moy for OSPF and Radia Perlman for IS-IS. Both are brilliant and charming people, but if there are two way to implement a functions with a seemingly similar purpose, the two are likely, through the expression of some mysterious cosmic force, to find different detailed ways to design the algorithms.

Advice before reading OSPF specifications

There are many places in OSPF where fields are 32 bits long. Simply because a field is 32 bits long, and may even be displayed in the format of an IPv4 address, does not mean that the field has to be a valid IPv4 address. One of the most common causes of confusion in OSPF is thinking that various 32-bit fields are IP addresses, and worrying about assigning a valid one.

There are cases, in OSPF for IPv4, where a 32-bit field indeed needs to be a valid IP address, or that its value defaults from some IPv4 address. Learn them, but treat them as exception conditions. It is also wise, since different implementations will default in different ways, to set, explicitly, all OSPF identifiers that can be set manually.

Since OSPF for IPv6 continues to retain 32-bit identifiers in many places, even though all its actual addressing is IPv6, getting into the habit of thinking "identifier" rather than "address" will enormously simplify OSPF for IPv6 deployment.

OSPF Version 1

The first version of OSPF produced by the IETF worked, but operational experience showed there were errors in parts of the specification. There were some early desires for additional functionality that simply did not prove to be necessary, partially because new specialized protocols could carry out those functions more effectively.

OSPF Version 2

In any event, the first widely implemented OSPF specification was called Version 2. That was to progress from IETF Proposed Standard to the more complete IETF Draft Standard in March 1994. There was a consolidation document in July 1997., and finally the culminating full IETF standard in April 1998.

At that point, additional features were incremental improvements. The next major version would first be called version 3, and then OSPF for IPv6. The most recent version supporting IPv6 was approved in July 2008, still at the lowest (PROPOSED STANDARD) level of the IETF.

Router types

OSPF has some inconsistent ways to refer to "router". As used in this section, a router is a multiple-interface device with interfaces in one or more areas. There is another OSPF usage of the word "router", discussed under "neighbor discovery", that is an attribute of an interface of a router.

Route types

At the highest level, OSPF knows about two kind of routes; an OSPF concept called a virtual route is outside the scope of the immediate discussion.:

Internal routes

These originate inside the domain, and may be intra-area or inter-area.

External routes

External routes are generated from ASBRs that connect the domain to other sources of routing information, including manually generated static routes. In most OSPF implementations, unless otherwise specified, externals are of Type 2: their cost is that of the external interface only. An external route can be configured as Type 1, which means that its cost will be the sum of the external interface cost plus the cost of all internal interfaces traversed from the starting point, through the domain, to the ASBR external interface.

Area organization

OSPF has two basic kinds of areas, always with a 32-bit area identifier. That identifier is usually displayed in the dotted decimal form of an IP address, but it doesn't need to comply with IP addressing rules.

The backbone area must always be 0.0.0.0; the remaining areas can use any other identifier. It can be perfectly reasonable to start with a single OSPF area, but it is unwise to designate that 0.0.0.0, because as soon as another area is needed, you would have to renumber the existing routers into a nonzero area.

Three types of area characteristics are standard; Cisco defined an additional one that is widely used.

Regular area

Connected to area 0.0.0.0 by one or more area border routers, a regular area accepts all types of internal and external routes from area 0.0.0.0, or from autonomous system border routers in the regular area that connect outside it. Advertises both its intra-area routes, and external routes from ASBRs connected to it, to the backbone.

Stub area

Also connected to the backbone via one or more ABRs, it accepts only inter-area routes and a default route generated by the ABR; advertises its intra-area routes to the backbone. It cannot contain an ASBR.

Not-so-stubby area (NSSA)

From one or more ABRs, it accepts only inter-area routes from area 0.0.0.0, to which it advertises its intra-area routes. A NSSA also can contain an ASBR, whose external routes propagate through the area and then, via the ABR, to area 0.0.0.0. HSSAs are defined in RFC 3101.

Totally stubby area

A Cisco proprietary feature that is present in some other implementations, a totally stubby area can have one or more ABRs, to which it advertises its intra-area routes. It accepts only the default routes generated by the ABR(s). Unless it is declared not-so-stubby as well, it cannot contain an ASBR.

Not-so-stubby and totally stubby

Combining the standard NSSA and the Cisco totally stubby feture, an area of this type behaves like an NSSA in that it can have an ASBR, but it only accepts default from area 0.0.0.0.

OSPF data exchange

Before going into the details of information exchange in the various cases of intra-area, inter-area, and external information, as well as various methods for area optimization, reviewing the OSPFv2 messages gives useful background. Be aware that while essentially the same set of messages exist in OSPF for IPv6, those messages are much less IPv4-specific than those that are discussed here. Functionality, however, is similar.

Please note that there are differences in the exchange involved in topological database initialization, and in the exchanges and triggers that keep the databases current and synchronized.

In the most common OSPF for IPv4, there is a standard header for all OSPF packets and five OSPF packet types. Four of the five types carry link state advertisements (LSA), which describe aspects of the topology. There are eleven types of LSA, some of which are no longer used.

Hellos are exchanged to initialize interfaces, database descriptions are used as part of a process to load the initial database, and the combination of LSA request, LSA update, and LSA acknowledgement are used to keep the database current.

OSPF packet header

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | Version #=2   |     Type      |         Packet length         |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                          Router ID                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           Area ID                             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |           Checksum            |             AuType            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       Authentication                          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       Authentication                          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

OSPF packet types

Hello packets are used for interface initialization, discovering other routers on the same subnet, and detecting router failures. Database description packets are used to initialize the topological database.

Link state request, link state update, and link state acknowledgement packets work together to propagate topology changes and keep the databases synchronized.

Link state advertisement types

Note that there are both new types, and changes of semantics, in OSPF for IPv6.

Intra-area behavior

While OSPF, as a whole, is usually called a link state protocol, there is a separate link state computation for each nonzero area.

OSPF router initialization

Each OSPF router must have a router ID unique to the routing domain. This is a 32 bit number that is usually displayed in the dotted decimal notation used for IPv4, but there is no requirement that the router ID be a valid IP address.

A common source of the router ID is what is variously called a "loopback interface" on the router. If no such software-defined interface exists, there are implementation-specific means to assign one, most commonly the IP address of the first LAN interface on which OSPF initializes.

The best practice, to avoid surprises, is, if the OSPF implementation allows it, to configure an explicit router ID.

Neighbor relationship

Not all routing protocols distinguish between routers that are adjacent and that are neighbors, but OSPF does, and it is an important distinction. A neighboring router has an interface on the same subnet as the local router. Once they are in the FULL state of awareness of the routing data base, one router can forward through any neighbor that advertises connectivity to the destination.

When a router interface initializes, it multicasts to the "all link state routers" group, 224.0.0.5 in IPv4, a HELLO message. This message contains the router IDs of all other routers, on the subnet, of which the router issuing the HELLO is aware.

When the local router hears a HELLO from another router on the same subnet, and that HELLO's parameters are compatible, the next local router HELLO will contain the other router's ID. When a router sees its own router ID in a HELLO message from another router, it knows that a neighbor relationship exists between them. It will be able to forward through that other router, as soon as the designated router election process completes and all the routers on the subnet synchronize their link state databases.

To be a neighbor, in OSPF terminology, does not mean that one is also adjacent. Adjacency is a characteristic of one router interface on the subnet, called the designated router.

Election of designated routers

It probably would have been better if the OSPF specification called this function a "designated interface", but it did not. A given physical router, with four interfaces, could be have two of those interfaces designated, one acting as backup designated, and another as assuming another router on the subnet is designated.

The DR function applies only to broadcast-capable media, and, in specialized cases, on a nonbroadcast multiaccess medium (NBMA). On point-to-point media, the election is skipped and the two routers go directly to database synchronization.

For the immediate discussion, assume that the OSPF priority value for an interface is nonzero, which means it can take on a designated router role. When a router initializes, it listens for HELLO message. It may hear none, so, when a specific timer expires, it will send out a HELLO nominating itself as Backup Designated Router (DR). If it still hears no other router, it will promote itself Designated Router (DR), and zero out the BDR field.

If the new router hears a HELLO, and the DR field is nonzero, it accepts that value. If the BDR field is also nonzero, it accepts that as well. If none of the HELLO messages have a nonzero BDR, BDR (not DR) election takes place:

1. If the routers have different OSPF priority values, the highest nonzero value wins.
2. If the local router and one or more other routers all have the same priority, and none or higher, the router with the numerically highest router ID will claim the BDR role.

If, after another timer expires, no router has claimed DR, the BDR will promote itself to DR and a new BDR election will be held.