Open Shortest Path First Protocol

Ron McCarty

In the March 2001 issue of Sys Admin, I covered the Routing Information Protocol (RIP). As discussed in that column, RIP is a distance-based protocol where each node advertises its complete routing table every 30 seconds. The distance is based on a maximum hop count of 15, where 16 represents infinity or a poisoned route that is to be dropped. The limited hop count, along with the practice of advertising the complete routing table, prevents RIP from being the protocol of choice for large networks.

Opens Shortest Path First (OSPF), on the other hand, is a link state protocol. A link state protocol advertises changes within the network, not the complete routing table. For example, consider the network shown in Figure 1. Using a link state protocol like OSPF, Router A tells Routers B and C that link A1 has failed. The state changes can immediately be sent when Router A notices that A1 has failed, for example, when the CRC errors become so high as to make the link unusable or when it loses its electronic signal. If RIP or another distance vector protocol were used, Router A would wait until its next update (in 30 seconds) to send out its routing table. The routing table would not include the route for path A1, and the change would "slowly" make its way through the network or "converge". OSPF's current version, version 2, is defined in RFC 2328, "OSPF Version 2".

Each OSPF node or router uses a link state advertisement (LSA) to tell other routers about link states it has received from other routers or neighbors through other LSAs and its own links to which it is directly connected. Because only changes are advertised, OSPF routers -- in addition to recognizing failures caused by physical or lower-level protocols -- must also have a mechanism for determining when an OSPF neighbor has failed. The mechanism used here is a Hello protocol, which is a subset of OSPF as defined in RFC 2328.

These link states are stored in a table within each router and referred to as link state databases.

Hello Protocol

The Hello protocol is dependent upon the type of network that connects the OSPF routers. On broadcast networks such as Ethernet and Token Ring, the router sends out a Hello protocol packet using the multicast address of 224.0.0.5 and 224.0.0.6.

On non-broadcast networks such as X.25, Frame Relay, or ATM, two methods can be used to send the Hello packets: either non-broadcast where all OSPF nodes are known, or point to multipoint where the router communicates with all routers to which it is directly connected. In these scenarios, the destination address of the Hello packet is the actual router's address.

The Hello packets are sent out to each interface, with one packet listing a minimum of one neighbor in the particular packet. There is no acknowledgement of the Hello packet; instead, the router will expect to receive a Hello packet with its own IP address listed as a neighbor address in a Hello packet from all of its neighbors.

In addition to the neighbor(s) listed in the packet, the packet also includes the designated router and the backup designated router. The designated router is the router on a broadcast network (such as Ethernet) that is responsible for the particular network so that not all routers within the network will advertise the links outside the broadcast network. (It is beyond the scope of this article, but OSPF also provides a quick convergence of a designated router failure using the backup designated router and new elections through the Hello protocol). OSPF also contains four other message types: database description packets, link state requests, link state updates, and link state acknowledgements.

The database description packets is used whenever nodes recognize each other as running OSPF. During the first communications (called creating adjacency), the nodes will transfer the contents of the link state tables. Additionally, link state requests, link state update, and link state acknowledgements are used by the protocol for received and acknowledging link state changes. Section 10.10 of RFC 2328 gives a detailed overview of routers creating adjacency.

Route Costs

One of OSPF's major benefits is its concept of costs for routes. RFC 2328 allows the administrator to specify cost; however, most organizations and vendors follow Cisco's lead and define the route as directly proportional to its bandwidth. (Remember, RIP only uses distance vector based on a count -- the protocol does not distinguish between a dial-up, 56-K line, and a 100-Mbit Ethernet.) This route cost is what determines the shortest path, hence the name Open Shortest Path First.

OSPF Topology

After an overview of the basics of OSPF, you might have recognized a weakness of OSPF -- scaling. With advertisements flooding immediately through the network, large networks could not have a router's failure consuming all available bandwidth as routing tables were updated and changes advertised; therefore, OSPF uses the concepts of areas to define smaller databases in the larger autonomous system. Figure 2 shows two areas with separate link-state databases. Each router within an area will have the same link-state database as the rest of the routers in the area; however, each of the routers within the area will have no state information on other areas within the complete autonomous system with the exceptions of routers connected to two areas. Such routers are aptly named "area border routers".

To support the scaling of areas, OSPF makes use of an OSPF backbone called Area 0 or 0.0.0.0. Area 0 contains all area border routers as shown in Figure 3. If area border routers are not directly connected, then they can be logically connected using OSPF virtual links. The virtual link simply defines the path for the OSPF protocol to travel. An area 0 using virtual paths is shown in Figure 4.

By dividing an OSPF network into areas, link-state databases are smaller and more manageable, which directly impacts the amount of bandwidth needed to advertise a change.

OSPF on Routers

The major router vendors support OSPF. Below follows a list of some additional resources for vendor-specific OSPF implementations. Keep in mind that most shops will tend to deploy all OSPF nodes on the same hardware, with an interoperability required at the area border router, if at all.

Juniper has several references, but is not a good starting point for OSPF:

http://www.juniper.net/techpubs/software/junos53/swconfig53-routing/html/ospf-config.html

http://www.juniper.net/techpubs/software/junos40/swcmdref40/html/ospf-monitor.html

http://www.riverstonenet.com/support/ospf_index.shtml

http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/ospf.htm
OSPF on UNIX

Zebra (http://www.zebra.org/) is an open source solution and commercial (http://www.ipinfusion.com/) offering that has a very Cisco-like user interface.

gated (http://www.nexthop.com/products/gated.shtml) is a commercial offering with roots in the original gated implementation found on most UNIX systems.

MRTd (http://www.mrtd.net/) or Multi-Threaded Routing Tool Kit is an open source solution funded by the National Science Foundation, but it has not received a lot of development or press lately.

A Linux implementation of OSPF to supplement the book OSPF Complete Implementation is available at: http://www.ospf.org/.

Ronald McCarty received his bachelor's degree in Computer and Information Systems at the University of Maryland's international campus at Schwaebisch Gmuend, Germany. He works for Sonus Networks as a senior systems engineer on a customer team responsible for a major telecommunications carrier. Ron is the co-author of New Rider's Linux Routing (http://www.linuxroutingbook.com/). He spends his free time with his two best friends in the world: his daughter, Janice, and his wife, Claudia. Ron can be reached at: ronald.mccarty@gte.net.