# CSE 1405 Computer Networks — Complete Summary

---

## Lecture 1: Introduction, Layered Architecture, OSI Model

### Key Concepts
- **Protocol**: An algorithm for communication between two or more parties; defines the rules of communication and provides a service.
- **Layered Architecture**: Networks are structured in layers. Each layer provides services only to the layer above it. This provides abstraction — lower layer details are hidden from higher layers, protocols/hardware can be swapped without affecting other layers.
- **OSI Model** (7 layers, from lowest to highest):
  1. **Physical**: Transmits bits over a physical medium
  2. **Data Link**: Detects/corrects errors from physical layer; allows multiple parties to share a physical medium
  3. **Network**: Realizes routing data over multiple networks (internet routing)
  4. **Transport**: Realizes a reliable or unreliable data stream between two hosts
  5. **Session**: Manages sessions/dialogues (no major protocols in practice)
  6. **Presentation**: Data format/encryption (no major protocols in practice)
  7. **Application**: Realizes internet applications (HTTP, DNS, SMTP, etc.)
- **TCP/IP Model**: Merges physical + data link into one layer; omits session and presentation layers. Designed based on existing protocols (bottom-up), unlike OSI which was designed top-down.

### OSI Layer Data Units
| Layer | Data Unit Name |
|---|---|
| Physical | bit |
| Data Link | frame |
| Network | packet |
| Transport | segment |
| Session / Presentation / Application | message (no specific name) |

### Key Concepts — Connection Types
- **Connection**: Stateful communication between two parties; requires agreement on initial state and exchange of state information.
- **Connection-oriented**: Establish connection, communicate, release connection. Requires state at both ends.
- **Connectionless**: Just send data; no state maintained.

### Key Concepts — Timing Terms
- **Latency (Propagation delay)**: Time between a very short message leaving machine A until it arrives at machine B.
- **RTT (Round Trip Time)**: Time between A sending a very short message to B and getting a very short response back.
- **Transmission delay**: Time it takes A to transmit a message (from first bit leaves A to last bit leaves A).
- **Bandwidth**: Maximum rate at which data can be sent between A and B (measured in bps, MiB/s).
- **Throughput**: Actual rate of sending (including overhead).
- **Goodput**: Actual rate of sending payload only (excluding headers/trailers).

---

## Lecture 2: Data Link Layer — Error Detection & Correction, Framing

### Key Concepts — Error Detection
- **Parity bit**: Add one bit so that the total number of 1s is even (even parity) or odd (odd parity). Detects an odd number of bit flips only. Cannot detect errors flipping an even number of bits.
- **Parity words (parity blocks)**: Arrange data in a 2D grid. Compute parity for each row and each column. Can detect up to 2-bit errors (single-bit errors corrected if even parity, detected if odd). Cannot always locate the error.
- **Internet Checksum** (1's complement): Divide data into fixed-size blocks. Add all blocks using 1's complement addition (carry around any overflow). Take 1's complement of the result. The receiver adds all blocks (including checksum) — result should be all 1s (i.e., complement is 0).
- **CRC (Cyclic Redundancy Check)**:
  - Generator polynomial $G(x)$ is represented as a bit string (e.g., $x^3 + x^2 + 1 \to 1101$).
  - To compute: append $r$ zeros to data (where $r$ = degree of $G$), then perform polynomial long division over GF(2) — XOR, no carries.
  - Remainder (of length $r$) is appended to the original data.
  - Receiver divides received message by $G$; if remainder = 0, no error detected.

### Method: CRC Computation
1. Determine degree $r$ of generator polynomial $G$ (number of bits in $G$ minus 1).
2. Append $r$ zeros to the end of the data message.
3. Divide the augmented data by $G$ using XOR long division (no carries, subtraction = addition = XOR).
4. The remainder (must be padded to $r$ bits) is the CRC check value.
5. Transmitted message = original data + remainder.

### Method: CRC Error Detection
1. Divide the received message by $G$ using XOR long division.
2. If remainder = 0, message is accepted. If remainder $\neq 0$, error detected.

### Key Concepts — Error Correction
- **Hamming Code**: Can detect and correct 1-bit errors.
  - Parity bits are placed at positions that are powers of 2 (positions 1, 2, 4, 8, ...).
  - Data bits fill the remaining positions.
  - Each parity bit covers specific bit positions (position $2^k$ covers all bits where the $k$-th bit of the position index is 1).
  - Number of parity bits: $r = \lceil \log_2(m + r + 1) \rceil$ where $m$ is the number of data bits. Total codeword length $l = m + r$.
  - The syndrome (computed parity checks) directly identifies the position of a 1-bit error.
  - Can be extended with an extra overall parity bit to detect (but not correct) 2-bit errors.
- **Hamming Distance**: The number of bit positions in which two messages differ.

### Method: Compute a Hamming Code
1. Determine the number of parity bits $r$ needed: $r = \lceil \log_2(m + r + 1) \rceil$ or simply find smallest $r$ satisfying $2^r \geq m + r + 1$.
2. Create positions for $m + r$ bits. Place parity bits at positions $1, 2, 4, 8, \ldots$.
3. Fill data bits into remaining positions (from left, starting at position 1).
4. For each parity bit at position $2^k$: compute parity over all bit positions where the $k$-th bit of the index is 1.
5. For even parity: set parity bit so the total number of 1s in covered positions is even. For odd parity: make it odd.

### WARNING
- Hamming codes correct 1-bit errors. If 2-bit errors occur, the algorithm may incorrectly "correct" to the wrong message. An extra overall parity bit can detect 2-bit errors (ask for retransmission instead).
- Parity bits can only detect errors, not locate them. Parity words with even parity can detect but not always locate 2-bit errors.

### Key Concepts — Framing
- **Problem**: The physical layer sends bits; how does the receiver know where one frame ends and the next begins?
- **Byte stuffing**: Prepend a special FLAG byte at the start and end of each frame. If the FLAG byte appears in data, insert an ESCAPE byte before it. Also escape the ESCAPE byte itself.
  - Example: FLAG = 01111110, ESC = 11100000. To transmit the byte 01111110 in data, send 11100000 01111110.
- **Bit stuffing**: Whenever $n$ consecutive 1s appear in data, insert a 0 after them (where $n$ is the number of consecutive 1s in the flag pattern minus 1).
  - Example: flag pattern = 011110 (4 consecutive 1s minus 1 = 3). Rule: after every 3 consecutive 1s, insert a 0.
  - Receiver reverses: when it sees 3 consecutive 1s followed by a 0, it discards the 0.
- **Bit flips in framing bytes**: Not included in error detection — a flipped flag byte can cause loss of synchronization, discarding the current and possibly subsequent frames.

### WARNING
- Fixed-length framing: if one frame has an error, the receiver finds the trailer in the wrong place, causing all subsequent frames to also appear corrupted.
- Byte count framing: if the count bit flips, the receiver misinterprets frame boundaries.
- Bit stuffing is preferred in practice (used in HDLC, Ethernet).

---

## Lecture 3: Data Link Layer — Sliding Window Protocols, Flow Control

### Key Concepts
- **ARQ (Automatic Repeat reQuest)**: Connection-oriented protocol. Receiver sends ACK for correctly delivered frames. Sender sets a timer and retransmits if no ACK arrives.
- **Stop-and-wait ARQ**: Sender transmits one frame and waits for ACK. Low throughput. Requires 1-bit sequence numbers (0 and 1).
  - **Problem with lost ACK**: Without numbering, receiver cannot distinguish retransmitted frame from a new one. Numbering solves this: receiver checks sequence number, discards duplicates, still sends ACK.
- **Piggybacking**: Receiver appends ACK to its own data frames instead of sending separate ACK frames.
- **Cumulative ACK**: ACK $n$ acknowledges all frames up to and including $n$. Saves messages.

### Sliding Window Protocols
- **Window size $k$**: Maximum number of unacknowledged frames the sender can have in flight.
- **Impact of $k$ without errors**: Choose $k$ large enough that bandwidth is always utilized. Optimal $k$ relates to the bandwidth-delay product.

### Go-Back-N (GBN)
- Sender maintains a window of up to $k$ unacknowledged frames.
- If a frame is lost, receiver **discards** frames with unexpected sequence numbers and sends duplicate ACKs for the last in-order frame.
- Sender times out and **retransmits all frames** from the lost one onwards.
- **Sequence number space**: Must have at least $k + 1$ distinct sequence numbers.
- Simpler receiver (no buffering of out-of-order frames).

### Selective Repeat (SR)
- Sender maintains a window of up to $k$ unacknowledged frames.
- Receiver **stores** out-of-order frames in a buffer and sends NAK (Negative ACK) for missing frames.
- Sender **retransmits only the specific lost frames**.
- **Sequence number space**: Must have at least $2k$ distinct sequence numbers (to distinguish new vs. retransmitted frames).
- More complex receiver (needs buffering), but more efficient.

### Method: Compare Go-Back-N vs Selective Repeat
| Property | Go-Back-N | Selective Repeat |
|---|---|---|
| Out-of-order handling | Discard | Buffer |
| Retransmission | All frames from lost one | Only lost frames |
| ACK type | Cumulative | Per-frame (or cumulative with NAK) |
| Sequence space | $\geq k + 1$ | $\geq 2k$ |
| Receiver complexity | Low | High |

### WARNING
- For Go-Back-N, if the receiver does not buffer out-of-order frames, those frames are lost and must be retransmitted.
- For Selective Repeat, if the sequence space is too small ($< 2k$), ambiguity arises between new frames and retransmissions.

### Method: Compute Throughput and Goodput for Sliding Window
1. Compute transmission time per frame: $T_{frame} = \frac{\text{frame size}}{\text{bandwidth}}$.
2. Compute time until first ACK: $T_{ACK} = T_{frame} + \text{latency}_{send} + \text{latency}_{receive}$.
3. Check: is $T_{ACK} > k \times T_{frame}$? If yes, sender is window-limited.
4. Throughput = $\frac{k \times \text{frame size}}{T_{ACK}}$ bytes/second (when window-limited).
5. Goodput = Throughput $\times (1 - \text{overhead fraction})$, where overhead fraction = $\frac{\text{header + trailer size}}{\text{frame size}}$.

---

## Lecture 4: MAC Sublayer — ALOHA, CSMA, Collision-Free Protocols

### Key Concepts
- **Collision**: Multiple parties use the medium simultaneously, interfering with each other. Detected via error detection.
- **Channel allocation**: Deciding how to share a medium among multiple users.
  - **Static**: Fixed allocation (rarely used for bursty traffic).
  - **Dynamic**: Users contend for the medium.

### ALOHA
- **Pure ALOHA**: Transmit whenever data is available. If collision, wait a random time and retry.
  - Max channel utilization: $\approx 18\%$.
- **Slotted ALOHA**: Time divided into slots. Transmit only at slot boundaries. If collision, wait a random number of slots and retry.
  - Max channel utilization: $\approx 37\%$ (twice as efficient as pure ALOHA).
  - Messages sent at fixed time slots reduce collision window.

### CSMA (Carrier Sense Multiple Access)
- Senders "sense" the channel before transmitting.
- **1-persistent CSMA**: Wait for idle, then send immediately (probability $p = 1$).
- **Non-persistent CSMA**: If busy, wait a random time, then check again.
- **p-persistent CSMA**: If busy, wait for next time slot. If idle, send with probability $p$ (otherwise wait for next slot).

### WARNING
- Wi-Fi (802.11) uses **CSMA/CA (Collision Avoidance)**, not CSMA/CD, because wireless nodes cannot transmit and receive simultaneously (half-duplex). The received signal is too weak compared to the transmitted signal to detect collisions.
- Ethernet uses **CSMA/CD (Collision Detection)** because wired stations can detect collisions while transmitting (by listening for noise).

---

## Lecture 5: MAC Sublayer — Ethernet (CSMA/CD)

### Key Concepts
- **Ethernet Frame Structure**: Preamble (8 bytes) | Destination MAC (6 bytes) | Source MAC (6 bytes) | Type (2 bytes) | Data (0–1500 bytes) | Pad (0–46 bytes) | CRC (4 bytes).
- **CSMA/CD (Carrier Sense Multiple Access with Collision Detection)**:
  1. Sense channel. If idle, start transmitting.
  2. While transmitting, also listen for collisions.
  3. If collision detected, send a **jam signal** (32 bits), then stop.
  4. Wait a **random backoff** time, then retry.
- **Binary Exponential Backoff**: After $n$ collisions, choose a random integer from $[0, 2^n - 1]$ time slots. Maximum $n = 10$ (clamped at $2^{10} - 1 = 1023$). After 16 collisions, give up.
  - After the 4th collision, $x = 2^4 - 1 = 15$.

### Why Minimum Frame Size?
- Ethernet requires a minimum frame size (72 bytes) to ensure that a sender finishes transmitting before a potential collision signal reaches it. If the frame is too short, the sender might finish before detecting a collision at the far end of the cable.

### Ethernet Performance
- **Half-dublex**: Devices can send or receive but not both simultaneously.
- **Full-duplex**: Devices can send and receive simultaneously (used with switches).
- **Versions**: 10 Mbps (classic), 100 Mbps (Fast), 1 Gbps (Gigabit), 10 Gbps, 40/100 Gbps.

### Switched Ethernet
- **Switch (bridge)**: Learns MAC addresses by observing source addresses of incoming frames.
- **Learning**: When a frame arrives on port $p$ from MAC address $A$, the switch records $A \to p$ in its forwarding table.
- **Forwarding**: If destination MAC is in the table, forward only to that port. If unknown, flood to all ports (except incoming).
- **MAC table update**: If the same MAC address appears on a different port, the entry is updated.

### Spanning Tree Protocol (STP)
- Prevents loops in switched networks.
- Selects a **root bridge** (switch with the smallest ID).
- Each non-root switch selects a **root port** (best path to root).
- On multi-access networks, one **designated bridge** is selected for each segment.
- All other ports are **blocked** (no forwarding).

---

## Lecture 6: MAC Sublayer — Wireless LANs (802.11), Bluetooth, Switching

### Key Concepts — 802.11 (Wi-Fi)
- **Architecture**: Access points (APs) form cells. Multiple APs connected via a distribution system. Clients roam between APs.
- **Half-duplex radios**: Cannot transmit and listen simultaneously. Collision detection via CSMA/CD does not work.
- **CSMA/CA (Collision Avoidance)**:
  1. Sense channel. If idle for DIFS (Distributed Inter-Frame Space), proceed.
  2. If busy, wait until idle, then apply **binary exponential backoff** (counter decrements only when channel is idle).
  3. After counter reaches 0, transmit data.
  4. Receiver responds with **ACK** after SIFS (shorter than DIFS — higher priority).
- **RTS/CTS (Request to Send / Clear to Send)**: Optional mechanism to avoid the **hidden node problem**.
  - Sender sends RTS to receiver. Receiver replies with CTS. Other nodes hearing CTS defer.
  - If RTS collides, no CTS is sent, and sender retries (no need for RTS/CTS ACK).

### WARNING — Hidden Node Problem
- Station A can hear the AP but not station C. If A transmits, C might also transmit, causing a collision at the AP. RTS/CTS prevents this by reserving the channel.

### 802.11 MAC Frame Fields
- Frame control, duration, addresses (up to 4), sequence control, data, FCS (Frame Check Sequence).

### Bluetooth
- **Piconet**: One master, up to 7 active slaves (more in parking mode). Uses frequency hopping.
- **Scatternet**: Multiple interconnected piconets.
- **Protocol stack**: Baseband, link manager, L2CAP, RFCOMM, SDP.

### Data Link Layer Switching
- **Bridges/switches**: Operate at the data link layer. Forward based on MAC addresses.
- **Learning bridges**: Build forwarding table dynamically by observing source MAC addresses.
- **Virtual LANs (VLANs)**: Logically partition a physical LAN. Each port tagged with a VLAN ID. Broadcasts stay within VLAN.
- **Repeaters**: Physical layer (amplify signal). **Hubs**: Multiport repeaters (all ports see all traffic). **Bridges**: Data link layer (filter based on MAC). **Routers**: Network layer (forward based on IP). **Gateways**: Application layer (translate between protocols).

---

## Lecture 7: Network Layer — IP, IPv4, IPv6, Addressing

### Key Concepts
- **Network Layer Services**:
  - **Connectionless (datagram)**: Each packet routed independently. No setup. Best-effort delivery. Internet IP is this type.
  - **Connection-oriented (virtual circuit)**: Setup path first, then packets follow the same path. Guaranteed in-order delivery. Example: ATM, MPLS.
- **Store-and-forward packet switching**: Each node receives the entire packet before forwarding it to the next hop.

### IPv4
- **Header**: Version (4 bits), IHL (5 bits), Type of Service (8 bits), Total Length (16 bits), Identification (16 bits), Flags (3 bits), Fragment Offset (13 bits), TTL (8 bits), Protocol (8 bits), Header Checksum (16 bits), Source IP (32 bits), Destination IP (32 bits).
- **IP Address**: 32-bit, typically written as dotted decimal (e.g., 130.140.0.0/16).
- **Classful addressing** (historical): Class A (0.x.x.x), Class B (10.x.x.x), Class C (110.x.x.x).
- **Subnetting**: Divide a network into smaller subnets using a subnet mask.

### CIDR (Classless Inter-Domain Routing)
- **Notation**: $A.B.C.D/n$ where $n$ is the number of network bits.
- **Example**: 130.140.0.0/16 means the first 16 bits are the network prefix; the remaining 16 bits are host addresses. Range: 130.140.0.0 to 130.140.255.255.
- **Longest prefix match**: When multiple prefixes match, use the longest (most specific) one. E.g., for destination 130.140.128.255, both 130.140.0.0/16 and 130.140.0.0/17 match, but /17 is more specific.

### Method: CIDR Subnet Calculations
1. Given $A.B.C.D/n$: first $n$ bits are the network address.
2. Number of addresses = $2^{32-n}$.
3. Number of host addresses = $2^{32-n} - 2$ (subtract network and broadcast).
4. To find the network address: AND the IP with the subnet mask.
5. To find the broadcast address: set all host bits to 1.

### IPv6
- **128-bit addresses** (vs. 32-bit for IPv4). Address space: $2^{128}$.
- **Notation**: 8 groups of 4 hex digits, separated by colons. E.g., 2001:0db8:0000:0000:0000:ff00:0042:8329.
- **Compression**: Leading zeros in each group can be omitted. One sequence of consecutive all-zero groups can be replaced with `::` (only once per address).
- **Fixed 40-byte header** (simpler than IPv4). No header checksum (relying on data link and transport layers).
- **Extension headers**: Optional headers placed after the fixed header.
- **No fragmentation at routers**: Only the source can fragment (using extension headers). Path MTU Discovery avoids fragmentation.
- **IPv4-to-IPv6 transition**: 6to4, tunneling, dual-stack.

### WARNING
- In IPv4, fragmentation can occur at each router (each with different MTU), potentially causing cascading fragmentation. IPv6 eliminates this — only the source fragments.
- The IPv4 header checksum is only over the header, not the data. IPv6 removed it entirely for performance.

---

## Lecture 8: Network Layer — IP Fragmentation, NAT, Routing Algorithms

### Key Concepts — IP Fragmentation
- **MTU (Maximum Transmission Unit)**: Maximum size of a packet that can be transmitted on a network.
- **Fragmentation**: When a packet exceeds the MTU of the next link, it is fragmented.
  - Each fragment has its own IP header (with updated length, fragment offset, and flags).
  - Fragment sizes (except the last) must be multiples of 8 bytes.
  - The **fragment offset** field indicates where in the original packet this fragment belongs (in units of 8 bytes).
- **MTU Discovery**: Source determines the smallest MTU along the path and fragments accordingly before sending, avoiding intermediate fragmentation.

### Method: Compute Fragmentation
1. Original packet size = header + payload.
2. For each network with MTU $M$: max payload per fragment = $M - \text{header size}$ (padded to multiple of 8).
3. Number of fragments = $\lceil \text{remaining payload} / \text{max payload per fragment} \rceil$.
4. Fragment offset = cumulative bytes before this fragment, divided by 8.

### WARNING
- Without MTU discovery: a packet may be fragmented at every router along the path, causing many small fragments.
- With MTU discovery: the source already knows the minimum MTU and fragments optimally at the source.

### Key Concepts — NAT (Network Address Translation)
- NAT replaces private/internal IP addresses and port numbers with a public/external IP address and port number.
- NAT maintains a **mapping table**: (internal IP, internal port) $\leftrightarrow$ (external IP, external port).
- Multiple internal devices share one external IP address (port multiplexing).
- When a response arrives at the external port, NAT looks up the mapping and forwards to the correct internal device.

### Key Concepts — Routing Algorithms
- **Shortest Path (Dijkstra's)**:
  - Each node knows costs to directly connected neighbors.
  - Iteratively builds the shortest path tree from the source.
  - **Optimality principle**: If the shortest path from $u$ to $v$ goes through $w$, then the subpath from $w$ to $v$ must also be the shortest path from $w$ to $v$.
- **Distance Vector Routing**:
  - Each node maintains a vector of costs to all destinations.
  - Nodes periodically exchange distance vectors with neighbors.
  - **Bellman-Ford equation**: $D_x(y) = \min_v \{c(x, v) + D_v(y)\}$ for each neighbor $v$.
  - **Count-to-infinity problem**: Slow convergence; routing loops can form.
- **Link State Routing (OSPF)**:
  - Each node floods link-state information to all other nodes.
  - Each node builds a complete graph and runs Dijkstra's algorithm locally.
  - Faster convergence, no count-to-infinity.

### Method: Distance Vector Routing Table
1. Node $D$ receives distance vectors from neighbors $N_1, N_2, \ldots$.
2. For each destination, compute: $\text{cost} = \text{cost to neighbor} + \text{neighbor's cost to destination}$.
3. Choose the minimum across all neighbors.
4. Ties broken alphabetically (by neighbor name).
5. Routing table entry: destination, cost, outgoing line (neighbor).

### WARNING
- In distance vector routing, always add the cost to reach the neighbor, not just use the neighbor's reported cost.
- Dijkstra's algorithm finds shortest paths from source to all nodes. Distance vector computes minimum cost via each neighbor.

### Key Concepts — Chord DHT (Distributed Hash Table)
- Nodes arranged in a ring with identifiers from $0$ to $2^m - 1$.
- Each node maintains a **finger table** with $m$ entries.
- Finger entry $i$: successor of $(node + 2^i) \bmod 2^m$.
- **Key lookup**: To find key $k$, the current node forwards the request to the closest preceding finger (the finger whose value is the largest that still precedes $k$).

---

## Lecture 9: Transport Layer — Services, UDP, TCP Basics

### Key Concepts
- **Transport Layer Services**:
  - **Multiplexing/demultiplexing**: Deliver data to the correct application (identified by port number).
  - **Reliable data transfer**: Ensure all data arrive in order (TCP).
  - **Flow control**: Prevent sender from overwhelming receiver.
  - **Congestion control**: Prevent sender from overwhelming the network.
  - **Connection management**: Set up and tear down connections.

### UDP (User Datagram Protocol)
- **Connectionless**, unreliable, no flow/congestion control.
- **Header** (8 bytes): Source port (16), Destination port (16), Length (16), Checksum (16).
- **Checksum is optional** in IPv4 (but mandatory in IPv6). If used, a zero checksum means no checksum.
- Used for real-time applications (voice, video) where late data is worse than bad data.
- **QUIC**: Quick UDP Internet Connections. Multiple independent streams over UDP to solve TCP's head-of-line blocking.

### TCP (Transmission Control Protocol)
- **Connection-oriented**, reliable, in-order delivery, flow control, congestion control.
- **Segment header** (minimum 20 bytes): Source port (16), Destination port (16), Sequence number (32), Acknowledgment number (32), Data offset (4), Flags (6: URG, ACK, PSH, RST, SYN, FIN), Window (16), Checksum (16), Urgent pointer (16), Options (variable).
- **Three-way handshake**:
  1. Client $\to$ Server: SYN (seq = $x$)
  2. Server $\to$ Client: SYN-ACK (seq = $y$, ACK = $x + 1$)
  3. Client $\to$ Server: ACK (seq = $x + 1$, ACK = $y + 1$)

### TCP Sequence Numbers
- **SYN consumes 1 sequence number**. **FIN consumes 1 sequence number**. **ACK does NOT consume a sequence number**.
- Sequence number of a data segment = previous ACK number + 1.
- Sequence number of the next segment = current sequence number + payload size.

### Method: Compute TCP Sequence Numbers
1. Client's initial sequence number: $ISN_{client}$.
2. After SYN: client's next seq = $ISN_{client} + 1$.
3. Server sends SYN-ACK with $ISN_{server}$, ACK = $ISN_{client} + 1$.
4. Client sends ACK with seq = $ISN_{client} + 1$, ACK = $ISN_{server} + 1$.
5. Data segments: each consumes payload bytes in the sequence number space.
6. Example: Client ISN = 101, sends segments of 12, 34, 56 bytes. Fourth segment seq = $101 + 1 + 12 + 34 + 56 = 204$.

### WARNING
- The SYN and FIN flags each consume one sequence number, even though they carry no data.
- ACK flags do NOT advance the sequence number.

### Key Concepts — TCP Connection Release
- **Four-way handshake**:
  1. A sends FIN (seq = $x$).
  2. B sends ACK (seq = $y$, ACK = $x + 1$).
  3. B sends FIN (seq = $y$).
  4. A sends ACK (seq = $x + 1$, ACK = $y + 1$).

---

## Lecture 10: Transport Layer — Sliding Window, Flow Control, Congestion Control

### Key Concepts — TCP Sliding Window
- TCP uses a **sliding window** for flow control.
- The **receive window** (advertised in ACKs) tells the sender how much buffer space the receiver has.
- **RTO (Retransmission Timeout)**: Timer set for each unacknowledged segment. If it expires, segment is retransmitted.
- **Duplicate ACKs**: Can indicate missing data (triggered by out-of-order arrivals).
- **Selective ACK (SACK)**: Allows receiver to tell sender which specific segments have been received.

### Key Concepts — Flow Control
- Receiver advertises its buffer capacity in the window field of ACKs.
- Sender must not send more data than the advertised window.
- **Zero window**: Receiver's buffer is full; sender stops.
- **Window of 1 byte**: Receiver advertises 1-byte windows to ensure the sender processes each byte before sending more.

### Key Concepts — Congestion Control
- **Congestion**: Too many packets in the network, causing losses and delays.
- **TCP uses AIMD (Additive Increase, Multiplicative Decrease)**:
  - **Slow start**: Exponentially increase congestion window ($cwnd$) — double every RTT until $ssthresh$.
  - **Congestion avoidance**: Linearly increase $cwnd$ by 1 MSS per RTT.
  - **Fast retransmit**: On 3 duplicate ACKs, retransmit the missing segment without waiting for timeout.
  - **Fast recovery**: Set $ssthresh = cwnd / 2$, then continue congestion avoidance (don't restart slow start).
  - **Timeout**: Set $ssthresh = cwnd / 2$, then restart slow start with $cwnd = 1$ MSS.

### TCP Congestion Control Phases
| Phase | Action | Window behavior |
|---|---|---|
| Slow start | 3 dup ACKs | $cwnd = 1$ MSS, exponential growth |
| Congestion avoidance | Normal | Linear growth (+1 MSS per RTT) |
| Fast retransmit | 3 dup ACKs | $ssthresh = cwnd / 2$, continue CA |
| Timeout | Timeout | $ssthresh = cwnd / 2$, restart SS |

### Other Congestion Control Techniques
- **RED (Random Early Detection)**: Routers intentionally drop packets probabilistically before queue is full, signaling congestion to TCP.
- **Traffic throttling**: Routers signal congestion to end hosts (e.g., ICMP source quench).
- **Network provisioning**: Adding bandwidth/paths/routers to handle load.
- **ECN (Explicit Congestion Notification)**: Routers mark packets (instead of dropping) to signal congestion. End hosts then reduce their sending rate.

### WARNING
- Stop-and-wait is a **flow control** method (between sender and receiver on a direct link), not a congestion control method (which addresses network-wide issues).
- TCP congestion control is end-to-end; routers may assist with ECN or RED.

---

## Lecture 11: Application Layer — DNS, Email, HTTP

### Key Concepts — DNS (Domain Name System)
- **Purpose**: Maps domain names to IP addresses. Hierarchical, distributed database.
- **Hierarchy**: Root servers $\to$ TLD (.com, .org, .nl) $\to$ Authoritative servers for each domain.
- **DNS Query Process**:
  1. Client sends query to local DNS server (recursive query).
  2. Local DNS server performs iterative queries to root, TLD, and authoritative servers.
  3. Returns the IP address to the client.
- **DNS Records**: A (IP address), AAAA (IPv6), CNAME (canonical name), MX (mail exchanger), NS (name server), PTR (reverse lookup).
- **CDN integration**: DNS can return different IP addresses based on user location, enabling CDN load distribution.

### Key Concepts — Email
- **SMTP (Simple Mail Transfer Protocol)**: Sends mail from sender to recipient's mail server. Uses port 25. Store-and-forward.
- **POP3 (Post Office Protocol)**: Retrieves mail from server to client. Deletes from server after download.
- **IMAP (Internet Message Access Protocol)**: Retrieves mail from server. Mail stays on server; client syncs with server state.
- **Email flow**: Sender UA $\xrightarrow{\text{SMTP}}$ Sender MTA $\xrightarrow{\text{SMTP}}$ Recipient MTA $\xrightarrow{\text{POP3/IMAP}}$ Recipient UA.

### Key Concepts — HTTP (Hypertext Transfer Protocol)
- **Stateless**: Each request/response is independent. Cookies/sessions maintain state.
- **HTTP/1.0**: Non-persistent. One TCP connection per object.
- **HTTP/1.1**: Persistent connections. Multiple objects over one connection. Pipelining possible but rarely used.
- **HTTP methods**: GET (retrieve), POST (submit data), PUT (upload), DELETE (remove), HEAD (headers only).
- **Status codes**: 200 (OK), 301/302 (redirect), 404 (not found), 500 (server error).
- **Headers**: Host, User-Agent, Accept, Content-Type, Cookie, Location, etc.
- **HTTPS**: HTTP over TLS/SSL for encryption.

### Key Concepts — FTP (File Transfer Protocol)
- **Two connections**: Control (port 21) for commands, Data (port 20) for file transfer.
- **Active mode**: Server initiates data connection to client.
- **Passive mode**: Client initiates data connection to server (works through NAT/firewalls).

---

## Lecture 12: Application Layer — Streaming, CDN, P2P, DHCP, NAT, Tor

### Key Concepts — Streaming Audio/Video
- **Streaming stored media**: Content pre-recorded, streamed progressively or via adaptive bitrate.
- **Real-time streaming**: Live content, low latency. Uses RTP (Real-time Transport Protocol) over UDP.
- **Adaptive bitrate**: Client adjusts quality based on available bandwidth.

### Key Concepts — Content Delivery Networks (CDN)
- **Purpose**: Distribute content to servers close to users, reducing latency and server load.
- **How**: DNS returns the IP of the nearest CDN server based on the user's location.
- **Web proxies**: Cache frequently accessed content. Transparent (user unaware) vs. non-transparent (user configured).

### Key Concepts — Peer-to-Peer (P2P)
- **Architecture**: No central server; peers act as both clients and servers.
- **Benefits**: Scalability (more users = more resources), no single point of failure.
- **Overlay network**: Logical connections between peers, running over the physical Internet.
- **Chord DHT**: Structured P2P overlay using consistent hashing. Each node responsible for a range of keys.

### Key Concepts — DHCP (Dynamic Host Configuration Protocol)
- **Purpose**: Automatically assign IP addresses and network configuration to devices.
- **Process**:
  1. Client sends DHCPDISCOVER (broadcast).
  2. Server responds with DHCPOFFER (IP address, gateway, DNS, etc.).
  3. Client requests with DHCPREQUEST.
  4. Server confirms with DHCPACK.
- **Information gathered**: IP address, gateway, DNS server, time server, etc.
- **Information provided by client**: MAC address (identifier).

### Key Concepts — NAT (Network Address Translation)
- **Purpose**: Allow multiple devices with private IP addresses to share a single public IP.
- **How**: Router replaces source IP and port in outgoing packets, maintains a mapping table.
- **Internal vs. external**: Internal IP/port (private, e.g., 192.168.1.x) $\leftrightarrow$ External IP/port (public).
- **Port mapping**: Multiple internal devices map to different ports on the same external IP.

### Key Concepts — Tor (The Onion Router)
- **Purpose**: Anonymous communication through multiple relays.
- **Process**: Message is encrypted with the key of every relay on the path, starting with the **last relay** (reverse order). Each relay decrypts one layer (hence "onion routing") and forwards to the next.
- **Guard node**: First relay in the circuit. An attacker controlling the guard knows the client's identity and traffic timing/volume, but **not** the content or final destination (since traffic is still encrypted for subsequent relays).

---

## Lecture 13: Security Fundamentals, Symmetric Encryption

### Key Concepts — Security Goals (CIA Triad)
- **Confidentiality**: Only authorized parties can access information.
- **Integrity**: Ensure data/services have not been altered. Users can verify they have the correct information.
- **Availability**: Ensure information and services are available when needed.

### Key Concepts — Other Security Properties
- **Authentication**: Verifying the identity of a party.
- **Access Control**: Ensure only authorized parties can use the network.
- **Non-repudiation**: A party cannot deny having performed an action (e.g., sent a message).
- **Goals of secure wireless communication**: Confidentiality, integrity, access control. Non-repudiation is NOT a goal of wireless security.

### Key Concepts — Symmetric-Key Encryption
- Same key used for encryption and decryption.
- **DES (Data Encryption Standard)**: 56-bit key, 64-bit blocks. Now considered insecure.
- **AES (Advanced Encryption Standard)**: 128/192/256-bit keys, 128-bit blocks. Current standard.
- **S-box (Substitution box)**: Non-linear substitution component. Maps input bits to output bits in a non-linear way. Provides confusion.
- **P-box (Permutation box)**: Rearranges bit positions. Provides diffusion.

### Cipher Modes
- **ECB (Electronic Codebook)**: Each block encrypted independently. Same plaintext block $\to$ same ciphertext block (not secure for patterns).
- **CBC (Cipher Block Chaining)**: Each plaintext block is XORed with the previous ciphertext block before encryption. First block XORed with IV (Initial Vector).
  - Encryption: $C_i = E_K(P_i \oplus C_{i-1})$ where $C_0 = IV$.
  - Decryption: $P_i = D_K(C_i) \oplus C_{i-1}$.
  - **Order matters for decryption**: XOR with previous ciphertext first, then apply the inverse permutation/decryption.

### Method: CBC Encryption
1. Split plaintext into blocks.
2. XOR first block with IV.
3. Apply encryption (S-box or cipher) to the result.
4. XOR second block with first ciphertext block.
5. Apply encryption. Continue for all blocks.

### WARNING
- In CBC decryption: **decrypt (apply inverse cipher) first, then XOR with previous ciphertext**. The wrong order (XOR then decrypt) gives incorrect results.
- ECB mode reveals patterns in the plaintext. Always use CBC or another chaining mode.

---

## Lecture 14: Security — Asymmetric Encryption, Digital Signatures, TLS

### Key Concepts — RSA (Public-Key Cryptography)
- **Key generation**: Choose two primes $p$ and $q$. Compute $n = p \times q$, $\phi(n) = (p-1)(q-1)$. Choose $e$ such that $\gcd(e, \phi(n)) = 1$. Compute $d = e^{-1} \bmod \phi(n)$.
  - Public key: $(e, n)$. Private key: $(d, n)$.
- **Encryption**: $c = m^e \bmod n$.
- **Decryption**: $m = c^d \bmod n$.
- **Example**: $p=3$, $q=11$, $n=33$, $\phi(n)=20$, $e=7$, $d=3$. Ciphertext $c=14$: $m = 14^3 \bmod 33 = 2744 \bmod 33 = 5$.

### Key Concepts — Digital Signatures
- **Symmetric-key signatures**: Shared secret key between sender and receiver. Both can create/verify signatures (no non-repudiation).
- **Public-key signatures**: Sender signs with private key, receiver verifies with public key. Provides authentication and non-repudiation.
- **Message digests (hashes)**: Hash the message first, then sign the hash (more efficient for long messages).
- **Birthday attack**: Finding a collision in a hash function requires approximately $2^{n/2}$ attempts for an $n$-bit hash.

### Key Concepts — Key Management
- **PGP (Pretty Good Privacy)**: Hybrid approach. Hash message, sign with sender's private key, then encrypt with a random symmetric key, which is encrypted with receiver's public key.
- **Diffie-Hellman**: Key exchange protocol (not encryption). Two parties establish a shared secret over an insecure channel.
- **PKI (Public Key Infrastructure)**: Certificate authorities verify public key ownership via digital certificates.

### Key Concepts — TLS (Transport Layer Security)
- Provides encryption, authentication, and integrity for application-layer communication.
- HTTPS = HTTP over TLS.
- TLS handshake: authenticate server (via certificate), negotiate cipher suite, establish shared symmetric key.

---

## Lecture 15: Additional Security Topics, Review

### Key Concepts — WEP (Wireless Encryption)
- **WEP**: 64-bit key with 24-bit initialization vector (IV).
- **Problem**: 5 ASCII characters provide only ~40 bits of key material, but don't use the full 256 possibilities per byte. Limited key space makes brute-force attacks feasible.
- **Security goals**: Confidentiality, integrity, access control. Non-repudiation is not a goal.

### Key Concepts — Blockchain
- Distributed ledger where each block contains a hash of the previous block.
- **Consensus**: Proof-of-work (mining), proof-of-stake.
- **Decentralization**: No single point of failure; tamper-resistant.
- **Do you need a blockchain?**: Usually not needed if a centralized database suffices. Blockchain adds value only when trust is distributed among untrusted parties.

### Key Concepts — IPv6 Address Types
- **Unicast**: One-to-one.
- **Multicast**: One-to-many. Class D addresses in IPv4 (224.0.0.0/4), prefix 255.0.0.0/112.
- **Anycast**: One-to-nearest. Same address assigned to multiple nodes; delivery to the nearest.

### Key Concepts — SDN (Software-Defined Networking)
- **Control plane**: Logically centralized software controller.
- **Data plane**: Programmable hardware (switches) that forwards packets based on flow tables.
- **Separation**: Control logic is separated from packet forwarding, enabling centralized network management.

### Key Concepts — MPLS (Multi-Protocol Label Switching)
- Packets wrapped in an MPLS header with a 20-bit label.
- Routers forward based on labels (label switching), not IP addresses.
- Used within ISP networks for traffic engineering and QoS.

---

## Quick Reference: When to Use What

| Problem Type | Method / Answer |
|---|---|
| OSI layer ordering (low to high) | Physical, Data Link, Network, Transport, Session, Presentation, Application |
| OSI data units | Bit, Frame, Packet, Segment, Message |
| Parity bit error detection | Even parity: check if total number of 1s is even |
| CRC computation | Append $r$ zeros, XOR divide by generator, remainder = CRC |
| CRC error detection | XOR divide received message by $G$; remainder 0 = no error |
| Hamming code length | Find smallest $r$ with $2^r \geq m + r + 1$; total length = $m + r$ |
| Hamming code placement | Parity bits at positions $1, 2, 4, 8, \ldots$ |
| Bit stuffing rule | After $n$ consecutive 1s (where flag has $n+1$ ones), insert 0 |
| Stop-and-wait | One frame at a time; 1-bit sequence numbers; low throughput |
| Go-Back-N | Retransmit all from lost frame; seq space $\geq k+1$ |
| Selective Repeat | Retransmit only lost frame; seq space $\geq 2k$; receiver buffers |
| ALOHA max utilization | Pure: 18%, Slotted: 37% |
| Binary exponential backoff | After $n$ collisions, random from $[0, 2^n - 1]$ slots |
| Ethernet minimum frame | Ensures collision detection before transmission completes |
| IPv4 vs IPv6 | 32-bit vs 128-bit; IPv6: no fragmentation at routers, no header checksum |
| CIDR notation | $A.B.C.D/n$; $n$ network bits; number of addresses = $2^{32-n}$ |
| Longest prefix match | Use the most specific (longest) matching prefix |
| NAT function | Maps internal IP+port to external IP+port via a translation table |
| Distance vector | $D_x(y) = \min_v \{c(x,v) + D_v(y)\}$ |
| Shortest path | Dijkstra's algorithm; optimality principle |
| Chord finger table | Entry $i$: successor of $(node + 2^i) \bmod 2^m$ |
| TCP sequence number | Next seq = current seq + payload size; SYN/FIN consume 1 byte |
| TCP three-way handshake | SYN $\to$ SYN-ACK $\to$ ACK |
| ACK flag | Does NOT consume a sequence number |
| TCP congestion control | Slow start (exponential) $\to$ congestion avoidance (linear) |
| Fast retransmit | Triggered by 3 duplicate ACKs; set ssthresh = cwnd/2 |
| Timeout | Set ssthresh = cwnd/2; restart slow start with cwnd = 1 |
| DNS resolution | Client $\to$ local DNS (recursive) $\to$ root $\to$ TLD $\to$ authoritative |
| Email protocols | SMTP = sending; POP3 = retrieve/delete; IMAP = retrieve/sync |
| HTTP methods | GET, POST, PUT, DELETE; status codes 2xx, 3xx, 4xx, 5xx |
| CBC encryption | $C_i = E_K(P_i \oplus C_{i-1})$, $C_0 = IV$ |
| CBC decryption | $P_i = D_K(C_i) \oplus C_{i-1}$ (decrypt first, then XOR) |
| RSA decryption | $m = c^d \bmod n$ |
| RSA parameters | $n = p \times q$, $\phi(n) = (p-1)(q-1)$, $d = e^{-1} \bmod \phi(n)$ |
| Tor encryption | Encrypt with each relay's key, starting from the last relay |
| Goodput vs Throughput | Goodput excludes headers/trailers; Throughput includes them |
| ECN | Routers mark packets; hosts reduce sending rate |
| RED | Routers drop packets probabilistically to signal congestion |