Student Name: ______________________________________________
UNIVERSITY OF TORONTO
FACULTY OF APPLIED SCIENCE AND ENGINEERING
Circle your section:
MIDTERM TEST February 14, 2019
ECE361S – Computer Networks
Type A Exam: Non-programmable calculators allowed Closed-Book, No Aid sheets
LEC0101 LEC0102 Leon-Garcia H. Timorababi
Student Name: ______________________________________________ Student Number: ________________________________
Question
Mark
1
/20
2
/20
3
/20
4
/25
5
/15
TOTAL
/100
Page 1 of 10 pages
Student Name: ______________________________________________
Question 1: [20 Marks – 1 mark per question] Circle the correct answer.
1. IP Packets are routed based on Net ID.
True(A) False
2. RTP uses the reliable stream transfer service provided by UDP.
True False(A)
3. A TCP session consists of two connections.
True(A) False
4. RTP typically supports real-time applications running over TCP.
True False(A)
5. In HTTP, the server uses port 80.
True(A) False
6. The transport layer is the lowest layer that is end-to-end.
True(A) False
7. The data link layer involves the exchange of packets.
True False(A)
8. Stop-and-Wait ARQ can be implemented in the application layer.
True(A) False
9. In the Internet, packets may arrive out of order.
True(A) False
10. In a low-pass communication system with 8 GHz bandwidth, 1 pulse level suffices to achieve 16 Gbps.
True(A) False
11. Suppose the block 10011100 is received by a destination. If the transmitter uses a single parity check bit,
the receiver detects no errors.
True(A) False
12. Ethernet can work over copper wires, coaxial cable and optical fiber.
True(A) False
13. The Internet check sum attaches 32 check bits to detect errors.
True False(A)
14. In Stop-and-Wait ARQ, Rnext in the ACK acknowledges receipt of frame Rnext by the receiver.
True False(A)
15. In Selective Repeat ARQ, Rnext in the ACK acknowledges receipt of all frames up to and excluding Rnext
by the receiver.
True(A) False
16. The physical address denotes the location of an endpoint in the physical layer.
True False(A)
17. DNS is an application layer protocol that runs over UDP.
True(A) False
18. Each network layer provides a service to the layer above it.
True(A) False
19. TCP assigns a sequence number to each segment.
True(A) False
20. A computer can keep its IP address even as the computer is moved from the university to home.
True False(A)
Page 2 of 10 pages
Student Name: ______________________________________________
Question 2: [20 Marks – 2 marks per question] Circle all correct answers.
1. The DNS protocol is used in the following queries:
a. Name-to-IP Address Translation(A)
b. URL-to-IP Address Translation(A)
c. Mail Exchange(A)
d. IP-to-MAC Address Translation
2. Which of the following is true about TCP:
a. Setup overhead and delay is incurred. (A)
b. Two connection releases are required to finish the session. (A)
c. Segments are tracked by sequence number.
d. Operates directly over Ethernet.
3. Which of the following digitized audio signals (20 kHz bandwidth) can be transmitted over a channel with bit rate 175 kbps.
a. 8 levels of quantizing(A)
b. 4 levels of quantizing(A)
c. 16 levels of quantizing(A)
d. 32 levels of quantizing
4. Transmission Control Protocol (TCP) uses sliding windows for:
a. Timing Recovery
b. Error control(A)
c. Flow control(A)
d. Congestion control(A)
5. Which of the following statements are true?
a. All codewords in a polynomial code are multiples of the generator polynomial. (A)
b. The receiver divides the received polynomial by the generator polynomial to check if the quotient is zero.
c. All error patterns that are multiples of the generating polynomial are detected.
d. The transmitter and receiver use the same generator polynomial. (A)
6. Suppose the global state of a Stop-and-Wait ARQ with binary sequence numbering is (0,1). Which of the following are true:
a. ACK for frame 1 arrived at transmitter
b. Error-free frame 0 arrived at receiver(A)
c. ACK for frame 0 arrived at transmitter
d. Error-free frame 1 arrived at receiver
7. The IP Header includes the following information:
a. SYN flag(A)
b. Transport protocol type(A)
c. Network protocol type
d. Sequence number
8. Which of the following Wr and Ws are valid in Stop-and-Wait ARQ with 4-bit sequence numbering?
a. Wr = 1, Ws = 1(A)
b. Wr=15,Ws=15 c. Wr = 8, Ws = 8 d. Wr=7,Ws=7
9. Which of the following protocols is used by Voice over IP? a. RIP
b. SIP(A) c. RTP(A) d. PCM
10. Which of the following are true:
a. In very noisy channels, Stop-and-Wait and Selective Repeat ARQ have the same performance. (A)
b. In error-free channels, Stop-and-Wait and Selective Repeat ARQ have the same performance.
c. In channels with large delay-bandwidth product, Stop-and-Wait has poor performance. (A)
d. Selective Repeat ARQ accepts frames out of order. (A)
Question 3: [20 Marks]
Three networks are interconnected using IP as shown in the figure below, with host IDs and net IDs as indicated. Page 3 of 10 pages
Student Name: ______________________________________________
H1
H3
H5
S7
Net1
R1 Net2 R2
Net3
H2
S8
H4
H6
a. Suppose web server S8 sends content to host H2. Show all the layer 3 and 4 addresses, ports, and protocol types in the headers of the packets that travel along the path from S8 to H2. 4 marks
Path Hop
Header Fields
Net2.S8 -> Net2.R1
IP src Net2.S8, IP dest Net1. H2
Protocol (TCP), src port (80), dest port (Ephemeral)
Net1.R1 -> Net1.H2
IP src Net2.S8, IP dest Net1. H2
Protocol (TCP), src port (80), dest port (Ephemeral)
b. Suppose video streaming server S7 sends a packet to host H2. Assume the streaming system operates on top of TCP. Show all the layer 3 and 4 addresses, ports, and protocol types in the headers of the packets that then travel along the path from S7 to H2. 6 marks
Path Hop
Header Fields
Net3.S7 -> Net3.R2
IP src Net3.S7, IP dest Net1. H2
Protocol (TCP), src port (Ephemeral), dest port (Ephemeral)
Net2.R2 -> Net2.R1
IP src Net3.S7, IP dest Net1. H2
Protocol (TCP), src port (Ephemeral), dest port (Ephemeral)
Net1.R1 -> Net1.H2
IP src Net3.S7, IP dest Net1. H2
Protocol (TCP), src port (Ephemeral), dest port (Ephemeral)
Page 4 of 10 pages
Student Name: ______________________________________________
c. Suppose H6 wishes to have a Voice-over-IP call with H2. To do this the SIP agent in H6 contacts the registrar server S8. Show all the resulting layer 3 and 4 addresses, ports, and protocol types in the headers of the packets. 6 marks
Path Hop
Header Fields
Net3.H6 -> Net3.R2
IP src Net3.H6, IP dest Net2. S8
Protocol (TCP/UDP), src port (5060/5061), dest port (5060/5061)
Net2.R2 -> Net2.S8
IP src Net3.H6, IP dest Net2. S8
Protocol (TCP/UDP), src port (5060/5061), dest port (5060/5061)
d. In part c, show all layer 2 addresses in the headers of the frames that transfer the packets that convey the SIP message. 4 marks
Path Hop
Header Fields
Net3.H6 -> Net3.R2
Src MAC (Net3.H6 MAC), dst MAC (Net3.R2 MAC), Protocol (IP)
Net2.R2 -> Net2.S8
Src MAC (Net2.R2 MAC), dst MAC (Net2.S8 MAC), Protocol (IP)
Page 5 of 10 pages
Student Name: ______________________________________________ Question 4: Part A: [10 Marks] 2 marks each
a) Is the congestion window in units of bytes or segments? bytes
b) How does the TCP sender use the congestion window and the advertized window. Sender keeps outstanding bytes below advertised window.
Allowed Window = MIN (advertised window, congestion window)
c) How does the TCP sender augment the congestion window cwnd when it is in slow start operation? By receiving each ack
cwnd=cwnd+MSS
d) How does the TCP sender augment the congestion window cwnd when it is in congestion avoidance mode?
By receiving each ack cwnd=cwnd+1/cwnd
e) When and how is the congestion threshold ssthresh adjusted? upon timeout or receiving three duplicate ack
adjusted ssthresh = 0.5 * current cwnd
Page 6 of 10 pages
Student Name: ______________________________________________
Question 4: Part B: [15 Marks]
Suppose a user clicks on a link within a web browser to obtain a webpage. The IP address is not cached in the host so DNS has to be invoked. Assume that DNS servers are queried in the following order until the IP address is obtained: 1. Local DNS server; 2. Root Server; 3. Top Level Domain Server (e.g. .com, .org, .edu…); and 4. Authoritative server, which we assume can always resolve the IP address.
Assume that one-way propagation delay between the user’s computer and the local DNS server is 2 msec and assume for simplicity that the one-way propagation delay across the internet is 20 msec.
Suppose the Local DNS server queries each DNS server in the hierarchy in order and that the queried server replies either with the IP address or with the address of the next DNS server in the hierarchy.
a. Sketch the sequence of possible queries that can occur. 6 marks
b. For each sequence identify the time that it takes to resolve the IP address. 6 marks
c. Give an expression for the average time to resolve an IP address. 3 marks
Page 7 of 10 pages
Student Name: ______________________________________________
User (Query) -> Local DNS Server Local DNS Server -> User (IP)
2+2 = 4 (msec)
User -> Local DNS Server
Local DNS Server -> User (IP of Root Server) User -> Root DNS Server
Root DNS Server -> User (IP)
2+2+20+20 = 44 (msec)
User -> Local DNS Server
Local DNS Server -> User (IP of Root Server) User -> Root DNS Server
Root DNS Server -> User (IP of Top Level Serv) User -> Top Level Server
Top Level Server -> User (IP)
2+2+20+20+20+20 = 84 (msec)
User -> Local DNS Server
Local DNS Server -> User (IP of Root Server) User -> Root DNS Server
Root DNS Server -> User (IP of Top Level Serv) User -> Top Level Server
Top Level Server -> User (IP of Authoritive Serv) User -> Authoritive Server
Authoritive Server -> User (IP)
2+2+20+20+20+20+20+20 = 124 (msec)
c.
P1: probability of resolving the query by Local DNS Server P2: probability of resolving the query by Root DNS Server P3: probability of resolving the query by Top Level Server P4: probability of resolving the query by Authoritive Server Average time = 4*P1+44*P2+84*P3+124*P4
Page 8 of 10 pages
Student Name: ______________________________________________
Question 5: [15 Marks]
Consider the efficiency of Selective Repeat ARQ in a noisy channel as a function of the frame size. a. What happens to the efficiency as the frame size becomes small? 3 marks
Efficiency decreases when frame becomes very small (approaches zero) because the overhead occupies most of the frame.
b. What happens to the efficiency as the frame size becomes large? 3 marks
Efficiency decreases when frame becomes very large (approaches infinity) because the large
frame size leads to high frame error rate and many retransmissions.
c. Suppose the total overhead in a frame is 100 bits and that the probability of bit error is 10-6. Try to find an optimal frame size by trial and error.
4 marks
N_f (bits)
8000
10000
11200
12000
Efficiency
97.96 %
98.01%
98.00 %
97.98 %
Page 9 of 10 pages
Student Name: ______________________________________________
d. Now try to find an equation for the optimal frame size.
5 marks
Page 10 of 10 pages
Student Name: ______________________________________________
Shannon channel capacity:
C=WC log2(1+SNR) ARQ performance:
η = Reff R
L=2(tprop +tproc)R=W −1
S
η =(1−P) SW f
nf
nf
1− n0
1−Pf n 2(t +t )R 1+L
t =t+PWStf GBN f f 1−P
f
nf −n0
η =tf /(1−Pf)=(1−n0)(1−P)(1−P)
1+ a + prop nf
proc nf
nf −n0
η=tGBN=(1−P) nf =1−Pf
1−n0
GBN R f 1+(W−1)P 1+LP
SR R n f f f
1−P=(1−p)nf e−nfp f
E[ X ] = 1 Geometric 1− Pf
Sff
Page 11 of 10 pages