COMP3234 Computer and Communication Networks
Assignment 3 (10%)
Due by: 23:59 Friday April 24, 2020
Total mark is 100.
1. (20 marks) [IP (Learning Outcomes 1, 2, 5)]
Consider a router with 5 interfaces that interconnects five subnets, numbered 0 through 4.
Suppose that Subnets 0 and 1 are each required to support up to 125 interfaces, Subnets 2
and 3 are each required to support up to 60 interfaces, and Subnet 4 is required to support
up to 290 interfaces. Also suppose IP addresses of all the interfaces in all subnets are
required to have prefix 221.1.8.0/21.
(1) Assign network addresses in the form a.b.c.d/x for the five subnets (Hint: a network
address is like 200.23.16.0/23 that we give on page 27 of lecture slides
10_Network_I_COMP3234_s2020.pdf), which lead to smallest subnets satisfying the above
requirements.
(2) Based on the network addresses you gave, provide a forwarding table for the router,
which has five entries and can be used to forward each datagram (destined to each subnet)
to the correct link interface based on longest prefix matching.
2. (23 marks) [NAT (Learning Outcomes 2, 5)]
Consider two hosts participating in a peer-to-peer application to request data from each other, as
shown in the following figure. Each host is connected to the Internet via a NAT-enabled router.
The external IP addresses of the two routers are given in the figure. Suppose each of the hosts
runs a server process on port 8372 and a client process on port 2563. When host A requests data
from host B, host A’s client process sends the request to the server process on host B; and when
host B requests data from host A, host B’s client process sends the request to the server process
on host A.
(1) Suppose host A resides in an institutional network 172.16.0.0/12 and host B resides in a home
network 192.168.0.0/16. Allocate an IP address to host A’s interface, router 1’s interface i, host
B’s interface, router 2’s interface j, respectively.
(2) What technology needs to be adopted to enable host A (or B) to serve as a server behind a
NAT-enabled router? What rule needs to be installed on router 1 and router 2, respectively?
(3) Consider host A is sending a request to host B. Use the assigned IP addresses and the installed
rules in previous questions. Complete the mapping to be added to the NAT translation table on
router 1 (you can assign the WAN side port number yourself):
NAT Translation Table on Router 1
WAN side LAN side
Give the following information in the request sent out from host A, in the request after it has
passed through router 1, and in the request after it has passed through router 2:
Request sent out from host A
Source IP address:
Source port number:
Destination IP address:
Destination port number:
Request sent out from router 1
Source IP address:
Source port number:
Destination IP address:
Destination port number:
Request sent out from router 2
Source IP address:
Source port number:
Destination IP address:
Destination port number:
Give the following information in the response sent out from host B, in the response after it has
passed through router 2, and in the response after it has passed through router 1.
Response sent out from host B
Source IP address:
Source port number:
Destination IP address:
Destination port number:
Response sent out from router 2
Source IP address:
Source port number:
Destination IP address:
Destination port number:
Response sent out from router 1
Source IP address:
Source port number:
Destination IP address:
Destination port number:
3. (18 marks) [Dijkstra’s Algorithm (Learning Outcome 3)]
Consider the network given below, where we assume that the costs are the same in both
directions. Use Dijkstra’s algorithm to compute the least-cost paths from node A to each of
the other nodes in the network, by completing the table to illustrate each step of the
algorithm. (Note: N’ is the set of nodes whose least-cost paths are known; D(x) is the current
estimate of the least path cost from node A to node x; p(x) is the predecessor node of x
along the current least-cost path from node A to node x.)
Step N’ D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F) D(G),p(G) D(H),p(H)
0
4. (21 marks) [Bellman-Ford Algorithm (Learning Outcome 3)]
Consider the network given below, where we assume that the costs are the same in both
directions. Use the Bellman-Ford algorithm to find the least-cost path between each pair of
nodes, by completing the tables in each iteration of the algorithm. Assume all nodes run the
algorithm in a synchronous fashion.
2 (20 marks) [TCP/IP Protocol (ILO1)]
Consider the 60-byte dump of an IP datagram containing a TCP segment below (in hexadecimal format):
1 4500 003c 2dcb 4000 4006 db41 c0a8 19ca
2 9308 c434 e009 60e0 3dcf 472a c154 0161
3 8018 0089 31de 0000 0101 080a 04e6 1008
4 5be3 f7d1 0000 0004 434e 4f50
List all the TCP and IP fields in the datagram, as well as their corresponding values (give a meaningful
value if taught in the lectures; otherwise, give the value in hexadecimal format).
Note: the 4-bit header length field in an IP datagram describes how big the IP header is in 32-bit words.
3 (15 marks) [Dijkstra’s Algorithm (ILO3)]
Consi er the etwork given below, where we assume that the costs are the sa e in both directions. Use
Dijkstra’s algorithm to compute the least-cost paths from node A to each of the other nodes in the network,
by completing the table to illustrate each step of the algorithm.
(Note: N’ is the set of nodes whose least-cost paths are known; D(x) is the current estimate of the least
path cost from node A to node x; p(x) is the pr decessor node of x along the current least-cost path from
node A to node x.)
Step N’ D(B), p(B) D(C), p(C) D(D), p(D) D(E), p(E) D(F ), p(F ) D(G), p(G) D(H), p(H)
0
4 (15 marks) [Bellman-Ford Algorithm (ILO3)]
Consider the same network as given in the previous question. Use the Bellman-Ford algorithm to find the
least-cost path from node B, C, D, E, F, G, H to node A, by completing the table to illustrate each step
of the algorithm.
(Note: D(x) denotes the current estimate of the least path cost from node x to node A; S(x) denotes the
successor node of x along the current least-cost path from node x to node A. Assume all nodes run the
algorithm in a synchronous fashion.)
Step D(B), S(B) D(C), S(C) D(D), S(D) D(E), S(E) D(F ), S(F ) D(G), S(G) D(H), S(H)
0
2
Node A’s table:
A B C D E
A
B
C
Node B’s table:
A B C D E
A
B
C
D
Node C’s table:
A B C D E
A
B
C
D
E
Node D’s table:
A B C D E
B
C
D
E
Node E’s table:
A B C D E
C
D
E
5. (18 marks) [Hierarchical Routing in the Internet (Learning Outcomes 2, 3)]
Consider the network shown below. Suppose AS3 and AS2 are running OSPF as their intra-AS
routing protocol. Suppose AS1 and AS4 are running RIP as their intra-AS routing protocol.
Suppose eBGP and iBGP are used for inter-AS routing. Initially suppose there is no physical
link between AS2 and AS4. Suppose the costs of all links are the same.
(1) Router 3a learns about network prefix x from which routing protocol (directly): OSPF, RIP,
eBGP, or iBGP?
(2) Router 1d learns about network prefix x from which routing protocol (directly): OSPF, RIP,
eBGP, or iBGP?
(3) Router 2a learns about network prefix x from which routing protocol (directly): OSPF, RIP,
eBGP, or iBGP?
(4) Give the entry (x, I) that router 1d puts in its forwarding table, once it learns about
network prefix x. Explain how you decide I.
(5) Now suppose that there is a physical link between AS2 and AS4, shown by the dotted line.
Suppose router 1d learns that network prefix x is accessible via AS2 as well as via AS3.
Consider that AS path with a smaller AS hop number is preferred first, and then an intra-AS
path with the smallest cost to the respective gateway router connected to the NEXT-HOP of
the AS path should be chosen. Will I in the entry (x, I) in router 1d’s forwarding table change?
Explain your answer.
(6) Now suppose there is another AS, called AS5, which lies on the path between AS2 and
AS4 (not shown in diagram). Suppose router 1d learns that network prefix x is accessible via
AS path AS2 AS5 AS4 as well as via AS path AS3 AS4. What will I be set to then? Explain your
answer.
reach a stable state again? Justify your answer.
c. How do you modify c(y, z) such that there is no count-to-infinity problem at all if c(y,x)
changes from 4 to 60?
P12. Describe how loops in paths can be detected in BGP.
P13. Will a BGP router always choose the loop-free route with the shortest ASpath length?
Justify your answer.
P14. Consider the network shown below. Suppose AS3 and AS2 are running OSPF for their
intra-AS routing protocol. Suppose AS1 and AS4 are running RIP for their intra-AS routing
protocol. Suppose eBGP and iBGP are used for the inter-AS routing protocol. Initially suppose
there is no physical link between AS2 and AS4.
a. Router 3c learns about prefix x from which routing protocol: OSPF, RIP, eBGP, or iBGP?
b. Router 3a learns about x from which routing protocol?
c. Router 1c learns about x from which routing protocol?
d. Router 1d learns about x from which routing protocol?
P15. Referring to the previous problem, once router 1d learns about x it will put an entry (x, I) in
its forwarding table.
a. Will I be equal to I or I for this entry? Explain why in one sentence.
b. Now suppose that there is a physical link between AS2 and AS4, shown by the dotted
line. Suppose router 1d learns that x is accessible via AS2 as well as via AS3. Will I be
set to I or I ? Explain why in one sentence.
c. Now suppose there is another AS, called AS5, which lies on the path between AS2 and
AS4 (not shown in diagram). Suppose router 1d learns that x is accessible via AS2 AS5
AS4 as well as via AS3 AS4. Will I be set to I or I ? Explain why in one sentence.
1 2
1 2
1 2
Submission:
You can write your answers in a word document or other document at your choice. Please
convert your answer document to a a3-yourstudentid.pdf file and submit the PDF file on
Moodle before 23:59 Friday April 24, 2020:
(1) Login Moodle.
(2) Find “Assignments” in the left column and click “Assignment 3”.
(3) Click “Add submission”, browse your .pdf file and save it. Done.
(4) You will receive an automatic confirmation email, if the submission was successful.
(5) You can “Edit submission” to your already submitted file, but ONLY before the deadline.