Chapter 6’s homework, made answerable in the browser — and every numeric answer here was computed with the same code the rest of the site runs on.
What this page is
-
Review questions — the book’s R1 to R16, the ones with a definite answer.
-
Problems — a selection of P1 to P33, chosen for having a number or a decision as an answer.
-
Three labs, each a widget from an earlier section, running on the problem’s own numbers.
-
The Wireshark labs, rebuilt over the captures this chapter already built.
-
A word from Albert Greenberg.
Answer before opening a solution. A solution read too early is a solution not learned, which is why each one stays hidden until you have tried.
Why this matters
Reading a chapter and being able to use it are different things, and the gap between them is exactly what these problems measure.
Several of them also close a loop. P8 and P9 derive the 1/e and 1/(2e) that section 6.3.2 simply stated. P32 computes the 2.5 Gbps that made data centre topologies change. P18 works out why Ethernet has a minimum frame size at all — a fact that had to be taken on trust when the frame was first drawn.
Review questions
Review questions
The book’s R1 to R16. Answer first, then open the solution — a solution read before you have tried is a solution not learned.
R2If every link in the Internet provided reliable delivery, would TCP’s reliable delivery service be redundant?
Choose the best answer.
R4Two nodes start transmitting at the same instant, a packet of length L over a broadcast channel of rate R. The propagation delay between them is d_prop. Is there a collision if d_prop < L/R?
Choose the best answer.
R6In CSMA/CD, after the fifth collision, what is the probability that a node chooses K = 4? And how long a delay is K = 4 on a 10 Mbps Ethernet?
a.Probability of choosing K = 4 after five collisions
b.The delay for K = 4 on a 10 Mbps Ethernet, in microseconds
µsR9How big is the MAC address space? The IPv4 space? The IPv6 space?
A MAC address is how many bits?
bitsR10A, B and C share a broadcast LAN. A sends thousands of datagrams to B, each frame addressed to B’s MAC address. Does C’s adapter process them? Does C’s network layer see them?
What does C do with these frames?
R12In Figure 6.19 the router has two ARP modules, each with its own table. Can the same MAC address appear in both?
Choose the best answer.
R13Compare the frame structures of 10BASE-T, 100BASE-T and Gigabit Ethernet. How do they differ?
How do the frame formats differ?
R15What is the maximum number of VLANs configurable on a switch supporting 802.1Q, and why?
Maximum number of VLANs
Problems
Problems
A selection of the book’s P1 to P33 — the ones whose answers are a number or a decision rather than a paragraph. Every numeric answer here was computed with the same code the widgets on this site run.
P5The generator is G = 10011 and the data is D = 1010101010. What is R?
Remember that r is one less than the length of G, so R has 4 bits, and all the arithmetic is modulo 2.
What is R?
P8Complete the derivation of slotted ALOHA’s efficiency.
With N active nodes the efficiency is N·p·(1 − p)^(N−1).
a.Which p maximises that expression?
b.Using that p, the efficiency as N approaches infinity
P11Four nodes A, B, C and D use slotted ALOHA, each with an infinite backlog and each transmitting in every slot with probability p.
a.Probability that some node succeeds in slot 5?
b.The efficiency of this four-node system (its maximum over p)
P17After a collision an adapter waits K × 512 bit times. For K = 100, how long is that on a 100 Mbps channel? On a 1 Gbps channel?
a.The wait on 100 Mbps, in microseconds
µsb.The wait on 1 Gbps, in microseconds
µsP18A and B are on the same 10 Mbps channel with a propagation delay of 325 bit times. A starts transmitting; before it finishes, B starts too. Can A finish before it detects B?
Can A finish transmitting before detecting the collision?
P32In the hierarchical data centre of Figure 6.30, each host has a 10 Gbps link to its TOR switch and the switch-to-switch links are 100 Gbps. Forty flows cross the same link.
a.The rate each flow receives, in Gbps
Gbpsb.Two hosts in the SAME rack: what rate, in Gbps?
Gbps
The CRC problems, stepped
P5 and P6 are the same division four times over. Rather than doing it on paper four times, do it once here and change the data.
Step 10: the working bit at position 10 is 0, so G does not fit here. The quotient gets a 0 and nothing changes.
The last 4 bits of the working value are 0100 — that is R, the CRC bits. What goes on the wire is D followed by R:
10101010100100click a bit to damage it in flight
The receiver divides by G and gets remainder 0000 — zero, so the data is accepted.
The generator from P5. Step through the long division, then edit the data to 1000100101, 0101101010 and 0110100011 for P6’s three parts. Damage the transmitted pattern afterwards and watch the receiver’s remainder stop being zero.
The ALOHA problems
| Slots so far: 40 | Counted | Fraction | Formula predicts |
|---|---|---|---|
| S — Successful | 17 | 42.5% | 42.2% |
| E — Empty | 14 | 35.0% | 31.6% |
| C — Collision | 9 | 22.5% | 26.2% |
The formula column is the book’s N·p·(1−p)N−1 for a success, (1−p)N for an empty slot, and the rest for a collision. A short run wanders; press “New run” a few times and watch it settle.
P11’s four nodes, started at the best p = 1/N = 0.25. The formula column predicts 42.2 per cent successful slots — higher than 1/e, because 1/e is the large-N limit and is approached from above. Drag p away from 0.25 in either direction and watch the measured column fall.
P12 asks you to graph the efficiency of both protocols against p for N = 10, 30 and 50. The plot on section 6.3.2 does exactly that, with N on a slider. Set it to each of the three values and watch the peak slide left while its height barely moves.
The switch problems
Switch table — 0 entries
| Address | Interface | Time |
|---|---|---|
| empty — a switch starts knowing nothing | ||
An entry is deleted when no frame has arrived with that address as its source for 60 minutes.
Frames sent
Send one frame, then send one back the other way. The second is the interesting one.
Send frames in whatever order the problem asks for and read the table off directly. Remember which address a switch stores: the source, never the destination.
Wireshark Labs: 802.3 Ethernet, and address resolution
The book points at two labs on its companion website. One covers the operation of the IEEE (Institute of Electrical and Electronics Engineers) Institute of Electrical and Electronics Engineers The body whose 802 committee standardises Ethernet and WiFi. introduced in ch. 1 802.3 protocol and the Ethernet frame format; the other covers ARP (Address Resolution Protocol) Address Resolution Protocol Translates an IP address into the MAC address of an interface on the same subnet. It works only within one subnet, which is the whole point. introduced in ch. 6 .
This site cannot run Wireshark, so both are here instead, over captures that were generated and then independently verified.
The Ethernet frame, field by field
Open any frame below and expand its Ethernet II layer. Every field of Figure 6.20 is there — destination, source, type — and clicking one highlights exactly the bytes it occupies.
Two things the lab asks you to look for:
- The type field. Compare an ARP frame (0x0806) with an IP (Internet Protocol) Internet Protocol The network-layer protocol that defines the datagram format and addressing every Internet device must use. introduced in ch. 1 one (0x0800), and you have seen demultiplexing happen.
- The padding. Every ARP frame here is exactly 60 bytes, because Ethernet’s data field has a 46-byte minimum. The trailing zeros are real.
| No. | Time | Source | Destination | Protocol | Length | Info |
|---|---|---|---|---|---|---|
| 1 | 0.000000 | 74:29:9c:e8:ff:55 | Broadcast | ARP | 60 | Who has 111.111.111.110? Tell 111.111.111.111 |
| 2 | 0.000400 | e6:e9:00:17:bb:4b | 74:29:9c:e8:ff:55 | ARP | 60 | 111.111.111.110 is at e6:e9:00:17:bb:4b |
| 3 | 0.000900 | 111.111.111.111 | 222.222.222.222 | ICMP | 58 | Echo (ping) request id=0x1c46 seq=1 |
| 4 | 0.001300 | 1a:23:f9:cd:06:9b | Broadcast | ARP | 60 | Who has 222.222.222.222? Tell 222.222.222.220 |
| 5 | 0.001600 | 49:bd:d2:c7:56:2a | 1a:23:f9:cd:06:9b | ARP | 60 | 222.222.222.222 is at 49:bd:d2:c7:56:2a |
| 6 | 0.002000 | 111.111.111.111 | 222.222.222.222 | ICMP | 58 | Echo (ping) request id=0x1c46 seq=1 |
| 7 | 0.002400 | 222.222.222.222 | 111.111.111.111 | ICMP | 58 | Echo (ping) reply id=0x1c46 seq=1 |
| 8 | 0.002900 | 222.222.222.222 | 111.111.111.111 | ICMP | 58 | Echo (ping) reply id=0x1c46 seq=1 |
Packet 1 — Subnet 1. The sending host wants to reach 222.222.222.222, which is NOT on its subnet, so it needs the MAC address of its first-hop router — not of the destination. The query goes to the MAC broadcast address FF-FF-FF-FF-FF-FF, so every adapter on the subnet passes it up to its ARP module.
Protocol tree — click a field
The actual bytes
0000 ff ff ff ff ff ff 74 29 9c e8 ff 55 08 06 00 01 ......t)...U....0010 08 00 06 04 00 01 74 29 9c e8 ff 55 6f 6f 6f 6f ......t)...Uoooo0020 00 00 00 00 00 00 6f 6f 6f 6e 00 00 00 00 00 00 ......ooon......0030 00 00 00 00 00 00 00 00 00 00 00 00 ............
Merged from two capture points, one on each subnet, because no single machine can see both. Packets 3 and 6 are the same datagram on either side of the router: identical IP addresses, and not one Ethernet address in common.
ARP, and the two-frame journey
The lab on ARP asks what a datagram’s addresses look like on either side of a router. Open packets 3 and 6 and compare them: identical IP addresses, identical payload, and not one Ethernet address in common.
The whole request
And if you want the lab the book does not set, section 6.7’s capture has every protocol in the chapter running at once.
| No. | Time | Source | Destination | Protocol | Length | Info |
|---|---|---|---|---|---|---|
| 1 | 0.000000 | 0.0.0.0 | 255.255.255.255 | DHCP | 292 | DHCP Request — Transaction ID 0x3d1e |
| 2 | 0.002100 | 68.85.2.1 | 255.255.255.255 | DHCP | 304 | DHCP ACK — yiaddr 68.85.2.101 |
| 3 | 0.010400 | 00:16:d3:23:68:8a | Broadcast | ARP | 60 | Who has 68.85.2.1? Tell 68.85.2.101 |
| 4 | 0.011100 | 00:22:6b:45:1f:1b | 00:16:d3:23:68:8a | ARP | 60 | 68.85.2.1 is at 00:22:6b:45:1f:1b |
| 5 | 0.011800 | 68.85.2.101 | 68.87.71.226 | DNS | 74 | Standard query A www.google.com |
| 6 | 0.039200 | 68.87.71.226 | 68.85.2.101 | DNS | 90 | Standard query response A 64.233.169.105 |
| 7 | 0.040100 | 68.85.2.101 | 64.233.169.105 | TCP | 54 | 49153 → 80 [SYN] Seq=0x51a20000 |
| 8 | 0.068400 | 64.233.169.105 | 68.85.2.101 | TCP | 54 | 80 → 49153 [SYN, ACK] Seq=0x9c4f0000 Ack=0x51a20001 |
| 9 | 0.068500 | 68.85.2.101 | 64.233.169.105 | TCP | 54 | 49153 → 80 [ACK] Ack=0x9c4f0001 |
| 10 | 0.068700 | 68.85.2.101 | 64.233.169.105 | HTTP | 162 | GET / HTTP/1.1 Host: www.google.com |
| 11 | 0.097100 | 64.233.169.105 | 68.85.2.101 | HTTP | 179 | HTTP/1.1 200 OK (text/html) |
Packet 1 — Steps 1 to 3. Bob’s laptop has no address yet, so the source IP is 0.0.0.0 and the destination is the broadcast 255.255.255.255. The frame goes to FF:FF:FF:FF:FF:FF, and the switch broadcasts it on every port — including the one leading to the router. Everything the laptop will do for the rest of this capture depends on the answer.
Protocol tree — click a field
The actual bytes
0000 ff ff ff ff ff ff 00 16 d3 23 68 8a 08 00 45 00 .........#h...E.0010 01 16 10 00 00 00 40 11 69 d8 00 00 00 00 ff ff ......@.i.......0020 ff ff 00 44 00 43 01 02 89 5a 01 01 06 00 00 00 ...D.C...Z......0030 3d 1e 00 00 00 00 00 00 00 00 00 00 00 00 00 00 =...............0040 00 00 00 00 00 00 00 16 d3 23 68 8a 00 00 00 00 .........#h.....0050 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................0060 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................0070 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................0080 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................0090 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................00a0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................00b0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................00c0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................00d0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................00e0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................00f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................0100 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................0110 00 00 00 00 00 00 63 82 53 63 35 01 03 37 03 01 ......c.Sc5..7..0120 03 06 ff 00 ....
Eleven frames, six protocols, and one chain: every address after frame 2 was learned from an earlier frame in this capture. Nothing here was typed in twice.
Voices from the field — Albert Greenberg
Albert Greenberg’s work is why the data centre section of this chapter looks the way it does. His group’s measurements of production data centres established the thing section 6.6 is built around. The hierarchical topology scales fine and then starves host-to-host traffic, and the answer is a denser interconnect rather than faster switches.
The reference at the heart of §6.6 — Greenberg 2009 — is the paper that put numbers on it. The 2.5 Gbps figure you computed in P32 is that argument in one line.
Worth noticing. The section’s most important claim is not a protocol at all. It is a measurement: networking is 15 per cent of a data centre’s cost, and it is the 15 per cent worth improving.
What to remember from the problems
- After n collisions K comes from 2ⁿ equally likely values. A wait in bit times then scales with the link: K × 512 is 512 µs on 100 Mbps and 51.2 µs on 1 Gbps.
- 1/e is a limit, not a cap for small N. Slotted ALOHA’s best p is 1/N, and the efficiency approaches 1/e from above — four nodes manage 42 per cent.
- A frame shorter than 2 × d_prop can finish before its sender learns of a collision. That is why Ethernet has a minimum frame size — and, like the 4,096 VLANs, most limits in this chapter are field widths.
What is not here
The book’s P14, P15, P16 and P31 ask you to enumerate every step of a datagram’s journey across a multi-router network, in prose. They are excellent problems and they do not become better for being made clickable.
Do them on paper, then check yourself against section 6.7’s capture — which is the same exercise, worked, for a network one router deep.