A network is

logical 逻辑上（transparent）

physical 实现

Remember that

base on which we build the Internet to connect everything.

Architecture & Layering

The network architecture, equivalently, the protocol stack, organizes communication into layers, each providing services to the layer above while hiding implementation details from the layer below.

A simple example is the OSI model, which partitions the communication process into seven layers:

The OSI model provides a conceptual framework; it does not define specific protocols. Now consider the TCP/IP model, which condenses these into four layers:

If we examine the Internet layer, IP provides a best-effort, connectionless datagram service — no guarantees of delivery, order, or integrity. This illustrates that architectural choices define the service model, while protocols implement it. The former is determined by design philosophy (e.g., the end-to-end principle), while the latter is determined by engineering constraints.

Density of Protocol Headers

Physical Layer

Physical layer is responsible for transmitting raw bits over a physical medium

with the concept of bandwidth (maximum data rate) and latency (propagation delay), where each signal faces attenuation, noise, and distortion. Fundamental concepts include

• Bandwidth/Throughput/Latency
• Signal-to-Noise Ratio (SNR)
• Modulation/Demodulation/Encoding

A word on units: b (bit) vs. B (Byte). Bandwidth and data rate are always expressed in bits per second (bps) — the physical layer transmits symbols that encode bits, not bytes. Storage and packet sizes use bytes.

Network speeds use decimal prefixes (M $=10^6$, G $=10^9$), so a $100$ Mbps link delivers at most $12.5$ MB/s at the application level — and less after protocol overhead. Memory and OS contexts typically use binary prefixes (Mi $=2^{20}$, Gi $=2^{30}$), which is why a “4 GB” file may not fit in a router’s $4$ GiB buffer.

Generally speaking, Shannon’s theorem is more likely to illustrate the fundamental limit of a physical channel.

Shannon’s Theorem

The maximum channel capacity $C$ (in $\text{bps}$) for a bandlimited channel with Gaussian noise:

where $B$ is bandwidth in $\text{Hz}$ and $S/N$ is the signal-to-noise power ratio (not in $\text{dB}$).

It is a theoretical upper bound; achieving it requires optimal coding. Practical systems approach this limit with advanced coding schemes (e.g., LDPC, Turbo codes).

Nyquist Criterion

For a noiseless channel, Nyquist gives:

where $V$ is the number of discrete signal levels. For a binary signal ($V=2$), $C=2B$. Combining Nyquist and Shannon yields the practical constraint:

Transmission Media

Encoding Schemes

Given a bit stream, we encode it into a signal waveform. Examples include:

• NRZ (Non-Return to Zero): $1\to\text{high}$, $0\to\text{low}$. Simple but suffers from baseline wander with long runs.
• NRZI: flip on $1$, stay on $0$. Solves consecutive $1$s but not $0$s.
• Manchester: $1\to\text{high-low}$, $0\to\text{low-high}$. Self-clocking (guaranteed mid-bit transition). Efficiency = $50\%$.
• 4B/5B: encode every 4 data bits into 5 code bits chosen to guarantee sufficient transitions, then transmit with NRZI. Efficiency = $80\%$. Used in Fast Ethernet (100BASE-TX).

Switching: The Network Core

Before diving into the data link layer, we must understand how data is transferred through the network core — the mesh of routers and switches that interconnect end systems. The fundamental question is: given a message to be sent from source $A$ to destination $B$ across a network of intermediate nodes, how should the network transfer the data?

There are three canonical answers, forming a historical progression:

Circuit Switching

Circuit switching establishes a dedicated, end-to-end communication path (a circuit) between the source and destination before any data is transmitted. The circuit reserves resources (bandwidth, buffer space) along the entire path, and these resources remain allocated for the duration of the communication, regardless of whether data is actively being sent.

This is exactly how the traditional Public Switched Telephone Network (PSTN) works: when you dial a number, the network establishes a physical (or virtual) circuit through a series of switches; voice samples flow along this dedicated path; when you hang up, the circuit is torn down and resources are released.

How Circuits Are Established

Circuit switching operates in three phases:

1. Circuit Establishment: the source sends a setup request; each switch along the path allocates a dedicated channel (a time slot in TDM or a frequency band in FDM) and forwards the request; an acknowledgment travels back to the source. This is essentially a signaling protocol (e.g., SS7 in telephony).
2. Data Transfer: data flows along the reserved path at a guaranteed constant rate. No addressing is needed during transfer — the switches know which channel belongs to which circuit.
3. Circuit Teardown: either party signals release; all switches along the path free the reserved resources.

Multiplexing on a Single Link

A physical link can host multiple circuits simultaneously through:

FDM (Frequency Division Multiplexing): the link’s frequency spectrum is partitioned into disjoint bands, each assigned to one circuit. For $n$ circuits sharing a link of bandwidth $B$, each gets $B/n$ Hz (plus guard bands). Radio and TV broadcasting, ADSL, and early analog telephony use FDM.

TDM (Time Division Multiplexing): time is divided into fixed-length frames, and each frame is partitioned into $n$ slots, one per circuit. Each circuit periodically gets its slot. For a link of rate $R$, each circuit effectively gets $R/n$ bps. Modern digital telephony (T1/E1, SONET/SDH) uses TDM.

Analysis of Circuit Switching

Suppose $n$ circuits share a link of rate $R$. If $k$ users are active simultaneously ($k\le n$), each gets exactly $R/k$ bps (often fixed at $R/n$ in practice).

• Advantages: guaranteed bandwidth, constant delay (no queuing), in-order delivery, no per-packet overhead once the circuit is set up. Ideal for real-time, constant-bit-rate applications (voice, video conferencing).
• Disadvantages:
  • Inefficient for bursty traffic. Resource reservation is wasteful if the circuit is idle (e.g., pauses in conversation — the “silent period” problem). In a phone call, about $50\%$ of the time is silence.
  • Long setup delay before data transfer can begin ($\sim$ seconds for international calls). This overhead is disproportionate for short messages.
  • Vulnerability to failure. If any switch or link along the circuit fails, the entire circuit is broken and must be re-established.
  • Stateful: each switch must maintain per-circuit state, limiting scalability.

Message Switching

Message switching eliminates the need for a dedicated circuit. Instead, the source sends the entire message (as a single unit) to the first switch. The switch receives the message in its entirety, stores it, checks for errors, selects the next hop (routing), and forwards it. This store-and-forward process repeats at each intermediate node until the message reaches its destination.

Telegraph networks historically used message switching, and email systems (SMTP store-and-forward relays) still follow this paradigm.

Store-and-Forward Delay

Consider a message of $L$ bits sent over a path of $h$ hops, each link having rate $R$ bps (and ignoring propagation, processing, and queuing delays for simplicity). At each hop, the entire message must be received before forwarding can begin:

For $h=3$ hops, a $L=7.5\times 10^6$ bit message ($\approx 1$ MB) over $R=1.5$ Mbps links would take:

Example (unified scenario, see end of section): $L=6\times 10^6$ bits, $h=3$, $R=2$ Mbps, $D_{\text{prop}}=10$ ms/hop, $D_{\text{proc}}=1$ ms/switch. Message switching total delay: $3\times 3.0 + 3\times 0.01 + 2\times 0.001 = 9.032$ s. The transmission component alone ($9$ s) is $3\times$ circuit/packet switching because each hop must receive the entire message before forwarding.

• Advantages: no circuit setup delay, dynamic routing (can adapt to link failures), efficient for messages with varying destinations (no reservation overhead).
• Disadvantages:
  • Enormous buffering requirement at each switch — must store the full message (potentially gigabytes).
  • Hop-by-hop delay accumulates multiplicatively with path length (unlike circuit switching, where delay is only propagation).
  • Head-of-line blocking: a long message blocks subsequent messages sharing the same link; a short interactive message behind a large file transfer suffers severe delay.
  • Error handling is expensive: a single bit error requires retransmission of the entire message across the entire path.

Packet Switching

Packet switching is the synthesis that resolves the weaknesses of both circuit and message switching, and it is the foundation of the modern Internet. The key insight is to break the message into small, fixed-maximum-size packets (typically $\sim 1500$ bytes). Each packet is independently switched through the network via the store-and-forward principle, but because packets are small, they interleave on links and pipelining hides latency.

How Packet Switching Works

Each packet carries a header containing the destination address (and other control information). Each switch (router):

1. Receives the packet.
2. Examines the header — the destination address determines the output interface.
3. Stores the packet in a queue for the output link (if the link is busy).
4. When the link becomes available, transmits the packet.

Crucially, routers do not maintain per-connection state (in the basic datagram model) — they are stateless with respect to end-to-end flows. This is the statistical multiplexing principle: resources are allocated on demand, aggregated over many flows, achieving much higher utilization than circuit switching for bursty traffic.

Pipelining and Delay Analysis

Consider the same message of $L$ bits, broken into $k$ packets each of size $L/k$ (plus header overhead, ignored here), over $h$ hops of rate $R$. Because packets are small, they can be pipelined: while the first packet is being forwarded from $N_1$ to $N_2$, the second packet can be transmitted from $A$ to $N_1$:

As $k\to\infty$ (infinitely fine-grained packets), $T_{\text{total}} \to L/R$ — only one transmission delay, plus propagation. In practice, $k$ is finite but still yields a dramatic improvement over message switching:

For the earlier example ($L=7.5\times 10^6$ bits, $h=3$, $R=1.5$ Mbps) with $k=500$ packets of $1500$ bytes ($1.2\times 10^4$ bits):

vs. message switching’s $15$ s — a $3\times$ speedup.

Example (unified scenario): $L=6\times 10^6$ bits, $h=3$, $R=2$ Mbps, $D_{\text{prop}}=10$ ms/hop, $D_{\text{proc}}=1$ ms/switch, $k=500$ packets of $12000$ bits. Packet switching total: $3.0 + 2\times 0.006 + 3\times 0.01 + 2\times 0.001 = 3.044$ s — only $14$ ms more than circuit switching’s data-transfer phase, dramatically better than message switching’s $9.032$ s.

Two Flavors: Datagram vs. Virtual Circuit

Packet switching comes in two variants, differing in whether the network maintains per-flow state:

Datagram (Connectionless): this is how IP works. Each packet is routed independently; successive packets between the same hosts may follow different paths. Routers maintain forwarding tables (prefix-based), but no per-connection state. Robust to failures, but QoS is challenging.

Virtual Circuit (Connection-Oriented): a setup phase establishes a path and assigns a VCI (Virtual Circuit Identifier) at each link. During data transfer, each packet carries only the VCI (short, local to that link), and switches forward based on (input interface, input VCI) $\to$ (output interface, output VCI) mappings. This resembles circuit switching, but resources are not exclusively reserved — statistical multiplexing still applies. ATM and MPLS use this model.

Comparison of the Three Switching Paradigms

Delay Example: Circuit vs. Message vs. Packet Switching

Consider a file of $L = 750\text{ KB}$ sent over $h=3$ hops

each link at $R = 2\text{ Mbps}$, with per-hop propagation $D_{\text{prop}} = 10\text{ ms}$ and per-switch processing $D_{\text{proc}} = 1\text{ ms}$. Circuit setup signaling takes $S = 200 \text{ ms}$ round-trip. For packet switching, the file is split into $k = 500$ packets of $1500\text{ B}$ each. Assume zero queuing delay (no competing traffic).

Circuit Switching:

No per-hop transmission or processing during data transfer — the circuit is a pre-established pipe. The dominant term is $D_{\text{trans}}$ ($3.0\text{ s}$); setup ($0.2\text{ s}$) is a one-time tax.

Message Switching:

Each hop must receive the entire $6$ Mbit message before forwarding — the store-and-forward tax multiplies $D_{\text{trans}}$ by $h$, dwarfing all other terms.

Packet Switching:

The store-and-forward penalty applies only to a single packet ($12$ ms extra), not the whole message. Pipelining brings the total within $14$ ms of circuit switching’s data phase — without any setup overhead.

Summary:

Data Link Layer

The data link layer is to send frames over a single link (point-to-point or broadcast). It provides a reliable link service to the network layer above, abstracting away the physical layer’s imperfections.

It transforms the raw bit stream of the physical layer into discrete frames:

and combines the physical links with protocols to form a logical link(circuit, bus, star and so on) between nodes. The data link layer is responsible for framing, addressing, error detection/correction, and flow control. It ensures that frames are delivered reliably and in order over the physical medium.

Framing Methods

• Byte count — first field gives frame length. Vulnerable: one corrupted count desynchronizes everything.
• Byte stuffing (flag bytes) — special start/end flag bytes (e.g., 0x7E in PPP); escape byte 0x7D precedes data bytes that match the flag. If 0x7E appears in data, send 0x7D 0x5E.
• Bit stuffing — e.g., HDLC: a frame starts and ends with the bit pattern 01111110 ($6$ consecutive $1$s). The sender inserts (stuffs) a $0$ after every five consecutive $1$s in the data; the receiver removes the $0$ following five consecutive $1$s. This ensures the flag pattern never occurs in the payload. $$011111\underbrace{0}_{\text{stuffed}}10 \implies \text{data: }01111110 \text{ won't appear.}$$

Error Detection

Given a frame of $m$ data bits, append a $r$-bit check code. In general, we want to detect/correct errors using Hamming distance: the number of bit positions where two codewords differ.

To detect $d$ errors: $\text{Hamming distance} \ge d+1$ (HDU, Hamming Distance Upperbound).
To correct $c$ errors: $\text{Hamming distance} \ge 2c+1$.

• Parity bit — single parity bit (appended $0$ or $1$ to make the total number of $1$s even/odd). Hamming distance $=2$, detects all odd numbers of bit errors, but no even numbers.
• CRC (Cyclic Redundancy Check) — treats bit strings as polynomials over $\mathbb{F}_2$. Append an $r$-bit remainder $R(x)$ such that the transmitted $T(x) = x^rM(x) + R(x)$ is divisible by a generator polynomial $G(x)$ of degree $r$. At the receiver, divide by $G(x)$; a non-zero remainder indicates errors. $$\frac{T(x)}{G(x)}\equiv 0 \pmod{2}.$$ Common generator polynomials: CRC-32 ($G(x)=x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$), used in Ethernet. CRC detects all burst errors of length $\le r$, all odd numbers of bit errors, and burst errors longer than $r$ with probability $1-2^{-r}$.
• Checksum — Internet checksum: split data into 16-bit words, sum (one’s complement), take one’s complement of the sum. Simple but weaker than CRC.

Hamming Code

For error correction, Hamming codes use $r$ parity bits to cover $m$ data bits such that:

Each parity bit $p_i$ at position $2^{i-1}$ checks bits whose binary index has the $i$-th bit set. The syndrome (computed at receiver) directly indicates the position of a single-bit error.

Flow Control & Stop-and-Wait

In Stop-and-Wait, the sender transmits one frame and waits for an acknowledgment (ACK) before sending the next. If no ACK arrives within a timeout, the frame is retransmitted.

Channel utilization $U$ (with negligible processing time):

where $a = T_{\text{prop}}/T_{\text{frame}}$. Utilization degrades badly for high-bandwidth, high-delay links.

Sliding Window Protocols

To improve utilization, the sender may transmit up to $W$ frames before receiving an ACK (pipelining).

Go-Back-N — the receiver discards all out-of-order frames; upon a timeout, the sender retransmits all frames from the lost one onward.

otherwise ambiguity between new and retransmitted frames.

Selective Repeat — the receiver buffers out-of-order frames and ACKs individually. The sender retransmits only lost frames.

MAC Sublayer: Medium Access Control

The MAC sublayer governs access to a shared broadcast medium.

ALOHA:

• Pure ALOHA: transmit whenever; if collision, wait a random time and retry. Maximum throughput $S = G e^{-2G} \to 1/(2e)\approx 18.4\%$ at $G=0.5$.
• Slotted ALOHA: time is divided into slots; stations transmit only at slot boundaries. Throughput $S = G e^{-G} \to 1/e \approx 36.8\%$ at $G=1$.

CSMA/CD (Ethernet, IEEE 802.3):

1. Carrier Sense: listen before transmitting. If idle, transmit; if busy, wait.
2. Collision Detection: while transmitting, monitor the medium. If collision detected, send a jam signal and stop.
3. Binary Exponential Backoff: after $k$ collisions, wait a random time in $\{0,1,\ldots,2^k-1\}$ slots ($k\le 10$), then retry. After $16$ collisions, give up.

To detect collisions reliably, Ethernet imposes a minimum frame length:

i.e., $64$ bytes at $10$ Mbps over $2500$ m (with $4$ repeaters). At higher speeds, either reduce distance or increase minimum frame size (Gigabit Ethernet pads to $512$ bytes using carrier extension).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Conceptual CSMA/CD state machine (pseudocode)
typedef enum { IDLE, TRANSMIT, BACKOFF } MACState;

void csma_cd_send(Frame *f) {
    MACState state = BACKOFF;
    int collisions = 0;
    while (1) {
        if (state == BACKOFF) {
            int slots = rand() % (1 << min(collisions, 10));
            wait(slots * SLOT_TIME);
        }
        carrier_sense();
        if (channel_busy()) { state = BACKOFF; continue; }
        start_transmit(f);
        if (collision_detected()) {
            abort_transmit();
            send_jam();
            collisions++;
            if (collisions > 16) { report_error(); return; }
            state = BACKOFF;
        } else {
            return;  // success
        }
    }
}

CSMA/CA (Wi-Fi, IEEE 802.11): Wi-Fi cannot reliably detect collisions (Hidden Terminal Problem), so it avoids them:

1. Sense the channel.
2. If idle for DIFS (Distributed Inter-Frame Space), transmit.
3. Else wait until idle, then start a random backoff counter. Decrement while idle; freeze while busy. Transmit when counter reaches $0$.
4. Receiver sends ACK after SIFS (Short IFS). If no ACK, sender assumes collision and doubles the contention window.

Optional RTS/CTS exchange: sender sends Request to Send; receiver replies with Clear to Send. Neighbors hearing RTS/CTS defer (Virtual Carrier Sense via NAV). This addresses the Hidden Terminal Problem.

Ethernet Frame Format

The Inter-Frame Gap (IFG) of $96$ bit times separates consecutive frames.

Bridges & Switches

A switch (multi-port bridge) connects LAN segments and forwards frames selectively using a MAC address table (a.k.a. forwarding database). It learns source MAC addresses and their incoming ports; unknown destinations are flooded. Loops are eliminated by the Spanning Tree Protocol (STP, IEEE 802.1D).

• Cut-through switching: forward as soon as destination MAC is read ($6$ bytes). Low latency, but propagates errors.
• Store-and-forward: receive entire frame, verify CRC, then forward. Higher latency, but error filtering.

VLAN (IEEE 802.1Q)

A Virtual LAN partitions a physical switch into separate broadcast domains. Frames are tagged with a $4$-byte 802.1Q tag (including a $12$-bit VLAN ID), inserted between the source MAC and Type/Length fields. Trunk links carry traffic for multiple VLANs between switches.

Network Layer

The network layer provides end-to-end packet delivery across multiple hops (routers). Its core functions:

• Routing: determine the path from source to destination (control plane).
• Forwarding: move packets from an input interface to the appropriate output interface (data plane).

The Internet’s network layer is built around the Internet Protocol (IP), which provides a connectionless, best-effort datagram service.

IPv4

An IPv4 address is $32$ bits, written in dotted-decimal notation:

IPv4 Header ($20$–$60$ bytes, typically $20$):

Key fields:

• TTL (Time To Live): decremented at each hop; packet discarded when $0$, prevents infinite loops.
• Protocol: identifies the transport-layer protocol (TCP = $6$, UDP = $17$, ICMP = $1$).
• Fragmentation Offset: when a packet is too large for a link’s MTU, the router fragments it. The destination reassembles using ID, Flags (MF bit), and Fragment Offset. The offset is in $8$-byte units, so fragmentation occurs at $8$-byte boundaries.

The header checksum covers only the IP header (not payload), recalculated at each hop since TTL changes.

IP Addressing & Subnetting

Classful addressing (historical):

CIDR (Classless Inter-Domain Routing): uses prefix notation $a.b.c.d/n$, where $n$ is the network prefix length and the remaining $32-n$ bits identify the host. Subnet mask: $n$ ones followed by $32-n$ zeros.

The number of usable hosts in a $/n$ subnet is

subtracting the network address (all host bits $0$) and the broadcast address (all host bits $1$).

Special addresses:

• 0.0.0.0/8 — “this” network (source only)
• 127.0.0.0/8 — loopback
• 169.254.0.0/16 — link-local (APIPA)
• 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16 — private (RFC 1918)
• 255.255.255.255 — limited broadcast

NAT (Network Address Translation)

NAT translates private IP addresses to a public IP at the network boundary. It maintains a translation table mapping private (IP, port) pairs to (public IP, NAT-assigned port). Outgoing packets have their source address/port rewritten; incoming packets are demultiplexed by port number. This provides address reuse and a basic firewall, but breaks the end-to-end principle and complicates protocols that embed IP addresses in payloads.

IPv6

IPv6 address is $128$ bits, written as eight groups of four hex digits separated by colons:

Double colon :: compresses consecutive zero groups (once per address). The header is a fixed $40$ bytes:

Key differences from IPv4:

• No header checksum (redundant with link-layer and transport-layer checksums).
• No fragmentation by routers (uses Path MTU Discovery; if needed, sender fragments).
• Extension headers replace the Options field.
• Neighbor Discovery Protocol (NDP) replaces ARP.
• Stateless address autoconfiguration (SLAAC).

Routing Algorithms

The routing problem: given a graph $G=(V,E)$ with edge weights $w(u,v)$, find a path of minimum cost from source $s$ to destination $t$.

Distance-Vector (Bellman–Ford based, e.g., RIP): Each router maintains a vector of distances to all destinations. Routers exchange their distance vectors with neighbors. Updates follow the Bellman–Ford equation:

Converges to correct distances but suffers from the count-to-infinity problem (bad news travels slowly). Mitigations: split horizon (don’t advertise a route back to the neighbor it was learned from), poison reverse (advertise with $\infty$), triggered updates, maximum hop count (RIP: $15$).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// Conceptual distance-vector update for router x
void dv_update(Router *x) {
    for (each destination y) {
        for (each neighbor v) {
            if (x->cost[v] + dv_table[v][y] < x->dist[y]) {
                x->dist[y] = x->cost[v] + dv_table[v][y];
                x->next_hop[y] = v;
            }
        }
    }
    // Send updated vector to neighbors
    send_distance_vector(x);
}

Link-State (Dijkstra-based, e.g., OSPF): Each router floods its link states (neighbors and costs) throughout the entire network via Link State Advertisements (LSAs). Once every router has the full topology, each independently runs Dijkstra’s algorithm to compute the shortest-path tree rooted at itself.

Dijkstra’s Algorithm for Routing

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#define INF 1000000
#define MAX_NODES 100

void dijkstra(int n, int cost[MAX_NODES][MAX_NODES], int src,
              int dist[], int prev[]) {
    bool visited[MAX_NODES] = {false};
    for (int i = 0; i < n; i++) { dist[i] = INF; prev[i] = -1; }
    dist[src] = 0;

    for (int count = 0; count < n; count++) {
        int u = -1, min_dist = INF;
        for (int i = 0; i < n; i++)
            if (!visited[i] && dist[i] < min_dist)
                { min_dist = dist[i]; u = i; }
        if (u == -1) break;
        visited[u] = true;
        for (int v = 0; v < n; v++)
            if (!visited[v] && cost[u][v] < INF)
                if (dist[u] + cost[u][v] < dist[v]) {
                    dist[v] = dist[u] + cost[u][v];
                    prev[v] = u;
                }
    }
}

• RIP uses distance-vector; metric = hop count; updates every $30$s.
• OSPF uses link-state; metric = configurable cost; flooded LSAs; hierarchical areas (area $0$ is backbone).
• BGP (Border Gateway Protocol) routes between autonomous systems (ASes) using path-vector: each route advertisement carries the full AS path. Policy-based routing, not purely shortest-path.

ARP (Address Resolution Protocol)

Maps an IP address to a MAC address within a LAN. A host broadcasts an ARP request: “Who has $192.168.1.1$?” The target replies with its MAC address. Results are cached in the ARP table (entries timeout to handle changes). For destinations outside the LAN, the sender uses the default gateway’s MAC address.

Transport Layer

The transport layer provides logical communication between application processes running on different hosts. The Internet offers two transport protocols:

UDP (User Datagram Protocol)

UDP is minimal: it adds only source/destination ports, length, and a checksum over a pseudo-header + UDP segment. No handshake, no state, no retransmission.

The UDP checksum covers the UDP header, payload, and a pseudo-header containing source/destination IPs, protocol number, and UDP length. This lets the receiver verify that the datagram arrived at the correct destination.

TCP (Transmission Control Protocol)

TCP provides a reliable, in-order, byte-stream abstraction between two endpoints. Its segment structure:

Key fields:

• Sequence number: byte offset of the first data byte in this segment (excluding SYN/FIN, which consume one sequence number each).
• Acknowledgment number: next expected byte from the other side (cumulative ACK).
• Flags: SYN (synchronize, open), FIN (finish, close), RST (reset), ACK, PSH (push), URG (urgent).
• Window size: receiver’s advertised window for flow control.

TCP Connection Management

The three-way handshake establishes a connection:

Each side chooses an Initial Sequence Number (ISN) independently (randomized to prevent sequence number attacks). After the handshake, both directions are open and can transfer data simultaneously (full-duplex).

Connection teardown uses a four-way handshake, as each direction closes independently (half-close possible):

After sending the final ACK, A enters TIME_WAIT state for $2\times\text{MSL}$ (Maximum Segment Lifetime, typically $2$ minutes) to ensure any delayed FIN retransmissions from B are handled. This prevents old segments from a previous incarnation from interfering with a new connection to the same (IP, port) pair.

TCP Reliability

TCP ensures reliability through:

1. Cumulative ACK: ACK number $n$ acknowledges all bytes up to $n-1$. If segments arrive out-of-order, the receiver repeats the last in-order ACK (duplicate ACK).
2. Timeout and Retransmission: TCP estimates RTT and sets a timeout. Jacobson’s algorithm computes: $$\text{SRTT} = (1-\alpha)\cdot\text{SRTT} + \alpha\cdot\text{SampleRTT},\quad \alpha=1/8$$ $$\text{DevRTT} = (1-\beta)\cdot\text{DevRTT} + \beta\cdot|\text{SampleRTT}-\text{SRTT}|,\quad \beta=1/4$$ $$\text{RTO} = \text{SRTT} + 4\cdot\text{DevRTT}.$$
3. Fast Retransmit: if the sender receives $3$ duplicate ACKs for the same sequence number, it retransmits the missing segment without waiting for the timeout. This handles isolated packet loss efficiently.

TCP Flow Control

TCP uses a sliding window to prevent the sender from overflowing the receiver’s buffer:

The receiver’s advertised window (WinSize in the header) tells the sender how much free buffer space is available. If the advertised window is $0$, the sender pauses and sends periodic window probes (1-byte segments) to detect when the window reopens.

TCP Congestion Control

TCP maintains a congestion window (cwnd) to limit the number of unacknowledged bytes in flight:

The canonical TCP congestion control (Reno) operates in phases:

1. Slow Start: cwnd starts at $1$ MSS (Maximum Segment Size) and doubles every RTT (increases by $1$ MSS per ACK). Exponentially probes available bandwidth until cwnd reaches ssthresh (Slow Start Threshold) or a loss is detected.
2. Congestion Avoidance: cwnd increases linearly (by roughly $1$ MSS per RTT: cwnd += MSS * MSS / cwnd per ACK).
3. Loss Detection:
   • Timeout (severe congestion): ssthresh = cwnd/2, cwnd = 1 MSS, re-enter Slow Start.
   • Triple Duplicate ACK (Fast Recovery): ssthresh = cwnd/2, cwnd = ssthresh + 3*MSS, enter Fast Recovery. For each additional duplicate ACK, cwnd += MSS. Upon receiving a new ACK, cwnd = ssthresh, enter Congestion Avoidance.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// Conceptual TCP congestion control state (Reno)
typedef enum { SLOW_START, CONG_AVOID, FAST_RECOVERY } CCState;

void on_ack(TCP *tcp, int acked_bytes) {
    if (tcp->cc_state == SLOW_START) {
        tcp->cwnd += acked_bytes;  // exponential growth
        if (tcp->cwnd >= tcp->ssthresh)
            tcp->cc_state = CONG_AVOID;
    } else if (tcp->cc_state == CONG_AVOID) {
        tcp->cwnd += MSS * (float)acked_bytes / tcp->cwnd;  // linear
    } else if (tcp->cc_state == FAST_RECOVERY) {
        tcp->cwnd = tcp->ssthresh;
        tcp->cc_state = CONG_AVOID;
    }
    // Clamp to receiver window
    tcp->cwnd = min(tcp->cwnd, tcp->rwnd);
}

void on_loss(TCP *tcp, bool is_timeout) {
    tcp->ssthresh = max(tcp->cwnd / 2, 2 * MSS);
    if (is_timeout) {
        tcp->cwnd = MSS;
        tcp->cc_state = SLOW_START;
    } else {  // triple duplicate ACK
        tcp->cwnd = tcp->ssthresh + 3 * MSS;
        tcp->cc_state = FAST_RECOVERY;
    }
}

Other variants: CUBIC (Linux default) uses a cubic function instead of AIMD, achieving better utilization on high-BDP (Bandwidth-Delay Product) paths. BBR (Bottleneck Bandwidth and RTT, Google) models the path rather than reacting to loss.

Application Layer

The application layer is where network applications and their protocols reside. Common architectures:

• Client-Server: a persistent server serves many clients (Web, email).
• P2P (Peer-to-Peer): peers communicate directly, with no central server (BitTorrent, blockchain).
• Hybrid: mix of both (Skype originally).

DNS (Domain Name System)

DNS maps human-readable domain names to IP addresses (and vice versa). It is a hierarchical, distributed database.

The namespace is a tree:

Resource Records (RRs) are the database entries, stored as $(\text{Name}, \text{Type}, \text{Class}, \text{TTL}, \text{Value})$:

Resolution process:

1. Client sends query to local DNS resolver.
2. Resolver iteratively queries root → TLD → authoritative servers (iterative), or forwards to another resolver (recursive).
3. Results are cached along the entire path, respecting TTL.

DNS uses UDP port $53$ (TCP for large responses or zone transfers). The protocol has a $16$-bit transaction ID to match queries with responses.

HTTP (Hypertext Transfer Protocol)

HTTP is the foundation of the World Wide Web. It follows a request-response model over TCP (typically port $80$, or $443$ for HTTPS/TLS).

Request format:

Common methods: GET, POST, PUT, DELETE, HEAD, OPTIONS.

Response format:

Status codes: $1\text{xx}$ (informational), $2\text{xx}$ (success, e.g., $200$ OK), $3\text{xx}$ (redirection, e.g., $301$ Moved Permanently), $4\text{xx}$ (client error, e.g., $404$ Not Found), $5\text{xx}$ (server error).

HTTP/1.1 features: persistent connections (reuse TCP for multiple requests), pipelining (send multiple requests without waiting for responses — rarely used due to head-of-line blocking), chunked transfer encoding, virtual hosting (Host header).

HTTP/2: binary framing, multiplexed streams (solves head-of-line blocking), header compression (HPACK), server push.

HTTP/3: runs over QUIC (UDP-based) instead of TCP, with built-in TLS 1.3, $0$-RTT handshake, per-stream flow control, and no head-of-line blocking across streams.

Cookies: HTTP is stateless; cookies add state. The server sends Set-Cookie: name=value, and the client echoes it in subsequent requests via Cookie: name=value. Cookies enable sessions, personalization, and tracking.

HTTPS (HTTP over TLS): TLS provides confidentiality (symmetric encryption with session keys), integrity (MAC), and authentication (certificates + PKI). The TLS handshake:

1. Client sends ClientHello (supported cipher suites, random nonce).
2. Server replies ServerHello (chosen cipher suite, random nonce), sends certificate chain, ServerHelloDone.
3. Client generates Pre-Master Secret, encrypts it with server’s public key (from certificate), sends ClientKeyExchange. Both derive session keys from the two nonces + pre-master secret.
4. Both switch to encrypted communication (ChangeCipherSpec + Finished).

TLS 1.3 reduces this to $1$-RTT (or $0$-RTT for resumed sessions).

Socket Programming

A socket is the interface between an application and the transport layer, identified by (IP address, port number). Sockets abstract the underlying protocol (TCP/UDP) into file-descriptor-like objects.

TCP Server (C):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <sys/socket.h>
#include <netinet/in.h>
#include <unistd.h>

int main() {
    int listen_fd = socket(AF_INET, SOCK_STREAM, 0);
    struct sockaddr_in addr = {
        .sin_family = AF_INET,
        .sin_port   = htons(8080),
        .sin_addr.s_addr = INADDR_ANY
    };
    bind(listen_fd, (struct sockaddr*)&addr, sizeof(addr));
    listen(listen_fd, 5);  // backlog = 5

    struct sockaddr_in client_addr;
    socklen_t len = sizeof(client_addr);
    int conn_fd = accept(listen_fd, (struct sockaddr*)&client_addr, &len);

    char buf[1024];
    int n = recv(conn_fd, buf, sizeof(buf), 0);
    send(conn_fd, "HTTP/1.1 200 OK\r\n\r\nHello", 26, 0);

    close(conn_fd);
    close(listen_fd);
    return 0;
}

TCP Client (C):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int sock = socket(AF_INET, SOCK_STREAM, 0);
struct sockaddr_in server = {
    .sin_family = AF_INET,
    .sin_port   = htons(8080)
};
inet_pton(AF_INET, "127.0.0.1", &server.sin_addr);
connect(sock, (struct sockaddr*)&server, sizeof(server));

char *msg = "GET / HTTP/1.1\r\nHost: localhost\r\n\r\n";
send(sock, msg, strlen(msg), 0);
// recv and process response...
close(sock);

Network Performance Metrics

Delay decomposes into four components:

• Processing delay ($D_{\text{proc}}$): header parsing, error checking, lookup ($\mu$s scale).
• Queuing delay ($D_{\text{queue}}$): time spent waiting in buffers. Highly variable, depends on traffic intensity $\rho = \frac{\lambda L}{R}$, where $\lambda$ is packet arrival rate, $L$ is packet length (bits), $R$ is link rate (bps). When $\rho\to 1$, queuing delay $\to\infty$.
• Transmission delay ($D_{\text{trans}}$): $L/R$, the time to push all bits into the link.
• Propagation delay ($D_{\text{prop}}$): $d/s$, distance divided by signal propagation speed ($s\approx 2\times 10^8$ m/s in copper/fiber).

The Pipe Capacity is the number of bits that can be physically in flight on a link at any instant — i.e., the product of the link rate and the one-way propagation delay:

This is how many bits the link “holds” at a snapshot. But from the sender’s perspective, after pushing the last bit into the link, it must wait for an ACK to travel back before sending more — the full round-trip time is the relevant interval. Hence the Bandwidth-Delay Product (BDP) is defined with RTT:

BDP is the minimum window size (in bits) required for the sender to keep the pipe continuously busy. If the window is smaller than BDP, throughput is capped by the window rather than the link rate.

Throughput is the effective data rate observed by an application. For a path of $n$ links with rates $R_1,R_2,\ldots,R_n$:

The bottleneck link determines the end-to-end throughput.

Delay $\times$ Bandwidth rule: to keep a link fully utilized, the sender must have at least BDP bytes of unacknowledged data in flight (or equivalently, the window must be at least BDP). If the window is too small, throughput is limited by:

Exercises

Ex.1.1. A message of $L=6\times 10^6$ bits is to be sent from $A$ to $B$ over $h=4$ hops, each link having rate $R=2$ Mbps. Compare the total delivery time (ignoring propagation and processing delays) under:

1. Circuit switching (setup time $S=500$ ms, ignore teardown).
2. Message switching.
3. Packet switching with packet size $P=1500$ bytes ($1.2\times 10^4$ bits).

Ex.1.2. Consider a $1$ Mbps link shared by $N$ users. Each user is active $10\%$ of the time, and when active, requires $100$ kbps. Find the maximum $N$ such that:

1. All users can be simultaneously supported under circuit switching (FDM, equal allocation).
2. The probability of more than $10$ users being active simultaneously is $< 0.001$ under packet switching. (Use the binomial distribution; a normal approximation is acceptable.)

Ex.1.3. A channel has bandwidth $B = 3\text{ MHz}$ and SNR $= 30\text{ dB}$. Compute the maximum achievable data rate according to Shannon’s theorem.

Ex.1.4. Show that for a Stop-and-Wait protocol with frame size $L$ bits, link rate $R$ bps, and one-way propagation delay $D$ seconds, the maximum throughput is

If $L=1000$ bits, $R=1$ Mbps, and $D=50$ ms, what is the utilization?

Ex.2.1. Given the data bit stream $101111110011111010$, show the transmitted bit stream after bit stuffing in HDLC (flag = $01111110$).

Ex.2.2. CRC: Let $M(x) = x^9 + x^8 + x^5 + x^4$ (data), and $G(x) = x^3 + 1$ (generator). Find the CRC remainder $R(x)$ and the transmitted codeword $T(x)$.

Ex.2.3. A slotted ALOHA network has $N$ stations, each transmitting in a slot with probability $p$. Derive the throughput $S$ as a function of $N$ and $p$, and show that $\max S = 1/e$ as $N\to\infty$.

Ex.3.1. Given an IPv4 address $172.20.150.46/27$, find:

1. The subnet mask in dotted-decimal notation.
2. The network address.
3. The broadcast address.
4. The number of usable hosts.

Ex.3.2. Show that in distance-vector routing, the count-to-infinity problem can cause a routing loop of length $\ge 2$ to persist for an unbounded number of update rounds if no mitigation is used.

Ex.3.3. Consider the graph $G$ with vertices $\{A,B,C,D,E\}$ and weighted undirected edges:

Run Dijkstra’s algorithm from $A$ and write out the distance and predecessor arrays after each iteration.

Ex.4.1. A TCP connection has RTT $= 100$ ms, MSS $= 1460$ bytes, and no packet loss. Approximately how many RTTs are needed for cwnd to reach $100$ KB starting from $1$ MSS in Slow Start? What if we start from Congestion Avoidance?

Ex.4.2. Show that the total number of segments transmitted in a three-way handshake followed by a four-way teardown (each FIN separately ACKed) is minimal for reliable connection setup and teardown.

Ex.4.3. Given the TCP sequence of cwnd values (in MSS): $1,2,4,8,16,32,33,34,35,36,18,19,20,\ldots$, identify:

1. The Slow Start phase.
2. The Congestion Avoidance phase.
3. When a triple-duplicate-ACK event occurred and the ssthresh value set.

Ex.5.1. A DNS resolver caches an A record with TTL $= 3600$s. At $t=0$, a client queries for the domain and the resolver must do a full iterative lookup. At $t=1800$, another client queries the same domain. Describe the difference in resolution time and explain the role of TTL.

Ex.5.2. Design a simple HTTP/1.1 request pipelining scenario: a client sends requests for a base HTML page and $3$ embedded images on a persistent connection with RTT $= 50$ ms, and each response takes $20$ ms transmission time. Compute the total page load time without pipelining vs. with pipelining vs. with HTTP/2 multiplexing. Ignore parsing and rendering delays.

Data Flow