MCS-377 Homework (Fall 2008)
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.
Chapter 1
Problem 1.r25, p. 69.
Problem 1.p5, pp. 70-71.
Problem 1.p6, p. 71.
Problem 1.p9, pp. 71-72. In the problem statement, after the words "Assuming no queueing delays, in terms of", insert "dproc,".
Problem 1.p24, pp. 74-75.
Chapter 2
Problem 2.p6, p. 182.
Problem 2.p9, pp. 182-183. Assume negligible time is spent in the
institutional network and cache. Give two answers: one for the
average response time for those requests that reach the external
network and one for the average response time over all the requests
initiated by the browsers.
Problem 2.p24, pp. 186-187.
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 2.x2: List at least five types of header lines that can be used in the HTTP
protocol. What is the function of each?
Problem 2.x3: Use the command
dig www.gustavus.edu
to trace the chain of CNAMES that leads from
www.gustavus.edu to a numerical IP address.
Chapter 3
Problem 3.r16, p. 295.
Problem 3.p6, p. 296. Ignore the first sentence,
"Consider our motivation..." This problem refers to an
unlabeled figure on p. 297, to which you need to make the following
corrections before working the problem:
Add a dotted arrow pointing to the start state, "Wait for 0 from
below".
In the action on that state's loop edge, replace "andpkt" by
"sndpkt".
Each line of the form "make_pkt(sndpkt, ...)" should be changed to
"sndpkt = make_pkt(...)".
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. Another assumption is that all corruption is detected.
Problem 3.p33, pp. 301-302.
Problem 3.x1:
Indicate whether each statement is true or false. If false, briefly
explain why.
Each TCP segment has a sequence number one greater than its
predecessor.
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
them.
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. 253), is there
any harm in this "divided ACK"? Next, consider the TCP congestion
control algorithm as summarized in Table 3.3 on page 285. What would the impact of
the divided ACK be on this algorithm? Is this a good or a bad thing? Why?
Chapter 4
- Problem 4.r16, pp. 417-418. Be sure to justify your answer. Assume no
TCP or IP options are used.
- Problem 4.p11, p. 422.
- Problem 4.p12, p. 422.
- Problem 4.p22, p. 424.
- Problem 4.p24, p. 425.
- Problem 4.p33, p. 427. There is an error in this problem: the reference to problem 4.p21 should actually be to problem 4.p22.
- Problem 4.x1:
-
Express the IP address 10100011000101000110100100001111 in dotted
decimal.
-
Express the IP address 194.73.127.10 in binary.
-
How many 1 bits does 255.255.192.0 start with?
-
How many 1 bits does 255.255.224.0 start with?
-
Write in dotted decimal form an address with 20 bits that are 1
followed by 12 that are 0.
-
Write in dotted decimal form an address with 22 bits that are 1
followed by 10 that are 0.
- Problem 4.x2: Use the command
/sbin/ifconfig eth0
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. Also, indicate which of the following IP
addresses would be reached directly and which would be reached by way
of the gateway router: 138.236.71.64,
138.236.72.64,
138.236.64.72,
and
216.114.254.180.
- Problem 4.x3: When I recently examined the BGP route advertisements collected at another point on the Internet, the following three particularly caught my attention:
- prefix 138.236.0.0/16, AS path 812 6461 701 7821 5006
- prefix 138.236.0.0/17, AS path 2152 2153 11537 57 17234
- prefix 138.236.128.0/17, AS path 2152 2153 11537 57 17234
Answer the following questions based on these route advertisements:
- Because the two /17 prefixes have the same AS path, those two route advertisements could be aggregated together into a single one if the prefixes are sufficiently similar. How many bits do they have in common? What are those common bits? Once the two prefixes differ, what are the bits in each? Based on these considerations, you should be able to conclude that aggregation is possible. What would the aggregated advertisement be?
- Given that the second and third advertisements can be aggregated, what advantage might there be in keeping them separate? To test whether your theory makes sense, you might find it useful to translate the last few AS numbers in each path to their owning organizations; you can do this using the whois service on www.arin.net.
Chapter 5
- Problem 5.p15, p. 505.
- Problem 5.p16, p. 505.
- Problem 5.x1: A computer wants to send the data bits 11011010,
followed by three CRC bits. What should those CRC bits be, if the
generator is 1001? Show your work.
- Problem 5.x2: 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.
Chapter 6
- Problem 6.r9, p. 579.
- Problem 6.p3, p. 580.
- Problem 6.p6, p. 581.
- Problem 6.p12, p. 583. Use Figures 6.22 and 6.23, not 6.21 and 6.22.
- 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. I would suggest that 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 wireshark on a system that can capture 802.11
frames, 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.
Chapter 8
- Problem 8.x1: Read one of the following papers, as determined by the
initial letter 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 17th
USENIX Security Symposium, July 28-August 1, 2008.
- Last name starting with B
- All Your iFRAMEs Point to Us
- Last name starting with H
- Highly Predictive Blacklisting
- Last name starting with K
- Proactive Surge Protection: A Defense Mechanism for Bandwidth-Based Attacks
- Last name starting with S
- BotMiner: Clustering Analysis of Network Traffic for Protocol- and Structure-Independent Botnet Detection
- Last name starting with W
- To Catch a Predator: A Natural Language Approach for Eliciting Malicious Payloads
- Last name starting with Y
- Privacy-Preserving Location Tracking of Lost or Stolen Devices: Cryptographic Techniques and Replacing Trusted Third Parties with DHTs
- Problem 8.x2: Do review problems 8.r1 and 8.r3 from page
722, but label your answers as a single problem, 8.x2. In problem 8.r1, the question "can you have one without the other?" should be interpretated as meaning "is there some means of assuring one without assuring the other?" rather than "might an adversary choose to violate one without violating the other?".
- Problem 8.p6, p. 750.
- Problem 8.p9, p. 751.
- Problem 8.p10, p. 751.
- Problem 8.p11, p. 751. In part e, replace "in class" by "in Section 4.6.2."
Instructor: Max Hailperin