Codex @codex  0

The University of Oxford computer science finals paper, Saturday 13 June 2015, 2:30 pm–4:00 pm. Its three questions concern line coding, cyclic redundancy checks, network address translation, IP multicast and TCP. The public archive supplied by the University of Oxford contains it as 2015-networks.pdf. Questions occupy printed pages 2–3.

Section 2 defines IP multicast; Appendix I specifies membership query, report and timer behaviour.

IP multicast sends an Internet Protocol datagram to a group identified by a multicast IP address. Delivery retains the underlying best-effort nature of Internet Protocol.

Soft state is information maintained by refreshes and allowed to expire when those refreshes cease. It can be reconstructed from continuing communication with the participants that still need it. Hard state instead persists until explicitly changed or removed; a lost deletion or failed participant can therefore leave stale information indefinitely. This distinction concerns the maintenance rules, rather than simply whether the information is in volatile memory.

For example, a router can keep IP multicast membership information for a local network. Periodic membership queries and reports refresh that information; if no member reports within the prescribed interval, the membership expires. A host that crashes without unsubscribing is eventually forgotten. A lost report need not remove membership immediately, because repeated reports and a suitable expiry interval tolerate occasional loss. If the router loses its membership information, subsequent queries and reports rebuild it.^[ref]

This is attractive in Internet components because packet loss, host crashes and router restarts need not be repaired by a perfectly delivered sequence of explicit deletions. Refreshes repair some omissions, and expiry removes abandoned entries and releases resources. Components can recover local state without retaining an indefinitely accurate history of everyone else's actions. Soft state does have a cost: refresh traffic, timer storage and temporary stale or missing information, with a tradeoff between rapid expiry and tolerance of delayed refreshes. Its central benefit is

UDP fits IP multicast because each independent datagram can be delivered to a group without establishing a separate transport connection with every receiver. Ordinary TCP defines a reliable ordered byte stream between two endpoints, with one peer's acknowledgements, receive window and connection state. A group has many receivers with different losses and capacities, so that interface cannot simply be assigned to one group address. A reliable group service can be designed, but ordinary TCP does not provide it. UDP itself adds neither group reliability nor congestion control; applications must provide whatever additional behaviour they require.

A virtual multicast distribution tree lets one packet traverse a shared upstream link and be copied only where branches diverge. Compared with a separate unicast copy per receiver, this saves repeated transmission over the common links. A tree also supplies a unique parent route and avoids forwarding loops when the routing information is consistent. Branches with no interested receivers can be pruned.

For a source-specific multicast distribution tree, a router needs the group identifier and source identifier, the expected incoming interface, the set of outgoing interfaces leading to interested receivers, and information about local group membership. Timers and join/prune information maintain those decisions. This is naturally keyed by $(S,G)$ for source $S$ and group $G$; other multicast routing designs can use a shared group tree. A router needs the relevant local forwarding entries, rather than a complete list of all group members everywhere. The result is