Computer Networks

TCP connection management

TCP connection management describes how a connection is opened, used and closed, and how each endpoint's state changes at each step. Establishment uses a three-way handshake, not a two-way one. The client sends a SYN segment with SYN = 1 and ACK = 0 that carries its initial sequence number. The server answers with a SYN-ACK segment, which has SYN = 1 and ACK = 1, carries the server's own initial sequence number, and has an acknowledgement number equal to the client's sequence number plus one. The client completes the exchange with an ACK segment in which ACK = 1 and SYN = 0.

Because a SYN consumes one sequence number, the acknowledgement number of the reply is always the peer's sequence number plus one. Initial sequence numbers are chosen by each host, and modern stacks randomize them to make sequence-number guessing harder, so an initial sequence number should never be assumed to be zero.

• SYN — synchronizes sequence numbers; it is set only in the first two segments of the handshake.
• ACK — marks the acknowledgement field as valid; it is set in every segment except the very first SYN.
• FIN — the sender has finished sending data; it is used only for an orderly close.
• RST — aborts a connection; it is sent when a segment does not match any connection the receiver knows.
• piggybacking — a TCP segment can carry data and an acknowledgement for data travelling in the opposite direction at the same time.

TCP is full-duplex, not half-duplex, so each direction is closed separately by its own FIN, and either endpoint may send the first FIN. When both endpoints send FIN at nearly the same time, the close is called a simultaneous close.

If the server host crashes and reboots, all of its TCP connection state is lost. A client without the keepalive timer has no mechanism to reveal that the peer has disappeared, so a client waiting to receive data may block indefinitely. When the rebooted host receives a segment for a connection it no longer knows, it answers with RST, because FIN is used only to close an existing connection in order. The restarted server application can bind and listen on its port again.

Example: a client's SYN carries sequence number 1000, and the server's SYN-ACK carries sequence number 4500 with acknowledgement number 1001.

IP fragmentation and MTU

The maximum transfer unit (MTU) is the largest payload that a link can carry in one frame. An IP datagram larger than the MTU of the outgoing link must be split into fragments. Each fragment receives its own IP header, which copies the identification value and carries a fragment offset. The offset is counted in 8-byte units, so every fragment except the last must carry a payload that is a multiple of 8 bytes. The largest allowed payload is therefore \lfloor (MTU - H)/8 \rfloor \times 8 bytes, where H is the IP header length. Example: with MTU 576 and H = 20, (576-20)/8 = 69.5, so the payload per fragment is 69 \times 8 = 552 bytes.

Fragmentation can take place at any router on the path whose outgoing MTU is smaller than the datagram, provided that the Don't Fragment flag is clear. Reassembly, however, is performed only at the final destination host, and intermediate routers never merge fragments. IP does not retransmit lost fragments. If one fragment is lost, the destination discards the incomplete datagram, so the source transport layer must resend the entire segment. Only the first fragment, whose offset is 0, carries the TCP or UDP header, so the port numbers cannot be read from later fragments.

To count fragments, first find the IP datagram size, which is the payload plus the header, and then check each link's MTU in turn. A fragment that is still too large for a later link is split again, so the final count depends on the most restrictive links the data must pass through. Example: a UDP segment with 3000 bytes of data has an IP payload of 3008 bytes, because the 8-byte UDP header is included. On an Ethernet link with MTU 1500, each fragment carries 1480 bytes of payload, so the datagram needs three fragments with payloads of 1480, 1480 and 48 bytes. The last fragment is 48+20 = 68 bytes long.

Sliding window protocol efficiency

Sliding window flow control allows a sender to keep up to W unacknowledged frames in flight. Three quantities determine its efficiency: the transmission time t_t = L/R of a frame of L bits on a link of rate R, the one-way propagation delay t_p, and the transmission time of the acknowledgement t_{ack}. One frame and its acknowledgement occupy a cycle of t_{cycle} = t_t + 2t_p + t_{ack}. In each cycle the sender transmits W frames, so the link utilization is U = \min(1,\; W t_t / t_{cycle}). When the acknowledgement time is negligible, full utilization requires W \geq (t_t + 2t_p)/t_t.

Example: frames of 500 bits on a 1 Mbps link with a one-way delay of 20 ms have t_t = 0.5 ms and a cycle of 40.5 ms. The window for 100% utilization is 40.5/0.5 = 81 frames. With W = 10, the utilization is only 10 \times 0.5 / 40.5 \approx 12.3\%.

When the acknowledgement has a nonzero transmission time, that time must be added to the cycle, and the window for a target utilization U is W = U \cdot t_{cycle}/t_t. Example: 1000-bit frames, 20-bit acknowledgements, a 2 Mbps link and a one-way delay of 50 ms give t_t = 0.5 ms, t_{ack} = 0.01 ms and t_{cycle} \approx 100.51 ms. For 50% utilization the window must be about 101 frames.

Byte-stream protocols number every byte, so the sequence field must be large enough that numbers do not wrap around while old segments can still be in the network. If the link rate is R and the maximum segment lifetime is MSL, at most R \times MSL/8 bytes can be sent in one MSL. An n-bit field provides 2^n values, so the requirement is 2^n \geq R \times MSL/8. The round trip time does not enter this bound. Example: at 10 Mbps with an MSL of 60 s, 10^7 \times 60/8 = 7.5 \times 10^7 bytes must be distinguishable. Since 2^{26} \approx 6.7 \times 10^7 is too small and 2^{27} \approx 1.34 \times 10^8 is enough, 27 bits are required.

For a lossless link designed for full utilization, the window needs only the bandwidth-delay product in bytes. When a wrap-around time limit is also imposed, the time limit usually determines the field size, because the bytes sent in that time are far more than the bandwidth-delay product.

IP subnetting and subnet counting

A subnet is a group of IP addresses that share the same network prefix. In a network topology, each point-to-point link between two router interfaces and each shared Ethernet segment forms one subnet, whereas individual hosts do not create subnets. To count subnets, list every link and LAN segment and count each once, regardless of how many devices are attached to it.

A prefix written as /n fixes the first n bits of the address. The block then contains 2^{32-n} addresses. The address whose host bits are all 0 is the network address, and the address whose host bits are all 1 is the broadcast address, so the number of addresses assignable to interfaces is 2^{32-n}-2. For a mask such as 255.255.240.0, there are 4 + 8 = 12 host bits, giving 2^{12}-2 = 4094 usable addresses.

To find the single prefix that exactly covers a range, count the addresses, which must be a power of two, and set the prefix length to 32 - \log_2(\text{count}). The first address of the range must also be a multiple of the block size. Example: the range 192.168.4.0 to 192.168.7.255 contains 1024 addresses, so it is the block 192.168.4.0/22.

A provider can split a larger block only at boundaries that are multiples of the smaller block size. A block of 6000 addresses needs 2^{13} = 8192 addresses, so it takes the prefix length 32 - 13 = 19, and its first address must be a multiple of 8192 counted from the start of the provider's block. Example: from an ISP block 172.20.0.0/16, a /20 block (4096 addresses) must start at a third octet that is a multiple of 16, so 172.20.16.0/20 is valid but 172.20.24.0/20 is not.

• subnet mask — a bit pattern whose leading 1s mark the network part of the address.
• network address — the address with all host bits 0, which cannot be assigned to a host.
• CIDR block — an aligned address range described by a prefix length.

Longest prefix match routing

A router searches its forwarding table for every entry whose prefix matches the destination address. An entry matches when the destination address ANDed with the entry's mask equals the entry's network address. When several entries match, the router chooses the one with the longest prefix, meaning the most 1-bits in its mask. The default route 0.0.0.0/0 matches every address and is used only when no more specific entry matches.

To test a match, do not compare the listed address directly with the destination. Instead, AND the destination with the mask and compare the result with the network address. Example: the destination 10.1.2.77 is tested against 10.1.2.64/27 by computing 77 \text{ AND } 224 = 64, which equals the network part, so the entry matches. A more specific entry that lies inside a broader one takes precedence for the addresses it covers, so a /25 entry can override the matching part of a /24 entry, and a /26 entry can further refine a /25 entry.

Route aggregation replaces a set of routes with one summary prefix. The summary is valid only if it covers exactly the addresses that the set covers, so the blocks in the set must tile the summary's range without leaving out or adding routed space. Example: 192.168.0.0/23 and 192.168.2.0/23 tile the aligned block 192.168.0.0/22, which is therefore a valid summary.

• longest prefix match — the rule that selects the matching entry with the longest prefix.
• summary route — a single prefix that replaces several more specific routes.
• default route — the entry used when no other entry matches.

Propagation and transmission delay

Transmission delay is the time needed to push all bits of a packet onto a link, t_t = L/R, where L is the packet length in bits and R is the link rate in bits per second. Propagation delay is the time for a bit to travel the physical distance, t_p = d/s, where d is the distance and s is the signal speed in the medium. Example: a 1000-byte packet on a 10 Mbps link has t_t = 8000/10^7 = 0.8 ms, and a 1500 km path at 2 \times 10^8 m/s has t_p = 7.5 ms.

The time until the receiver has the whole packet is the sum of the two delays, t_t + t_p, because the last bit leaves the sender after t_t and then travels for t_p. This is why propagation dominates for a long link such as a satellite path even when the packet is small.

In a store-and-forward path, each link adds its own transmission delay. When a file is split into chunks and sent back to back, the chunks pipeline across the links. The total time is the time for the sender to finish plus one chunk's transmission time on each remaining link. Example: 100 chunks of 8000 bits on two 1 Mbps links with negligible propagation delay: the sender finishes at 100 \times 0.008 = 0.8 s, and the last chunk reaches the destination at 0.8 + 0.008 = 0.808 s.

In CSMA/CD, a frame must still be transmitting when a collision signal could return to the sender, so the transmission time must be at least the round-trip time. This gives L_{min} = 2Rd/s. Example: with R = 10 Mbps, d = 2 km and s = 2\times10^8 m/s, the round-trip time is 20\ \mu s, so L_{min} = 10^7 \times 20 \times 10^{-6} = 200 bits.

When a file is sent through a path with no overhead and negligible delays, the transfer rate is set by the slowest link, so the total time is approximately the file size divided by the bottleneck bandwidth. Example: a 2 MB file is 16 Mbit, and over links of 2 Mbps, 4 Mbps and 1 Mbps it takes 16/1 = 16 s, since the 1 Mbps link is the bottleneck.

ARP address resolution

ARP (Address Resolution Protocol) maps an IP address on the local network to the matching link-layer (MAC) address. ARP does not map in the reverse direction, and it resolves only addresses on the same LAN.

A host that needs the MAC address of a neighbour sends an ARP request. The request is a broadcast frame whose destination MAC address is FF:FF:FF:FF:FF:FF, so every host on the LAN receives it, and only the host that owns the queried IP address replies. The reply is unicast back to the MAC address of the requester, which was learned from the request itself.

• ARP request — a broadcast frame sent to all hosts on the LAN.
• ARP reply — a unicast frame sent back to the requesting host.
• ARP cache — a table of recently learned IP-to-MAC mappings, whose entries expire after a period of time.

Example: host A wants to reach 192.168.1.20 on its own LAN but has no cache entry for it. A broadcasts an ARP request, the host with that IP replies with a unicast frame, and A stores the new mapping in its cache for later frames.

CRC error detection computation

CRC (cyclic redundancy check) treats a bit string as the coefficients of a polynomial over GF(2). The sender and receiver agree on a generator polynomial G(x) of degree r; for example, x^3+x+1 is written as the bit pattern 1011. The procedure is as follows. Append r zero bits to the message, divide the result by the generator using modulo-2 long division, and append the r-bit remainder as check bits. In modulo-2 division, each subtraction is an XOR, so no borrows occur, and a quotient bit is 1 exactly when the leading bit of the current remainder is 1.

The receiver divides the whole received codeword by G(x). If the remainder is zero, the frame is accepted; a nonzero remainder reveals an error.

Example: the message 1101 with generator 1011 is extended to 1101000. Long division gives the remainder 001, so the transmitted codeword is 1101001. Dividing 1101001 by 1011 leaves the remainder 000, as expected.

• generator polynomial — the agreed divisor that determines which errors are detected.
• check bits — the remainder of the division, appended after the message, not inserted before it.
• modulo-2 division — long division in which subtraction is replaced by XOR.

Distance vector routing updates

In distance vector routing, each router keeps the estimated cost to every destination and updates it from the vectors advertised by its neighbours, using the Bellman-Ford equation D_x(y) = \min_v \{c(x,v) + D_v(y)\}, where c(x,v) is the cost of the link to neighbour v. The minimizing neighbour gives both the new cost and the next hop. Example: to reach a destination Z through neighbour A (link cost 2, A advertises 7) or neighbour B (link cost 3, B advertises 4), the candidates are 2+7 = 9 and 3+4 = 7, so the stored cost is 7 and the next hop is B.

Because updates are exchanged at different times, a router may act on a stale advertisement. After a link failure, two neighbours can keep advertising routes through each other, and their costs to an unreachable destination grow in small steps. This is the count-to-infinity problem. A loop forms only when one router's stale update reaches the other before the other router's update reaches it. If both update orders are equally likely, the probability of the loop is 0.5.