CSCI4211: Introduction to Computer Networks
Fall 2021
Homework Assignment 2
Due Wed Nov 14 11:55pm
Instructions:
1. Please submit your homework using the on-line electronic submission system (via the
class Convas site).
In case you could not use the on-line electronic submission system, please hand in
your homework to the instructors or TAs on the due day. Please email csci4211-
[email protected] to let us know that you have handed in a hard-copy of your
homework immediately afterwards. (Make sure that you also make and retain a copy
of your homework!)
Please make sure that you include your name and student id in your submission, and
retain a copy of your submission!
2. There are seven questions in total. The number of points for each question is given
in parentheses. There are 130 points in total. An estimated time for answering each
question is also given in parentheses. This is just a guideline, you may take less or
more time on each problem.
3. Partial credit is possible for an answer. Please try to be as concise and make your
homework as neat as possible. We must be able to read your handwriting in order to
be able to grade your homework.
4. Enjoy!
1. Short Questions and Answers: (10 points; 15 minutes)
(Two or three sentences would generally suffice.)
a. (2 points) Can we assign any arbitrary IP address to a computer connected to a
network? Please briefly explain your answer.
b. (2 points) A network on the Internet has a subnet mask of 255.255.224.0. What is
the maximum number of hosts it can handle?
c. (2 points) Can an IP packet loop forever inside an IP network even though there is a
cycle in the topology? Briefly explain your answer.
d. (2 points) When an IP host receives two IP datagrams, how can it tell that these
two IP datagrams are two IP datagram “fragments” belonging to one single original IP
datagram?
e. (2 points) Briefly explain why IP datagram re-assembly is done only at the destination
host, not by any intermediate IP router.
2. TCP Flow & Congestion Control (25 points total. Approx. 25 minutes)
(a) (4 points) Briefly describe how TCP congestion control works.
In answering the following questions, we assume that the TCP Reno version (the most
commonly used version in today’s Internet) is used, i.e., with the Fast Recover/Fast
Retransmit mechanisms implemented.]
(b) (7 points) Suppose that the current congestion window, CongWin, of a TCP connection
is currently at 12 KB, and threshold = 24 KB. During this round, the sender sends
8 TCP data segments, each of size 1500 bytes. [Here we assume that 1KB = 1000
bytes; and the TCP maximum segment size is 1500 bytes.] The last segment of these 8
data segments sent by the send carries the sequence number 2003000 (in decimal repre-
sentation, not binary representation). The sender then receives four acknowledgments
from the receiver, each acknowledging the receipt of two consecutive data segments.
In particular, the last acknowledgment from the receiver carries the acknowledgment
number 2004500. What will the sender set CongWin to at the end of this round?
(c) (7 points) Suppose that during the next round of data transmission after b., a time-out
event occurs at the sender side. What will be the value (in bytes) of CongWin after
this event? What will be the value (in bytes) of threshold?
1
(d) (7 points) Now consider a new scenario where the congestion window, CongWin, at the
sender side is currently set to 9 KB, and threshold = 9 KB. The sender then sends
6 data segments of 1500 bytes each (thus a total of 9 KB data is sent), where the
last data segment carries a sequence number 3001500 (in decimal representation, not
binary representation). After having sent these 6 data segments, the sender receives 3
acknowledgments from the receiver, each acknowledging the receipt of two consecutive
data segments. In particular, the last acknowledgment from the receiver carries the
acknowledgment number 3003000. What will the sender set CongWin to at the end?
What will be the value (in bytes) of threshold?
3. More on TCP Congestion Control (25 points total. Approx. 25 minutes)
a. (5 points) Briefly describe how TCP flow control works.
[In answering the following questions, we assume that the TCP Reno version (the most
commonly used version in today’s Internet) is used, i.e., with the Fast Recover/Fast Retrans-
mit mechanisms implemented.]
(20 points) Please Do Problem P40 a. b. c. d., Chapter 3 in the textbook (Kurose &
Ross, 7th & editions). In case you do not have the textbook, the problem is reproduced
below for you.
2
4. Longest Prefix matching (10 points total. Approx. 15 minutes)
Do Problem P8, Chapter 4 in the textbook, 8th edition (it is Problem P5, Chapter 4,
page 366, in the 7th edition). In case you do not have the textbook, the problem is reproduced
below for you.
3
5. MAC Address, ARP, Switching and IP Forwarding(25 points. Approx. 30 minutes)
Consider the following switched network (Figure 1), where we have one Ethernet switch
S, connecting three hosts, host H on port 1, host X on port 2 and host Z on port 3, as well
as an IP router R (default router for the hosts) on port 0. These hosts lie on an IP network
with the network prefix 127.64.1.0/24. The IP address for the interface of router R that is
connected to switch S is 127.64.1.254. The IP addresses for hosts H, X and Z are shown
in the figure. Furthermore, the current switch (forwarding) table at switch S and the ARP
caches at host X and router R are also shown in the figure.
Host X
Internet
Host Z
Router R
Switch S
port 0
port 1
port 3
port 2
Switch Table at B
R’s MAC addr
host port
0
1 H’s MAC addr
Server W
IP network
127.64.1.0/24
127.64.1.254
127.64.3.254
127.64.1.3 52.14.101.204
127.64.1.2
Host H
ARP cache at X
R’s MAC addr
IP MAC
127.64.1.254
127.64.1.1
127.64.1.1 H’s MAC addr
ARP cache at R
Z’s MAC addr
IP MAC
127.64.1.3
127.64.1.1 H’s MAC addr
Figure 1: Figure for Question 6.
(a) (9 points) Suppose host X wants to send an IP datagram to host Z, and assume that
host X knows the IP address of host Z (e.g., via DNS lookup).
• (3 points) Briefly explain how host X obtains the MAC address of host Z. Describe
how switch S handles the ARP request and response messages, and builds its
switch table.
• (3 points) Will router R also receive the ARP request? If your answer is affirma-
tive, what action does router R take? What about the ARP response message
from host Z?
• (3 points) After host X learns the MAC address of host Z. Briefly describe how
the IP datagram is delivered from host X to host Z, paying particular attention
to the actions taken by switch S, and router R if any.
(b) (7 points) Suppose host X sends an IP datagram to host H instead of host Z. Repeat
the above questions.
4
(c) (9 points) Suppose now that host X wants to send an IP datagram to a remote server W
outside the network. The IP address of sever W is 52.14.101.204. Answer the following
questions.
• (3 points) Since sever W’s MAC address is not currently in its ARP cache, will
host X issue an ARP request for server W? Briefly explain your answer.
• (3 points) How does X know that it should forward the IP datagram to router R
so that it can be delivered (via the Internet) to server W?
• (3 points) Briefly describe how the IP datagram is delivered from host X to router
R, paying in particular attention to the actions taken by switch S and router
R. Moreover, please explicitly describe the source and destination IP and MAC
addresses contained in the IP datagram and the encapsulating Ethernet frame.
5. Virtual Circuits (15 points total. Approx. 15 minutes)
Host H
Host F
Host G
Host A
3
Host C
2
2
0
Host J
1
Router 3
Host B
Host D
Router 1
Host M
Host L
Host E
Router 2
Router 4
3
2
1
03
2
0
1
0
4
4
3
3
0
2Router 5
Host N
Host K
Host I
1
1
Figure 2: Figure for Question 5.
(a) (5 points) What is the key difference between virtual circuit and circuit switching?
(one or two sentences should suffice!)
5
(b) (10 points) Consider the network shown in Figure 2, where the numbers beside the
links connecting hosts and routers represents the port numbers of the routers. Please
write down the virtual circuit translation tables for all the routers after the following
connections are established in the order given below. You can assume that the VCI
assignment always picks the lowest unused VCI on an outgoing link.
(1) Host A connects to host E.
(2) Host C connects to host J.
(3) Host C connects to host D.
(4) Host D connects to host G.
(5) Host E connects to host M.
7. (Optional Bonus Question) IP Forwarding, Default Router and ICMP Redirect
(20 points. Approx. 30 minutes)
Refer to Figure 3 and answer the following questions as concisely as you can. In answering
these questions, you’ll need to google and look up relevant information on ICMP Redirect,
e.g., on wikipedia.
a. (4 points) Consider the following scenario: host C in LAN2 wants to send an IP packet
to host B, which is connected to LAN1 (IP network prefix: 128.105.0.0/16). Since host B
is not on the same IP network as host C. Hence host C will send it to its default gateway
router R1. Describe the actions taken by router R1 (and subsequently at router R2) at both
the network layer and data link layer for sending this IP packet to host B. You can assume
that R1 has the MAC address of R2, and R2 has the MAC address of host B.
b. (4 points) Continue the scenario in problem 7.a: suppose host C wants to send another
IP packet to host B. Will host C still send it to router R1? Or will it send it to router R2?
(Hint: if you did not mention ICMP Redirect message in your answer to problem 7.a, your
answer is not complete].) Since host C does not have router R2’s MAC address. Describe
how host C obtains R2’s MAC address using the ARP protocol.
c. (4 points) Consider yet another scenario: suppose host C now wants to send an IP
packet to host A, which is connected to LAN3 (IP network prefix: 131.16.143.0/20). Host
C will send it to its default gateway router R1, which will send it to router R2, based on its
current routing table. Now let’s assume that, based on the routing table at router R2 (not
shown), it will send the packet to router R3 via its interface 2, namely, back to the same
interface where it comes from. Will router R2 send an ICMP Redirect message to router R1,
telling it to use R3 for destination network prefix 131.16.143.0/20? (Hint: ICMP messages are
always sent to the source IP address of an IP packet.) More basically, can the network layer
at router R2 tell whether router R1 or host C sends the packet to it? Briefly explain your
answer.
6
d. (4 points) Continue the scenario in problem 7.c: how will router R1 eventually know
that it can reach destination network prefix 131.16.143.0/20 directly via router R3 instead
of router R2? Namely, changing the next hop from R2 to R3?
e. (4 points) What might have happened that caused R1 to have a “non-optimal” route
entry that has router R2 as the next-hop to the destination network prefix 131.16.143.0/20
instead of router R3 in the first place?
Host A
Host B
Switch S1
Router R3
LAN1: 128.105.0.0/16
LAN3: 131.16.143.0/20
Switch S2
LAN2: 191.11.1.0/24
Host C
Host D
Wireless LAN: 109.11.12.8/24
2
1
1
1
2
23
Router R2
Router R1
3
Host D
Switch S4
LAN4: 112.10.128.0/20
R1’s IP addr R1’s MAC addr
Host C’s ARP cache
Destination n/w Next hop Interface
191.11.1.0/24 direct 1
112.10.128.0/20 direct 2
128.105.0.0/16 R2 1
131.16.143.0/20 R2 1
109.11.12.8/24 R2 1
R1’s routing table
Figure 3: Figure for Question 7.
7

欢迎咨询51作业君