Advance Internetworking (old course)

• Logical addressing (IP addresses of source and destination)
• Routing: finding the best path from source to destination
• Packet forwarding from input to output interface
• Fragmentation and reassembly of packets
• Host-to-host (source to destination) packet delivery
• Congestion control and error reporting (e.g. ICMP)

• Address exhaustion: the 32-bit space (about $2^{32}$ addresses) is too small
• Large routing tables because of weak hierarchical addressing
• No built-in security (IPsec is optional)
• No quality-of-service support for real-time traffic (audio, video)
• Header of variable length with options, and checksum recomputed at every router, which slows processing
• Needs manual or DHCP configuration and relies on NAT as a workaround

Routing is the process of selecting the best path for packets to travel from a source to a destination across one or more networks. Routers do this using routing tables built by static configuration or routing protocols (RIP, OSPF, BGP).

Multicast is one-to-many (or many-to-many) communication in which a packet is sent once to a group of interested receivers identified by a group address (IPv4 class D, 224.0.0.0 to 239.255.255.255), rather than separately to each receiver.

A playback buffer is a buffer at the receiver of streaming audio or video that stores data before it is played. It absorbs delay variation (jitter) in packet arrival so that playback is smooth, at the cost of a small start-up delay.

In virtual-circuit switching, each switch keeps a table whose entry maps an incoming interface and incoming VCI to an outgoing interface and outgoing VCI: (In-interface, In-VCI) to (Out-interface, Out-VCI). A packet carries only the VCI, and the switch uses this table to forward it and rewrite the VCI. Entries are created when the circuit is set up and removed when it is torn down.

Multi-homing is connecting a host or network to more than one network or ISP at the same time, to provide redundancy (backup if one link fails), better performance and load sharing.

IP (route) aggregation, also called route summarization or supernetting, combines several contiguous address blocks into one larger prefix, e.g. 192.168.0.0/24 to 192.168.3.0/24 become 192.168.0.0/22. It reduces the size of routing tables and the routing updates exchanged.

RTP (Real-time Transport Protocol) itself gives no retransmission or guaranteed delivery. It numbers packets with sequence numbers so the receiver can detect loss, and loss is hidden or recovered by application-level techniques:

1. Forward Error Correction (FEC): the sender adds redundant packets, e.g. an XOR of every $n$ packets, so one lost packet among the group can be rebuilt without retransmission.
2. Interleaving: units of audio/video are rearranged before sending so a lost packet causes small scattered gaps rather than one large gap, which is easier to conceal.
3. Redundant (piggybacked) encoding: a lower-quality copy of the previous packet is carried in the next packet, so if one is lost the next packet supplies a replacement.
4. Receiver-based concealment: the receiver repeats the previous packet, interpolates or substitutes silence/noise, using sequence numbers and timestamps to detect the gap.
5. Selective retransmission: if delay allows, the receiver reports loss through RTCP (receiver reports / NACK) and the sender resends the lost packet or adapts its rate.

Rule: an IP multicast address is mapped to an Ethernet multicast address by placing the low-order 23 bits of the IP address into the low-order 23 bits of the Ethernet address 01-00-5E-00-00-00. (The physical address 68-94-23-40-E9-9C is a unicast address of the host; it plays no part in the mapping.)

IP multicast address: 229.122.54.99

The low 23 bits come from the last three octets 122.54.99, with the top bit of the second octet cleared (122 is less than 128, so it is unchanged):

• 122 = 7A
• 54 = 36
• 99 = 63

Ethernet multicast address:

$\texttt{01-00-5E}\;|\;\texttt{7A-36-63}=\texttt{01-00-5E-7A-36-63}$

Since 5 bits of the IP group address (the upper 5 of the 28-bit group ID) are ignored, 32 different multicast IP addresses map to the same Ethernet address.

Given block 92.16.1.0/24 (256 addresses). Allocate the largest subnet first (VLSM). Host requirement needs $2^h-2\ge$ hosts.

Addresses 92.16.1.248 to 92.16.1.255 remain unused for future growth.

The block is ABCD:EFAB::/32. A /42 block uses 10 more bits (bits 33 to 42) which fall in the top 10 bits of the third 16-bit group. Consecutive /42 blocks therefore differ by $2^{6}=64=\text{0x40}$ in the third group.

The first six /42 blocks:

1. ABCD:EFAB:0000::/42
2. ABCD:EFAB:0040::/42
3. ABCD:EFAB:0080::/42
4. ABCD:EFAB:00C0::/42
5. ABCD:EFAB:0100::/42
6. ABCD:EFAB:0140::/42

Each block has $2^{128-42}=2^{86}$ addresses, and there are $2^{10}=1024$ /42 blocks in the /32.

The shortest paths from source S to all other nodes are found with Dijkstra's algorithm (link-state shortest path), which is used in OSPF.

Algorithm

1. Set $D(S)=0$ and $D(v)=\infty$ for every other node; the permanent set $N'=\{S\}$.
2. Initialise $D(v)=c(S,v)$ for the neighbours of S.
3. Repeat: choose the node $w\notin N'$ with the smallest $D(w)$, add it to $N'$, and for each neighbour $v$ of $w$ not in $N'$ update $D(v)=\min\big(D(v),\,D(w)+c(w,v)\big)$, recording $w$ as the predecessor when the value improves.
4. Stop when all nodes are in $N'$. Trace the predecessors back to S to get each path.

Worked illustration. Take the link costs S-A = 2, S-B = 5, A-B = 1, A-C = 4, B-C = 2, B-D = 3, C-D = 1.

Shortest paths from S: S-A (cost 2); S-A-B (cost 3); S-A-B-C (cost 5); S-A-B-D (cost 6).

For the figure in the question, the same table is built with its link costs; the node with the minimum label is made permanent at each step until all nodes are reached.

DCCP (Datagram Congestion Control Protocol) is a connection-oriented, unreliable transport protocol that provides congestion control without guaranteed delivery, suited to streaming media and telephony.

Connection initiation (three-way handshake plus data)

1. The client sends DCCP-Request (with a service code) and moves from CLOSED to REQUEST.
2. The server, in LISTEN state, replies with DCCP-Response (acknowledging the request) and moves to RESPOND.
3. The client sends DCCP-Ack (or a DCCP-DataAck carrying data); both ends move to OPEN. During the handshake the endpoints can negotiate features such as the congestion control ID (CCID).

Connection termination

• The end that wants to close (usually the server) sends DCCP-CloseReq, asking the other end to close. The other end replies with DCCP-Close, and the first sends DCCP-Reset to complete the termination.
• Alternatively, either side sends DCCP-Close directly; the peer answers with DCCP-Reset (reason "Closed") and the connection is released, the closing side waiting in a TIMEWAIT state (about 2 maximum segment lifetimes) so old packets expire.
• DCCP-Reset is also sent to abort a connection abnormally.

Congestion control with CCID 2 (TCP-like)

CCID 2 uses an AIMD window scheme similar to TCP:

• The sender keeps a congestion window cwnd and a slow-start threshold ssthresh.
• Receivers send Ack Vectors (in DCCP-Ack) that report which packets arrived, ECN-marked, or were lost.
• Slow start: cwnd doubles each round trip until ssthresh; then congestion avoidance increases cwnd by one packet per RTT (additive increase).
• On loss or an ECN mark (detected through the Ack Vector) cwnd and ssthresh are halved (multiplicative decrease), at most once per window.
• A timeout reduces cwnd to 1.
• Lost packets are not retransmitted, but the sending rate is controlled, giving a bursty, rapidly changing rate, which suits applications that want to use available bandwidth quickly.

Differences between peer-to-peer (P2P) and client-server networks

Peer discovery methods in a P2P network

Peer discovery is how a new node finds other peers to join the network.

1. Centralised directory (index server): A central server keeps a list of peers and the resources they share. A new peer registers with it and queries it to find others, as in Napster. It is simple and fast, but the server is a single point of failure.
2. Flooding / broadcast query: A peer sends its query to all its neighbours, which forward it to their neighbours until a TTL (time to live) expires, as in early Gnutella. It needs no central server but creates heavy traffic.
3. Bootstrap nodes / well-known peers: A new peer connects to a pre-configured list of known peers (hard-coded addresses, web caches or DNS seeds). It then learns more peers from them. Gnutella and Bitcoin use this.
4. Distributed Hash Table (DHT): Peers and resources get IDs in a common key space, and each peer keeps a routing table. A lookup is routed to the responsible peer in about $O(\log n)$ hops, as in Chord, Kademlia and Pastry.
5. Peer exchange (gossip): Connected peers exchange lists of other peers they know, so the neighbour list grows without a central server (e.g. PEX in BitTorrent).
6. Tracker-based discovery: In BitTorrent, a tracker returns the list of peers sharing a given file.
7. Local broadcast / multicast: On a LAN, a peer announces itself using broadcast or multicast messages (e.g. mDNS, UPnP/SSDP).