Optional Lesson: Algorithms Detour - How Routers Learn
Overview
This lesson is the last of the algorithm series. Building off of the previous lesson about shortest path algorithms, the activity in this lesson shows how routers learn about the rest of the Internet in order to route traffic so it takes the shortest path. In the previous lessons, students use the Internet Simulator to send packets to other students through simulated routers. The path that the packet follows, and how the router knows where to send it, however, has been largely untouched. Today, students simulate the process of a router joining a network and generating a router table that would allow them to send packets to anyone else in their network as efficiently as possible. They then reflect on the process by comparing the similarities between the SSSP problem and the process the used today, and how it facilitates the structure of the Internet.
Purpose
Routers, like many systems on the Internet, are governed by protocols. In order to determine where a packet should be sent so that it can reach its desired destination, the router uses a static or dynamic routing protocol such as Routing Information Protocol (RIP) or Open Shortest Path First (OSPF), which both create and maintain a routing table.
Routers are only able to communicate with their directly connected neighbors, so in order to generate an efficient table for sending packets they communicate with their neighbors, comparing who has the best way to reach a particular destination. As routers learn about more paths, they are able to share this information with their neighbors to help update and maintain their routing tables.
Agenda
Getting Started
Activity
Extended Learning
Wrap-up
Assessment
View on Code Studio
Objectives
Students will be able to:
- Describe how routers develop routing tables to determine how to send packets.
- Develop a router table to efficiently transmit packets from one destination to another across the Internet.
- Simulate the job of a router.
Preparation
- Print activity guides for each group. Even if there are fewer than 8 students in a group, all 8 router worksheets must be printed.
- Way to display the Network Diagram
- Classroom Setup: There is more significant classroom setup for this lesson. See directions in the Activity Guide.
- Chart paper and markers
Links
Heads Up! Please make a copy of any documents you plan to share with students.
For the Teachers
For the Students
- Simulation: How Routers Learn - Activity Guide
- How Routers Learn - Activity Demo - Video (download)
Teaching Guide
Getting Started
Setup: There is more significant work necessary to prepare the classroom for this lesson than most others. Students will need to be arranged in circles of eight, with each one being given a 2-page section of the Activity Guide - Simulation: How Routers Learn (lettered A-H). Activity guides must be handed out in alphabetical order, as shown in the diagram below. It may make sense to have these waiting at seats when students arrive at class. The dotted lines in the diagram indicate who each person is allowed to exchange information with during the activity; they represent direct connections between routers. If you wish, you may indicate these connections with string, masking tape, etc.
Teaching Tips
Importance of Order: If tables are immobile, it is sufficient to create circles of chairs. This activity relies on each student communicating with a specific set of individuals. The activity guides are designed with the assumption that students will be sitting in alphabetical order, and the lesson will be much harder to facilitate if this not the case.
Groups of Eight: This activity has been designed with eight routers, because that’s enough to make the shortest paths between nodes interesting and to give students an idea of the kind of interactions that routers have. Using the current set of routers and costs, all students will find that there is a more efficient route between themselves and one of their neighbors than through the direct connection. With smaller groups, these connections are much more subtle to the student.
Class Not Divisible by Eight: Even if the class is not divisible by eight, set up groups of eight. The empty space(s) should be occupied by “static” (unchanging) routers. Lay out the worksheets for the missing routers in the empty spaces. Students can look at the sheets to get information from the missing routers, but obviously the missing routers’ tables will never be updated. You can say that these routers are ”static” because they will never learn anything. Their information can still be learned and used by the other participants.
Activity
Introduction: How does a router learn which way to route packets?
Say: A router is connected to a few other routers but the Internet is much bigger. If a packet is supposed to get to destination X, but the router is only connected to other routers A, B, and C, how do you know which one you should forward the packet to in order to reach X as fast as possible? There might be a lot of Internet between you, your neighbors, and X. Even though the cost or distance to your neighbor B might be the greatest of your other neighbors, you can’t know what lies beyond B. It might be the best way to send traffic to X, but how can you know?
Like the problems we considered yesterday, a router wants to find the shortest path through the network to any possible location on the Internet. Unlike the algorithm from yesterday, today we recognize that a router cannot see how the entire network is connected ahead of time. Not only is this not possible because the Internet is too big, but also the network changes all the time, new routers come online, cables get cut accidentally, etc. Instead, a router can only observe traffic between it and its direct connections. The question, then, is how can a router learn about the network in order to optimally route packets?
Distribute Activity Guide.
Distribute Activity Guide - Simulation: How Routers Learn (if you have not done so already). Again, make sure students are in circles of 8 and handed their worksheets in alphabetical order, going around the circle. If some groups don’t have 8 members, distribute worksheets for those routers anyway. (See Teaching Tip above about groups that have fewer than 8 people.)
Students should read through the description of the activity, the goal, and the example on the first page; you can do this as a class, individually, or in pairs.
(Optional) Show Activity Demo video.
Show How Routers Learn - Activity Demo - Video to the class to see a demonstration of the conversation that will happen during each round of the activity, and how students will use the worksheet.
Teaching Tips
Misconception Alert: The activity in this lesson addresses a different problem from the one that appears in The Muddy City activity of the Exploring Computer Science curriculum.
When presenting the activity, make sure students are clear what problem they are solving. In this simulation they are not actually routing traffic, but learning which paths would be fastest to use if they were to route traffic. This same process is carried out by real routers at the same time as they do the work of routing packets.
Using the Routing Table.
Students will likely need some help learning to use the routing table diagram on the activity guide.
Below are a few examples that you can walk the class through to make sure that students are clear on what is supposed to happen.
Use the diagram on the first page of the activity guide with these examples and have students update the table accordingly; make sure that students understand what to do after each example.
Example 1:
- Let’s say you are router X, you are connected to routers Q, S and W, and you are now talking to router S.
- You would ask S, “Do you have a path to Q?”
- S responds “Yes, I have a path to Q. The best one has a cost of 3.”
- Update your routing table diagram to reflect what S just told you.
Give students a few seconds to update the example table on the front page of their handout. The updated information is marked in red on the diagram to the right.
Example 2:
- Then S asks you, “Do you have a path to Q?”
- How should you respond?
- Correct response: “My best path to Q has a cost of 2.”
- Explanation: If you read across the row for Q in your chart, it tells you about all the ways you know to get to Q and how much each one costs. Looking at your table right now, you know about two paths to Q. (One goes through S with a cost of 7, the other is your direct connection to Q with a cost of 2.) Of these two, the direct path is the best one available to you, so you report to S, “I can get to Q, and my best path costs 2.”
Example 3:
- Later on, after exchanging information about all the other nodes, you end up looking at paths to W.
- S asks you, “What’s your best path to W?”
- How should you respond?
- Correct response: “My best path to W has a cost of 7.”
- Then S says, “Well, I can get to W with a cost of 2.”
- Update your table to reflect this information. (See diagram to right.)
- Wait a second...now you have a new best path to W! You could tell S: “Wait! my new best path has a cost of 6.”
- Explanation: You might think it’s weird that you’re just reporting back to S effectively what she just told you. But it’s OK, because you only need to worry about your own table and reporting the best path you currently have, and the best path you have to W now has a cost of 6.
Example 4:
- Later on, you might talk to S again, and start going through best paths.
- What if S says, “My best path to Q is 1”? How should you update your diagram?
A possible solution is shown to the right. S’s path has improved since you last exchanged information. So cross out what was there before and write the new info.
Creating Pairs: Once students have clarity on the instructions, start the activity. Information exchange will happen in several rounds. Each round, every student should have a partner to talk to.
Round 1: Talk to an elbow partner. Round 2: Talk to the person you are connected to on the other side of the circle. Round 3: Talk to the other elbow partner.
For Round 1, have students identify the first person they will talk to; it should be an elbow partner, and everyone should have someone to talk to. Students will cycle through these pairings multiple times. Below is a diagram that shows a possible way for the pairings to go.
Once the first round gets going, you might have to encourage or tell students to move onto the next partner, but different pairings will take different amounts of time to process all the information. It’s OK if pairings happen organically after the first round. Just ensure that students (routers) only talk to the students (routers) they are directly connected to.
Mid-Simulation Reflection.
After the students have completed three rotations, they will have met all of their neighbors and will have at least one path to all other routers within their network. Have a quick discussion:
| Prompt | Possible responses / answers |
|---|---|
| Do you have a path to all other routers in your network? How do you know? | For every possible destination (A-H), I should know at least one way to route traffic to it. (If I don’t, it’s because I haven’t met with one of my neighbors yet, or I forgot to record something in my table.) |
| Is your path to each router the shortest or fastest route to that router? How can you be sure? | It might be, but I don’t know yet. If I keep talking to my neighbors, they might know paths that they didn’t know the last time, or existing paths might have improved. |
| How many times will you have to meet with your neighbors in order to determine the shortest path to each router? | I also don’t know this. All I can do is keep talking to my neighbors to see if information changes. |
Continue the Simulation.
After 5 or 6 meetings with neighbors, each student should have found the shortest paths to all of the other routers. Once things seem to stop changing, you can stop and move on.
Share the Network.
- Bring all the students back together.
- Display the Network Diagram for the whole class to look at.
- Say: We are going to look at the diagram of the whole network. As routers you would not be able to know this. We are using the network and your routing table check to see if you were able to find the shortest routing path without being able to see the network.
Prompt:
- What is the shortest path from C to B? Look at the diagram and consult your routing tables. If a packet started at C and needed to get to B, which router would C pass it to? Once it got there, where would it go next? and so on. If you all followed your routing tables, would it take the shortest path to get to B?
- Say: Notice that as routers you never saw the whole network, but you were able to learn the best ways to get to other routers . You didn't even need to know who was connected to whom! You just needed to ask your neighbors if they had a path and how long it took. So routers don't actually need see a picture of the whole internet in order to know the best way to route packets.
You can repeat this with other nodes if you want to continue to check.
Teaching Tips
All groups may not have the shortest paths reflected in their routing tables because they didn’t get through enough rounds of information exchange, or because the order in which they talked to people didn’t allow the information to be disseminated as quickly. This is OK.
Extended Learning
- Article: “Understanding routing tables”: http://www.techrepublic.com/article/understanding-routing-tables/
- Send students to discover their own routing tables by typing in the command prompt: netstat -rn
Wrap-up
(Also in Code Studio.)
Say: Consider the relationship between our simulation today and the shortest path problem you worked on last class period.
Prompts:
- Why does a router keep track of the cost to a destination through multiple routers, instead of only the fastest one?
- How is creating a router table similar to finding the shortest path in a graph? How is it different?
- Why do routers store information about neighbors and costs, rather than the whole path from themselves to another router?
Assessment
Questions (also in Code Studio):
-
In this activity, you filled in a routing table by visiting other routers you were directly connected to find out what paths they had. Why do routers need to use this method of talking to their direct neighbors in order to fill in their routing tables?
-
Here is a new router network. You’re router Z, and you just joined this network, and router A is showing you its table, which is shown below. Based on your current knowledge as router Z, what is the cost of the most efficient way to send traffic to router C?
- Lesson Overview
- Student Overview
- Internet Simulator: Sending Binary Messages
- Student Overview
Coordination and Binary Messages Activity
Develop your Protocol Develop a protocol that allows you to use Internet Simulator to relay a message, i.e. one member sends a message and the other member sends the same message back. You or a teacher will say “Go” to begin the exchange but otherwise all communication must be through the widget. As you’re working, consider:
- How will you know when the exchange is supposed to begin?
- How will you know whose turn it is to send or receive the message?
- How will you coordinate your actions?
Document your protocol on the worksheet provided, and test your protocol using the Internet Simulator
- The Internet: Wires, Cables, and Wifi_2018
- Teacher Overview
- Student Overview
One of the goals of this lesson is to help students understand why binary is important. This video about the Internet was created for the Code.org Computer Science Principles course. The video could be used to help motivate why binary is important in computer science.
Teaching Tip
The answer is AABB. If person 1 is setting the wire at a rate of one bit every 2 seconds, and person 2 is reading once per second you can look at the timeline...
person 1(set) A---------B---------A--------B person 2(read) ^----^----^----^----
You can see person 2 is going to read the wire twice while A is still on the wire.
Student Instructions
A binary message consisting of four bits was sent to you by a friend. The message was supposed to be ABAB. Unfortunately, your friend set the bit on the wire once every 2 seconds, but you read the wire once every second. Assuming that the first bit was sent and read at the same time, what message did you receive instead?
Student Instructions
Student Instructions
A binary message was recorded as a wave as shown in the image below. Can you decode the message? Explain what information you would need in order to successfully decode the message into A’s and B’s.
Student Instructions
Standards Alignment
View full course alignment
CSTA K-12 Computer Science Standards (2011)
CD - Computers & Communication Devices
- CD.L3A:8 - Explain the basic components of computer networks (e.g., servers, file protection, routing, spoolers and queues, shared resources, and fault-tolerance).
- CD.L3A:9 - Describe how the Internet facilitates global communication.
- CD.L3B:4 - Describe the issues that impact network functionality (e.g., latency, bandwidth, firewalls, server capability).
CT - Computational Thinking
- CT.L3B:3 - Critically examine classical algorithms and implement an original algorithm.
- CT.L3B:4 - Evaluate algorithms by their efficiency, correctness, and clarity.
- CT.L3B:6 - Compare and contrast simple data structures and their uses (e.g., arrays and lists).
Computer Science Principles
4.1 - Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages.
4.1.2 - Express an algorithm in a language. [P5]
- 4.1.2A - Languages for algorithms include natural language, pseudocode, and visual and textual programming languages.
- 4.1.2B - Natural language and pseudocode describe algorithms so that humans can understand them.
- 4.1.2C - Algorithms described in programming languages can be executed on a computer.
4.2 - Algorithms can solve many but not all computational problems.
4.2.1 - Explain the difference between algorithms that run in a reasonable time and those that do not run in a reasonable time. [P1]
- 4.2.1A - Many problems can be solved in a reasonable time.
- 4.2.1B - Reasonable time means that as the input size grows, the number of steps the algorithm takes is proportional to the square (or cube, fourth power, fifth power, etc.) of the size of the input.
4.2.4 - Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity. [P4]
- 4.2.4A - Determining an algorithm’s efficiency is done by reasoning formally or mathematically about the algorithm.
- 4.2.4B - Empirical analysis of an algorithm is done by implementing the algorithm and running it on different inputs.
- 4.2.4C - The correctness of an algorithm is determined by reasoning formally or mathematically about the algorithm, not by testing an implementation of the algorithm.
- 4.2.4D - Different correct algorithms for the same problem can have different efficiencies.
- 4.2.4G - Efficiency includes both execution time and memory usage.
6.2 - Characteristics of the Internet influence the systems built on it.
6.2.1 - Explain characteristics of the Internet and the systems built on it. [P5]
- 6.2.1D - Routing on the Internet is fault tolerant and redundant.
6.2.2 - Explain how the characteristics of the Internet influence the systems built on it. [P4]
- 6.2.2A - Hierarchy and redundancy help systems scale.
- 6.2.2B - The redundancy of routing (i.e., more than one way to route data) between two points on the Internet increases the reliability of the Internet and helps it scale to more devices and more people.