Past exam of the computer science course of the University of Oxford / 2015 / Computer networks / 2

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

Network address translation lets a router join a private Internet Protocol address realm to the public Internet. On outbound packets it replaces the private source IP address by a public IP address. On returning packets it applies the inverse mapping to the destination IP address, then forwards to the internal host. Basic network address translation changes addresses; the common many-to-one form, network address and port translation, also changes the source transport port so several internal hosts can share one public IP address.^[ref]

For example, suppose the public-facing router has IP address 198.51.100.7. An internal TCP exchange might be translated as follows; the addresses are illustrative:An entry records that traffic returning to external transport port 62001 belongs to 10.0.0.2:49152 for this transport protocol. The destination on the return path is rewritten accordingly. A second internal host using the same private transport port can receive a different public transport port. The actual lookup may also use the remote endpoint, depending on the mapping and filtering policy.

The router must update the IPv4 header checksum, and any affected TCP or UDP checksum: transport checking includes the relevant IP addresses as well as the transport header. Bindings may be allocated dynamically and removed after inactivity or observed termination. Traffic for a live exchange must traverse a translator that possesses the binding, or equivalent shared information.

An unsolicited incoming packet generally has no dynamic inverse mapping, so exposing a private service usually needs a configured mapping or port forwarding. Application data that embeds a private IP address can also need special handling. Address translation saves public address space, but changes the addressing visible to the two endpoints and can disrupt an exchange if its mapping disappears. Its essential mechanism is

Dynamic network address and port translation has an important soft state aspect: activity refreshes a binding's lifetime, and inactivity eventually expires it without a reliably delivered close message. This is especially useful for UDP, which supplies no connection-closing exchange. Even for TCP, the router cannot assume that it will observe every closing packet.

However, an expiring entry is not necessarily harmlessly disposable. Suppose the binding 10.0.0.2:49152 to 198.51.100.7:62001 disappears while the remote endpoint is still using it. A reply to port 62001 no longer reveals the private destination. New outbound traffic might obtain a different public transport port, which does not reconstruct the old connection as viewed by the remote endpoint. Losing the binding can therefore break the exchange even though both endpoints remain alive. This conflicts with fate-sharing when indispensable connection information resides in a separate router.

Static address mappings and configured port forwarding are hard state; a fixed translation rule need not even require a dynamic per-exchange table. ThusDescribing all network address translation information as fully reconstructible soft state would overlook both this recovery limitation and the static configuration.

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

In reverse path forwarding, a router uses its unicast routing information to ask which interface it would use to send a packet back towards source $S$. It accepts a multicast packet from $S$ only when it arrives on that interface, and otherwise discards it. An accepted packet can be forwarded on the other eligible interfaces. This needs no globally computed multicast distribution tree before the first transmission.^[ref]

With stable, loop-free routes and a consistent choice of parent when routes tie, each non-source router selects one upstream parent towards $S$. Following parent links reaches $S$, so the accepted parent links form a source-rooted tree over reachable routers. A packet arriving across a cross-link from a non-parent fails the reverse-path test. Basic flooding can still transmit copies that will be discarded; downstream-neighbour information can suppress such useless transmissions, and a designated forwarder prevents duplicate delivery on a shared local network.

To adapt the forwarding structure to a particular multicast group, retain branches with local members or interested descendants and prune the others. Leaf routers with no interested receivers initiate pruning; a router with no local members and no remaining interested children can propagate that condition upstream. A new subscriber requires a join/graft or later refresh to restore a pruned branch. Thus reverse path forwarding gives the source-rooted reachability structure, while membership and pruning restrict it to useful branches.

This tree need not minimize total transmission cost. Even if the unicast routes are shortest paths under symmetric positive link costs, their union minimizes individual distances from the source, rather than the sum of the costs of all used links. For a small example, let $SA$ and $SB$ each cost 2 and let $AB$ cost 1, with receivers at $A$ and $B$. The shortest-path tree uses $SA$ and $SB$, costing 4 in total. Using $SA$ and $AB$ costs 3, although the route from $S$ to $B$ then has length 3 instead of 2. Moreover, real unicast policies may optimize other criteria, and reverse routes need not be best forward routes when costs are asymmetric. Therefore