Question 4 of 5: IP Packet Routing

Question 4: 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.

Part (a) — Size of the IPv4 address space.

Given. The IPv4 header carries a source and a destination address, each a fixed field of 32 bits.

Find. The total number of distinct addresses that field can express, ignoring reservations.

1. Count the codepoints of a 32-bit field. Each bit doubles the number of distinct patterns, so $$\boxed{2^{32} = 4{,}294{,}967{,}296 \approx 4.29 \times 10^{9}\ \text{addresses.}}$$ Written in dotted decimal this is every value from 0.0.0.0 to 255.255.255.255.

Address space exhaustion is the fact that this number, large as it looked in 1981, is smaller than the world’s population and far smaller than the count of devices wanting an address. The shortage was made much worse by how the space was handed out. Classful allocation gave an organisation an entire class A block of $2^{24}$ addresses or a class B block of $2^{16}$ whether or not it could use them, so an institution needing 300 hosts consumed 65,536; the addresses were allocated, hence unavailable to anyone else, while sitting idle. IANA distributed its last unreserved blocks to the regional registries in February 2011, and ARIN, which serves Canada, ran its free pool down to exhaustion in September 2015.

Several solutions exist and all have been deployed. Network address translation (NAT) lets an entire site hide behind one public address, rewriting the address and port of each outgoing packet and keeping a translation table to reverse the change; it is why RFC 1918 private ranges such as 192.168.0.0/16 can be reused endlessly, at the cost of breaking end-to-end addressing and complicating inbound connections. Classless inter-domain routing (CIDR) replaced fixed classes with a variable prefix length, so a site needing 300 hosts receives a /23 rather than a class B, and it aggregates routes to keep backbone tables small. The permanent fix is IPv6, whose 128-bit address gives $2^{128} \approx 3.4 \times 10^{38}$ addresses. Any one of these is an acceptable answer to the question; NAT and CIDR bought the time in which IPv6 could be deployed.

Part (b) — Routing tables at both routers.

Given. The three-LAN internetwork drawn with the question, redrawn below. Each LAN is a class B network subnetted on a byte boundary, so the netmask throughout is 255.255.255.0, equivalently a /24 prefix.

Find. A complete forwarding table for each router, giving destination network, netmask, gateway and outgoing interface.

Approach. Enter one directly-connected route per interface, one indirect route for each subnet reachable only through the other router, and a default route for everything else; the router that owns the Internet link is the one whose default points outward.

1. Fix the netmask. The three subnets differ in the third octet, so the network part is 24 bits: the mask is 255.255.255.0, leaving $2^{8} - 2 = 254$ usable host addresses per subnet after excluding the all-zeros network address and the all-ones broadcast address. Both routers use this mask on every entry.
2. Enter R1’s directly-connected routes. R1 has an interface on 128.100.11.0 and one on 128.100.12.0, so packets for either are delivered by ARP on the local wire with no gateway.
3. Enter R1’s indirect and default routes. 128.100.13.0 is reachable only through R2, whose near-side address is 128.100.12.254, so that is the gateway and 128.100.12.3 the outgoing interface. Everything else must also leave through R2, which owns the Internet link, so R1’s default route 0.0.0.0/0.0.0.0 points at the same gateway.

4. Enter R2’s directly-connected routes. R2 sits on 128.100.12.0 through 128.100.12.254 and on 128.100.13.0 through 128.100.13.3, so both are direct.
5. Enter R2’s indirect and default routes. 128.100.11.0 lies behind R1, so the gateway is 128.100.12.3 out of the 128.100.12.254 interface. R2 owns the Internet link, so its default route points out of that interface to the upstream provider’s router rather than back into the site — pointing it at R1 would create a routing loop between the two.

Each host needs only two entries of its own: its local subnet as a direct route, and a default route to the router interface on its wire — 128.100.11.3 for the hosts on the top LAN, 128.100.12.3 or 128.100.12.254 for those on the middle LAN, and 128.100.13.3 for those on the bottom LAN. Forwarding is by longest-prefix match, so the specific /24 entries are always preferred over the /0 default.

Part (c) — Path from 128.100.11.2 to 128.100.13.1. The source host masks its own address and the destination with 255.255.255.0, obtaining 128.100.11.0 and 128.100.13.0. These differ, so the destination is not on the local wire and the packet cannot be delivered by ARP; the host sends it instead to its default gateway, addressing the frame to the MAC address of 128.100.11.3 while leaving the IP destination untouched at 128.100.13.1.

R1 receives the frame, strips it, and looks up 128.100.13.1 in the table above. The longest match is the 128.100.13.0/24 entry, whose gateway is 128.100.12.254, so R1 decrements the time-to-live, recomputes the header checksum, and forwards the packet out of its 128.100.12.3 interface in a frame addressed to R2. R2 in turn matches 128.100.13.0/24 as a direct route, ARPs for 128.100.13.1 on the bottom LAN, and delivers it. The path is therefore

128.100.11.2 → R1 (128.100.11.3 in, 128.100.12.3 out) → R2 (128.100.12.254 in, 128.100.13.3 out) → 128.100.13.1

three IP hops, crossing all three LANs. Note that the middle LAN is traversed as a transit segment even though neither endpoint lives on it.

Part (d) — Path from 128.100.11.1 to 128.100.1.1. The arithmetic begins the same way and ends differently. Masking 128.100.1.1 with 255.255.255.0 gives the network 128.100.1.0, which matches none of the three subnets in the diagram, so the source host again hands the packet to 128.100.11.3.

R1 searches its table and finds no /24 entry for 128.100.1.0; the only entry that matches is the default route, whose gateway is 128.100.12.254. R1 forwards to R2, which likewise finds no specific match and falls back on its default route, sending the packet out of the Internet interface toward the upstream provider. The path within the site is

128.100.11.1 → R1 → R2 → Internet (destination lies outside this internetwork)