Open Shortest Path First

See also: OSPF for IPv6

Open Shortest Path First (OSPF) provides a means of automatically distributing routing information between various network devices (such as routers), in order to allow for computer networks to effectively "move packets around" so to speak. OSPF is one of a handful of protocols known as "dynamic routing protocols." This term is applied because several routers that interconnect several disparate networks can simply be "plugged into" one another and semi-automatically discover each others' networks and routes, without extremely specific and tedious configurations being done on each router in the network (such as what would be required with static routing). Minimal configuration is needed to tell the routers the criteria for connecting with another router. For example, two routers may be near one another, but are intended to be used at different levels of hierarchical routing and should not directly connect.

Note that this is less automatic than a self-organizing network, where the discovery is truly automatic unless explicitly blocked. Self-organizing networks are usually nonhierarchical (i.e., "flat"). Depending on the requirements, it may be desirable for some routers not to automatically interconnect, so independent routed networks can coexist for different applications.

OSPF is one of the two open (nonproprietary) and highly scalable interior routing protocols of the Internet (the other nonproprietary interior routing protocol being ISIS). Cisco's Enhanced Interior Gateway Routing Protocol is one example of a proprietary interior routing protocol - only Cisco gear can implement and use EIGRP. Partially for this reason OSPF has become a popular routing protocol, partially as a means of avoiding being "locked in" to Cisco equipment.

OSPF's principal specification is Internet RFC 2328. While it internally uses multicast addresses for some of its internal functions, its current specification only allows for routers to set up unicast route definitions.

OSPF is designed for hierarchical routing, from a set of nonzero "edge" areas, to a backbone area, forming what is called 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 similarity 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 Corporation'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.

Area types

The "backbone" is area 0.0.0.0, which is the only area ID of special significance.

Router types

Type	Relationship to backbone	Additional constraints
Backbone area	Is in the backbone; may connect to any number of nonzero areas and external interfaces	Carries all LSA types
Regular area	Can be a standalone area or connect to the backbone; may connect to external interface	Accepts all LSA types and can advertise all to the backbone; can be traversed by a virtual link
Stub area	Connects to backbone	Cannot have autonomous system border router (ASBR) or be traversed by virtual link. Accepts all inter-area links from the backbone, but only the default route as an external
Not-so-stubby area	Connects to backbone and one or more external interfaces	May have autonomous system border router (ASBR). Cannot have virtual link. Accepts all inter-area links from the backbone, but only the default route as an external. All external routes from the ASBR propagate in this area, and also are advertised to the backbone
Totally stubby area (Cisco proprietary extension)	Connects to backbone	Cannot have autonomous system border router (ASBR) or be traversed by virtual link. Accepts only the default route as an external; does not accept inter-area routes; advertises all its intra-area links to the backbone
Totally stubby and not-so-stubby area (Cisco proprietary extension)	One or more interfaces in one or more areas	Cannot have autonomous system border router (ASBR) or be traversed by virtual link. Accepts only the default route as an external; does not accept inter-area routes. All external routes from the ASBR propagate in this area, and also are advertised to the backbone.

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.

Topological definition of routers

Router types

Type	Interfaces in nonzero area	Interfaces in area 0.0.0.0	Additional constraints
Internal router	One or more interfaces in one or more	None	An interface routes only between routers in that area; if there were interfaces in area 0.0.0.1 and 0.0.0.2, this router would not route anything between them.
Backbone router	None	Two or more
Area border router	One or more interfaces in one or more areas	One or more
Autonomous system border router	One or more interfaces in one or more areas	One or more	One or more interfaces external to the OSPF domain

Functional definition of designated routers

Designated (DR), and backup designated routers (BDR), exist to reduce the amount of overhead traffic on multiaccess, multicast-capable media, such as local area networks. They are not relevant on point-to-point or nonbroadcast multiaccess links.

When any router on a subnet detects a change in a topological element it is monitoring, such as a subnet advertisement being withdrawn or initially advertised, it sends out that information as a multicast to the All Designated Routers (AllDRouters) group. Such a group is local to each subnet.

The group consists of the DR and BDR. As long as the BDR detects that the DR is active, the BDR passively shadows the DR's actions, but remains ready to take over.

When the DR receives an update, it compares it with its own database. The following discussion assumes that the LSA is more recent than anything in the DR's topological database (i.e., link state database).

The DR collects all new updates and periodically refreshes all other local routers. While all the timing mechanisms are beyond the scope of this article, although they are detailed in the RFC, think of the DR as trying to collect the batch of all recent updates, to be sent to all the other router when a fairly short, configurable timer expires.

When this timer expires, the DR sends a multicast, with all available new information, to the multicast group AllSPFRouters: all other OSPF speakers on the subnet. The DR expects each of those routers to send a multicast acknowledgement to allDRouters. If it does not hear an acknowledgement, it retransmits the update until either it receives an acknowledgement, or infers, from the lack of acknowledgements, that the individual router interface is no longer operating on the subnet. In the latter case, it includes, in its next multicast update, a withdrawal of that router link.

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 feature, 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.