8.0.1.2 Can Submarines Swim? (Instructor Version)
Instructor Note: Red font color or Gray highlights indicate text that appears in the instructor copy only.
Objectives
Explain the process by which link-state routers learn about other networks.
This modeling activity focuses students’ thoughts on the basic idea of using the shortest path to find the best network path for data communications.
Scenario
Edsger Wybe Dijkstra was a famous computer programmer and theoretical physicist. One of his most famous quotes was: “The question of whether computers can think is like the question of whether submarines can swim.” Dijkstra’s work has been applied, among other things, to routing protocols. He created the Shortest Path First (SPF) algorithm for network routing.
- Visit the Association for Computing Machinery’s (ACM) website at
http://amturing.acm.org/award_winners/dijkstra_1053701.cfm. Read the article about the life of Dijkstra. List five facts from the article you found interesting about him and his work. - Next, view Dijkstra’s animation of how to find the shortest path first located at
http://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif. While viewing the animation, pay close attention to what is occurring in it. Note three observations about the animation. - Lastly, view the graphic located at
http://upload.wikimedia.org/wikipedia/commons/3/37/Ricerca_operativa_percorso_minimo_01.gif. Take a few moments to view the visual and notate three observations you have made about the visual. (Note: Use a web translator if you do not know the Italian words “Casa” and “Ufficio”.)
Now, open the PDF provided with this activity and answer the reflection questions. Save your work. Get together with two of your classmates to compare your answers.
Resources
- Internet connection
- Internet browser
Reflection
1. List five facts you found interesting about Edsger Wybe Dijkstra’s life.
___________________________________________________
Answers will vary based on student preference after reading the site information. Some answers may include: Dijkstra was originally from the Netherlands. He was a computer programmer. His workforce title changed from programmer to theoretical physicist when he was denied a marriage license by the Netherlands. He worked for Burroughs Corporation. He spent 20 years of his life at the University of Texas/Austin in the Computer Science Department. It took only 20 minutes to develop the algorithm for shortest path first, this algorithm was based on a square diagram.
2. List three observations about the animation found at
http://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif.
____________________________________________________
Different paths are shown from source to destination. Numbers are shown to calculate path cost from one place to another. Some paths are shorter than others; therefore, finding the shortest path is key to find the shortest path from source to destination.
3. List three observations about the visual shown at
http://commons.wikimedia.org/wiki/File:Ricerca_operativa_percorso_minimo_01.gif.
____________________________________________________
Casa and Ufficio indicate source and destination locations on the diagram. Numbers are provided to indicate cost on each line to travel from source to destination. Some costs (when added) will be lower or higher than others when travelling from source to destination.
4. Distance vector routing protocols basically depend on number of hops to find the best route from source to destination. If you apply the information you learned from this introductory activity to routing, would hops be the main factor in finding the best path from source to destination? If compared to network communication, could it possibly be better to find the best path using a different metric than hop count? Justify your answer.
_____________________________________________________
Using the information found in this research activity, it appears that the metric of the path can vary from source to destination. Hop count can be used to find the best path for network communications, or a different metric can be used. Calculations can be based on numbers – these numbers can be added to find the best route from source to destination. Therefore, numbers or cost, instead of hops, can provide an alternative metric to finding the best path from source to destination.
Identify elements of the model that map to IT-related content:
- Routes
- Dijkstra
- Shortest path first
- Metrics