THE UNIVERSITY OF HONG KONG
FACULTY OF ENGINEERING DEPARTMENT OF COMPUTER SCIENCE
COMP3234 Computer and Communication Networks
Date: May 26, 2020 Time: 2:30 pm – 5:30 pm University Number:
Write your answers on paper. Clearly mark your University Number and which questions you are answering. Scan your handwritten answers into a PDFfile for submission.
This is an open-book examination. Candidates are permitted to look up hardcopy materials including textbook, lecture slides, lab and assignment handout and sample solutions, and self-made notes, or refer to these materials by displaying them on your laptop computers. Candidates are not allowed to search the Internet for answers during the examination.
Only approved calculators as announced by the Examinations Secretary can be used in this examination. It is candidates’ responsibility to ensure that their calculator operates satisfactorily, and candidates must record the name and type of the calculator used on the
first page of the examination script.
Total mark is 100.
Question
1 (15%)
2 (9%)
3 (14%)
4 (20%)
5 (15%)
6 (10%)
7 (17%)
Total (100%)
Score
Page 1 of 6
UID
Question 1 (15%): Consider an application that transmits data at a steady rate, i.e., sending an N-bit unit of data per unit time. Also, when such an application starts, it will continue running for a relatively long period of time.
(1) (4%) Briefly describe what circuit switching and packet switching are. Would a packet-switched network or a circuit-switched network be more appropriate for this application? Explain why.
(2) (3%) Suppose a packet-switched network is used, and there are multiple such applications generating traffic in this network. Suppose the bottleneck link capacity in the network is M bits per unit time. How many applications can be supported in the network concurrently without the need of some form of congestion control? Briefly describe the definition of congestion control.
(3) (8%) Suppose a packet-switched network is used, there are two applications in the network running at Host A and Host B, respectively, and the bottleneck link capacity is M bits per time slot, as illustrated in Figure 1-1. Each application lasts for T time slots: as illustrated in Figure 1-2, one application transmits a packet of N bits at the speed of Kl bits per time slot at the beginning of each time slot, and the other application transmits a packet of N bits at the speed of K2 bits per time slot immediately following that. Suppose N>M/2 (bits), Kl>M (bits per time slot), K2>M (bits per time slot), and N/Kl+N/K2=1. What is the queueing delay experienced by the last packet from application 2 at the bottleneck link?
Application 1
Application 2
to
Figure 1-1
to+1 to+2 Figure 1-2
Page 2 of 6
UID———-
Question 2 (9%): Suppose in the address bar of your Web browser you enter a URL to obtain a Web page, which contains the hostname of the Web server hosting the Web page. The IP address of the Web server is not cached in your local host, so a DNS lookup is necessary to obtain the IP address. Suppose n DNS servers are visited before your host receives the IP address; the successive visits incur an RTI of RTT1, .. ., RTTn, respectively. The Web page at the URL contains one HTML file of size a, which references 3 images on the same Web server, of size b, c and d, respectively. Let RTTo denote the RTI between your local host and the Web server. Ignore any detailed nodal processing, queueing or transmission delay at your local host, DNS servers and the Web server, but only consider the respective RTI.
(1) (3%) How much time elapses from when the client enters the URL in the Web browser until the client receives the IP address of the Web server?
(2) (3%) Consider the three-way handshake procedure between your Web browser and the Web server for retrieving Web objects. Suppose the client ACK in the third step of three-way handshake is piggybacked onto the TCP segment carrying the first HTIP request. If persistent connection is used (as in HTIP 1.1), how long does it take from when your Web browser initiates the three-way handshake procedure to when your browser has received all Web objects to display the complete Web page?
(3) (3%) What is the data throughput of the connection between your localhost and the Web server, by the time computed in (2)?
Question 3 (14%): Reliable data transfer (RDT).
(1) (4%) Briefly compare the differences between a stop-and-wait ROT protocol and a pipelined RDT protocol.
(2) (10%) Consider the sender FSM and receiver FSM of RDT 3.0. Design an NAK-only protocol that implements the same functionality as implemented by RDT 3.0, by plotting the sender and receiver FSMs. Define variables and functions not included in the FSMs of RDT 3.0.
Question 4 (20%): Suppose Host A sends 2 files to Host B over TCP. Each file is 27.2 Kbytes long. Each TCP segment contains data of 1 MSS long, where 1 MSS=536 bytes, and ignore the header bytes. Assume that the bottleneck link bandwidth between A and B is 1 Mbps; if there are N parallel TCP connections sharing the bottleneck link, each gets 1/N of the link bandwidth. The RTI between the two hosts is 32 milliseconds. The initial CongWin is 1 MSS, and simple AIMD congestion control is used along a TCP connection, i.e., congestion window is cut to half after loss and ignore slow start etc. In additive increase, CongWin is increased by 1 MSS in each transmission round (1 RTI). Suppose when
Page 3 of 6
UID———-
the average sending rate in one transmission round along one TCP connection is larger than its share of the bottleneck link bandwidth, the last segment sent in the round is lost, the loss is detected slightly before the beginning of the next transmission round, and the segment is retransmitted in the next transmission round. Host B immediately sends an acknowledgement whenever it has received a segment. There is no other traffic in the network. Ignore segment transmission delays and you do not need to consider packet corruption.
(1) (10%) Suppose only one TCP connection is used for sending the two files. How long is the time T from when Host A sends the first segment to the time it receives the acknowledgement from Host B for the last segment sent? What is the average throughput to send the files, over time T?
(2) (10%) Suppose 2 concurrent parallel TCP connections are used to send the 2 files respectively. How long is the time T along each TCP connection, from when the first segment is sent to the time when the acknowledgement for the last segment is received? What is the average throughput along each TCP connection, over time T?
Question 5 (15%): Consider a network of routers given below. The numbers on the links indicate link costs, and the numbers in brackets denote interfaces of the adjacent router.
(1) (11%) Find a least-cost path from router la to router 3b. You can use Dijkstra’s algorithm, or Bellman-Ford algorithm, or both. Show your steps of the algorithm(s).
(2) (4%) You are given the following forwarding tables at router 3c and router 4c. Suppose router le, router 2a, router 3d and router 4a are each connected to a host, respectively. Assign an IP address to each of the four hosts, such that packets destined towards each host can be forwarded correctly (along the least-cost paths) at router 3c and router 4c. Ignore the cost along the link from a router to its connected host.
Page 4 of 6
UID———- Router 3c’s forwarding table:
IP Address Prefix 11001000 0001011 J 00011
11001000 00010111 00010
11001000 000101 11 00011000
Interface
l
4
3
2
Interface 1
2
3
4
others
Router 4c’s forwarding table:
IP Address Prefix
11001000 00010111 00011010
11001000 00010111 00011001
11001000 000 101 1 00011 00
others
Note that there could be many answers all fulfilling the requirements, and you only need to write down one set of correct IP addresses.
Question 6 (10%}: Consider 3 LANs interconnected by two routers, as shown in the following figure. Consider sending an IP datagram from Host A to Host F. Suppose the ARP table in Host A is empty while the ARP table in any other host/router is up to date. Enumerate the steps involved for sending the IP datagram from A to F. You should specify the interfaces traversed, the source and destination IP addresses contained in each datagram sent, the source and destination MAC addresses contained in each frame sent, and the basic steps of acquiring an IP-address-to-MAC-address mapping (if not known) using ARP. Suppose the IP datagram can always be carried entirely in a frame.
192.168.1.001 ll-11-11-22-22-22
192.168.3.001 77-77-77-77-77-77
Router 2
/
192.168.2.003
192.168 .3 .002
55-55-55-55-55-55
�LJ,192.168.2.004 66-66-66-66-66-6192.168.3.003 � F 99-99-99-99-99-99
Page 5 of 6
88-88-88-88-88-88
UID
Question 7 (17%): Consider nodes A and B on a shared 10 Mbps CSMA/CD channel. Suppose both A and B have one 512-byte frame to send. The propagation delay between the two nodes is 400 bit time. As shown in the figure below, suppose node A begins transmitting its frame at time tA=O, node B starts to transmit its frame at time tB=300 bit time, and then collision occurs. The CSMA/CD protocol at A and B follows the conventions that A (or B) will immediately abort its transmission as soon as a collision is detected, and then A (or B) will back off and attempt to retransmit after waiting 512K bit times, where K is chosen each time by exactly following the sequence of {l, 2, 3, 4, 5, …}, i.e., K=l is used after the 1st collision, K=2 is used after the 2nd collision, and so on. A and B will re-attempt transmissions until their frames are successfully sent.
-space-
AB
IA ,—–,�——,
T
512 X 1 bit time
_J_ ···················
512 X 2 bit time
_j
(1) (6%) What is the start time (in microseconds) of the successful transmission from A, after which A successfully transmits its entire frame without collision?
(2) (6%) What is the start time (in microseconds) of the successful transmission from B, after which B successfully transmits its entire frame without collision?
(3) (5%) Let T be the time when both A and B have completed the successful transmission of their respective frame. Calculate the efficiency of the CSMA/CD channel during the time interval [O, T].
-END OF PAPER–
Page 6 of 6