Question 1 of 5: IP Packet Routing

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.

[Figure not reproduced: Figure 1.1 — The three-LAN internetwork of Question 1, redrawn from the examination paper. Each dark box is a router with one interface on the bus above it and one on the bus below; R1 joins 128.100.11.0 to 128.100.12.0, and R2 joins 128.100.12.0 to 128.100.13.0 and also carries the Internet u. See the official exam paper.]

Approach. Read the two router boxes as two-interface devices, build each table by listing first the directly connected prefixes and then the remote ones reachable through the neighbouring router (plus one default route), and then trace the datagram by applying the longest-prefix-match rule at every device it meets.

1. Part (a) — establish what each router owns. A router is identified by its interfaces, not by a single address. The upper dark box has one interface on 128.100.11.0 numbered 128.100.11.3 and one on 128.100.12.0 numbered 128.100.12.3; call it R1. The lower dark box has one interface on 128.100.12.0 numbered 128.100.12.254 and one on 128.100.13.0 numbered 128.100.13.3, plus the uplink; call it R2. Applying the netmask confirms the assignment, because the bitwise AND of an interface address with 255.255.255.0 must equal the network number of the bus it sits on:
   $$128.100.11.3 \;\wedge\; 255.255.255.0 = 128.100.11.0, \qquad 128.100.12.3 \;\wedge\; 255.255.255.0 = 128.100.12.0$$

   so R1 genuinely straddles the top two LANs, and the same test puts 128.100.12.254 and 128.100.13.3 on the lower two.

2. Write R1's forwarding table. R1 is directly attached to 128.100.11.0 and 128.100.12.0, so those two entries need no gateway — delivery is by ARP on the local medium. Everything else, including 128.100.13.0 and the whole Internet, lies beyond R2, so the next hop is R2's near-side interface 128.100.12.254 and the outgoing interface is 128.100.12.3.

   Destination	Netmask	Next hop (gateway)	Out interface
   128.100.11.0	255.255.255.0	direct delivery	128.100.11.3
   128.100.12.0	255.255.255.0	direct delivery	128.100.12.3
   128.100.13.0	255.255.255.0	128.100.12.254	128.100.12.3
   0.0.0.0 (default)	0.0.0.0	128.100.12.254	128.100.12.3

   The default entry could equally be omitted and the 128.100.13.0 line kept, but with a default route present the explicit 128.100.13.0 line is what makes the internal traffic follow the same path deterministically rather than by accident.

3. Write R2's forwarding table. R2 is directly attached to 128.100.12.0 and 128.100.13.0. The only remote internal prefix is 128.100.11.0, reached through R1's near-side interface 128.100.12.3, and every non-local destination leaves by the uplink.

   Destination	Netmask	Next hop (gateway)	Out interface
   128.100.12.0	255.255.255.0	direct delivery	128.100.12.254
   128.100.13.0	255.255.255.0	direct delivery	128.100.13.3
   128.100.11.0	255.255.255.0	128.100.12.3	128.100.12.254
   0.0.0.0 (default)	0.0.0.0	Internet next hop	uplink

   Each table has exactly four entries because there are three internal prefixes plus one default, and in both tables the default is the least specific line, so longest-prefix match reaches it only when nothing else applies.

4. State the hosts' side of the arrangement. The hosts need only their own netmask and one default gateway: the two hosts on 128.100.11.0 point at 128.100.11.3, the two on 128.100.12.0 may point at either 128.100.12.3 or 128.100.12.254 (128.100.12.254 is the sensible choice, since most traffic is Internet-bound and R1 would otherwise redirect), and the two on 128.100.13.0 point at 128.100.13.3. A host applies its own mask first: if the destination is on its own subnet it ARPs for the destination directly, otherwise it sends the frame to the gateway.

5. Part (b) — the originating host decides the packet is off-net. Host 128.100.13.2 masks both its own address and the destination with 255.255.255.0:
   $$128.100.13.2 \;\wedge\; 255.255.255.0 = 128.100.13.0 \;\neq\; 128.100.11.0 = 128.100.11.1 \;\wedge\; 255.255.255.0$$

   The two results differ, so the destination is not on the local LAN. The host therefore ARPs for its default gateway 128.100.13.3, and sends a frame whose destination MAC address is R2's but whose IP destination is still 128.100.11.1.

6. R2 forwards toward R1. R2 looks up 128.100.11.1 in the table above. The 128.100.11.0/24 entry matches, so R2 does not use its default route; it decrements the TTL, recomputes the header checksum, ARPs for 128.100.12.3 and transmits the datagram onto 128.100.12.0 in a new frame addressed to R1.

7. R1 delivers. R1 matches 128.100.11.1 against its 128.100.11.0/24 entry, which is directly connected, so there is no further gateway. R1 decrements the TTL again, ARPs for 128.100.11.1 on the top LAN and delivers the datagram in a frame addressed to the destination host's own MAC address. The complete path is
   $$\boxed{128.100.13.2 \;\rightarrow\; \text{R2 } (128.100.13.3 / 128.100.12.254) \;\rightarrow\; \text{R1 } (128.100.12.3 / 128.100.11.3) \;\rightarrow\; 128.100.11.1}$$

   two router hops across three LANs. Note what changes and what does not: the IP source and destination addresses are constant end to end, the link-layer addresses are rewritten on every hop, and the TTL falls by one per router, so a datagram launched with TTL 64 arrives with TTL 62. The traffic never touches the Internet uplink, because the specific 128.100.11.0/24 entry outranks the default route.

8. Part (c) — why IPv4 addresses ran out. An IPv4 address is a 32-bit integer, so the entire address space is
   $$2^{32} = 4\,294\,967\,296 \approx 4.3 \times 10^{9} \ \text{addresses}$$

   fewer than the human population and far fewer than the number of connected devices. The usable figure is smaller still: the loopback block 127.0.0.0/8, multicast space 224.0.0.0/4 and the old class-E range are reserved; the original classful allocation handed a class-A holder 16.7 million addresses whether or not it needed them; and every subnet loses its network and broadcast addresses. IANA distributed its last free /8 blocks in February 2011 and the regional registries have been rationing ever since, which is the practical form the exhaustion takes: a new network cannot obtain a globally unique public block.

9. Give a solution. The definitive answer is IPv6, whose 128-bit addresses give $2^{128} \approx 3.4 \times 10^{38}$ addresses, roughly $2^{96}$ times the IPv4 space, so that global uniqueness can be restored and end-to-end connectivity recovered; dual-stack operation and tunnelling let it be deployed alongside IPv4 rather than by flag day. Two stop-gaps that are also acceptable answers are NAT, which hides a whole private RFC 1918 network such as 10.0.0.0/8 behind one public address by multiplexing the 16-bit TCP/UDP port number space, at the cost of breaking end-to-end addressing and complicating incoming connections and peer-to-peer applications; and CIDR, which replaced fixed class boundaries with variable-length prefixes so blocks can be sized to actual need and aggregated in the routing tables, buying roughly a decade but not creating new addresses.