Open Shortest Path First

OSPF packet format

OSPF was designed as an interior gateway protocol (IGP), for use in an autonomous system such as a local area network (LAN). It implements Dijkstra's algorithm, also known as the shortest path first (SPF) algorithm. As a link-state routing protocol it was based on the link-state algorithm developed for the ARPANET in 1980 and the IS-IS routing protocol. OSPF was first standardized in 1989 as RFC 1131, which is now known as OSPF version 1. The development work for OSPF prior to its codification as open standard was undertaken largely by the Digital Equipment Corporation, which developed its own proprietary DECnet protocols.[3]

Routing protocols like OSPF calculate the shortest route to a destination through the network based on an algorithm. The first routing protocol that was widely implemented, the Routing Information Protocol (RIP), calculated the shortest route based on hops, that is the number of routers that an IP packet had to traverse to reach the destination host. RIP successfully implemented dynamic routing, where routing tables change if the network topology changes. But RIP did not adapt its routing according to changing network conditions, such as data-transfer rate. Demand grew for a dynamic routing protocol that could calculate the fastest route to a destination. OSPF was developed so that the shortest path through a network was calculated based on the cost of the route, taking into account bandwidth, delay and load.[4] Therefore, OSPF undertakes route cost calculation on the basis of link-cost parameters, which can be weighted by the administrator. OSPF was quickly adopted because it became known for reliably calculating routes through large and complex local area networks.[5]

As a link-state routing protocol, OSPF maintains link-state databases, which are really network topology maps, on every router on which it is implemented. The state of a given route in the network is the cost, and OSPF algorithm allows every router to calculate the cost of the routes to any given reachable destination.[6] Unless the administrator has made a configuration, the link cost of a path connected to a router is determined by the bit rate (1 Gbit/s, 10 Gbit/s, etc.) of the interface. A router interface with OSPF will then advertise its link cost to neighboring routers through multicast, known as the hello procedure.[7] All routers with OSPF implementation keep sending hello packets, and thus changes in the cost of their links become known to neighboring routers.[8] The information about the cost of a link, that is the speed of a point to point connection between two routers, is then cascaded through the network because OSPF routers advertise the information they receive from one neighboring router to all other neighboring routers. This process of flooding link state information through the network is known as synchronization. Based on this information, all routers with OSPF implementation continuously update their link state databases with information about the network topology and adjust their routing tables.[9]

An OSPF network can be structured, or subdivided, into routing areas to simplify administration and optimize traffic and resource utilization. Areas are identified by 32-bit numbers, expressed either simply in decimal, or often in the same dot-decimal notation used for IPv4 addresses. By convention, area 0 (zero), or 0.0.0.0, represents the core or backbone area of an OSPF network. While the identifications of other areas may be chosen at will; administrators often select the IP address of a main router in an area as the area identifier. Each additional area must have a connection to the OSPF backbone area. Such connections are maintained by an interconnecting router, known as an area border router (ABR). An ABR maintains separate link-state databases for each area it serves and maintains summarized routes for all areas in the network.

OSPF detects changes in the topology, such as link failures, and converges on a new loop-free routing structure within seconds.[10]

OSPF has become a popular dynamic routing protocol. Other commonly used dynamic routing protocols are the RIPv2 and the Border Gateway Protocol (BGP).[11] Today routers support at least one interior gateway protocol to advertise their routing tables within a local area network. Frequently implemented interior gateway protocols besides OSPF are RIPv2, IS-IS, and EIGRP (Enhanced Interior Gateway Routing Protocol).[12]

OSPF supports complex networks with multiple routers, including backup routers, to balance traffic load on multiple links to other subnets. Neighboring routers in the same broadcast domain or at each end of a point-to-point link communicate with each other via the OSPF protocol. Routers form adjacencies when they have detected each other. This detection is initiated when a router identifies itself in a Hello protocol packet. Upon acknowledgment, this establishes a two-way state and the most basic relationship. The routers in an Ethernet or Frame Relay network select a Designated Router (DR) and a Backup Designated Router (BDR) which act as a hub to reduce traffic between routers. OSPF uses both unicast and multicast transmission modes to send "Hello" packets and link-state updates.

As a link-state routing protocol, OSPF establishes and maintains neighbor relationships for exchanging routing updates with other routers. The neighbor relationship table is called an adjacency database. Two OSPF routers are neighbors if they are members of the same subnet and share the same area ID, subnet mask, timers and authentication. In essence, OSPF neighborship is a relationship between two routers that allow them to see and understand each other but nothing more. OSPF neighbors do not exchange any routing information – the only packets they exchange are Hello packets. OSPF adjacencies are formed between selected neighbors and allow them to exchange routing information. Two routers must first be neighbors and only then, can they become adjacent. Two routers become adjacent if at least one of them is Designated Router or Backup Designated Router (on multiaccess type networks), or they are interconnected by a point-to-point or point-to-multipoint network type. For forming a neighbor relationship between, the interfaces used to form the relationship must be in the same OSPF area. While an interface may be configured to belong to multiple areas, this is generally not practiced. When configured in a second area, an interface must be configured as a secondary interface.

An OSPF network can be divided into areas that are logical groupings of hosts and networks. An area includes its connecting router having interfaces connected to the network. Each area maintains a separate link-state database whose information may be summarized towards the rest of the network by the connecting router. Thus, the topology of an area is unknown outside the area. This reduces the routing traffic between parts of an autonomous system.

OSPF can handle thousands of routers with more a concern of reaching capacity of the forwarding information base (FIB) table when the network contains lots of routes and lower-end devices.[14] Modern low-end routers have a full gigabyte of RAM [15] which allows them to handle many routers in an area 0. Many resources[16] refer to OSPF guides from over 20 years ago where it was impressive to have 64 MB of RAM.

Areas are uniquely identified with 32-bit numbers. The area identifiers are commonly written in the dot-decimal notation, familiar from IPv4 addressing. However, they are not IP addresses and may duplicate, without conflict, any IPv4 address. The area identifiers for IPv6 implementations (OSPFv3) also use 32-bit identifiers written in the same notation. When dotted formatting is omitted, most implementations expand area 1 to the area identifier 0.0.0.1, but some have been known to expand it as 1.0.0.0.

OSPF defines several special area types:

OSPF defines the following overlapping categories of routers:

Internal router (IR)

An internal router has all its interfaces belonging to the same area.

Area border router (ABR)

An area border router is a router that connects one or more areas to the main backbone network. It is considered a member of all areas it is connected to. An ABR keeps multiple instances of the link-state database in memory, one for each area to which that router is connected.

Backbone router (BR)

A backbone router has an interface to the backbone area. Backbone routers may also be area routers, but do not have to be.

Autonomous system boundary router (ASBR)

An autonomous system boundary router is a router that is connected by using more than one routing protocol and that exchanges routing information with routers autonomous systems. ASBRs typically also run an exterior routing protocol (e.g., BGP), or use static routes, or both. An ASBR is used to distribute routes received from other, external ASs throughout its own autonomous system. An ASBR creates External LSAs for external addresses and floods them to all areas via ABR. Routers in other areas use ABRs as next hops to access external addresses. Then ABRs forward packets to the ASBR that announces the external addresses.

The router type is an attribute of an OSPF process. A given physical router may have one or more OSPF processes. For example, a router that is connected to more than one area, and which receives routes from a BGP process connected to another AS, is both an area border router and an autonomous system boundary router.

Each router has an identifier, customarily written in the dotted-decimal format (e.g., 1.2.3.4) of an IP address. This identifier must be established in every OSPF instance. If not explicitly configured, the highest logical IP address will be duplicated as the router identifier. However, since the router identifier is not an IP address, it does not have to be a part of any routable subnet in the network, and often isn't to avoid confusion.

In addition to the four router types, OSPF uses the terms designated router (DR) and backup designated router (BDR), which are attributes of a router interface.

Designated router

A designated router (DR) is the router interface elected among all routers on a particular multiaccess network segment, generally assumed to be broadcast multiaccess. Special techniques, often vendor-dependent, may be needed to support the DR function on non-broadcast multiaccess (NBMA) media. It is usually wise to configure the individual virtual circuits of an NBMA subnet as individual point-to-point lines; the techniques used are implementation-dependent.

Backup designated router

A backup designated router (BDR) is a router that becomes the designated router if the current designated router has a problem or fails. The BDR is the OSPF router with the second-highest priority at the time of the last election.

A given router can have some interfaces that are designated (DR) and others that are backup designated (BDR), and others that are non-designated. If no router is a DR or a BDR on a given subnet, the BDR is first elected, and then a second election is held for the DR.[1]^:75 The DR is elected based on the following default criteria:

• If the priority setting on an OSPF router is set to 0, that means it can NEVER become a DR or BDR.
• When a DR fails and the BDR takes over, there is another election to see who becomes the replacement BDR.
• The router sending the Hello packets with the highest priority wins the election.
• If two or more routers tie with the highest priority setting, the router sending the Hello with the highest RID (Router ID) wins. NOTE: a RID is the highest logical (loopback) IP address configured on a router, if no logical/loopback IP address is set then the router uses the highest IP address configured on its active interfaces (e.g. 192.168.0.1 would be higher than 10.1.1.2).
• Usually the router with the second-highest priority number becomes the BDR.
• The priority values range between 0 – 255,[21] with a higher value increasing its chances of becoming DR or BDR.
• If a higher priority OSPF router comes online after the election has taken place, it will not become DR or BDR until (at least) the DR and BDR fail.
• If the current DR 'goes down' the current BDR becomes the new DR and a new election takes place to find another BDR. If the new DR then 'goes down' and the original DR is now available, still previously chosen BDR will become DR.

DR's exist for the purpose of reducing network traffic by providing a source for routing updates. The DR maintains a complete topology table of the network and sends the updates to the other routers via multicast. All routers in a multi-access network segment will form a slave/master relationship with the DR. They will form adjacencies with the DR and BDR only. Every time a router sends an update, it sends it to the DR and BDR on the multicast address 224.0.0.6. The DR will then send the update out to all other routers in the area, to the multicast address 224.0.0.5. This way all the routers do not have to constantly update each other, and can rather get all their updates from a single source. The use of multicasting further reduces the network load. DRs and BDRs are always setup/elected on OSPF broadcast networks. DR's can also be elected on NBMA (Non-Broadcast Multi-Access) networks such as Frame Relay or ATM. DRs or BDRs are not elected on point-to-point links (such as a point-to-point WAN connection) because the two routers on either side of the link must become fully adjacent and the bandwidth between them cannot be further optimized. DR and non-DR routers evolve from 2-way to full adjacency relationships by exchanging DD, Request, and Update.

OSPF uses path cost as its basic routing metric, which was defined by the standard not to equate to any standard value such as speed, so the network designer could pick a metric important to the design. In practice, it is determined by comparing the speed of the interface to a reference-bandwidth for the OSPF process. The cost is determined by dividing the reference bandwidth by the interface speed (although the cost for any interface can be manually overridden). If a reference bandwidth is set to '10000', then a 10 Gbit/s link will have a cost of 1. Any speeds less than 1 are rounded up to 1.[22] Here is an example table that shows the routing metric or 'cost calculation' on a interface.

OSPF is a layer 3 protocol: if a layer 2 switch is between the two devices running OSPF, one side may negotiate a speed different than the other side. This can create an asymmetric routing on the link (Router 1 to Router 2 could cost '1' and the return path could cost '10'), which may lead to unintended consequences.

Metrics, however, are only directly comparable when of the same type. Four types of metrics are recognized. In decreasing preference, these types are (for example, an intra-area route is always preferred to an external route regardless of metric):

1. Intra-area
2. Inter-area
3. External Type 1, which includes both the external path cost and the sum of internal path costs to the ASBR that advertises the route,[23]
4. External Type 2, the value of which is solely that of the external path cost,

OSPF version 3 introduces modifications to the IPv4 implementation of the protocol.[2] Except for virtual links, all neighbor exchanges use IPv6 link-local addressing exclusively. The IPv6 protocol runs per link, rather than based on the subnet. All IP prefix information has been removed from the link-state advertisements and from the hello discovery packet making OSPFv3 essentially protocol-independent. Despite the expanded IP addressing to 128-bits in IPv6, area and router identifications are still based on 32-bit numbers.

In broadcast multiple-access networks, neighbor adjacency is formed dynamically using multicast hello packets to 224.0.0.5. A DR and BDR are elected normally, and function normally.

For non-broadcast multiple-access networks (NBMA), the following two official modes are defined:[1]

• non-broadcast
• point-to-multipoint

Cisco has defined the following three additional modes for OSPF in NBMA topologies:[26]

• point-to-multipoint non-broadcast
• broadcast
• point-to-point

• Allied Telesis implements OSPFv2 & OSPFv3 in Allied Ware Plus (AW+)
• Arista Networks implements OSPFv2 and OSPFv3
• BIRD implements both OSPFv2 and OSPFv3
• Cisco IOS
• Cisco Meraki
• D-Link implements OSPFv2 on Unified Services Router.
• Dell's FTOS implements OSPFv2 and OSPFv3
• ExtremeXOS
• GNU Zebra, a GPL routing suite for Unix-like systems supporting OSPF
• Juniper Junos
• NetWare implements OSPF in its Multi Protocol Routing module.
• OpenBSD includes OpenOSPFD, an OSPFv2 implementation.
• Quagga, a fork of GNU Zebra for Unix-like systems
• XORP, a routing suite implementing RFC2328 (OSPFv2) and RFC2740 (OSPFv3) for both IPv4 and IPv6
• Windows NT 4.0 Server, Windows 2000 Server and Windows Server 2003 implemented OSPFv2 in the Routing and Remote Access Service, although the functionality was removed in Windows Server 2008.

OSPF is a widely deployed routing protocol that can converge a network in a few seconds and guarantee loop-free paths. It has many features that allow the imposition of policies about the propagation of routes that it may be appropriate to keep local, for load sharing, and for selective route importing. IS-IS, in contrast, can be tuned for lower overhead in a stable network, the sort more common in ISP than enterprise networks. There are some historical accidents that made IS-IS the preferred IGP for ISPs, but ISPs today may well choose to use the features of the now-efficient implementations of OSPF,[27] after first considering the pros and cons of IS-IS in service provider environments.[28]

OSPF can provide better load-sharing on external links than other IGPs. When the default route to an ISP is injected into OSPF from multiple ASBRs as a Type I external route and the same external cost specified, other routers will go to the ASBR with the least path cost from its location. This can be tuned further by adjusting the external cost. If the default route from different ISPs is injected with different external costs, as a Type II external route, the lower-cost default becomes the primary exit and the higher-cost becomes the backup only.

The only real limiting factor that may compel major ISPs to select IS-IS over OSPF is if they have a network with more than 850 routers.

• Fabric Shortest Path First
• Mesh networking
• Route analytics
• Routing
• Shortest Path Bridging
• Shortest path problem

• Colton, Andrew (October 2003). OSPF for Cisco Routers. Rocket Science Press. ISBN 978-0972286213.
• Doyle, Jeff; Carroll, Jennifer (2005). Routing TCP/IP. 1 (2nd ed.). Cisco Press. ISBN 978-1-58705-202-6.
• Moy, John T. (1998). OSPF: Anatomy of an Internet Routing Protocol. Addison-Wesley. ISBN 978-0201634723.
• Parkhurst, William R. (2002). Cisco OSPF Command and Configuration Handbook. ISBN 978-1-58705-071-8.
• Basu, Anindya; Riecke, Jon (2001). "Stability issues in OSPF routing". Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications. pp. 225–236. CiteSeerX 10.1.1.99.6393. doi:10.1145/383059.383077. ISBN 978-1-58113-411-7. S2CID 7555753.
• Valadas, Rui (2019). OSPF and IS-IS: From Link State Routing Principles to Technologies. CRC Press. doi:10.1201/9780429027543. ISBN 9780429027543.

• IETF OSPF Working Group
• Cisco OSPF
• Cisco OSPF Areas and Virtual Links
• Summary of OSPF v2
• OSPF Router Startup Flow
• "Configuring OSPF Authentication". Tech Tips. Netcordia. Archived from the original on February 26, 2013.