This exam is open-book, open-notes, open-computer, open-Internet, but closed-other-people. Have fun.

1. (20 points) Suppose I am logged onto knuth.mathcs.carleton.edu, and I type (as I often used to before the Web) "ftp ftp.apple.com". Suppose further that ftp.apple.com is not in my DNS cache, that my IP routing table is as you will find it by logging onto knuth and typing "netstat -r", that my ARP cache is empty (by some bizarre and disturbing Act of the Test Writer), and that there exist on knuth some sort of software "entities" corresponding to and named after IP and TCP.
   • Describe clearly and concisely what happens next, as my command tries to make contact with the ftp server at ftp.apple.com. Try to be complete within reason--the story you are going to tell me could be quite long. Keep your version of the story under two pages. One page should really be enough.
   • My ftp client will be sending a first message off in the direction of ftp.apple.com. (Note that the message I'm talking about is not the first message of any kind that knuth sends out while trying to talk to ftp.apple.com. I'm talking about the first message whose destination is ftp.apple.com.) After passing through quite a bit of software and accumulating several headers, this first message will become a grown-up 802.3 frame on the Math/CS network. Show me the contents of this frame, in as much detail as you can. Whenever possible, I want you to show me exactly what numbers are stored in the various header fields. For those fields whose values you can't know at test-taking time, explain why you can't know them. What, if any, non-header data will this frame contain? (To answer this last question, you need to explain the purpose of this very first ftp.apple.com-bound message.)
   
   
   
2. (12 points) The protocol ICMP is described in RFC 792. Answer the following questions about ICMP.
   • Briefly, what is ICMP's job?
   • Suppose an IP datagram gets broken into 5 fragments, each of which arrives at a router ("gateway"--RFC 791 was written in 1981) on the destination's LAN. If the destination host is down at the time, what ICMP message does the router send back to the sender of the datagram? How many copies of this ICMP message does the sender receive?
   • An ICMP message includes the first 64 data bits from the IP datagram it is responding to. Why?
   • What purpose does the ICMP Redirect message serve?
   • In what situations would the Echo and Echo Reply messages be useful?
   • Which ICMP message is involved in flow control?
   
   
   
3. (3 points) It occurred to me recently that for the last ten or fifteen years, I have been completely out of touch with popular culture (except, of course, for that portion of popular culture whose audience is 2- to 8-year-olds). For example, I don't think I could name a chart-topping song from the nineties, an MTV host, or a cast member from Melrose Place. So help me out here. Tell me something I should read or watch or listen to if I hope to get caught up before my children start rolling their eyes at me.
   
   
4. (6 points) The following is an adjacency table for a 10-node weighted graph, with nodes numbered 0 through 9.

   
       0 1 2 3 4 5 6 7 8 9
      ---------------------
   0 | 0 1 0 0 2 0 0 5 0 0
   1 | 1 0 1 0 0 0 0 0 0 0
   2 | 0 1 0 2 0 2 0 0 0 0
   3 | 0 0 2 0 0 0 1 0 0 1
   4 | 2 0 0 0 0 1 0 0 0 0
   5 | 0 0 2 0 1 0 3 0 0 0
   6 | 0 0 0 1 0 3 0 2 1 0
   7 | 5 0 0 0 0 0 2 0 0 0
   8 | 0 0 0 0 0 0 1 0 0 2
   9 | 0 0 0 1 0 0 0 0 2 0
   

   • Draw the graph.
   • Show the shortest-path spanning tree starting at node 0 that would be computed by Dijkstra's algorithm, assuming that Dijkstra chooses the lowest numbered node whenever it has a choice.
   • List the nodes in the order in which Dijkstra's algorithm determines their shortest paths to node 0.
   
   
   
5. (8 points) Consider distance vector routing, link state routing, and fixed table routing. Explain the advantages and disadvantages of each, and describe typical situations in which each would be a good choice.