CS337
Midterm 2
Ondich
Due in class Monday, March 6, 2000
This exam is open-book, open-notes, open-computer, open-Internet,
but closed-other-people. Have fun.
- (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.)
- (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.)
- (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?
Jeff Ondich,
Department of Mathematics and Computer Science,
Carleton College, Northfield, MN
55057,
(507) 646-4364,
jondich@carleton.edu