SEN2008 · Week 9 · Midterm

Midterm review: from network basics to TCP

All the formulas of weeks 2-8 in one table, which exam question fits which pattern, and a mixed 12-question practice test: Shannon, CRC, sliding window, subnetting, fragmentation, Dijkstra, Bellman-Ford, handshake, cwnd, RTT estimation.

Shannon capacityCRCutilizationslotted ALOHACIDRfragmentation offsetDijkstraBellman-Fordthree-way handshakeslow startcongestion avoidanceEWMATimeoutIntervalreceive window

The midterm covers the networking topics from week 2 to week 8. The security part starts after the midterm. This page teaches nothing new: it collects all the formulas in one place, gives the “recognition signal” for each question type, and ends with an exam rehearsal. First read the tables, then solve the questions with pen and paper, and go back to the page of any topic where you get stuck.

Exam strategy:

Write the units first. Bytes or bits, km or m, ms or s. Most of the points are lost to unit errors.
Write the formula, then plug in the numbers. Partial credit comes from the formula.
Draw a table for trace questions. In questions like Dijkstra, cwnd and GBN, write each step on one line.
State your assumptions. Add things like “tie broken alphabetically” or “cwnd capped at ssthresh” to your answer.

Formula summary, week by week

Weeks 1-2: delay, layers, the physical layer

Topic	Formula / rule	Recognition signal
Transmission	$d_{trans} = L/R$	“packet of L bits on a link of rate R”
Propagation	$d_{prop} = d/s$	“km long”, “propagation speed”
Multiple links	$(N + P - 1)L/R$	“store-and-forward”, “P packets”
Traffic intensity	$La/R$	“packets arrive at rate a”
Encapsulation efficiency	data / (data + headers)	“header overhead”
Nyquist	$2B\log_2 V$	“noiseless”, “levels”
Shannon	$B\log_2(1 + \text{SNR})$	“SNR”, “dB”, “noisy”
Baud	bit rate $=$ baud $\times \log_2 V$	“symbols per second”, “QAM”

Layers and PDUs: Application (message), Transport (segment), Network (datagram), Link (frame), Physical (bit). OSI additionally has Presentation and Session.

Week 3: error control and sliding window

Topic	Procedure	Pitfall
Parity	Count the 1s, even/odd	Double errors escape
2D parity	The bad bit is at the row and column intersection	The 4 corners of a rectangle escape
Checksum	Add 16 bits, carry to the start, invert	The carry is not dropped
CRC	Append $r$ zeros, XOR divide	Write 0 for a missing degree in the polynomial
Hamming	$2^r \ge m + r + 1$ ; the syndrome gives the position	Positions of p1, p2, p4
Efficiency	$U = \min(1, N \frac{L/R}{RTT + L/R})$	RTT is two-way
Sequence number	GBN $2^k - 1$ , SR $2^{k-1}$	Half in SR

In GBN the receiver discards out-of-order frames and sends a cumulative ACK; on a timeout everything from the lost frame on is resent. In SR the receiver buffers, and each frame gets its own ACK and timer.

Week 4: multiple access and Ethernet

Topic	Formula
Slotted ALOHA	$Ge^{-G}$ , max $1/e$ ; $Np(1-p)^{N-1}$
Pure ALOHA	$Ge^{-2G}$ , max $1/(2e)$
CSMA/CD minimum frame	$L_{min} = 2 d_{prop} R$
Backoff	$K \in \{0..2^{\min(n,10)} - 1\}$ , $K \times 512$ bit times
Ethernet efficiency	$1/(1 + 5 d_{prop}/d_{trans})$
Frame	64 to 1518 bytes; payload 46 to 1500

A switch learns from the source MAC and looks up the destination: if it is not found, flood; if it is the same port, filter; if it is another port, forward. An ARP request is broadcast, the reply is unicast. For a remote destination, the destination MAC is the gateway’s MAC.

Weeks 5-6: the network layer

Subnet calculation (a.b.c.d/n):
  mask         : n ones, the rest zeros
  block size   : 256 - (mask value in the interesting octet)
  network addr : round the interesting octet down to a multiple of the block size, zeros to the right
  broadcast    : next network address - 1
  number hosts : 2^(32-n) - 2
  b borrowed   : 2^b subnets

Fragmentation:
  fragment data: (MTU - header) rounded down to a multiple of 8
  offset field : starting byte of the fragment in the data / 8
  MF           : 1 except on the last fragment
  total length field includes the header

Routing:

Link-state (Dijkstra, OSPF): every node knows the whole map. At each step add the smallest $D$ outside N’, and update its neighbours with $D(v) = \min(D(v), D(w) + c(w,v))$ .
Distance-vector (Bellman-Ford, RIP): every node knows only its neighbours’ vectors. $D_x(y) = \min_v \{c(x,v) + D_v(y)\}$ . Bad news spreads slowly (count-to-infinity); poisoned reverse is a partial fix.
OSPF is intra-AS, link-state. BGP is inter-AS, path-vector; it decides by policy.

Weeks 7-8: the transport layer

Topic	Rule
UDP header	8 bytes: src port, dst port, length, checksum
TCP header	at least 20 bytes; seq, ack, flags (SYN, ACK, FIN, RST), rwnd
Seq / ack	seq = first byte of the segment; ack = next expected byte
Handshake	SYN (x) → SYN-ACK (y, x+1) → ACK (x+1, y+1)
Flow control	rwnd $=$ RcvBuffer $-$ (LastByteRcvd $-$ LastByteRead)
Sending limit	LastByteSent $-$ LastByteAcked $\le \min(\text{cwnd}, \text{rwnd})$
Slow start	cwnd ×2 every RTT, up to ssthresh
Congestion avoidance	+1 MSS every RTT
Timeout	ssthresh = cwnd/2, cwnd = 1 MSS, slow start
3 dup ACKs (Reno)	ssthresh = cwnd/2, cwnd = ssthresh (+3), fast recovery
Average throughput	$\approx 0.75\,W/RTT$
RTT estimation	Est $= (1-\alpha)$ Est $+ \alpha S$ ; Dev $= (1-\beta)$ Dev $+ \beta

PITFALL · SYN and FIN each consume one sequence number. Even though they carry no data. After the handshake, the first byte of data is ISN + 1.

PITFALL · Tahoe versus Reno. On a timeout both drop cwnd to 1. The difference is only with three duplicate ACKs: Tahoe again drops to 1, while Reno halves and continues from congestion avoidance. On the exam, read from the question text which one is asked and whether the textbook’s “+3” rule is used.

Worked mixed example: the journey of a web request

A laptop (192.168.1.10/24) connects to a web server. See all the weeks together:

1. Application: HTTP request (message)
2. Transport: TCP handshake (SYN, SYN-ACK, ACK), then segments; cwnd starts at 1 MSS
3. Network: is the destination IP in my subnet? Outside 192.168.1.0/24 -> default gateway
4. Link: ARP for the gateway MAC (broadcast request, unicast reply)
5. Ethernet frame: dst MAC = gateway, FCS = CRC-32
6. Switch: learns the source MAC, forwards the frame to the gateway port
7. Router: looks at the IP header, longest prefix match, TTL - 1
8. Core: paths found with OSPF inside an AS, BGP between ASes
9. On every link: dtrans + dprop + queuing; the bottleneck link determines throughput

After the midterm we will look at each step of this journey through an attacker’s eyes: ARP spoofing (4), forged IP (7), SYN flood (2), BGP hijacking (8).

Common mistakes (all topics)

Wrong idea	Correct
Putting dB directly into Shannon	First $10^{dB/10}$
In CRC, as many zeros as the generator length	As many as the degree ( $r$ )
$U = (L/R)/RTT$	The denominator is $RTT + L/R$
The GBN receiver buffers	It discards; SR buffers
$L_{min} = d_{prop} R$	$2 d_{prop} R$
Hosts for /n are $2^{32-n}$	$-2$ (network and broadcast)
The offset is written in bytes	8-byte units: byte / 8
In Dijkstra, go to the cheapest neighbour	Choose by total path cost
ACK = the last byte I received	The next byte I expect
Slow start goes past ssthresh	On reaching ssthresh it switches to CA
UDP delivers in order	No sequence numbers or ACKs; unreliable

Test yourself

Exam-style questions. Solve them on paper first, then reveal the answer.

Question 1easy

A channel has bandwidth 4 kHz and SNR = 30 dB. What is its Shannon capacity (nearest bps)?

Show answer

39,869 bps

30 dB → ratio $10^{3} = 1000$ . $C = 4000 \log_2(1001) \approx 4000 \times 9.967 = 39{,}869$ bps.

Question 2medium

Compute the CRC bits for data 100101 with generator 1101, and give the transmitted bit string.

Show answer

R = 100, sent 100101100

The degree is 3, so append three zeros: 100101000.1001⊕1101=0100 → with the following bits 1000⊕1101=0101 → 1011⊕1101=0110 → 1100⊕1101=0001, and the remainder is the last 3 bits 100.
Transmitted: 100101 + 100 = 100101100. When the receiver divides this by 1101 it gets remainder 0.

Question 3medium

A 10 Mbps link carries 1000-byte frames with RTT = 10 ms. What is the stop-and-wait utilization, and what is the smallest window that gives 100% utilization?

Show answer

≈ 0.0741; 14 frames

$L/R = 8000/10^7 = 0.8$ ms. $U = 0.8 / (10 + 0.8) \approx 0.0741$ .
For full utilization: $N \ge 10.8/0.8 = 13.5$ , and the window must be an integer: $N = 14$ .

Question 4medium

Host 172.16.45.130/21: what are its network address, broadcast address and number of usable host addresses?

Show answer

172.16.40.0, 172.16.47.255, 2046

/21 → mask 255.255.248.0. The interesting octet is the third, and the block size is $256 - 248 = 8$ .
45 lies between the multiples of 8, 40 and 48: the network is 172.16.40.0, and the broadcast is one less than the next block, 172.16.47.255.
Host bits $32 - 21 = 11$ : $2^{11} - 2 = 2046$ .

Question 5medium

The network 200.10.20.0/24 must be divided into at least 6 equal subnets. What prefix length results, and how many usable hosts does each subnet have?

Show answer

/27, 30 hosts

$2^b \ge 6$ → borrow $b = 3$ bits ( $2^3 = 8$ subnets). The prefix is $24 + 3 = 27$ .
The remaining host bits are 5: $2^5 - 2 = 30$ .

Question 6hard

A 4000-byte IPv4 datagram (20-byte header, no options) must cross a link with MTU 1500 bytes. List each fragment's total length, offset field and MF flag.

Show answer

1500/0/1, 1500/185/1, 1040/370/0

The data to carry is $4000 - 20 = 3980$ bytes. At most $1500 - 20 = 1480$ bytes of data per fragment (a multiple of 8, so fine).
Fragment 1: 1480 data, length 1500, offset $0/8 = 0$ , MF=1.
Fragment 2: 1480 data, length 1500, offset $1480/8 = 185$ , MF=1.
Fragment 3: $3980 - 2960 = 1020$ data, length 1040, offset $2960/8 = 370$ , MF=0.

Question 7hard

Run Dijkstra from node u on the graph below. In what order are nodes added to N', and what is the least-cost path from u to z with its cost? (Break ties alphabetically.)

edges (undirected, cost):
u-v 2   u-x 1   u-w 5
v-x 2   v-w 3   x-w 3
x-y 1   w-y 1   w-z 5
y-z 2

Show answer

x, v, y, w, z; u-x-y-z, cost 4

Start: D(v)=2, D(w)=5, D(x)=1, D(y)=D(z)=∞.
x is added (1): D(w)=min(5, 1+3)=4, D(y)=1+1=2.
v and y are tied (2), alphabetically v: no update (via v, w would be 5 and x 3, which are worse).
y is added (2): D(w)=min(4, 2+1)=3, D(z)=2+2=4.
w (3): D(z)=min(4, 3+5)=4 does not change. Finally z (4).
Tracing the path back: z←y←x←u, that is u-x-y-z, with cost 4.

Question 8medium

Node x has neighbors y, v and w with link costs c(x,y) = 2, c(x,v) = 7, c(x,w) = 1. They advertise distances to z of $D_y(z) = 5$ , $D_v(z) = 1$ , $D_w(z) = 9$ . Using Bellman-Ford, what is $D_x(z)$ and the next hop?

Show answer

7, via y

$D_x(z) = \min\{c(x,y) + D_y(z),\ c(x,v) + D_v(z),\ c(x,w) + D_w(z)\}$ $= \min\{2 + 5,\ 7 + 1,\ 1 + 9\} = \min\{7, 8, 10\} = 7$ , and the next hop is y.
The cheapest neighbour (w) is not the best path; the neighbour cost and the distance the neighbour reports are added together.

Question 9medium

A client chooses ISN 1000 and the server chooses ISN 5000. Give the (seq, ack) values of the SYN-ACK and of the final ACK of the handshake. If the client then sends 500 bytes of data starting right after the handshake, what is the sequence number of the next byte after that segment?

Show answer

SYN-ACK (5000, 1001); ACK (1001, 5001); next 1501

A SYN consumes one sequence number. Client SYN: seq=1000.
Server SYN-ACK: seq=5000, ack=1001 (I got 1000, I expect 1001).
Client ACK: seq=1001, ack=5001.
Data starts at 1001, 500 bytes: 1001..1500. The next byte is 1501.

Question 10hard

TCP Tahoe starts with cwnd = 1 MSS and ssthresh = 16. cwnd doubles each RTT in slow start (never above ssthresh) and grows by 1 MSS per RTT in congestion avoidance. A timeout occurs at the end of round 9. What is cwnd in rounds 9, 10, 13 and 14?

Show answer

20, 1, 8, 10

Rounds: 1:1, 2:2, 3:4, 4:8, 5:16 (reached ssthresh), 6:17, 7:18, 8:19, 9:20.
Timeout: ssthresh = 20/2 = 10, cwnd = 1.
10:1, 11:2, 12:4, 13:8, 14: it would be 16 but cannot exceed ssthresh 10 → 10, then 15:11.

Question 11medium

EstimatedRTT = 200 ms, DevRTT = 20 ms, and a new SampleRTT = 240 ms arrives. With α = 0.125 and β = 0.25, updating EstimatedRTT first and then DevRTT with the new estimate, what is the new TimeoutInterval?

Show answer

300 ms

$\text{Est} = 0.875 \times 200 + 0.125 \times 240 = 175 + 30 = 205$ ms. $\text{Dev} = 0.75 \times 20 + 0.25 \times |240 - 205| = 15 + 8.75 = 23.75$ ms. $\text{Timeout} = 205 + 4 \times 23.75 = 300$ ms.

Question 12easy

Which statement is FALSE?

A switch learns MAC addresses from the source field of incoming frames
An ARP request is broadcast and the reply is unicast
UDP provides reliable, in-order delivery using sequence numbers
Go-Back-N receivers discard out-of-order frames

Show answer

C) UDP provides reliable, in-order delivery using sequence numbers

UDP has no sequence numbers, ACKs or retransmission. Its header has only 4 fields: source port, destination port, length, checksum (8 bytes). Whoever wants reliability either uses TCP or builds it in the application.
The other three statements are true.

Verification: All answers were computed with node (verify/SEN2008/09.mjs): Shannon, mod-2 CRC division, stop-and-wait efficiency, subnetting with 32-bit mask operations, fragmentation offsets, a step-by-step Dijkstra table, the Bellman-Ford equation, seq/ack arithmetic, a Tahoe cwnd simulation and EWMA.

Review card

dtrans=L/R dprop=d/s (N+P-1)L/R La/R>1 -> unbounded queue throughput=min Nyquist 2B log2V Shannon B log2(1+SNR), SNR=10^(dB/10) CRC: append r zeros, XOR divide, last r bits | checksum: add, wrap the carry, invert Hamming: 2^r >= m+r+1, syndrome = position of the bad bit U = min(1, N(L/R)/(RTT+L/R)) GBN W<=2^k-1, SR W<=2^(k-1) slotted 1/e, pure 1/(2e), Np(1-p)^(N-1) Lmin = 2 dprop R /n -> hosts 2^(32-n)-2, block = 256 - mask octet fragment data = (MTU-20) rounded down to a multiple of 8, offset = byte/8, last fragment MF=0 Dijkstra: add the smallest D, update neighbours DV: Dx(y)=min_v{c(x,v)+Dv(y)} SYN and FIN each consume one seq; ack = next expected byte slow start x2 (up to ssthresh), CA +1, timeout: ssthresh=cwnd/2, cwnd=1 Reno 3 dupACK: ssthresh=cwnd/2, cwnd=ssthresh(+3), continue from CA Est=0.875Est+0.125S, Dev=0.75Dev+0.25|S-Est|, TO=Est+4Dev rwnd = RcvBuffer - (LastByteRcvd - LastByteRead); sending <= min(cwnd, rwnd)