Tutorial 1 Answer
Tutorial 1 Solutions (Week 5)
Section I – Multiple Choice, Fill-in Questions
1. List the four different types of delays encountered in packet switched networks:
a. processing delay
b. queuing delay
c. transmission delay
d. propagation delay
2. Consider the operation of downloading a Web page consisting of an index page that references 3
JPEG objects located on the same server. Ignoring latency involved in transferring the objects
themselves, fill in the blanks below with the correct values:
a. Utilizing HTTP/1.0 with no parallel connection capability, the number of RTTs required
to download the page is 8RTT.
b. Utilizing HTTP/1.1 with pipelining, 3 RTTs are required to download the page.
3. DNS responses have a TTL field. Why is this necessary?
a. The TTL field is decremented at each DNS server that the response passes through on its
way to the client, and servers drop responses with a TTL of 0, so the TTL field prevents
responses from looping indefinitely.
b. The TTL field allows DNS servers to prevent cache poisoning.
c. The TTL field is necessary for tracking the number of DNS servers involved in resolving
the query.
d. The TTL field causes DNS servers to delete entries after some time, so that if the
host moves and the underlying address changes, the server will eventually get the
correct address.
4. Transport layer may be able to provide reliability by using its own mechanisms, despite working
over an unreliable network layer.
a. True.
b. False.
5. UDP has which of the following characteristics:
a. Three-way hand shake for connection establishment.
b. Connection state at the server.
c. Regulated send rate.
d. None of the above.
Section II – Problem Solving
1. Calculate the end-to-end delay, dend-end, between the source host and the destination host in a network
with 4 routers between source and destination? Assume that the network is NOT congested (i.e. dqueue
is insignificant), and that:
a. all packets are 10,000 bits in length,
b. each link is 5 kilometers long,
c. the processing time is 10msec at the source host and at each router,
d. the transmission rate of each link is 1Mbps,
e. the propagation speed of each link is 2.5 x 108 meters/second.
CALCULATIONS:
The delay along one hop = dproc+dprop+dtrans=10msec+5×103/2.5×108 + 10,000/1 x 106 = 10 msec +
0.02msec + 10msec = 20.02 msec
The packet will be transmitted along 5 hops (first hop is from the source, and once at each router).
Thus, the end-to-end delay = 5 x 20.02 = 100.1 msec
2. UDP and TCP use 1s complement for their checksums. Suppose you have the following three 8-bit
bytes: 01010101, 01110000, 01001100. What is the 1’s complement of the sum of these 8-bit bytes?
(Note although TCP and UDP use 16-bit words in computing the checksum, for this problem we will
only consider 8-bit summands). Show all work. Is it possible that a 1-bit error will go undetected by
the checksum? How about a two-bit error?
Answer:
0 1 0 1 0 1 0 1
+ 0 1 1 1 0 0 0 0
1 1 0 0 0 1 0 1
+ 0 1 0 0 1 1 0 0
0 0 0 1 0 0 1 0
The last addition has an overflow so we add it to the above sum resulting in a final result of 00010010.
One’s complement of this is 11101101 which is the final checksum value.
All one-bit errors will be detected by checksum, but two-bit errors can be undetected (e.g. if the last
digit of the first word is converted to a zero and the last digit of the second word is converted to a 1).
3. Answer these questions in a concise manner. A few sentences (2-3) should suffice.
(a) List one advantage and one disadvantage of using a text-based header (as in HTTP) instead of a
binary format (as in IP and TCP).
Advantages: A text-based header is easier for human beings to read and debug. Text-based headers are
also extensible.
Disadvantages: However, they are verbose (i.e., waste bandwidth) and harder to parse. IP use a binary
format to limit the bandwidth consumed by the header, and to simplify parsing at the router, which must
process packets very quickly (e.g., within a few nanoseconds on high-speed links). In fact, big-header
size needs to be compressed for many low-bandwidth/low-power communication.
(b) Web caches and content distribution networks (CDNs) both reduce the time for a client to download
Web pages by moving content closer to the users. Give two reasons why CDNs have been more widely
deployed (and successful) than Web caching?
Answer: The content providers can contract with CDNs to deliver their content, which improves
performance, reduces cost, and makes their site robust to unexpected surges in demand. In contrast, the
content provider cannot require millions of sites throughout the world to deploy proxy servers.
Also, proxies cannot cache all content. Some content is un-cacheable because it is dynamically generated.
CDNs can run the server software that generates the dynamic content.
4(a)
Seq Type Data
1 Q vid1.streaming.uefa.org (A)
2 Q vid1.streaming.uefa.org (A)
3 R R3 (NS), R4 (A)
4 Q vid1.streaming.uefa.org (A)
5 R R5 (NS), R6 (A)
6 Q vid1.streaming.uefa.org (A)
7 R R7 (NS), R8 (A)
8 Q vid1.streaming.uefa.org (A)
9 R R9 (CNAME) + R10 (A)
10 R R9 (CNAME) + R10 (A)
4(b)
After 2 minutes, all records other than R7, R8, R9 and R10 would be cached at the local DNS server.
This is because R7, R8, R9 and R10 have a TTL of 10 seconds. Hence, the sequence of queries would be
as follows:
Seq Type Data
1 Q vid1.streaming.uefa.org (A)
2 Q vid1.streaming.uefa.org (A)
3 R R7 (NS) + R8 (A)
4 Q vid1.streaming.uefa.org (A)
5 R R9 (CNAME) + R10 (A)
6 R R9 (CNAME) + R10 (A)
5. Two hosts located at two ends of a continent are trying to transfer data using a window based reliable
transport protocol (for pipelining). Suppose that the one-way propagation delay between the hosts is 15
milliseconds. If the hosts are using packets of length 1500 bytes over a 1 Gbps transmission link, how
big the window size must be for the channel utilization to be greater than 98%?
0.98=X (L/R)/(RTT+L/R)
0.98=X ((1500*8)/10^9))/(30*10^-3 + (1500*8)/10^9)
=2450 packets
6. Consider the circular DHT with shortcuts in Figure below, where each node in the DHT also keeps
track of (i) its immediate predecessor, (ii) its immediate successor, and (iii) its second successor (i.e., the
successor of the node’s immediate successor).
a) Suppose that peer 1 wants to learn where file with content ID 9 is stored. Write down the sequence
of DHT protocol messages that the nodes exchange until peer 1 discovers the location of the file.
Answer: The file is located at Peer 10. So, the sequence of queries would be as follows: Peer1-
>Peer4->Peer8->Peer10
b) Suppose that peer 3 learns that peer 5 has left. How does peer 3 update its successor state
information?
Answer: Peer 3 would ask Peer 4 (its immediate successor) for its two successors. Peer 4 would
reply indicating Peer 5 and 8 (or 8 and 10 if peer 4 has already updated its records). Peer 3 would
then update its second successor to be Peer 8.
Now consider that the DHT nodes do not keep track of their second successor (the figure should look
like simple circular DHT as in lecture notes). Suppose that a new peer 6 wants to join the DHT and
peer 6 initially only knows the IP address of peer 15. What steps are taken?
Answer: Peer 6 will contact Peer 15 with a join request. Peer 15, whose successor is Peer 1, knows that
Peer 6 should not be its successor. Peer 15 will forward the join request from Peer 6 to Peer 1. Peer 1,
whose successor is Peer 3, knows that Peer 6 should not be its successor. Peer 1 will forward the join
request from Peer 6 to Peer 3. The actions of Peers 3 and 4 are identical to those of Peers 15 and 1. The
join request will finally arrive at Peer 5. Peer 5 knows that its current successor is Peer 8, therefore peer
6 should become its new successor. Peer 5 will let peer 6 knows that its successor is Peer 8. At the same
time, Peer 5 updates its successor to be Peer 6.
7. Consider a TCP connection between sender A and receiver B. Sender A sends a 900 byte TCP
segment (including 20 bytes of TCP header) with sequence number 3100. What acknowledgement
number will receiver B reply with to inform sender A that it has received this segment correctly and in
order? (Ignore the possibility of a cumulative ack for this question.)
Answer:
Data contained in the Segment is 900 – 20=880 Bytes. Sequence Number = 3100 (pointing towards first
byte of data). Ack = 3100+880 = 3980.
8. Given that the previously calculated values for Estimated RTT and RTT Deviation are as shown
below, and that the new sample RTT shown has just been measured, what Timeout interval will TCP use
for the next transmitted segment?
i. EstimatedRTT (k) = 4 ms
ii. DevRTT (k) = 2 ms
iii. New SampleRTT = 8 ms
iv. a = .125
v. b = .25
Answer:
DevRTT = (1- b ) (DevRTT) + b | New SampleRTT – Estimated RTT | = (1-0.25)(2) + 0.25(8-4) = 2.5
ms
Estimated RTT = (1- a ) EstimatedRTT + a (New SampleRTT) = (1-0.125)(4) + 0.125(8) = 4.5 ms
Timeout = 4.5 + 4(2.5) = 14.5 ms
9. A host A establishes a TCP connection with host B. Host A transfer 200 Bytes of data to host B in a
single TCP segment that is successfully received and acknowledged by B. Host B then transfers 1000
Bytes of data to host A in a single segment that A acknowledges. Host B then closes the connection by
issuing a FIN that is acknowledged by host A. Host A now issues a FIN segment that is acknowledged
by B. Assume that the Initial Sequence Numbers (ISN) used by host A and B are 33000 and 55000, what
are the sequence numbers used by A and B in their final ACK send in response to the FIN segment from
the other side? How many total segments are sent out by A and B in this interaction?
Segment
No
Type Sender Receiver SeqNo AckNo
1 SYN A B 33000 NA
2 SYN/ACK B A 55000 33001
3 ACK A B 33001 55001
4 DATA A B 33001 55001
5 ACK B A 55001 33201
6 DATA B A 55001 33201
7 ACK A B 33201 56001
8 FIN B A 56001 33201
9 ACK A B 33201 56002
10 FIN A B 33201 56002
11 ACK B A 56002 33202