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 Dijkstras shortest path algorithm is to find the shortest route between two points through a series. To describe the operation of his algorithm in laymans 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:
This example helps demonstrate the reason behind the algorithms 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 protocolOpen 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. OSPF RFCsTo 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.
Before discussing the origins of the OSPF protocol, you should review some of its key characteristics. These characteristics and the protocols many labels will be the focus while reviewing the RFCs. The Open Shortest Path First protocol is also known by the following various definitions:
|