How the Internet Works - Part II - The Phone System

[This is the second in a 4-part post that describes an activity to demonstrate how the internet works. This part contains an introduction and a description of how the (landline) phone system works.]

Some notes on presentation:

This document presents the activity as a rough script. For this activity, you will be presenting information and directing the students as they act out the various parts of the internet.

You shouldn't just read from this script verbatim (since that will be rather dull), but you will probably want to have this printed out with you while you're presenting. Use a highlighter and mark key points so that you can find them easily while presenting.

Feel free to include additional information if you feel like it and accept questions and ad lib to follow the class interest. Throughout the script, there are a number of questions for the students that can be used to make the presentation more interactive.

The files for this part of the activity (routing tables and labels) can be downloaded from www.cse4k12.org/internet/how-internet-works.html.

Introduction

What is the internet? Basically, the internet is just an interconnected collection (a "network") of computers throughout the world. The interesting part of the internet is how the computers are connected with each other. It's easy to connect a small number of computers to each other, but the internet consists of millions of computers.

In order to understand how the internet works (i.e., how these millions of computers interact with each other), it's useful to start with a networking system that you're already (somewhat) familiar with and then compare that system to the internet.

So, let start with a discussion of the phone system.

(Note, we're talking about traditional landline phones here. Cellular phones are different beasts and we don't cover them.)

Phone system

Let's say you want to call someone on the telephone. What do you do?

You somehow get their phone number and dial it. Then the phone system finds the target phone and makes it ring.

This raises 2 questions:

1. How do you know which number is associated with the person you want to call?
2. How does the phone system use the number to find the target phone for that person?

(#1) So, how do you know the phone number?

Well, you ask someone. Either the person you want to call (if they're around), or a mutual friend (if there are any). You can also try the phone book, but people might be unlisted or listed under a different name (like their parent's name).

In addition, when using a phone book that covers an entire city, multiple people might have the same name - what do you do then? You may only know one person named “John Smith”, but there may be a dozen people with the same name in a single city. The phone system uses phone numbers instead of names to avoid this problem.

So, once you get the phone number, you probably write it in your personal address book so that you don't forget it. This address book provides a mapping from “name” to “phone number” for you. Once you write a number in your address book, you don't have to ask around or search for that number again.

ACTION (optional) : Show a small personal address book.

The point of showing this object is to emphasize that each person typically keeps track of a relatively small number of people/phone numbers. Larger phone books will be shown later for comparison.

But what happens if the person moves and gets a new phone number? Well, if they remember, they tell you the new number. But if they don't contact you, then you will still have this old, obsolete number that no longer connects you to that person.

(This is a great way to discover if someone is still your friend ^_^)

(#2) How does the phone system connect calls?

Like most automated systems, the phone system works with numbers.

In this case, you give the telephone system the telephone number it needs to identify the target phone. It then uses this number to set a bunch of switches to make the complete connection.

The exact details of this routing are complex and have evolved considerably over time. In the early days of the phone system, there was a person who manually connected the calls using a plugboard. Nowadays, there are computerized systems that handle the connection automatically.

What we'll do here is present a greatly simplified system that is intended to give a general overview of how this switching works:

ACTION: Assign students and add labels to the nodes in the network graph:

1, 2, 3 : These are switches. No need for labels, but they should be referred to as switches during this part of the activity.
4 : Area code "206" – The next 3 are also switches, but it's convenient to refer to them as "area codes" or "local switches".
5 : Area code "212"
6 : Area code "425" – Only a label is needed here. No need to assign a student to this node since there is nothing for them to do.
7 : "you : (206) 555-1000"
8 : “neighbor : (206) 555-2000”
9 : "friend : (212) 555-3000”

You will need 9 students total: 8 students for the nodes (1-5 & 7-9) plus an additional student to act as a "runner" to help you make the phone connection.

Depending on how everyone is arranged, you may want to have the students sitting down at each node so that everyone can see what's going on. Have them stand up only when they are an active part of the demonstration.

Feel free to change the area codes and numbers, but make sure that you keep the labels consistent with the switching tables.

Each of these nodes has a "switching table" that tells it how to connect phone calls. Simply look up the phone number in the table and it will tell you which link to connect the call to. There's a primary and a secondary column - we're only going to use the primary column for now.

ACTION: Hand out the printed switching tables to the students in nodes 1-5. Node 6 also has a switching table, but it is not used in this exercise so it can be placed on the ground by node 6. This table can be used to extend the exercise if desired.

So, let's pretend that "you" are located in area code "206" and your phone number is "555-1000". If you want to call your neighbor at "555-2000" in the same area code, you simply dial your neighbor's phone number and your request is sent to the local phone company.

ACTION: Using a rope, have the "runner" student start from the "you" node and travel along the "Aa" link to the “206” switch. The rope should trail behind the runner so that it maintains a connection back to the "you" node. The student at the "you" node should pay out the rope as the runner walks away.

When the phone company gets the request, it uses the phone number and the switching table to connect the call.

ACTION: The runner student should approach the "206" node and ask to be connected to "555-2000". The student at the "206" node should look up this number in the switching table and direct the runner down the "Bb" link.

The runner should give a part of the rope for the 206 node to hold and then continue down the "Bb" link. When the runner reaches the destination, the rope should form a connection from the start (“you”) to the end (“neighbor”) nodes through the “206” switch.

Even if you want to call your friend who lives far away in a different area code (212-555-3000), the process is the same: you simply dial the number. The "206" node recognizes that it needs to send this to a different area code when it looks at the switching table.

ACTION: Reset the rope from the previous part and have the runner go back to the "you" node.

Have the runner start again, this time asking to be connected to "(212) 555-3000". As before, have the rope trail out behind the runner and have each visited node hold onto the rope and let it slide through their hand.

The "206" node directs the call down the "Dd" link to switch "1".

ACTION: For each of these connections, have the runner walk from the one node to the next along the path indicated by the switching table. As the runner gets to each node, they need to ask the node where to go next.

Switch "1" directs the call down the "Ii" link to area code "212".

And the "212" node sends the call down the "Pp" link to the friend's phone.

ACTION: At this point the rope should run from "you" (node 7) to "friend" (node 9) going through area code "206" to switch "1" and area code "212".

But what happens if one of the links or if an entire switch goes away?

ACTION: Disable the "Dd" link by "cutting" it. You can actually cut the rope to be dramatic, but it suffices to simply pretend.

What happens? You get "cut off" and the connection is dropped.

If you want, you can call back. And you might get the same connection path if the problem has been fixed. But if the problem has not yet been fixed, you'd like the call to be directed around the problem. For this reason, the switches typically have a primary/secondary path. If there's a problem with the primary path, it uses the secondary.

Let's assume that the problem has not been fixed. Now if you call back, you get a new path around the problem and your call will go through.

ACTION: Reset and start the call over again. Stand in the middle of the "Dd" link as a reminder that it is currently not working.

Now when the "206" node tries to connect the call through the "Dd" link, it fails and it needs to rely on the secondary path "Ee" which leads to switch "2".

Switch "2" sends the call down "Gg" to switch "1".

Where it continues, as before, down the "Ii" link to area code "212" and then down the "Pp" link to the friend's phone.


Notice how the connection is directed around the damaged part of the network. What happens if there is more damage to the network, for example, if the "Gg" link is also disabled? What happens if the entire switch "1" is broken?

ACTION: Remove other links/switches and see how the phone connection is directed around the damage. Have the students experiment with damaging the network. Which nodes are critical to making the connection? How much damage can this network sustain and still be able to connect the phone call?

So that is a (greatly) simplified view of how the phone system connects phone calls. But you may recall that the point of this activity is to demonstrate how the internet works, so we'll get to that in the next part.

[to be continued in Part III]

School presentation for CS Education Week

Since last week was Computer Science Education Week, I spent some time at my daughter's new school to give a short presentation about computer science and engineering.

It was an eclectic mix of topics/activities:

• They had to find all the computers in the classroom. That is, find all the items that had computers/microprocessors inside them, so it included the printers, microwave ovens, CD players, cell phones and TVs in addition to the obvious desktop computers.
• I took apart an old GBA and identified the various components. Also, I put it back together afterwards to verify that it still worked!
• We discussed the logic needed to control a character in a simple platforming video game - how to move the character when the player presses the buttons on the control pad.
• Demonstrated some small electronics projects that show how a single bit of memory is stored.
• Passed around an 8" wafer from Intel. These are really neat to look at - and one of the students had a parent working at Intel but had never seen a wafer.

And finally, I had them get into groups of 3 and do the How Computers Work activity. And that's where things got a bit interesting.

Competition

There were 6 students - 3 boys and 3 girls - and they naturally divided themselves into a group of boys and a group of girls.

While handing out the papers for the activity, one of the boys suggested that it should be a competition to see who would finish first. I watched to see the reaction of the students - the girls (and perhaps the other boys as well) didn't seem to be interested, and the one who suggested it moved on and didn't push for it.

I realized how easy it would have been for me to encourage this competition - I would be reacting to a student's request and that's usually an appropriate thing to do as an instructor. But it also would have partially alienated some of the students who did not want to be part of a competition. At the very least, it would have made it more stressful for them to participate. It made me wonder how many times in the past I had inadvertently done something similar and made things more difficult for some of the students.

Knowing what I know now about learning differences between girls/boys (and students in general), I would have stopped the competition anyway by pointing out that the two teams had different (albeit comparable) "programs" so a timed competition wouldn't really be fair. But I was relieved that the topic went away on its own.

Starting early

The other aspect that was interesting was that as the boys were forming their group, they discussed all the computer/technology stuff they had done before: The computer camps they went to, the programs they had written, the robot they helped build, and so on.

This sort of conversation did not happen with the girls team.

One comment from a boy struck me. I can't remember the exact quote and when I replay my best recollection it seems harsher now than it did at the time (so I'm sure I have the quote wrong somewhat). But the comment was something like: "the girls aren't interested in computers" or "they don't know much about programming, except for GirlX". GirlX being my daughter, the only one that apparently had been exposed to computer programming beforehand.

So, by 7th grade, the majority of boys (in this admittedly very small sample) had already gone to a computer camp of some sort whereas none of the girls had. Some of them had already formed their view of what was interesting to boys vs. girls.

So now I wonder,

• Is 7th grade too late to start introducing computer programming in the classroom?
• Is this related to boys tendency to brag and overstate accomplishments vs. girls tendency to understate?
• What are the parents' roles in this? Did they offer computer/math camp to their daughters? Should they have? My assumption is that most parents follow the natural interests of their children, so they will look for camps that their children have already expressed an interest in.

I have been working on the assumption that 6th through 8th grade was the critical period to introduce programming, with pre-programming skills (binary, logic, ...) taught in 3rd through 5th grade. But I also assumed that starting anytime in 6-8th grade would be OK, even if it could have been started earlier.

After this, I'm wondering if the first introductory programming class really needs to be before middle school starts.

How the Internet Works (activity for elementary/middle school)

The post is the first installment of a "How the Internet Works" activity which is suitable for upper-elementary and middle school students.

I've been running this activity for the past year or so and have been promising to write it up for a while. With Computer Science Education Week happening this week, it seems like the perfect opportunity to get my act together.

I'll be posting this activity in 4 separate parts:

(1) Overview and setting up
(2) The phone system (switching network)
(3) The internet (routing network)
(4) DNS (Domain Name Server)

Overview

This activity is an interactive demonstration of what happens when you type a URL into a browser.

In this activity the students will be guided to act out the various parts of the internet: websites, routers, name servers, ISPs and home computers. In this activity, students will:

• Learn the difference between a switching (phone system) and routing (internet) network
• See how packets are routed through the internet
• See how the internet routes around damage
• See how domain name servers are used to lookup an IP address

It is designed for 8-13 students, but fewer or more can be accommodated if needed.

Required time

Preparation:

• 30 minutes printing and creating signs
• 1 hour room prep (creating network on the floor using tape)
• plus whatever time you need to familiarize yourself with the material

Activity: 45 minutes

Note: Because of the room preparation required for this activity, you may want to present it multiple times back-to-back to different groups of students.

Materials

You will need the following materials:

• Masking tape/chalk to mark network on floor
  Masking tape is useful indoors, chalk works well on hard surfaces outdoors
  You'll want at least a couple of rolls of masking tape for this
  Alternately, if outdoors, you can use hula hoops and rope to mark the network
  Note that you'll need to attach labels to each rope
• Rope (50' is more than enough)
  This is used to show the phone switched connection
• Manilla folders
  Used to label the network nodes
  You can skip this if you have another way of labelling nodes
• Markers
  To write labels on the masking tape and manilla folders.
• Print out the following:
  Routing tables
  Packets
  Website results
• Scissors (to cut out holes for the “images” from the web page printout)
• Props (optional):
  Small, personal address book
  City phone book (as thick as possible, perhaps have a few from different cities)

Preparations

(1) Draw the network map on the floor

Draw the following network map on the floor using masking tape:



You'll want an open space roughly 20'x20' (6m x 6m) in size for this.

If you're outdoors, you can use chalk or you can use anything else convenient: hula hoops connected by rope would also work. The important thing is that you're able to label each node and link in the diagram.

Make each node (circles/boxes) large enough for a student to stand/sit within. Circles are hard to do with masking tape, so squares are fine (the shape of each node does not matter). Each square should be about 3' (1m) on each side. Nodes 10-13 can be a different shape (like a triangle) if desired.

Make sure there's enough space between each node so that the links between them are easy to see. Ideally it should take from 2-3 steps (~5' or ~1.5m) to go from one node to another.

The graph is easier to make if you start with the 3 central nodes (1, 2, and 3) and label them for identification. Add the other nodes to this core network, but don't label them yet (since they will change function during the activity) – you will make signs for these nodes. See the next section (about creating signs) for information about labeling each of the nodes.

Each of the links between the nodes should be labeled so that they are easy to identify. If using masking tape, write the label directly on the tape.

• Write the label more than once along the tape. At least mark the points closest to each node, but it is preferable to mark all along the tape (separated by ~1' (~30cm)).
• Note that the students will be walking around and viewing the labels from all angles, so make sure that they are easy to read.
• We use both upper-case and lower-case letters to label each link (e.g., "Aa"). This is because the labels will be viewed from all angles as the students walk around and using just upper or lower case letters leads to cases where the labels are ambiguous ("p" vs. "d" or "H" vs. capital "I" with serifs) .

The graph can be stretched and distorted to conform to your environment, but do not change the topology (i.e., don't change the connections between the nodes).

(2) Create signs to place on the internet nodes

Only 3 of the nodes that you just created can be labeled permanently (i.e.: for the duration of the activity): “1”, “2” and “3”. You can label these using tape or chalk or whatever is convenient.

Don't give permanent labels to the other 10 nodes because we need to give them more descriptive names during the presentation (and these names will change during the course of the activity). You should create name tags for these nodes - I just use manilla folders and wrote the node names on them, but you can label them however you see fit.

You will need to create the following 10 signs:

For Part II (phone system):

• “206”
• “425”
• “212”

(or you can choose whichever 3 area codes you like. Just remember to adjust the switching tables to be consistent.)

For Part III (internet):

• “google.com”
• “wikipedia.org”
• “ISP”

(or you can replace these with whichever search engine / web resource you prefer. Just remember to adjust the routing table and all the packets to be consistent.)

For Part IV (DNS):

• “root name server” (rns)
• “.com name server” (.com ns)
• “.org name server” (.org ns)
• “ISP name server” (ISP ns)

(3) Print out the switching/routing tables and internet packets

Print out all of the switching/routing tables and internet packets in the PDF files. They should all be printed single sided.

[Links to these files will be in the following posts.]

(4) Cut out holes for the “images” from webpage in last set of packets

The last set of printouts requires that you cut out the squares where the images should be displayed in the web page.

[to be continued...]

Octal counting worksheets

I've added a couple of worksheets for practicing with writing numbers in octal to the cse4k12.org website.

These worksheets can be used by students to practice counting/converting numbers in octal. They each show a set of circles that the student must count in both octal and decimal. The circles are arranged in groups of eight to make the octal calculation straightforward.

cse4k12 ~ resources

Over Thanksgiving I started playing around with App Engine and threw together an a fairly simple app for keeping track of Computer Science (& Engineering) teaching resources.

I probably would have waited a bit before making it available, but with Computer Science Education Week going on right now, I figured that this was as good a time as any.

It's running at http://cse4k12.appspot.com/ and you can use it to search for resources by topic, add comments/reviews or you can add links to your own material.

It's still fairly early and I'm still going through and adding all the material that I'm aware of - I'll be adding it piece-by-piece as I get around to it. If you know of anything that is not listed, then please feel free to add it.

Authentication... sigh...

The thing that bugs me the most about it is that, while no login is required to access any content on the site, you do need to login in order to add resources or comments. This is to help prevent people from spamming the site with useless comments/advertisements.

I didn't want to force people to create yet another account/password just for this site, so you can use your Google account (gmail account) for authentication. And no, this doesn't mean that you give your password to us - what happens is that we send you to Google where you login and then they send back a token that says "the current user has successfully logged in as xxx@gmail.com". That's all we get: your email (well, and a "nickname"). Which is great because we don't really want or need anything else.

Of course, this doesn't help you if you don't already have a Google account. While it's easy to create one, you'd probably rather use your Passport or OpenID account or whatever it is you use on a day-to-day basis. I plan on adding support for these different authentication providers, but haven't had a chance to do it yet. Please let me know if you would find this useful so that I can prioritize adding support for this.

Updated bitmap (binary/hex) worksheets

I've updated the bitmap (binary/hexadecimal conversion) worksheets. There is now an instruction sheet that contains 5 bitmap grids for students to create their own bitmaps plus 2 grids for them to convert from hexadecimal into a bitmap.

There are also blank worksheets (grids only - no instructions) for 8x8 and 16x16 bitmaps.

Slides for AMS 2009 workshop

These are the slides for the "Computer Science Education in the Montessori Classroom" workshop that I presented yesterday at the AMS Fall 2009 conference.

I added an extra slide to include a diagram of a ripple carry adder.

Slides are available in the following formats:

• OpenDocument (.odp) 945K
• PDF 448K
• PowerPoint (.ppt) 1409K

Note that the PDF and PowerPoint versions were converted from the original OpenDocument format file. Because of the conversion, a few of the slides look a bit funky in the PowerPoint version. If this is a concern, please use the OpenDocument (using OpenOffice) or PDF (using Adobe Reader) version.

How Computers Work (high level)

This is an activity for 3 students to work together as a group. Each student takes on the role of a different part of the computer:

• CPU
• ALU (& memory)
• Graphics display

They work through the project with the CPU running the "program", the ALU performing the math and keeping track of the variables, and the display plotting the values as needed.

The purpose of the activity is to give the students a sense of how computers work at a reasonably high level.

I created this a while ago, but neglected to actually post the information here. Full information about this activity can be found at http://cse4k12.org/how_computers_work/index.html.

Computer Science Education in the Montessori Classroom

I gave a "Computer Science Education in the Montessori Classroom" workshop at the American Montessori Society (AMS) Fall conference yesterday.

The workshop description that we submitted (oh so many months ago) was:

How can we better prepare our children for life in a high-technology society? How early should we teach them computer and pre-programming skills? How can we integrate computer science education into Montessori classrooms? This presentation of Montessori-friendly and age-appropriate activities will include stand-alone activities and extensions to existing classroom curricula as well as a take-home list of some useful online resources for teachers.

Looking back at this, it sounds sufficiently vague that I probably could have talked about anything as long as I mentioned computers every so often.

The following would perhaps have been a better overview:

Why aren't we teaching pre-programming skills (binary, boolean logic, transistors) to our children during elementary school? Why don't we teach students how computers actually work instead of simply how to use them? In this workshop, we will show (1) how computers work and (2) how you can teach these concepts to your elementary/middle school classroom.

A part of me wants to say something more confrontational like "how we're failing our students by not providing a solid understanding of computer technology", but I'll resist the urge and hold off on that rant (until another time perhaps ^_^).

I'll be posting the slides here once I get a chance to upload them.

cse4k12.org vs. cse4k12.com

Grrrr....

cse4k12.org is supposed to be the main URL for the website and cse4k12.com is supposed to simply redirect to .org.

Unfortunately, it looks like things are set up screwy and .org no longer redirects to the right place. I'll have to fix that but in the meantime all of the cse4k12.org links in the blog were not working.

Temp fix: change all the links to .com. I'll change them back once I fix the issue with .org, but for now if you have problems with any .org address, just change the "org" to "com" and it should work.

[Update: This has been fixed. All .org links are working again.]

New Spritely tutorials: Creating NDS ROMs

Two new tutorials for Spritely:

* Creating an NDS ROM File
* Info about GBA and NDS cartridges

Crossbin puzzle #2

Binary magic trick

I've added documents for the binary magic trick activity that I use after introducing the students to binary numbers.

This includes the cards (to cut out) and a set of instructions on how to perform the trick.

Crossbin puzzles

I've started adding crossbin puzzles to cse4k12.org. Crossbin puzzles are similar to crossword puzzles except that the clues are hexadecimal numbers and the answers are binary numbers.

When the puzzle is complete, the grid is filled with '0's and '1's. Then all the '1's can be filled in with black (and, optionally, '0's erased to white) to create a simple black and white image.



These are useful as a simple exercise in a computer science class after the students have been introduced to binary and hexadecimal numbers (and how to convert between them).

Basic instructions and a simple example are given at cse4k12.org:

http://www.cse4k12.org/crossbin/index.html

New Spritely tutorial: Adding a Projectile

I've added a new tutorial for Spritely that shows how to add a single projectile to a game project.



http://spritely.googlecode.com/svn/trunk/tutorials/projectiles.html

Spritely in action

John is using Spritely to introduce his son to programming and made a video:

http://botchagalupe.tumblr.com/post/84674186/teaching-kids-how-to-code

It looks like I have to get my act together and make more tutorials available (e.g., projectiles).

SIGCSE 2009 slides

Here are the slides from my SIGCSE 2009 presentation:

"Introducing Computer Programming via Gameboy Advance Homebrew"

• Slides (PDF)
• Paper (PDF)
  Note: Requires ACM Web Account.