Chapter 4 Problems, Wireshark Lab and Interview

Network layer ✎ Practice Kurose & Ross pp. 364–376 · ~9 min read

  • longest prefix matching
  • subnet
  • network address translation

Where you are

  • Application layer
  • Transport layer
  • Network layer you are here
  • Link layer
  • Physical layer

Thirty-five review questions and twenty-five problems — mostly about addresses, and several of them traps for an answer that is very nearly right.

How to use this page

  • Attempt first. A numeric answer reveals its working once you get it right, or when you explicitly ask. An open question hides behind “think first”.
  • Numeric answers accept a 1 % tolerance by default. Counts of addresses and interfaces accept none — they are exact or they are wrong.
  • Two problems are traps. P1(b) says so itself. P8 does not.
  • The interactive address tools below are the same ones from sections 4.3.2 and 4.3.3 — use them to check any answer you are unsure of.

Why this matters

This chapter’s problems are unusually worth doing, because IP (Internet Protocol) addressing is the one topic where an answer can be almost right and completely wrong.

P8 is the clearest case. The obvious five-entry table uses a seven-bit prefix, gets two of the three test addresses right, and fails the third. P9 and P10 look like the same problem and are not — in one the prefixes are disjoint, in the other they nest, and the counts differ accordingly. P1(b) and P22 ask the identical question either side of section 4.4, and the answer changes from “impossible” to “four rows”.

Review questions

Review Questions R1–R35

Thirty-five questions, and several of them are traps for an answer that is nearly right. Attempt first; the worked solution appears once you have.

  1. R1What is a network-layer packet called? And what is the fundamental difference between a router and a link-layer switch, given that both are packet switches?

    a.The name of a network-layer packet:

    b.The fundamental difference between a router and a link-layer switch:

  2. R2What are the main functions of the data plane? Of the control plane?

    Give both.

  3. R3What are the key differences between routing and forwarding?

    Pick the pair.

  4. R4What is the role of the forwarding table within a router?

    Answer, then read the solution.

  5. R5What is the service model of the Internet's network layer? What guarantees does it make about host-to-host delivery?

    The guarantees are:

  6. R6A router consists of input ports, output ports, a switching fabric and a routing processor. Which are hardware and which are software, and why?

    Answer for the four components, then for the two planes.

  7. R7Why does each input port in a high-speed router store a shadow copy of the forwarding table?

    Pick the reason.

  8. R9An arriving packet matches two or more entries in a router's forwarding table. With destination-based forwarding, which rule decides?

    The rule is:

  9. R10List the three switching fabrics. Which, if any, can send multiple packets across the fabric in parallel?

    All three, and the answer to the parallel question.

  10. R11How can packet loss occur at input ports? How can it be eliminated without infinite buffers?

    Both halves.

  11. R12How can packet loss occur at output ports? Can it be prevented by increasing the switch fabric speed?

    Can a faster fabric prevent it?

  12. R13What is head-of-line blocking? Does it occur at input ports or output ports?

    Where does it occur?

  13. R14Of FIFO, priority, round robin and WFQ, which ensure that packets depart in the order they arrived?

    Which ones?

  14. R15Give an example of why a network operator might want one class of packets to have priority over another.

    Give one, and then note where it becomes controversial.

  15. R16What is the essential difference between round robin and WFQ? Is there a case where they behave exactly the same?

    a.When do they coincide?

    b.And the essential difference?

  16. R17Host B receives an IP datagram carrying a TCP segment. How does its network layer know to pass the payload to TCP rather than UDP?

    From which field?

  17. R18Which IP header field ensures a packet is forwarded through no more than N routers?

    The field is:

  18. R19A transport-layer segment is encapsulated in an IP datagram. Are the segment checksum and the datagram checksum computed over any common bytes?

    Answer, then read the solution.

  19. R20When a large datagram is fragmented, where are the fragments reassembled?

    Where?

  20. R21Do routers have IP addresses? If so, how many?

    Answer:

  21. R22What is the 32-bit binary equivalent of 223.1.3.27?

    Pick the binary form.

  22. R24Three routers sit between a source host and a destination host. Ignoring fragmentation, how many interfaces does a datagram travel over? How many forwarding tables are indexed?

    a.Interfaces traversed:

    interfaces

    b.Forwarding tables indexed:

    tables

  23. R25An application generates 40 bytes of data every 20 ms. Each chunk is put in a TCP segment and then an IP datagram. What percentage of each datagram is overhead?

    Percentage that is overhead:

    %

  24. R26You buy a wireless router, connect it to a cable modem, and your ISP dynamically assigns it one IP address. Five PCs connect wirelessly. How do they get addresses? Does the router use NAT?

    Both questions.

  25. R27What is route aggregation, and why is it useful?

    Define it and say what it buys.

  26. R28What is meant by a "plug-and-play" or "zeroconf" protocol?

    It means:

  27. R29What is a private network address? Should a datagram carrying one ever appear in the public Internet?

    Should it?

  28. R30Compare the IPv4 and IPv6 header fields. Do they have any in common?

    Which survive, which are renamed, and which are gone.

  29. R31It has been said that when IPv6 tunnels through IPv4 routers, IPv6 treats the IPv4 tunnels as link-layer protocols. Do you agree?

    Agree or not?

  30. R33What is the difference between a destination-based forwarding table and OpenFlow's flow table?

    Give the differences.

  31. R35Name three IP datagram header fields that can be matched in OpenFlow 1.0, and three that cannot.

    Three of each, and why the line falls where it does.

Problems

Problems P1–P25

Every address, prefix and count here was computed rather than copied. Two problems are traps — P1(b) says so itself, and P8 has one the book does not warn you about.

  1. P1A network with hosts H1 and H2 on the left, routers A, B, C and D, and host H3 on the right. A's interfaces 1 and 2 face the hosts; 3 goes to B and 4 goes to C.

    a.Give a forwarding table in router A that sends all traffic destined to H3 out of interface 3.

    b.Can you write a table in A that sends H1's traffic for H3 out of interface 3, but H2's traffic for H3 out of interface 4?

  2. P2Two packets arrive at two different input ports at exactly the same time, and the router is otherwise empty.

    a.Different output ports, shared-bus fabric. Can both cross at once?

    b.Different output ports, switching via memory. Can both cross at once?

    c.The SAME output port, crossbar fabric. Can both cross at once?

  3. P3R_switch = R_line, and all packets go to different output ports. Let D be the time to transmit one packet. What is the maximum input queueing delay for each fabric?

    Give it for memory, bus and crossbar, as a function of D and N.

  4. P4A crossbar switch, slotted and synchronous. Input queues hold: X · X,Y · Z,Y (front of each queue listed first). At most one datagram may reach a given output port per slot.

    a.Minimum number of slots, with any scheduling order you like:

    slots

    b.Maximum number of slots, with the worst scheduling order — a non-empty input queue is never idle:

    slots

  5. P5WFQ over three classes with weights 0.5, 0.25 and 0.25.

    a.All three classes are backlogged. Which service sequence achieves the weights?

    b.Classes 1 and 2 are backlogged; class 3 has nothing queued. Now what?

  6. P6Twelve packets arriving over time, one transmitted per slot. Arrivals: packet 1 at t = 0; 2 and 3 at t = 1; 4 and 5 at t = 2; 6 at t = 3; 7 at t = 4; 8 at t = 5; 9 at t = 6; 10 at t = 7; 11 and 12 at t = 8.

    a.FIFO service — give the departure order.

    b.Priority service — odd packets high, even packets low. Give the departure order.

    c.What do you notice about the average delay across all four disciplines?

  7. P8A router with four links, 0 to 3, and 32-bit addresses. Interface 0 takes 11100000 00000000 … through 11100000 00111111 …; interface 1 takes 11100000 01000000 00000000 … through 11100000 01000000 11111111 …; interface 2 takes 11100000 01000001 … through 11100001 01111111 …; otherwise interface 3.

    a.Give a five-entry forwarding table using longest prefix matching.

    Hint: Interface 2's range crosses a byte boundary. One prefix will not express it.

    b.Which interface does 11100001 10000000 00010001 01110111 take?

  8. P98-bit addresses. Forwarding table: prefix 00 → interface 0; 010 → 1; 011 → 2; 10 → 2; 11 → 3.

    How many addresses reach interface 2?

    addresses

  9. P108-bit addresses. Forwarding table: prefix 1 → interface 0; 10 → 1; 111 → 2; otherwise → 3.

    How many addresses reach interface 0?

    addresses

  10. P11A router joins three subnets, all required to have the prefix 223.1.17/24. Subnet 1 needs at least 60 interfaces, Subnet 2 at least 90, Subnet 3 at least 12. Give three addresses of the form a.b.c.d/x.

    Give the three, and say why the order matters.

  11. P12Rewrite section 4.2.1's example forwarding table in a.b.c.d/x notation instead of binary.

    Give the four entries.

  12. P13Rewrite P8's forwarding table in a.b.c.d/x notation.

    Give the five entries.

  13. P14Consider the subnet 128.119.40.128/26. Then suppose an ISP owns 128.119.40.64/26 and wants four equal subnets from it.

    a.Which address can be assigned to an interface on 128.119.40.128/26?

    b.Split 128.119.40.64/26 into four equal subnets.

  14. P17Datagrams are limited to 1,500 bytes including header, with a 20-byte IP header. How many datagrams are needed to send an MP3 of 5 million bytes?

    Number of datagrams:

    datagrams

  15. P18Figure 4.25's setup, but the ISP assigns the router 24.34.112.235 and the home network is 192.168.1/24.

    a.Assign addresses to all interfaces in the home network.

    b.Each host has two TCP connections to port 80 at 128.119.40.86. Give the six NAT translation table entries.

  16. P19You want to count the hosts behind a NAT. The IP identification field is stamped sequentially by each host, starting from a random number, and you can sniff every packet the NAT sends outward.

    a.Outline a technique, and justify it.

    b.If identification numbers were assigned randomly rather than sequentially, would the technique work?

  17. P20Arnold wants to download a file from Bernard. Both are behind NATs. Devise a technique that lets Arnold open a TCP connection to Bernard without application-specific NAT configuration — or explain why it is hard.

    Try it, then read the solution.

  18. P21Figure 4.30's OpenFlow network. In s2: datagrams on input port 1 from h5 or h6 destined to h1 or h2 go out port 2; datagrams on input port 2 from h1 or h2 destined to h5 or h6 go out port 1; datagrams on ports 1 or 2 destined to h3 or h4 go to that host; h3 and h4 can send to each other.

    Give s2's flow table.

  19. P22Same network. Datagrams from h3 destined for h1, h2, h5 or h6 go clockwise; datagrams from h4 to the same destinations go counter-clockwise.

    Give s2's flow table.

  20. P24Make s2 act as a firewall. Give a separate flow table for each of four behaviours, covering delivery to h3 and h4.

    All four tables.

  21. P25Consider the protocol stack of Figures 1.23 and 4.31. Is ICMP a network-layer protocol or a transport-layer protocol?

    Which is it?

P8, with the addresses live

P8 — the two addresses that differ in one bit
looking up
11100001.01000000.11000011.00111100
prefixbitsmatches?interface
224.0.0.0/1010no0
224.64.0.0/1616no1
224.0.0.0/88no2
225.0.0.0/99yes2← longest match wins
0.0.0.0/00yes3

2 of 5 entries match. The router takes 225.0.0.0/9 because it is the longest — the most specific rule, written with the most knowledge about this particular address. This is the entry interface 2 needs because its range crosses a byte boundary.

P8’s second address, 11100001 01000000 …, in decimal. Now type 225.128.17.119 — the third address, differing in one bit — and watch the /9 stop matching.

The trap in P8, stated plainly

The natural five-entry table is:

1110000000 → 0 1110000001000000 → 1 1110000 → 2 ← seven bits otherwise → 3

It looks right. Interface 2’s range starts 11100000 01000001 and ends 11100001 01111111, and both of those begin 1110000.

But so does 11100001 10000000, which is past the end of interface 2’s range and should take the default. The seven-bit prefix swallows it.

The fix is to give interface 2 two prefixes — 11100000 and 111000010 — which stop exactly where the range stops. Type 225.128.17.119 into the box above: with the correct table it falls through to 0.0.0.0/0.

The general lesson: a range that crosses a power-of-two boundary cannot be one prefix. Interface 2’s range spans 11100000… into 11100001…, so it needs one prefix for each side.

P11, with the blocks live

P11 — checking a subnet plan
the address223.1.17.011011111.00000001.00010001.00000000
the mask255.255.255.12811111111.11111111.11111111.10000000
subnet223.1.17.0/2511011111.00000001.00010001.00000000
last address223.1.17.12711011111.00000001.00010001.01111111
addresses in the block
128
usable for interfaces
126
host bits
7

The shaded bits are the network prefix — the 25 bits every interface on this subnet shares. The rest identify one interface within it. Two of the 128 are reserved: 223.1.17.0 names the subnet itself and 223.1.17.127 is its broadcast address, which is why the usable count is 128 − 2.

Subnet 2 needs 90 interfaces, so it takes the /25. Move the slider to 26 for Subnet 1’s block and to 28 for Subnet 3’s, and read the usable counts.

Allocate the largest subnet first

P11 asks for three subnets inside 223.1.17/24 supporting 60, 90 and 12 interfaces.

SubnetNeedsBlockUsable
290223.1.17.0/25126
160223.1.17.128/2662
312223.1.17.192/2814

Each size is the smallest that fits after subtracting the two reserved addresses — 90 needs more than 62, so a /26 will not do.

The order matters. A /25 must begin at .0 or .128; a /26 at a multiple of 64; a /28 at a multiple of 16. Placing the largest block first always leaves correctly aligned space for the smaller ones. Placing the smallest first can strand the largest with nowhere aligned to go.

Wireshark Lab: IP

The book points at a lab on the companion site that examines the operation of IP, and the datagram format in particular. The site cannot run Wireshark, so here is a real capture instead: the DHCP (Dynamic Host Configuration Protocol) exchange from section 4.3.2-dhcp. It is the best IP capture this chapter has — every packet is a bare IP datagram carrying UDP (User Datagram Protocol) , with nothing above it to distract.

DHCP — four messages, and a host that knew nothing is configured
No.TimeSourceDestinationProtocolLengthInfo
10.0000000.0.0.0255.255.255.255DHCP292DHCP Discover - Transaction ID 0x0000028e
20.002100223.1.2.5255.255.255.255DHCP316DHCP Offer - Transaction ID 0x0000028e
30.0043000.0.0.0255.255.255.255DHCP298DHCP Request - Transaction ID 0x0000028e
40.005800223.1.2.5255.255.255.255DHCP316DHCP ACK - Transaction ID 0x0000028e

Packet 1 — Packet 1 of 4. The client has just joined the network and knows nothing — not its own address, not the subnet it is on, not where a server is. So it shouts. Source 0.0.0.0 because it has no address to use; destination 255.255.255.255 so every host on the subnet hears it. The link layer broadcasts the frame to all nodes.

Protocol tree — click a field

The actual bytes

0000  ff ff ff ff ff ff aa bb  cc 00 00 2a 08 00 45 00  ...........*..E.
0010  01 16 4a 01 00 00 40 11  2f d7 00 00 00 00 ff ff  ..J...@./.......
0020  ff ff 00 44 00 43 01 02  54 ca 01 01 06 00 00 00  ...D.C..T.......
0030  02 8e 00 00 00 00 00 00  00 00 00 00 00 00 00 00  ................
0040  00 00 00 00 00 00 aa bb  cc 00 00 2a 00 00 00 00  ...........*....
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 01 37 04 01  ......c.Sc5..7..
0120  03 06 33 ff                                      ..3.

The exchange of Figure 4.24, as bytes. Watch the source address in packets 1 and 3: still 0.0.0.0, because the address is not the client’s until packet 4 confirms it.

What to look for, as the lab would ask

The version and header length. Every datagram here is IPv4 (Internet Protocol version 4) — version 4 — with a 20-byte header — header-length field 5, counted in 32-bit words. No options, as usual.

The protocol field. 17 in all four packets, meaning UDP. Compare the chapter 3 capture, where it is 6 for TCP (Transmission Control Protocol) . This is section 4.3.1’s glue between the network and transport layers, doing its job.

The header checksum. Different in every packet, because the identification field differs. Verify one by hand if you want the exercise: add the ten 16-bit words of the header, including the checksum itself, with end-around carry, and the answer must be 0xFFFF.

The source address in packets 1 and 3 is 0.0.0.0. A datagram whose sender has no address. Nothing else in this book produces one.

The destination is 255.255.255.255 in all four. The broadcast address of section 4.3.2 — including on the server’s replies, because the client has no address to receive at.

No fragmentation anywhere. All four datagrams are under 320 bytes, far below the 1,500-byte limit, so the identification, flags and offset fields sit unused. That is the normal case, which is part of why the book felt able to skip fragmentation.

An interview with Vinton G. Cerf

Voices from the field

Vinton G. Cerf has served as Vice President and Chief Internet Evangelist for Google since 2005, after more than fifteen years at MCI. He is widely known as the co-designer of the TCP/IP (Transmission Control Protocol / Internet Protocol) protocols and the architecture of the Internet. From 1976 to 1982 at DARPA (Defense Advanced Research Projects Agency) he led the development of Internet and Internet-related packet communication and security techniques. He received the US Presidential Medal of Freedom in 2005 and the National Medal of Technology in 1997.

His closing answer below mentions IPv6 (Internet Protocol version 6) , and it is worth reading against section 4.3.4.

What brought you to specialize in networking?

I was working as a programmer at UCLA in the late 1960s. My job was supported by the US Defense Advanced Research Projects Agency (called ARPA then and DARPA now). I was working in the laboratory of Professor Leonard Kleinrock in the Network Measurement Center of the newly created ARPANet. The first node of the ARPANet was installed at UCLA on September 1, 1969. I was responsible for programming a computer that was used to capture performance information about the ARPANet and to report this information back for comparison with mathematical models and predictions of the performance of the network.

Several of the other graduate students and I were made responsible for working on the so-called host-level protocols of the ARPAnet — the procedures and formats that would allow many different kinds of computers on the network to interact with each other. It was a fascinating exploration into a new world (for me) of distributed computing and communication.

Did you imagine that IP would become as pervasive as it is today when you first designed the protocol?

When Bob Kahn and I first worked on this in 1973, I think we were mostly very focused on the central question: How can we make heterogeneous packet networks interoperate with one another, assuming we cannot actually change the networks themselves? We hoped that we could find a way to permit an arbitrary collection of packet-switched networks to be interconnected in a transparent fashion, so that host computers could communicate end-to-end without having to do any translations in between. I think we knew that we were dealing with powerful and expandable technology, but I doubt we had a clear image of what the world would be like with billions of computers all interlinked on the Internet.

What do you now envision for the future of networking and the Internet? What major challenges lie ahead?

I believe the Internet itself and networks in general will continue to proliferate. There are already billions of Internet-enabled devices on the Internet, including appliances like cell phones, refrigerators, personal digital assistants, home servers, televisions, as well as the usual array of laptops, servers, and so on. Big challenges include support for mobility, battery life, capacity of the access links to the network, and ability to scale the optical core of the network in an unlimited fashion. The interplanetary extension of the Internet is a project that is well underway at NASA and other space agencies. We still need to add IPv6 [128-bit] addressing to the original IPv4 [32-bit addresses] packet format. The list is long!

The sentence to take from this page

“How can we make heterogeneous packet networks interoperate with one another, assuming we cannot actually change the networks themselves?”

That constraint — stated as the central question of 1973 — is the reason for almost everything in this chapter.

It is why the network layer promises so little: a service model that assumes nothing about the networks below it can be built on top of any of them. It is why section 4.5’s waist is narrow, and why Clark calls IP a spanning layer whose job is to hide the differences underneath. And it is why “communicate end-to-end without having to do any translations in between” is both the original goal and the thing middleboxes now violate.

Cerf’s closing line is worth noticing too. “We still need to add IPv6 (Internet Protocol version 6) addressing” — written half a century after the design, and thirty years after IPv6 was specified. Section 4.3.4 explains why that sentence is still true: changing the network layer is like replacing a foundation.

What these problems are really testing

  • A range that crosses a power-of-two boundary is not one prefix. P8’s whole content, and the reason interface 2 needs two entries. Overlapping prefixes then change the counts, because a shorter one keeps only what the longer ones leave.
  • Subtract two from every block. P11 and P14 both turn on a subnet ’s own address and its broadcast address not being assignable.
  • Scheduling redistributes delay; it does not reduce it. P6(e) is the point, and it is worth more than the four schedules that lead to it.