MCS-377 Homework (Fall 2004)
When turning in a homework problem, if it is one from the book, you
should indicate not only the exercise number, but also which kind of
exercise it is: review question, problem, or discussion question. The
code I will use for this is as follows: 1.r5 is review question 5 of
chapter 1; 1.p7 is problem 7 of chapter 1; 1.d1 is discussion problem
1 of chapter 1. Please use this code when you turn in the problems,
and I will use them in reporting back your standing on the homework.
For any problems that are not from the book, I will specify the
problem number to use, which will have an x in it (e.g., 2.x1).
Note that I will add problems to this list from time to time, but
unless I warn you otherwise, only by adding entire new chapters at the
end. So if you check back, tell your browser to reload the page (in
case it has an old version cached) and then look and see if there are
any new chapters after what used to be the last chapter with problems
- Problem 1.r5, p. 61.
- Problem 1.r9, p. 61.
- Problem 1.r23, p. 62.
- Problem 1.p7, p. 64.
- Problem 2.r8, p. 170.
- Problem 2.r19, p. 171. Assume the organization's web and mail
servers are different. For example, they might be www.foo.com and
mail.foo.com, each with a type A record with a different IP address.
Web access to foo.com should be just like to www.foo.com, whereas mail
addressed to foo.com should go to mail.foo.com. What RR type is used
to provide the translation of foo.com in each context? (The book just
asks about the mail context; I want both.) There may be more than one
- Problem 2.p5, p. 172.
- Problem 2.p17, p. 173. Also, what are some of the comparative
advantages and disadvantages of the alternatives described in parts
(b) and (c)?
- Problem 2.p21, p. 176.
- Problem 2.x1: SMTP and POP3 are both used for email, but play different roles.
Explain the difference in their roles. Make your explanation concrete
by mentioning typical commands from each of the two protocols and
explaining their general function.
- Problem 3.r6, p. 286.
- Problem 3.p4, p. 287. This problem refers to an
unlabeled figure on p. 288, to which you need to make the following
corrections before working the problem:
The "deadlock" may not be a state where packets stop being
sent; it can be a situation where no forward progress is made on
delivering new data, even though packets go back and forth.
Also, the problem should be worked within the context of no lost
packets, only corruption, and with the assumption that even
corruption will not continue forever.
- Add a dotted arrow pointing to the start state, "Wait for 0 from
- In the action on that state's loop edge, replace "andpkt" by
- The right-hand edge of the figure is chopped off; on the line
printed as "make_pkt(sndpkt, NAK, c", tack on "hksum)".
- Problem 3.x1:
Indicate whether each statement is true or false. If false, briefly
- Each TCP segment has a sequence number one greater than its
- A TCP sender can send as much data as the current congestion
window before it has to wait for acknowledgments.
- If a TCP receiver receives a corrupt segment, it sends a NAK.
- In TCP's slow-start mode, each segment acknowledged causes the congestion window
to expand by one segment.
- In TCP's congestion-avoidance mode, each segment acknowledged causes the
congestion window to expand by one segment.
- A lost TCP segment will result in a timeout.
- Problem 3.x2: The X in the following diagram is a lost segment. The TCP segments
flowing in the left-to-right direction each carry 1000 bytes of data,
whereas those in the right-to-left direction are pure ACKs. Add
the sequence and ACK numbers to the nine arrows that don't already have
- Problem 3.x3: Normally if a TCP host receives a segment with
sequence number 1000 and length 1460 (for example), it will respond
with an ACK of 2460, since that is the sequence number of the next
byte anticipated. Suppose instead that it sent two ACKs, one with the
ACK number field being 2000 and the second with it being 2460. In
terms of the simplified TCP sender of Figure 3.33 (p. 240), is there
any harm in this "divided ACK"? Next, consider the TCP congestion
control algorithm as summarized in Table 3.3 on page 269. What would the impact of
the divided ACK be on this algorithm? Is this a good or a bad thing?
- Problem 3.x4:
- How does TCP provide flow control?
- What two ways does TCP, as currently standardized, use to detect
- What two additional ways for TCP to detect congestion have been
- Problem 4.r16, p. 401. Be sure to justify your answer. Assume no
TCP or IP options are used.
- Problem 4.p10, p. 406.
- Problem 4.p11, p. 406.
- Problem 4.p21, p. 408.
- Problem 4.p23, p. 408.
- Problem 4.x1: We have seen two general approaches to multicast
routing: one exemplified by DVMRP and PIM Dense Mode, the other
exemplified by CBT and PIM Sparse Mode (at least initially; PIM Sparse
mode has the ability to switch approaches).
- What are the names of these two approaches?
- Which one of them has more in common with the spanning trees used
by Ethernet switches to avoid cycles?
- Briefly explain what the similarity is.
- Problem 4.x2: Use the command
on an MCS-department Linux machine to find the mask and the "inet
addr" (i.e., IP address). How many 1 bits does the mask contain? Use
that as the value of x to express the subnet address in the form
a.b.c.d/x. To find a.b.c.d, take the machine's IP address and change
the rightmost 32-x bits to zeros.
- Problem 5.p11, p. 496.
- Problem 5.p12, p. 496.
- Problem 5.p17, p. 498. In Figure 5.42, there is no interface
number on the links leading from R6 and R5 to R4. Assume these are
interface 0 in each case.
- Problem 5.x1: A computer wants to send the data bits 11010010,
followed by three CRC bits. What should those CRC bits be, if the
generator is 1001? Show your work.
- Problem 5.x2: (For this problem, note an erratum on p. 461: change
2m-1 to 2m-1.) Suppose two nearby computers, A
and B, both have numerous frames queued up
for transmission on the same Ethernet segment. Call these frames A1,
A2, etc. at A, and B1, B2, etc. at B. Assume there are no other
computers trying to transmit on this Ethernet segment. At time 0, A
makes an initial attempt to transmit A1 and B makes an initial attempt
to transmit B1. They collide. A chooses K=0 and B chooses K=1.
The result is that the first frame successfully transmitted is A1.
Afterward there is another collision, between A2 and B1. Suppose A2
wins, i.e., A again picks a smaller K than B does. After A2 is done being
transmitted, A3 collides with B1. When A and B back off and retry
their transmissions, which is more likely to go first, A3 or B1?
Explain why. You need not calculate the exact probability that the
more likely one goes first, but you should at least provide a lower
bound on this probability that is greater than 1/2.
- Problem 6.r6, p. 560.
- Problem 6.p3, p. 560.
- Problem 6.p5, p. 560.
- Problem 6.p8, p. 561.
- Problem 6.x1: Do either of the following:
Section 6.3 says that address 3 in an 802.11 frame
contains a router's MAC address. In class, I suggested it could
instead be the MAC address of another host on the same subnet as the
AP. Resolve this disagreement, in one of the following ways: by reference to the text of the
802.11 standard, by reference to another credible text, by
experimentation with ethereal on a system that can capture 802.11
frames (which ethereal under Windows, unfortunately, cannot), or by
making a convincing argument why one of the two contenting claims
makes more sense.
The text's description of Mobile IP assumes that only unicast
datagrams are sent to the permanent address. By default, broadcast
datagrams are not forwarded. However, an option allows them to be
forwarded. Explain how this optional forwarding works. That is, what
mechanism is used for the optional forwarding? Some issues to
consider are whether the forwarded
packet winds up (re-)broadcast on the visited network, and whether
there is any sacrifice of transparency.
- Problem 8.x1: Read one of the following papers, determined by the
start of your last name. Write a one-page summary, in your own words,
of the paper. All these papers were published in the
Proceedings of the 13th
USENIX Security Symposium, August, 2004.
- Last names A-C
Fast Containment of Scanning Worms," by Nicholas Weaver, Stuart
Staniford, and Vern Paxson, pp. 29-44.
- Last names D-Ha
How to Set Up a Secure Wireless Network in Under a Minute," by
Dirk Balfanz, Glenn Durfee, Rebecca E. Grinter, Diana K. Smetters, and
Paul Stewart, pp. 207-222.
- Last names He-Ho
Sharing and Correlation of Security Alerts," by Patrick Lincoln,
Phillip Porras, and Vitaly Shmatikov, pp. 239-254.
- Last names K-Sche
Toward Automated, Distributed Worm Signature Detection," by
Hyang-Ah Kim and Brad Karp, pp. 271-286.
- Last names Schm-W
The Second-Generation Onion Router," by Roger Dingledine, Nick
Mathewson, and Paul Syverson, pp. 303-320.
- Problem 8.x2: Do review problems 8.r1 and 8.r3 from page
722, but label your answers as a single problem, 8.x2.
- Problem 8.x3: 8.p7 mentions that BGP can use MD5 for signatures.
However, this leaves open how a message digest function can be used
(without also using either public-key or symmetric-key cryptography) for signatures. In particular, where
does a key fit into this? Answer this question of mine (not the
original 8.p7 question), refering to the RFC about BGP's use of MD5 if
you need to.
- Problem 8.x4: On p. 683, Kurose and Ross say that "no one has
argued with [Rivest's] claim" that finding an MD5 collision is hard.
This is outdated. Find up-to-date information on MD5 collision
attacks, and briefly summarize it.
- Problem 8.p10, p. 724. That is, can any of the three parties be
impersonated? Why or why not?
- Problem 8.p11, p. 724.
- Problem 8.p13, p. 725
Instructor: Max Hailperin