SI 540: Fall 1999

HW 9 Solutions

due December 6
(note that HW10 will also be due on December 6)

Last modified 11/29/99 --PR
Class home page

You can do this assignment in pairs, but not in groups larger than two.

Readings

For November 29:

Chapter 13; supplement to chapter 19 on network security

I also strongly encourage you, before class on Nov. 29, to do the get-acquainted with PGP exercise below to give you a more concrete sense of how encryption works. Next week there will be a graded exercise using PGP.

PGP Intro Exercise (ungraded)

(I strongly recommend that you do this exercise with a partner, even if you don't do the rest of the assignment with a partner. There's lots of opportunity to get frustrated over small syntactic problems, as well as conceptual problems, and a partner can help you get through the roadblocks.)

The official version of PGP (Pretty Good Privacy) for this exercise is v2.6.2. You may use any version you like as long as the keys and cryptographic operations are compatible with v2.6.2. There are significant compatibility problems between v2.6.2 and version 5, including the use of different cryptographic algorithms (and hence different keys).

PGP v2.6.2 is available on both login.si.umich.edu and login.itd.umich.edu in the path /usr/um/bin/pgp. If you use these, you will not need to worry about installing PGP.

User documentation on PGP:

 

Create your own key pair

You'll first need to create a subdirectory .pgp in your home directory.

Now create your pgp keys:

 

Experiment with encrypting and decrypting messages

Try sending and receiving encrypted messages with your partner

Hint: at the end of the first volume of documentation, there's a PGP Quick Reference.

Text exericses

(1 point) Create an "is a" hierarchy and a "part of" hierarchy for a teaching hospital (a hospital where doctors are trained: for example, interns and residents are young doctors who have completed medical school but who are still being supervised by other more experienced doctors). You may want to use a single diagram with two different colors of arrows, one to indicate inheritance between classes (is a) and one to indicate that an instance of one class is a part of an instance of another class. You may find it easier to do this on paper, by hand, than with a computer program. You don't need to be complete about all the parts and occupations of a hospital. Just demonstrate that you understand the distinction between is-a and part-of and that the same item can be in both is-a and part-of relations with other items.

(1 point) How long would phone numbers have to be (how many digits) in order to accomodate as many different devices as can be identified with 32-bit IPv4 addresses? How about 128-bit IPv6 addresses? (Hint: 210 is approximately 1000 = 103).

2128 = 2120+8= 2120*28 = (210)12* 28 = (103)12*28 = 1036* 256 < 1036* 103 = 1039.
39 decimal digits would be sufficient.

(3 points) Why are network functions layered the way they are?

Think of TCP as a "higher" layer than IP, meaning that an application that requests network services might request a TCP service, which might call on IP-layer services in order to fulfill the TCP request, but the implementation of the IP layer service would never result in a TCP request. Forget for a moment about actual network protocols you may know about (such as TCP and IP), though you may use them as an inspiration for answering the following question.

Suppose that we were designing a set of network layers, such that at each layer one and only "function" was provided. You may assume that the lowest layer is a best-effort delivery of a message (with maximum size 64K) from one host to another over a direct connection (e.g., a wire).

Consider the following functions that might be provided at higher layers and order them from highest to lowest in terms of what layer you would like to see them. For each adjacent pair of layers, argue for why you put one higher than the next.
A. Compression and decompression
B. Packet fragmentation and reassembly
C. Multi-hop routing
D. Reliable delivery through resends

[If, for example, you had compression and reliable delivery as adjacent layers, here's an argument you might use to justify the order. "Compression should be at a higher layer than reliable delivery. If reliable delivery were at a higher layer, then, as part of the resend process, the sender would have to run the compression algorithm on it again, which would be unnecessary duplication of effort." Note, however, that you only need to justify orderings for layers that you claim should be adjacent (i.e., no other layers in between them).]

The general form for these answers is: Suppose the order of layers were reversed. The following might happen. It would be bad. It is possible to argue for a different ordering of these layers, especially the lowest 3, depending on how frequent you think packets are garbled between links, or on complete paths.

Compression and decompression
--Some compression algorithms take advantage of knowing characteristics about the data stream. For example, there are special compression algorithms for video that eliminate redundancy between frames. If the data stream was fragmented into packets before compression, then each packet would be compressed independently and there would be no way to take advantage of redundancies between packets.

Packet fragmentation and reassembly
--If only one packet is not received properly, it can be transmitted again without retransmitting everything. If reliable delivery through resends were done for the entire message (i.e., reliable delivery at a higher layer), then one undelivered packet would cause all packets to be resent.

Reliable delivery through resends
--Since data is rarely garbled and packets are rarely lost, it's better not to do resends at each intermediate stop along the way from source to destination, but rather to postpone the integrity check and acknowledgement steps (which incur overhead) until a packet reaches its final destination. If lost and garbled data were frequent, then it might be better to have reliable delivery at each hop.

Multi-hop routing
 

Lab Exercises

(1 point) Fetching Web Pages by hand

 Log on to a UNIX machine (e.g., login.si.umich.edu)
It turns out with the newer HTTP/1.1 protocol, a web browser needs to send a Host: header. This allows the protocol to work better with "proxy" servers that do caching of pages from other servers. Here are the commands you need to enter to fetch the SI home page by hand.

Type: telnet www.si.umich.edu 80 (hit return)
        (Note: this makes a telnet connection on port 80 to the host www.si.umich.edu)
Type: GET / HTTP/1.1 (hit enter)
       (Note: you won't see a login: prompt because you're not using the usual telnet port, 23, and hence your data is not being passed to the login shell application on the server. Just start  typing.)
Type: Host: www.si.umich.edu (hit enter again)
(hit enter a third time) 

Question: give similar instructions for fetching the URL http://www.w3.org/MarkUp/

Type: telnet www.si.umich.edu 80 (hit return)
Type: GET /Markup/ HTTP/1.1 (hit enter)
Type: Host: www.si.umich.edu (hit enter again)
(hit enter a third time)

(2 points) Internet Names, Address, and Routing

HINTS: you may find the following UNIX commands useful in answering these questions:

Some of these commands are also available on the DOS command-line, though there may be slight variations. For example, traceroute in UNIX is tracert in DOS.

A. What are the IP addresses for the hostname www.w3.org?

Name:    www.w3.org
Addresses:  18.23.0.23, 18.23.0.22

B. What are the IP addresses for the hostname w3.org?

Name:    w3.org
Address:  18.23.0.20

C. What are the IP addresses for www.si.umich.edu and si.umich.edu?

141.211.203.34 and 141.211.203.32

D. If a hostname (e.g., www.si.umich.edu) is in a subdomain of another hostname (e.g., si.umich.edu), is it always the case that the first three parts of the IP address will be the same (Hint: check out umich.edu)?

No. The IP addresses associated with the domain name 'umich.edu' start with 141.211.83, which is different from that for si.umich.edu. In fact, the IP addresses could be completely unrelated.

E. What's the complete path that data follows to www.w3.org (hint: use traceroute)? The path need not be stable, so don't be alarmed if your result is different from your classmates. Which link in that path seems to cause the biggest delay? Can you make any educated guesses about which hosts might be part of "NAPs" (the places where backbone providers pass traffic to each other)?

bart% traceroute www.w3.org
traceroute to www.w3.org (18.23.0.22), 30 hops max, 40 byte packets
 1  fe-si.c-ugli.umnet.umich.edu (141.211.203.1)  2 ms  1 ms  1 ms
 2  f-backbone.c-ccb.umnet.umich.edu (141.211.0.1)  2 ms  5 ms  2 ms
 3  fddi4-0-0.michnet1.mich.net (198.108.3.1)  4 ms  4 ms  3 ms
 4  hssi1-0-0.msu.mich.net (198.108.22.102)  12 ms  23 ms  14 ms
 5  aads.vbns.net (198.32.130.14)  16 ms  221 ms  22 ms
 6  cs-atm0-0-12.cht.vbns.net (204.147.130.74)  38 ms  37 ms  33 ms
 7  VBNS-RTR-OC3.MIT.EDU (18.3.0.1)  40 ms  41 ms  41 ms
 8  B24-RTR-FDDI.MIT.EDU (18.168.0.14)  40 ms  54 ms  47 ms
 9  18.201.1.3 (18.201.1.3)  45 ms  46 ms  40 ms
10  third.lcs.mit.edu (18.24.10.1)  45 ms  45 ms  44 ms
11  www12.w3.org (18.23.0.22)  39 ms *  39 ms

The key to reading the times is to think of each number as a separate event. A packet was sent from the original host to the specified router or host, and was ACKed. The time recorded is the time from sending to receipt of the ACKnowledgement. Thus, to find a slow link between adjacent routers, we need to subtract the time it took to get to the closer one from the time it took to get to the farther. The link between nodes 5 and 6 semms to have the biggest differential (if we ignore the one time when it took 221 ms to get to node 5.) One could also make an argument for the link between 3 and 4 being slow or between 7 and 8.

The NAPs should be places where traffic transits from a network owned by one organization to a network owned by some other organization. You can guess at that by looking at the domain names. Between 2 and 3 traffic leaves umich.edu and goes to mich.net, but that's probably just a direct connection rather than being part of a NAP where several backbone providers exchange traffic. Likewise for 6 to 7, where traffic leaves vbns.net and goes to mit.edu. The 4 to 5 link might be at a NAP, since that link connects mich.net and vbns.net.

Explanation exercise (2)

Explain (to someone) the difference between domain names and IP addresses. If the person you're talking with is interested, try to explore why both are needed: what if there were no IP addresses and domain names were used in routing? what if there were no domain names and IP addresses were used in URLs?