Open Shortest Path First

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.

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.

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