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, 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.

Goals

Students will be able to:

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.

Resources

Getting Started

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.

Image depicting arrangement of 8-student groups.

Activity

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?

Pro Tip


Activity Examples

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.




Pro Tip

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.

Mid-Simulation Reflection

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.

Possible Responses / Answers

Finish 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.

Pro Tip

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:

Pro Tip

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.

Wrap Up

Consider the relationship between our simulation today and the shortest path problem you worked on in the last lesson.

Assessment


Assessment Question 2 - Diagram

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.

Extended Learning

Standards Alignment