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

1. (20 points) The cnet program flood.c implements a very simple-minded flooding algorithm. There is a globally defined maximum hop count. Whenever a node receives a frame, it increments the frame's hop count. If the resulting hop count is larger than the maximum, the node discards the frame. Otherwise, the node sends a copy of the frame to all its neighbors.

   This implementation tests its algorithm by allowing node 0 to flood a single frame, after which no more original frames are sent. When each node receives the frame for the first time, it saves a copy.

   Use flood.c and the topology file MINNESOTA to answer the following questions.

   • Start MAX_HOP_COUNT at 1 and increase it. As a function of MAX_HOP_COUNT, which nodes receive a copy of the frame and which don't?

   • Modify the code to report the time at which the last copy of the frame is discarded. Now start MAX_HOP_COUNT at 1 and increase it (try going up to 8). For each value of MAX_HOP_COUNT, record the total number of frames sent (the -s command-line argument to cnet will tell you this) and the time it takes for the flood to subside. Discuss the apparent growth rates of these quantities as a function of MAX_HOP_COUNT.

   • Modify the code so that when a node receives a frame from a neighbor, it does not flood a copy back to that neighbor. Collect the same statistics as in the previous question, and discuss the effect of your change to the algorithm.

   • Keep the code change from the previous question. Modify the Frame data type to include a sequence number field that will store a sequence number between 0 and 63. Modify the code so that a node will only flood an incoming frame if (1) the incoming frame's hop count isn't too high, and (2) the incoming frame's sequence number is "greater" than the sequence number the node has previously stored.

     
     		int greater_than( int m, int n )
     		{
     			return( (m > n  &&  m - n <= 32 )  ||  (m < n  &&  n - m >= 32) );
     		}
     	

     Once again, collect time and frame count statistics as MAX_HOP_COUNT increases. How does this algorithm compare to the previous versions. How does it compare to the minimum possible time and frame count?

   • One last thing. Have node 0 flood three frames with sequence numbers 8, 40, and 44, without pausing. What happens? (You might notice that in the previous versions of the code, if you increased the simulation time past the time it takes for the flood to die out, the frame count doesn't change.)
   
   
   
2. (20 points) Suppose I am logged onto hamming.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 hamming 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 hamming 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 hamming 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.)
   
   
   
3. (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?