18 · Sample midterm: practice run

CMPEN/EE 362 Midterm Sample · answers are unofficial (worked from slides + HW solutions)

How to use this: close your notes, grab paper, and set a timer for about 45 minutes. Write every answer before opening the answer box. Then grade yourself and reread the linked topic for anything you missed.

Problem 1

Briefly answer the following questions (one or two sentences will be enough for each question).

a) In the client/server model, how to uniquely identify a client process?

Answer

By its IP address + port number. The IP address identifies the host. The port identifies which process on that host, since many processes can run on one host. (topic 7)

b) Which layer in the Internet protocol stack does routing?

Answer

The network layer (IP and routing protocols). (topic 6)

c) TCP can provide reliable service, but UDP can't. Why do we need UDP?

Answer

No connection setup (no extra RTT delay), no connection state at sender or receiver, small header (8 bytes), and no congestion control, so the app can send as fast as it wants. Good for loss-tolerant, delay-sensitive apps (streaming, games, DNS). Apps that need reliability can add it on top (HTTP/3). (topic 14)

d) Under what condition will the Selective Repeat protocol be the same as the Stop and Wait protocol?

Answer

When the window size is 1 (sender and receiver windows both 1). Only one packet can be in flight, so the sender waits for each ACK before sending the next. (topic 15)

e) Consider a new peer Alice that joins BitTorrent without possessing any chunks. Without any chunks, she cannot become a top-four uploader for any of the other peers, since she has nothing to upload. How will Alice get her first chunk?

Answer

Through optimistic unchoking. Every 30 s, each peer randomly picks one extra peer and starts sending it chunks, regardless of that peer's upload rate. Some neighbor will pick Alice, and once she has chunks she can trade tit-for-tat. (topic 11)

Problem 2

Consider a message that is 8 × 10⁶ bits. The message is sent from the source to the destination over four intermediate routers. Suppose each link is 1.6 Mbps, and 10 users use the network. Ignore propagation, queuing, connection setup and processing delays.

a) Suppose the network is packet-switched, and there is no message segmentation. What's the total time to move the message from the source to destination?

Answer

4 routers → 5 links. One hop: $$\frac{8 \times 10^6}{1.6 \times 10^6} = 5 \text{ s}$$ Store-and-forward over 5 links: $5 \times 5 = \mathbf{25 \text{ s}}$.
("10 users" doesn't divide the rate: in packet switching each packet goes at the full link rate.) (topic 4)

b) Suppose the message is segmented into 5000 packets, each 1600 bits. To reassemble the packets, each packet also includes an extra 160 bits of header. What's the total time to move the message from the source to destination?

Answer

Packet with header: $L = 1600 + 160 = 1760$ bits. $$\frac{L}{R} = \frac{1760}{1.6 \times 10^6} = 1.1 \text{ ms}$$ $$T = (N + P - 1)\frac{L}{R} = (5 + 5000 - 1) \times 1.1 \text{ ms} = 5004 \times 1.1 = \mathbf{5.5044 \text{ s}}$$ (topic 4)

Problem 3

Suppose users share a 3 Mbps link. Each user requires 150 kbps when transmitting, but each user transmits only 10 percent of the time.

a) When circuit switching is used, how many users can be supported?

Answer

$$\frac{3 \text{ Mbps}}{150 \text{ kbps}} = \frac{3000}{150} = \mathbf{20 \text{ users}}$$ (topic 2)

b) Suppose there are 100 users. What's the probability that 20 or more users are transmitting simultaneously? (A formula is enough.)

Answer

Each user is active with $p = 0.1$, independently. Binomial with $N = 100$: $$P(X \ge 20) = \sum_{k=20}^{100} \binom{100}{k} (0.1)^k (0.9)^{100-k}$$ Equivalently $1 - \sum_{k=0}^{19} \binom{100}{k}(0.1)^k(0.9)^{100-k}$. (topic 2)

Problem 4

Suppose a Go-Back-N protocol is used, and there are k bits of sequence number. What's the maximum window size? Explain the reason using an example with k = 2. Without a concrete example, you will not get any points.

Answer

Max window = 2^k − 1. With k = 2, the seq #s are 0, 1, 2, 3, so max W = 3.

W = 4 fails:

Sender sends pkts 0, 1, 2, 3.
Receiver gets all four, delivers them, sends ACK0–ACK3, and now expects seq 0 (the next new packet).
All 4 ACKs are lost.
Sender times out and resends the old pkts 0, 1, 2, 3.
Receiver expects seq 0, so it accepts the old pkt 0 as new data. Error.

W = 3 works:

Sender sends 0, 1, 2. Receiver gets all three, ACKs them, and expects seq 3.
All ACKs lost. Sender resends old 0, 1, 2.
Receiver expects 3, gets 0 → out of order → discards and re-ACKs 2. Correct.

The window must leave at least one seq # unused, so the number the receiver expects next is never one the sender might resend. (topic 15)

Problem 5

The following is the result of running traceroute.

 1  cs-gw (128.119.240.254)                          1 ms    1 ms    2 ms
 2  border1-rt-fa5-1-0.gw.umass.edu (128.119.3.145)  1 ms    1 ms    2 ms
 3  cht-vbns.gw.umass.edu (128.119.3.130)            6 ms    5 ms    5 ms
 4  jn1-at1-0-0-19.wor.vbns.net (204.147.132.129)   16 ms   11 ms   13 ms
 5  jn1-so7-0-0-0.wae.vbns.net (204.147.136.136)    21 ms   18 ms   18 ms
 6  abilene-vbns.abilene.ucaid.edu (198.32.11.9)    22 ms   18 ms   22 ms
 7  nycm-wash.abilene.ucaid.edu (198.32.8.46)       22 ms   22 ms   22 ms
 8  62.40.103.253 (62.40.103.253)                  104 ms  109 ms  106 ms
 9  de2-1.de1.de.geant.net (62.40.96.129)          109 ms  102 ms  104 ms
10  de.fr1.fr.geant.net (62.40.96.50)              113 ms  121 ms  114 ms
11  renater-gw.fr1.fr.geant.net (62.40.103.54)     112 ms  114 ms  112 ms
12  nio-n2.cssi.renater.fr (193.51.206.13)         111 ms  114 ms  116 ms
13  nice.cssi.renater.fr (195.220.98.102)          123 ms  125 ms  124 ms
14  r3t2-nice.cssi.renater.fr (195.220.98.110)     126 ms  126 ms  124 ms
15  eurecom-valbonne.r3t2.ft.net (193.48.50.54)    135 ms  128 ms  133 ms
16  194.214.211.25 (194.214.211.25)                126 ms  128 ms  126 ms
17  * * *
18  * * *
19  fantasia.eurecom.fr (193.55.113.142)           132 ms  128 ms  136 ms

a) For the first router, the three round-trip delays are 1 ms, 1 ms, 2 ms. Why are they different?

Answer

Queuing delay varies. Each probe hits the routers at a different moment with a different amount of traffic queued ahead of it. (Propagation and transmission delay are the same for all three.) (topic 3)

b) From router 7 to router 8, the delay jumps from about 22 ms to 104 ms. What's the main reason?

Answer

Router 7 is in New York (nycm = NYC) and router 8 is in Europe (GÉANT). That hop is a trans-oceanic link, and the jump is mostly propagation delay over thousands of km of cable. (topic 3)

Problem 6

Consider distributing a file of F bits to N peers using a client-server architecture. Assume a fluid model where the server can simultaneously transmit to multiple peers, at different rates, as long as the combined rate does not exceed u_s. Suppose that u_s/N ≤ d_min. Specify a distribution scheme that has a distribution time of NF/u_s.

Answer

The server sends the file to all N clients in parallel, at rate u_s/N each. The total is u_s, so the server can do it.
Since u_s/N ≤ d_min, every client can download at that rate. Each client receives the file in $$\frac{F}{u_s/N} = \frac{NF}{u_s}$$ All clients finish at the same time, so the distribution time is $NF/u_s$. (topic 11)

Things the real exam could swap in

The sample skips some HW calculations. If you have time left, redo these from the topic pages:

Likely calc	Where
HTTP RTT counting (non-persistent / parallel / persistent)	topic 8 · HW2 P2
Caching access delay Δ/(1 − Δβ)	topic 9 · HW2 P3
P2P vs client-server distribution time	topic 11 · HW2 P5
1s complement checksum	topic 14 · HW3 P2
Window size for a target utilization	topic 16 · HW3 P4
Delay components, BDP	topic 3, topic 5 · HW1

Good luck!

← 17 · rdt details · all topics · Final review sheet →