Understanding Selecting Network Protocols

Previous Table of Contents Next

His most remembered contribution to the computer world is his algorithms, specifically the shortest path algorithm. Dijkstra did not consider his algorithm very remarkable at the time, and many years passed before he published it. Today, his algorithm is being applied to road building, routing of communications, and the airline industry. His algorithm was even altered slightly to determine the most inexpensive way to wire a computer. The goal of what has commonly become known as the Dijkstra algorithm is to find the shortest route between two points.

There are quite a few more resources available to you on this subject. If you require further information, I suggest you reference the following Web sites:

    http://students.ceid.upatras.gr/-papagel/project/kef5_7_1.htm    http://cda.mrs.umn.edu/-englinjm/EWD.html    http://www.ctc.dcu.ie/ctcweb/courses/heuristics/course/dij.html    http://www.geekchic.com/repliq5.htm    http://www.cbi.umn.edu/inv/burros/ewddocs.htm 

The goal of Edsger Dijkstra’s shortest path algorithm is to find the shortest route between two points through a series. To describe the operation of his algorithm in layman’s terms, look at the following example. Suppose you are trying to find the shortest path between two cities: Atlanta and Boston (a core set of routers). The purpose in this example is to determine the minimum time needed to drive to every city (routers) in an ever-expanding core of cities (network). The sequence to find this minimum time value is as follows:

1.  Begin in the city of origin (router). The time (distance) needed to reach this city is, of course, zero because it is your origin.
2.  Then you discover a new city, which you will call city X (router), that you wish to reach.
If the time to drive (distance) to city X is shorter than the time to drive to any other city outside the core set.
If the time to drive to city X is the minimum time to drive to city Y in the core set from Atlanta, plus the time to drive from Y to X.
3.  Then add city X to the core set (network), and record the time (distance) computed.
4.  If it is a city named Boston then you are done, if not, repeat.

This example helps demonstrate the reason behind the algorithm’s name. Another important factor in its operation is how SPF converges. Essentially, it will converge in 0(M.log M) iterations, where M is the number of links. This is far superior to the Bellman-Ford algorithm, which converges in 0(N.M) iterations where N, is the number of nodes.

These characteristics and because the specification was developed in an open fashion by the IETF explains the name of the OSPF protocol—“Open Shortest Path First.” Also, the OSPF protocol is an open standard that allows the publication of all data relating to its design and function. This information has been published in a series of RFCs.


To properly reference the technical documents used in the design and evolution of OSPF, each of them will be briefly discussed in chronological order. The following is a list of the Request for Comments (RFCs) that have been published by the IETF relating to the OSPF protocol. Each RFC will contain a brief summary of its contents and purpose. Furthermore, the tracking of the RFC evolution will include information on which are current and which have been made obsolete. This will enable the reader to understand where they should go for additional reading, as further discussion is beyond the scope of this book. Figure 4-1 provides a timeline of the development and evolution of OSPF.

Figure 4-1  OSPF evolution timeline.

  RFC 1131: OSPF Specification Version 1 (J. Moy, Oct. 1989)
  RFC 1245: OSPF Protocol Analysis (J. Moy, July 1991)
  RFC 1246: Experience with the OSPF Protocol (J. Moy, July 1991)
  RFC 1247: OSPF Version 2 [obsoletes 1131] (J. Moy, July 1991)
  RFC 1248: OSPF Version 2 Management Information Base (F. Baker & R. Coltun, July 1991)
  RFC 1252: OSPF Version 2 Management Information Base [obsoletes 1248] (F. Baker & R. Coltun, July 1991)
  RFC 1253: OSPF Version 2 Management Information Base [obsoletes 1252] (F. Baker & R. Coltun, Aug. 1991)
  RFC 1364: BGP OSPF Interaction [obsoletes 1247 & 1267] (K. Varadhan, Sept. 1992; IAB; L. Chapin, Oct. 1992)
  RFC 1371: Choosing a &Common IGP& for the IP Internet (IESG; P. Gross, Oct. 1992)
  RFC 1403: BGP OSPF Interaction [obsoletes 1364] (K. Varadhan, Jan. 1993)
  RFC 1583: OSPF Version 2 [obsoletes RFC1247] (J. Moy, March 1994)
  RFC 1584: Multicast Extensions to OSPF (J. Moy, March 1994)
  RFC 1585: MOSPF: Analysis and Experience (J. Moy, March 1994)
  RFC 1586: Guidelines For Running OSPF Over Frame Relay Networks (O. deSouza & M. Rodriguez, March 1994)
  RFC 1587: The OSPF NSSA Option (V. Fuller & R. Coltun, March 1994)
  RFC 1745: BGP4/IDRP for IP-OSPF Interaction (K. Varadhan, S. Hares, Y. Rekhter, Dec 94)
  RFC 1765: OSPF Database Overflow (J. Moy, March 1995)
  RFC 1793: Extending OSPF to Support Demand Circuits (J. Moy, April 1995)
  RFC 1850: OSPF Version 2 Management Information Base [obsoletes 1253] (F. Baker & R. Coltun, Nov. 1995)
  RFC 2178: OSPF Version 2 [obsoletes 1583] (J. Moy, July 1997)
  RFC 2328: OSPF Version 2 [obsoletes 2178] (J. Moy, April 1998)

Before discussing the origins of the OSPF protocol, you should review some of its key characteristics. These characteristics and the protocol’s many labels will be the focus while reviewing the RFCs.

The Open Shortest Path First protocol is also known by the following various definitions:

  Link-state routing protocol
  Shortest path first (SPF) protocol
  Interior gateway protocol
  Distributed routing protocol

Previous Table of Contents Next

OSPF Network Design Solutions
OSPF Network Design Solutions
ISBN: 1578700469
EAN: 2147483647
Year: 1998
Pages: 200
Authors: Tom Thomas

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net