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