Shortest Path First Protocol
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.
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 184.108.40.206 and 220.127.116.11.
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.
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.
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
Riverstone has a good OSPF starting page at:
Cisco Overview of OSPF:
OSPF on UNIX
OSPF is not as widespread on UNIX systems as RIP since OSPF will typically
be deployed in large IP networks with dedicated infrastructure staff
to support routers; however, OSPF is available and can be used where
host-based routing is used. There are several implementations, most
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