Question 1 of 5: IP packet routing (25 marks)

Question 1 — IP packet routing (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. An IPv4 internet of three Ethernet LANs joined by two routers, as printed on page 2 of the paper and redrawn below. The addresses used are:

Each LAN is identified in the drawing by an address ending in .0 (128.100.11.0, 128.100.12.0, 128.100.13.0), which is the standard notation for a subnet number rather than a host. The three subnets differ only in the third octet, so the subnet mask is 255.255.255.0, i.e. a 24-bit prefix carved out of the class-B block 128.100.0.0/16 owned by the organisation.

Find. (a) the size of the IPv4 address space and what exhaustion means; (b) the complete forwarding table of each router, with netmask and gateway on every row; (c) the hop-by-hop path taken by one named packet, with the forwarding decision justified at each hop; and (d) a defensible commercial recommendation on the offered address.

[Figure not reproduced: Figure 1.1 — The network of page 2, redrawn. Dark boxes are routers, light boxes are hosts, and the heavy horizontal lines are the three Ethernet segments. R1 bridges 128.100.11.0 and 128.100.12.0; R2 bridges 128.100.12.0 and 128.100.13.0 and also carries the site's uplink to the Internet. See the official exam paper.]

Approach. Count the address space from the width of the IPv4 address field, then build each router's table by listing its directly-connected subnets first and reaching every remaining destination through the neighbour router that owns it, and finally trace one packet by applying the longest-prefix-match rule at each hop.

Part (a) — The size of the IPv4 address space

1. Part (a) — count the addresses from the field width. An IPv4 address (RFC 791) is a fixed 32-bit unsigned integer, so the number of distinct bit patterns is

$$N_{\text{IPv4}} = 2^{32} = 4\,294\,967\,296$$

so, ignoring every reserved and special-purpose block as the question directs,

$$\boxed{N_{\text{IPv4}} = 2^{32} \approx 4.29 \times 10^{9} \text{ addresses}}$$

Address space exhaustion is the fact that this total is fixed and finite while the number of devices wanting a globally unique address is not. Two effects consumed it faster than the raw count suggests. First, the original classful allocation was extremely wasteful: an organisation that needed 300 addresses was given a class-B block of 65,536, and the reserved blocks (127.0.0.0/8 loopback, 10.0.0.0/8 and the other private ranges, 224.0.0.0/4 multicast, 240.0.0.0/4 reserved) remove roughly a further seventh of the space from public use. Second, growth was exponential. The consequence is not that the Internet stops working but that no new globally routable addresses can be assigned: IANA handed out its last free /8 blocks to the Regional Internet Registries in February 2011, and ARIN — the registry serving Canada and the United States — ran its free pool to zero in September 2015, before this paper was written.

One possible solution — IPv6. IPv6 (RFC 4291) widens the address to 128 bits, giving

$$N_{\text{IPv6}} = 2^{128} \approx 3.40 \times 10^{38}, \qquad \frac{N_{\text{IPv6}}}{N_{\text{IPv4}}} = 2^{96} \approx 7.92 \times 10^{28}$$

which removes the constraint for any foreseeable device population. Two palliatives are also acceptable answers and both are in wide use: CIDR (RFC 4632), which replaced the fixed class boundaries with an arbitrary-length prefix so a site that needs 300 addresses receives a /23 of 512 rather than a class B of 65,536; and NAT with port translation, which lets an entire site share one public address by rewriting the source address and port of outbound flows. NAT is a palliative rather than a cure because it breaks the end-to-end addressing model and complicates any protocol that carries addresses in its payload.

Part (b) — Routing tables at R1 and R2

Part (b) — method. A router's forwarding table has one row per destination prefix. Rows for subnets the router is physically attached to need no gateway, because the router can ARP for the destination and deliver the frame itself. Every other destination needs a next-hop gateway, and the gateway address must lie on a subnet the router is directly attached to — otherwise the router could not reach the gateway either. Applying that rule mechanically to Figure 1.1 gives the two tables below; the netmask on every LAN row is 255.255.255.0, because each segment is a /24.

Router R1 (interfaces 128.100.11.3 on the upper LAN and 128.100.12.3 on the middle LAN):

Router R2 (interfaces 128.100.12.254 on the middle LAN, 128.100.13.3 on the lower LAN, and the Internet uplink):

Three points earn the marks here. R1's row for 128.100.13.0 is strictly redundant — its default route already points at R2 and would carry that traffic — but it is written out because the question asks for the routing tables of a three-subnet internet, and an explicit row documents the topology and survives a later change of default gateway. R2, by contrast, must carry an explicit row for 128.100.11.0, because its default route points outward at the ISP; without that row every packet for the upper LAN would be sent to the Internet and discarded. Finally, the default route is written 0.0.0.0 with netmask 0.0.0.0, a zero-length prefix that matches every address and therefore always loses the longest-prefix-match competition to any real route.

Host tables follow the same pattern and are worth stating: each host carries one direct row for its own /24 and a default route to the router interface on its own LAN — 128.100.11.3 for the upper LAN, 128.100.12.3 or 128.100.12.254 for the middle LAN, and 128.100.13.3 for the lower LAN. Each /24 offers

$$2^{32-24} - 2 = 256 - 2 = 254 \text{ usable host addresses}$$

after removing the all-zeros subnet number and the all-ones broadcast address, which is why R2 can legitimately sit at .254 while R1 sits at .3.

Part (c) — Path from 128.100.11.2 to 128.100.13.1

1. Part (c) — the source host decides whether the destination is local. Host 128.100.11.2 masks both its own address and the destination with its own netmask and compares:
   $$128.100.11.2 \;\wedge\; 255.255.255.0 = 128.100.11.0, \qquad 128.100.13.1 \;\wedge\; 255.255.255.0 = 128.100.13.0$$The two subnet numbers differ, so the destination is off-link and the packet must go to the default gateway. The host ARPs for 128.100.11.3, and sends an Ethernet frame whose destination MAC address is R1's but whose destination IP address is still 128.100.13.1.
2. R1 performs a longest-prefix-match lookup. 128.100.13.1 matches R1's row for 128.100.13.0/24 (24-bit prefix) and also its default row (0-bit prefix); the longer prefix wins, so R1 forwards to gateway 128.100.12.254 out of interface 128.100.12.3. R1 decrements the TTL, recomputes the header checksum, and rewrites the layer-2 addresses for the middle LAN — the IP addresses are untouched.
3. R2 finds the destination directly connected. 128.100.13.1 matches R2's direct row for 128.100.13.0/24, so there is no further gateway: R2 ARPs for 128.100.13.1 on the lower LAN and delivers the frame. The packet has crossed two routers, so a datagram leaving with $\text{TTL} = 64$ arrives with $\text{TTL} = 62$.

Collecting the hops:

$$\boxed{128.100.11.2 \;\rightarrow\; \text{R1 } (128.100.11.3 \;/\; 128.100.12.3) \;\rightarrow\; \text{R2 } (128.100.12.254 \;/\; 128.100.13.3) \;\rightarrow\; 128.100.13.1}$$

The packet never leaves the site, so R2's default route to the Internet is not used; and note that the middle LAN carries the packet even though neither its source nor its destination lives there, which is exactly why 128.100.12.0 is the busiest segment in this design.

Part (d) — The offer to sell 127.0.0.1

Part (d) — recommendation: do not buy it. 127.0.0.1 is the IPv4 loopback address. The whole of 127.0.0.0/8 — all $2^{24} = 16\,777\,216$ addresses in it — is reserved by RFC 1122 and listed in the IANA special-purpose registry (RFC 6890) for traffic that a host sends to itself. Three separate facts make the offer worthless:

• It is not globally routable. Every conforming router silently discards a datagram whose destination is in 127.0.0.0/8 if it arrives on a real interface, and no registry will advertise the prefix. Bought or not, no packet from the Internet would ever reach it.
• It is not the salesman's to sell. Public IPv4 addresses are assigned, not owned: IANA delegates blocks to the Regional Internet Registries, and in Canada an organisation obtains address space from ARIN or from its upstream ISP under ARIN policy. Reserved space is never transferable under any registry's transfer policy.
• The company already has it. Every IP host on the planet, including every machine in the company, already answers on 127.0.0.1 through its own loopback interface. There is nothing to acquire.