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, we explored how packets are sent through routers. The path that the packet follows, and how the router knows where to send it, however, has been largely untouched. This lesson simulates 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.
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.
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.
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 (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.
- Groups of Eight: This activity is designed for groups of 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. However, their information can still be learned and used by the other participants.
- 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 of the guides' letters, and the lesson will be much harder to facilitate if this not the case.
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 in the last lesson, a router wants to find the shortest path through the network to any possible location on the Internet. Unlike the algorithm from before, now 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?
- Watch the Activity Demo Video to see how the activity should work.
Use the diagram on the first page of the activity guide with these examples and update the table accordingly; make sure that you 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.
- 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.
- 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?
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.
Now that you have worked through the examples, complete three rounds of the activity. The rules of these rounds are as follows.
- Round 1: Talk to a router next to you.
- Round 2: Talk to a router across from you.
- Round 3: Talk to a router on the other side of you.
After the students have completed three rotations, they will have met all of their neighbors and should have at least one path to all other routers within their network. Have a quick discussion using the following three prompts.
- 1. Do you have a path to all other routers in your network? How do you know?
- 2. Is your path to each router the shortest or fastest route to that router? How can you be sure?
- 3. How many times will you have to meet with your neighbors in order to determine the shortest path to each router?
Possible Responses / Answers
- 1. 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.)
- 2. 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.
- 3. I also don't know this. All I can do is keep talking to my neighbors to see if information changes.
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.
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!
As you finish up the simulation, have students reflect on this 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?
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.
Consider the relationship between our simulation today and the shortest path problem you worked on in the last lesson.
- 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?
- 1. 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?
- 2. 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?
Teacher's Tip: Diagram Description
The network contains four nodes, "A," "B," "C," and "D," connected in a circular fashion, with no diagonals. A fifth node, "Z", is only connected to A. The cost of A-Z is 3, A-B is 2, B-C is 4, C-D is 5, and D-A is 3. A table is provided with cost information, titled Router A. The table has three columns labeled "Router," "Through Router B: Cost 2," and "Through Router D: Cost 3." The first row is "A," followed by two blanks (since there is no cost to get to router A from router A). Row 2 is "B," followed by "2" and "3+." Row 3 is "C," followed by "2+4=6," and "3+5=8." Lastly, Row 4 is "D," followed by "2+" and "3.
- Article: "Understanding routing tables"
- Discover your own routing tables by typing in the command prompt: netstat -rn
- CSTA K-12 Computer Science Standards: CD.L3A:8, CD.L3A:9, CD.L3B:4
- CSTA K-12 Computer Science Standards: CT.L3B:3, CT.L3B:4, CT.L3B:6
- Computer Science Principles: 4.1.2 (A, B, C)
- Computer Science Principles: 4.2.1 (A, B)
- Computer Science Principles: 4.2.4 (A, B, C, D, G)
- Computer Science Principles: 6.2.1 (D)
- Computer Science Principles: 6.2.2 (A, B)