COMP9121: Design of Networks and Distributed Systems - Assignment 1: CRC, ALOHA, CSMA and Routing
COMP 9121 Assignment 1 (2022)
Due: 14/September/2022, 23:59
8 questions; each question is equally weighted.
Question 1 (CRC). Answer questions below.
(1) What is your student number? Convert your student number to binary and hexadecimal numbers. (Warning: you will get zero
if you use another student’s number.)
(2) Let D be the binary number your derived above. Let the generator G = 100101. Calculate the CRC bits.
(3) Following (2), give an example that the transmitted bits are not error-free but the receiver cannot detect the error.
Question 2 (Delay). Consider two hosts, A and B, are connected by three links and two routers as shown the figure below. Suppose node A sends two packets consecutively to B. Each packet is with the size of 64 bytes. Each router applies store and forward. Nodal processing and queueing delays can be ignored. There is no bit error or packet loss.
We have: Bandwidth of L1 = 1 Mbps. Bandwidth of L2 = 2 Mbps. Bandwidth of L3 = 2 Mbps. Length of L1 = 100 km. Length of L2 = 200 km. Length of L3 = 200 km. Propagation speed of links= 2 × 108 (m/s).
(1) What is the overall delay to deliver the two packets? (From the start of sending first packet at A till the second packet is completely received by B)
(2) At time t = 0.6 ms, where is the first bit of the first packet? (t = 0 is the time instant when A starts to send the first packet.)
(3) At what time instant, the first bit of the second packet arrives at the second router R2? At what time instant, the first bit of the second packet leaves the second router R2?
Question 3 (ALOHA). Suppose nodes A, B, C, D, and E are competing to have access to a shared channel using slotted ALOHA. Each node attempts to transmit in each slot with probability p independently. The first slot is numbered slot 1, the second slot is numbered slot 2, and so on.
(1) What is the probability that node B succeeds three times no later than slot 6?
(2) What is the probability that there are three successful transmissions no later than slot 6? (3) What is the probability that a node succeeds three times no later than slot 6?
uestion 4 (CSMA Performance). M + N computers have been connected in a network as illustrated. M computers are in the left side and N computers are in the right side. CSMA-CD is used. X0 is a switch. X1 and X2 are hubs. The length of each link is written in meters. Each computer generates 500 packets per second with each packet being 1000 bytes. The maximum rate of all links is 1 Gbps. The propagation speed in the medium is 2.0 × 108 meters/second.
For the M computers, 21 traffic is kept locally, 21 traffic goes to the other side. For the N computers, 12 traffic is kept locally, 12 traffic goes to the other side.
What is the max number of the computers that can be supported in the network, i.e., what are the max values of M and N?
Question 5 (NAT). In the figure below, assume the addresses 134.89.31.4 and 192.168.1.144/28 are assigned as NAT public IP and the local IPs. Assume application 1 is running on port 5500 on all hosts A, B, C, and D. Each application 1 in each host generates a packet to Server 1 (140.21.77.5, 80). In addition, application 2 is running on port 5505 on all hosts. Each application 2 in each host sends a packet to Server2 (128.119.40.153, 443).
(1) Assign local IP addresses to the four hosts.
(2) Following (1), generate the NAT translation table for all traffic in the network by considering that port numbers in the range of [5500, 5510] are available to be used in the NAT.
(3) Following (2), when Server 1 sends a reply to node D, what are (IP address, port) fields in the packet header for source and destination?
(4) Following (3), how does the NAT modify (IP address, port) fields of the packet so that it will be delivered to D? (Note that the answer is not unique.)
Question 6 (Shortest Path). Consider the network topology presented in the figure below. The link costs (distances) are labelled.
(1) Use the distance vector algorithm to find the shortest distances from all routers to router F by filling out the table below (assume that exchanges of routing information and routing table updates are synchronous). The table allows up to ten iterations, but you can stop whenever the algorithm converges.
(2) After the convergence of (1), assume that the links B − E and B − C are connected with costs shown below. Do NOT use split horizon or reverse poisoning. Fill out the table below using the distance vector algorithm to find the shortest distance from each router to router F. The table allows up to ten iterations, but you can stop whenever the algorithm converges.
ABCDE
Question 7 (Intra-AS and Inter-AS Routing). Consider the network topology as follows. There are multiple ASes in the network. A–F indicate routers within AS1. X and Y are gateway routers of AS131 and AS105. Link costs (distances) in AS1 are labelled in the figure. AS1 is a customer network of AS105 and AS131. 11.11.11.0/24 is a customer network of AS132 and AS106. 22.22.22.0/24 is a customer network of AS133 and AS107. AS107 is a customer network of AS106.
(1) Within AS1, use the Dijkstra Algorithm to find the shortest distances from router A to all other routers.
(2) What BGP messages does X send to E? What BGP messages does Y send to C? Are these messages iBPG or eBGP messages? Fill the following form. You can leave rows blank if there are only 1 or 2 messages from X to E or from Y to C.
Prefix AS PATH
Next Hop
iBPG or eBGP?
From X to E From X to E From X to E From Y to C From Y to C From Y to C
(3) Assume that AS1 accepts all possible inter-AS routing. Find out entries in forwarding tables at different routers. Fill the table below. (In each blank, choose one of the follows: A, B, C, D, E, F, X, Y.) Show your reasons.
Question 8 (Cross Layer). Consider the following network where A, B, C, D, G, H, and I are hosts. S1, S2, . . . , S5 are switches. R1 and R2 are routers.
(A) Consider sending an packet from Host A to Host B.
(A1) Is it possible that the packet can reach R1? Why or why not?
(A2) In the packet (Ethernet frame containing the IP datagram), what are the source and destination IP and MAC addresses?
(B) G wants to send an packet to C. G does not know C’s MAC address.
(B1) Will G perform an ARP query to find C’s MAC address? Why?
(B2) G sends a packet which will finally be delivered to C. What are the source and destination IP and MAC addresses of
the packet when G sends it? What are the source and destination IP and MAC addresses of the packet when C receives it? (B3) Following (B2), when R2 receives the packet, how does R2 know that it should forward the packet to R1?
(C) Now I joins the network.
(C1) How does I know the IP address of R2’s right interface? How does I know the MAC address of R2’s right interface?
How does S4 know I’s MAC address. Does S4 also know I’s IP address? Does S3 also know I’s MAC address? Why? (C2) Under what situation can S5 know I’s MAC address?
