Description
CMSC 440 – Homework Assignment 1
Questions:
You are required to answer the following questions from the attached document
“HomeAssign_1_Questions.pdf”:Question Question
P.2 P.20
P.3 P.23
P.4 P.25
P.6 P.31
P.8 P.33
P.10
P2. Equation 1.1 gives a formula for the end-to-end delay of sending one packet
of length L over N links of transmission rate R. Generalize this formula for
sending P such packets back-to-back over the N links.
P3. Consider an application that transmits data at a steady rate (for example, the
sender generates an N-bit unit of data every k time units, where k is small and
fixed). Also, when such an application starts, it will continue running for a
relatively long period of time. Answer the following questions, briefly justifying your answer:
a. Would a packet-switched network or a circuit-switched network be more
appropriate for this application? Why?
b. Suppose that a packet-switched network is used and the only traffic in
this network comes from such applications as described above. Furthermore, assume that the sum of the application data rates is less than the
capacities of each and every link. Is some form of congestion control
needed? Why?
P4. Consider the circuit-switched network in Figure 1.13. Recall that there are 4
circuits on each link. Label the four switches A, B, C and D, going in the
clockwise direction.
a. What is the maximum number of simultaneous connections that can be in
progress at any one time in this network?
b. Suppose that all connections are between switches A and C. What is the
maximum number of simultaneous connections that can be in progress?
c. Suppose we want to make four connections between switches A and C,
and another four connections between switches B and D. Can we route
these calls through the four links to accommodate all eight connections?
P6. This elementary problem begins to explore propagation delay and transmission delay, two central concepts in data networking. Consider two hosts, A
and B, connected by a single link of rate R bps. Suppose that the two hosts
are separated by m meters, and suppose the propagation speed along the link
is s meters/sec. Host A is to send a packet of size L bits to Host B.
a. Express the propagation delay, dprop, in terms of m and s.
b. Determine the transmission time of the packet, dtrans, in terms of L
and R.
c. Ignoring processing and queuing delays, obtain an expression for the endto-end delay.
d. Suppose Host A begins to transmit the packet at time t = 0. At time t = dtrans,
where is the last bit of the packet?
e. Suppose dprop is greater than dtrans. At time t = dtrans, where is the first bit of
the packet?
f. Suppose dprop is less than dtrans. At time t = dtrans, where is the first bit of
the packet?
g. Suppose s = 2.5 · 108, L = 120 bits, and R = 56 kbps. Find the distance m
so that dprop equals dtrans.
P8. Suppose users share a 3 Mbps link. Also suppose each user requires
150 kbps when transmitting, but each user transmits only 10 percent of the
time.
a. When circuit switching is used, how many users can be supported?
b. For the remainder of this problem, suppose packet switching is used. Find
the probability that a given user is transmitting.
c. Suppose there are 120 users. Find the probability that at any given time,
exactly n users are transmitting simultaneously. (Hint: Use the binomial
distribution.)
d. Find the probability that there are 21 or more users transmitting
simultaneously.
P10. Consider a packet of length L which begins at end system A and travels over
three links to a destination end system. These three links are connected by
two packet switches. Let di
, si
, and Ri denote the length, propagation speed,
and the transmission rate of link i, for i = 1, 2, 3. The packet switch delays
each packet by d
proc. Assuming no queuing delays, in terms of di
, si
, Ri
,
(i = 1,2,3), and L, what is the total end-to-end delay for the packet? Suppose
now the packet is 1,500 bytes, the propagation speed on all three links is 2.5 ·
108 m/s, the transmission rates of all three links are 2 Mbps, the packet switch
processing delay is 3 msec, the length of the first link is 5,000 km, the length
of the second link is 4,000 km, and the length of the last link is 1,000 km. For
these values, what is the end-to-end delay?
P20. Consider the throughput example corresponding to Figure 1.20(b). Now
suppose that there are M client-server pairs rather than 10. Denote Rs
, Rc
, and
R for the rates of the server links, client links, and network link. Assume all
other links have abundant capacity and that there is no other traffic in the
network besides the traffic generated by the M client-server pairs. Derive a
general expression for throughput in terms of Rs
, Rc
, R, and M.
P23. Consider Figure 1.19(a). Assume that we know the bottleneck link along the
path from the server to the client is the first link with rate Rs bits/sec. Suppose
we send a pair of packets back to back from the server to the client, and there
is no other traffic on this path. Assume each packet of size L bits, and both
links have the same propagation delay d
prop.
a. What is the packet inter-arrival time at the destination? That is, how much
time elapses from when the last bit of the first packet arrives until the last
bit of the second packet arrives?
b. Now assume that the second link is the bottleneck link (i.e., Rc < Rs
). Is it
possible that the second packet queues at the input queue of the second
link? Explain. Now suppose that the server sends the second packet T seconds after sending the first packet. How large must T be to ensure no
queuing before the second link? Explain.
P25. Suppose two hosts, A and B, are separated by 20,000 kilometers and are
connected by a direct link of R = 2 Mbps. Suppose the propagation speed
over the link is 2.5 ! 108 meters/sec.
a. Calculate the bandwidth-delay product, R ! dprop.
b. Consider sending a file of 800,000 bits from Host A to Host B. Suppose
the file is sent continuously as one large message. What is the maximum
number of bits that will be in the link at any given time?
c. Provide an interpretation of the bandwidth-delay product.
d. What is the width (in meters) of a bit in the link? Is it longer than a football field?
e. Derive a general expression for the width of a bit in terms of the propagation speed s, the transmission rate R, and the length of the link m.
P31. In modern packet-switched networks, including the Internet, the source host
segments long, application-layer messages (for example, an image or a music
file) into smaller packets and sends the packets into the network. The receiver
then reassembles the packets back into the original message. We refer to this
process as message segmentation. Figure 1.27 illustrates the end-to-end
transport of a message with and without message segmentation. Consider a
message that is 8 · 106 bits long that is to be sent from source to destination in
Figure 1.27. Suppose each link in the figure is 2 Mbps. Ignore propagation,
queuing, and processing delays.
a. Consider sending the message from source to destination without message
segmentation. How long does it take to move the message from the source
host to the first packet switch? Keeping in mind that each switch uses
store-and-forward packet switching, what is the total time to move the
message from source host to destination host?
b. Now suppose that the message is segmented into 800 packets, with each
packet being 10,000 bits long. How long does it take to move the first
packet from source host to the first switch? When the first packet is being
sent from the first switch to the second switch, the second packet is being
sent from the source host to the first switch. At what time will the second
packet be fully received at the first switch?
c. How long does it take to move the file from source host to destination host
when message segmentation is used? Compare this result with your
answer in part (a) and comment.
d. In addition to reducing delay, what are reasons to use message segmentation?
e. Discuss the drawbacks of message segmentation.
P33. Consider sending a large file of F bits from Host A to Host B. There are three
links (and two switches) between A and B, and the links are uncongested (that
is, no queuing delays). Host A segments the file into segments of S bits each and
adds 80 bits of header to each segment, forming packets of L = 80 + S bits. Each
link has a transmission rate of R bps. Find the value of S that minimizes the
delay of moving the file from Host A to Host B. Disregard propagation delay.
Submission Materials:
• Submit your answers through Canva as a single PDF file
CMSC 440 -Homework Assignment 2
Questions:
You are required to ONLY answer the following questions from the attached
questions document “HomeAssign_2_Questions.pdf”:
Question
P.4
P.5
P.7
P.8
P.9
P.10
P4. Consider the following string of ASCII characters that were captured by Wireshark when the browser sent an HTTP GET message (i.e., this is the actual content of an HTTP GET message). The characters are carriage return and line-feed characters (that is, the italized character string in the text below represents the single carriage-return character that was contained at that point in the HTTP header). Answer the following questions, indicating where in the HTTP GET message below you find the answer.
GET /cs453/index.html HTTP/1.1Host: gai a.cs.umass.eduUser-Agent: Mozilla/5.0 ( Windows;U; Windows NT 5.1; en-US; rv:1.7.2) Gec ko/20040804 Netscape/7.2 (ax) Accept:ex t/xml, application/xml, application/xhtml+xml, text /html;q=0.9, text/plain;q=0.8,image/png,*/*;q=0.5 Accept-Language: en-us,en;q=0.5AcceptEncoding: zip,deflateAccept-Charset: ISO -8859-1,utf-8;q=0.7,*;q=0.7Keep-Alive: 300 Connection:keep-alive a. What is the URL of the document requested by the browser? b. What version of HTTP is the browser running? c. Does the browser request a non-persistent or a persistent connection? d. What is the IP address of the host on which the browser is running? e. What type of browser initiates this message? Why is the browser type needed in an HTTP request message?
P5. The text below shows the reply sent from the server in response to the HTTP GET message in the question above. Answer the following questions, indicating where in the message below you find the answer. 172 CHAPTER 2 • APPLICATION LAYER HTTP/1.1 200 OKDate: Tue, 07 Mar 2008 12:39:45GMTServer: Apache/2.0.52 (Fedora) Last-Modified: Sat, 10 Dec2005 18:27:46 GMTETag: “526c3-f22-a88a4c80”AcceptRanges: bytesContent-Length: 3874 Keep-Alive: timeout=max=100Connection: Keep-AliveContent-Type: text/html; charset= ISO-8859-1<!doctype html public “- //w3c//dtd html 4.0 transitional//en”>a. Was the server able to successfully find the document or not? What time was the document reply provided? b. When was the document last modified? c. How many bytes are there in the document being returned? d. What are the first 5 bytes of the document being returned? Did the server agree to a persistent connection?
P7. Suppose within your Web browser you click on a link to obtain a Web page.
The IP address for the associated URL is not cached in your local host, so a
DNS lookup is necessary to obtain the IP address. Suppose that n DNS
servers are visited before your host receives the IP address from DNS; the
successive visits incur an RTT of RTT1, . . ., RTTn. Further suppose that the
Web page associated with the link contains exactly one object, consisting of a
small amount of HTML text. Let RTT0 denote the RTT between the local host
and the server containing the object. Assuming zero transmission time of the
object, how much time elapses from when the client clicks on the link until
the client receives the object?
P8. Referring to Problem P7, suppose the HTML file references eight very small
objects on the same server. Neglecting transmission times, how much time
elapses with
a. Non-persistent HTTP with no parallel TCP connections?
b. Non-persistent HTTP with the browser configured for 5 parallel connections?
c. Persistent HTTP?
P9. Consider Figure 2.12, for which there is an institutional network connected to
the Internet. Suppose that the average object size is 850,000 bits and that the
average request rate from the institution’s browsers to the origin servers is 16
requests per second. Also suppose that the amount of time it takes from when
the router on the Internet side of the access link forwards an HTTP request
until it receives the response is three seconds on average (see Section 2.2.5).
Model the total average response time as the sum of the average access delay
(that is, the delay from Internet router to institution router) and the average
Internet delay. For the average access delay, use ∆/(1 – ∆!), where ∆ is the
average time required to send an object over the access link and ! is the
arrival rate of objects to the access link.
a. Find the total average response time.
b. Now suppose a cache is installed in the institutional LAN. Suppose the
miss rate is 0.4. Find the total response time.
P10. Consider a short, 10-meter link, over which a sender can transmit at a rate of
150 bits/sec in both directions. Suppose that packets containing data are
100,000 bits long, and packets containing only control (e.g., ACK or handshaking) are 200 bits long. Assume that N parallel connections each get 1/N
of the link bandwidth. Now consider the HTTP protocol, and suppose that
each downloaded object is 100 Kbits long, and that the initial downloaded
object contains 10 referenced objects from the same sender. Would parallel
downloads via parallel instances of non-persistent HTTP make sense in this
case? Now consider persistent HTTP. Do you expect significant gains over
the non-persistent case? Justify and explain your answer.
CMSC 440 – Homework Assignment 3
Questions:
You are required to answer the following questions from the attached document:
Question Question
P.6 P.27
P.15 P.37
P.17 P.40
P.22 P.44
P.25
P6. Consider our motivation for correcting protocol rdt2.1. Show that the
receiver, shown in Figure 3.57, when operating with the sender shown in Figure 3.11, can lead the sender and receiver to enter into a deadlock state, where
each is waiting for an event that will never occur.
P15. Consider the cross-country example shown in Figure 3.17. How big would
the window size have to be for the channel utilization to be greater than 98
percent? Suppose that the size of a packet is 1,500 bytes, including both
header fields and data.
P17. Consider two network entities, A and B, which are connected by a perfect bidirectional channel (i.e., any message sent will be received correctly; the
channel will not corrupt, lose, or re-order packets). A and B are to deliver
data messages to each other in an alternating manner: First, A must deliver a
message to B, then B must deliver a message to A, then A must deliver a message to B and so on. If an entity is in a state where it should not attempt to
deliver a message to the other side, and there is an event like
rdt_send(data) call from above that attempts to pass data down for
transmission to the other side, this call from above can simply be ignored
with a call to rdt_unable_to_send(data), which informs the higher
layer that it is currently not able to send data. [Note: This simplifying
assumption is made so you don’t have to worry about buffering data.]
Draw a FSM specification for this protocol (one FSM for A, and one FSM for
B!). Note that you do not have to worry about a reliability mechanism here;
the main point of this question is to create a FSM specification that reflects
the synchronized behavior of the two entities. You should use the following
events and actions that have the same meaning as protocol rdt1.0 in
Figure 3.9: rdt_send(data), packet = make_pkt(data),
udt_send(packet), rdt_rcv(packet), extract
(packet,data), deliver_data(data). Make sure your protocol
reflects the strict alternation of sending between A and B. Also, make sure to
indicate the initial states for A and B in your FSM descriptions.
P22. Consider the GBN protocol with a sender window size of 4 and a sequence
number range of 1,024. Suppose that at time t, the next in-order packet that the
receiver is expecting has a sequence number of k. Assume that the medium
does not reorder messages. Answer the following questions:
a. What are the possible sets of sequence numbers inside the sender’s window at time t? Justify your answer.
b. What are all possible values of the ACK field in all possible messages currently propagating back to the sender at time t? Justify your answer.
P25. We have said that an application may choose UDP for a transport protocol
because UDP offers finer application control (than TCP) of what data is sent
in a segment and when.
a. Why does an application have more control of what data is sent in a segment?
b. Why does an application have more control on when the segment is sent?
P27. Host A and B are communicating over a TCP connection, and Host B has
already received from A all bytes up through byte 126. Suppose Host A then
sends two segments to Host B back-to-back. The first and second segments
contain 80 and 40 bytes of data, respectively. In the first segment, the
sequence number is 127, the source port number is 302, and the destination
port number is 80. Host B sends an acknowledgment whenever it receives a
segment from Host A.
a. In the second segment sent from Host A to B, what are the sequence number, source port number, and destination port number?
b. If the first segment arrives before the second segment, in the acknowledgment of the first arriving segment, what is the acknowledgment number,
the source port number, and the destination port number?
c. If the second segment arrives before the first segment, in the acknowledgment of the first arriving segment, what is the acknowledgment
number?
d. Suppose the two segments sent by A arrive in order at B. The first acknowledgment is lost and the second acknowledgment arrives after the first timeout interval. Draw a timing diagram, showing these segments and all other
segments and acknowledgments sent. (Assume there is no additional packet
loss.) For each segment in your figure, provide the sequence number and
the number of bytes of data; for each acknowledgment that you add, provide the acknowledgment number.
P37. Compare GBN, SR, and TCP (no delayed ACK). Assume that the timeout
values for all three protocols are sufficiently long such that 5 consecutive data
segments and their corresponding ACKs can be received (if not lost in the
channel) by the receiving host (Host B) and the sending host (Host A) respectively. Suppose Host A sends 5 data segments to Host B, and the 2nd segment
(sent from A) is lost. In the end, all 5 data segments have been correctly
received by Host B.
a. How many segments has Host A sent in total and how many ACKs has
Host B sent in total? What are their sequence numbers? Answer this question for all three protocols.
b. If the timeout values for all three protocol are much longer than 5 RTT,
then which protocol successfully delivers all five data segments in shortest
time interval?
P40. Consider Figure 3.58. Assuming TCP Reno is the protocol experiencing the
behavior shown above, answer the following questions. In all cases, you
should provide a short discussion justifying your answer.
a. Identify the intervals of time when TCP slow start is operating.
b. Identify the intervals of time when TCP congestion avoidance is
operating.
c. After the 16th transmission round, is segment loss detected by a triple
duplicate ACK or by a timeout?
d. After the 22nd transmission round, is segment loss detected by a triple
duplicate ACK or by a timeout?
e. What is the initial value of ssthresh at the first transmission round?
f. What is the value of ssthresh at the 18th transmission round?
g. What is the value of ssthresh at the 24th transmission round?
h. During what transmission round is the 70th segment sent?
i. Assuming a packet loss is detected after the 26th round by the receipt of a
triple duplicate ACK, what will be the values of the congestion window
size and of ssthresh?
0
0 2 4 6 8 10 12
Transmission round
14 16 18 20 22 24 26
5
10
15
20
25
Congestion window size (segments)
30
35
40
45
Figure 3.58 ! TCP window size as a function of time
j. Suppose TCP Tahoe is used (instead of TCP Reno), and assume that triple
duplicate ACKs are received at the 16th round. What are the ssthresh
and the congestion window size at the 19th round?
k. Again suppose TCP Tahoe is used, and there is a timeout event at 22nd
round. How many packets have been sent out from 17th round till 22nd
round, inclusive?
P44. Consider sending a large file from a host to another over a TCP connection
that has no loss.
a. Suppose TCP uses AIMD for its congestion control without slow start.
Assuming cwnd increases by 1 MSS every time a batch of ACKs is received
and assuming approximately constant round-trip times, how long does it take
for cwnd increase from 6 MSS to 12 MSS (assuming no loss events)?
b. What is the average throughout (in terms of MSS and RTT) for this connection up through time = 6 RTT?
Submission Materials:
• Submit your answers through Canva as a single PDF file
CMSC 440 – Homework Assignment 4
Questions:
You are required to answer the following questions from the attached document:
Question Question
P.4 (only
parts a & b)
P.17
P.10 P.19
P.12 P.21
P.13 P.26
P4. Consider the network below.
a. Suppose that this network is a datagram network. Show the forwarding
table in router A, such that all traffic destined to host H3 is forwarded
through interface 3.
b. Suppose that this network is a datagram network. Can you write down a
forwarding table in router A, such that all traffic from H1 destined to host
H3 is forwarded through interface 3, while all traffic from H2 destined to
host H3 is forwarded through interface 4? (Hint: this is a trick question.)
P10. Consider a datagram network using 32-bit host addresses. Suppose a router
has four links, numbered 0 through 3, and packets are to be forwarded to the
link interfaces as follows:
Destination Address Range Link Interface
11100000 00000000 00000000 00000000
through 0
11100000 00111111 11111111 11111111
11100000 01000000 00000000 00000000
through 1
11100000 01000000 11111111 11111111
11100000 01000001 00000000 00000000
through 2
11100001 01111111 11111111 11111111
otherwise 3
a. Provide a forwarding table that has five entries, uses longest prefix matching, and forwards packets to the correct link interfaces.
b. Describe how your forwarding table determines the appropriate link interface for datagrams with destination addresses:
11001000 10010001 01010001 01010101
11100001 01000000 11000011 00111100
11100001 10000000 00010001 01110111
P12. Consider a datagram network using 8-bit host addresses. Suppose a
router uses longest prefix matching and has the following forwarding
table:Prefix Match Interface
1 0
10 1
111 2
otherwise 3
For each of the four interfaces, give the associated range of destination host
addresses and the number of addresses in the range.
P13. Consider a router that interconnects three subnets: Subnet 1, Subnet 2, and
Subnet 3. Suppose all of the interfaces in each of these three subnets are
required to have the prefix 223.1.17/24. Also suppose that Subnet 1 is
required to support at least 60 interfaces, Subnet 2 is to support at least 90
interfaces, and Subnet 3 is to support at least 12 interfaces. Provide three network addresses (of the form a.b.c.d/x) that satisfy these constraints.
P17. Consider the topology shown in Figure 4.17. Denote the three subnets with
hosts (starting clockwise at 12:00) as Networks A, B, and C. Denote the subnets without hosts as Networks D, E, and F.
a. Assign network addresses to each of these six subnets, with the following constraints: All addresses must be allocated from 214.97.254/23;
Subnet A should have enough addresses to support 250 interfaces; Subnet B should have enough addresses to support 120 interfaces; and
Subnet C should have enough addresses to support 120 interfaces. Of
course, subnets D, E and F should each be able to support two interfaces.
For each subnet, the assignment should take the form a.b.c.d/x or
a.b.c.d/x – e.f.g.h/y.
b. Using your answer to part (a), provide the forwarding tables (using longest
prefix matching) for each of the three routers.
P19. Consider sending a 2400-byte datagram into a link that has an MTU of
700 bytes. Suppose the original datagram is stamped with the identification number 422. How many fragments are generated? What are the
values in the various fields in the IP datagram(s) generated related to
fragmentation?
P21. Consider the network setup in Figure 4.22. Suppose that the ISP instead
assigns the router the address 24.34.112.235 and that the network address of
the home network is 192.168.1/24.
a. Assign addresses to all interfaces in the home network.
b. Suppose each host has two ongoing TCP connections, all to port 80 at
host 128.119.40.86. Provide the six corresponding entries in the NAT
translation table.
P26. Consider the following network. With the indicated link costs, use Dijkstra’s
shortest-path algorithm to compute the shortest path from x to all network
nodes. Show how the algorithm works by computing a table similar to
Table 4.3.