Cheatsheet Computer Networks - Computer Networks - Computer Science Engineering

1. OSI and TCP/IP Models

1.1 OSI Model Layers

1.2 TCP/IP Model

2. Physical Layer

2.1 Transmission Media

2.2 Signal Encoding

• NRZ (Non-Return to Zero): Simple; no clock synchronization
• Manchester: Self-clocking; transition at bit center; used in Ethernet (10 Mbps)
• Differential Manchester: Transition at start for 0; used in Token Ring
• 4B/5B: Maps 4 data bits to 5 code bits; used in Fast Ethernet

2.3 Multiplexing

2.4 Switching Techniques

• Circuit Switching: Dedicated path; connection-oriented; predictable performance; e.g., PSTN
• Packet Switching: Store-and-forward; connectionless or connection-oriented; efficient bandwidth use
• Message Switching: Entire message stored then forwarded; no real-time; store-and-forward delays. (Message switching is a historical concept and not used in modern computer networks; included only for conceptual understanding.)

3. Data Link Layer

3.1 Framing Methods

• Character Count: First field indicates frame length; error-prone
• Flag Bytes with Byte Stuffing: Start/end flags (e.g., 0x7E); ESC character for stuffing
• Flag Bits with Bit Stuffing: Start/end flag (01111110); insert 0 after five consecutive 1s
• Physical Layer Coding Violations: Use invalid signals to delimit frames

3.2 Error Detection and Correction

3.3 Flow Control Protocols

3.3.1 Stop-and-Wait

• Sender waits for ACK before sending next frame
• Efficiency: η = 1/(1 + 2a) where a = Tp/Tt
• Simple but inefficient for high bandwidth-delay product

3.3.2 Sliding Window

• Go-Back-N: Sender window size N; receiver window size 1; retransmit all frames from error
• Selective Repeat: Sender and receiver window size N; retransmit only erroneous frames
• Efficiency: η = N/(1 + 2a) for Go-Back-N when N ≥ 1 + 2a
  This efficiency expression assumes an error-free channel and full window utilization.
  
• Window size: N ≤ 2^{m - 1} for Go-Back-N; N ≤ 2^(m-1) for Selective Repeat (m = sequence number bits)

3.4 MAC Sublayer Protocols

3.4.1 ALOHA

• Pure ALOHA: Transmit anytime; max throughput = 18.4% at G = 0.5
• Slotted ALOHA: Synchronize to time slots; max throughput = 36.8% at G = 1
• Throughput S = G × e^(-2G) for Pure ALOHA; S = G × e^(-G) for Slotted ALOHA

3.4.2 CSMA Protocols

• 1-persistent: Sense channel; if idle transmit immediately; if busy wait and transmit when idle
• Non-persistent: Sense channel; if idle transmit; if busy wait random time then sense again
• p-persistent: Sense channel; if idle transmit with probability p; used in slotted channels
• CSMA/CD: Collision detection; min frame size = 2 × Tp × bandwidth; CSMA/CD applies only to half-duplex shared Ethernet and is not used in modern switched full-duplex Ethernet.
• CSMA/CA: Collision avoidance; RTS/CTS; used in WiFi (802.11)

3.4.3 Ethernet (IEEE 802.3)

• Frame format: Preamble (7B) + SFD (1B) + DA (6B) + SA (6B) + Type/Length (2B) + Data (46-1500B) + FCS (4B)
• Min frame size: 64 bytes (including header); max: 1518 bytes. With IEEE 802.1Q VLAN tagging, maximum Ethernet frame size becomes 1522 bytes.
• 10Base5: Thick coax, 500m; 10Base2: Thin coax, 185m; 10BaseT: UTP, 100m
• Fast Ethernet: 100 Mbps; Gigabit Ethernet: 1000 Mbps
• Binary exponential backoff: After nth collision, wait random time from {0, 1, ..., 2^min(n,10) - 1} slot times

3.4.4 Token Ring (IEEE 802.5)

• Token passing; deterministic access; no collisions
• Token format: SD + AC + ED; frame format adds FC, DA, SA, Data, FCS fields
• Priority mechanism with reservation bits

3.5 Bridges and Switches

• Transparent Bridge: Learning bridge; builds forwarding table; backward learning
• Spanning Tree Protocol (STP): Prevents loops; root bridge selection; BPDU messages
• Switch: Multi-port bridge; operates at Layer 2; MAC address-based forwarding
• Store-and-forward vs Cut-through switching

4. Network Layer

4.1 IPv4

4.1.1 IPv4 Header

• Version (4 bits), IHL (4 bits), ToS (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), Options (variable)
• Header length: 20-60 bytes; IHL in 4-byte units

4.1.2 IP Addressing

4.1.3 Special IP Addresses

• Loopback: 127.0.0.0/8 (127.0.0.1)
• Private: 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16
• APIPA: 169.254.0.0/16 (link-local)
• Broadcast: 255.255.255.255 (limited), x.x.x.255 (directed)
• Network address: Host bits all 0; Broadcast: Host bits all 1

4.1.4 Subnetting

• Number of subnets: 2ⁿ where n = borrowed bits
• Hosts per subnet: 2^{h - 2} where h = host bits
• CIDR notation: x.x.x.x/prefix-length
• Subnet mask calculation: Convert prefix length to 32-bit mask

4.2 IPv6

• 128-bit address; 8 groups of 4 hexadecimal digits
• Header: Version (4), Traffic Class (8), Flow Label (20), Payload Length (16), Next Header (8), Hop Limit (8), Source (128), Destination (128)
• Fixed header size: 40 bytes; extension headers for options
• No checksum, no fragmentation by routers
• Loopback: ::1; Unspecified: ::; Link-local: FE80::/10
• Unicast, Multicast, Anycast (no broadcast)

4.3 ICMP

4.4 ARP and RARP

• ARP: Resolves IP to MAC address; broadcast ARP request, unicast ARP reply
• ARP cache: Stores IP-MAC mappings; timeout period
• RARP: Resolves MAC to IP; used by diskless stations
• Gratuitous ARP: Sender IP = Target IP; detects duplicate IP, updates ARP caches
• Note : RARP is deprecated and obsolete; replaced by BOOTP and DHCP and rarely relevant in modern networks.

4.5 Routing Algorithms

4.5.1 Distance Vector

• Bellman-Ford algorithm; distribute routing tables to neighbors
• Metric: Hop count or cost
• Count-to-infinity problem; solutions: split horizon, poison reverse, hold-down timer
• RIP: Max 15 hops; updates every 30s; uses UDP port 520

4.5.2 Link State

• Dijkstra's algorithm; flood link state information
• Each router builds complete topology map
• OSPF: Open Shortest Path First; areas for scalability; uses IP protocol 89
• LSA (Link State Advertisement); SPF (Shortest Path First) tree calculation

4.5.3 Path Vector

• BGP: Border Gateway Protocol; inter-AS routing; path vector to avoid loops
• AS_PATH attribute; policy-based routing
• eBGP (external) and iBGP (internal); uses TCP port 179

4.6 IP Fragmentation

• MTU: Maximum Transmission Unit (e.g., Ethernet: 1500 bytes)
• Fragmentation fields: Identification, Flags (DF, MF), Fragment Offset
• Fragment Offset in 8-byte units
• MF = 1 for all fragments except last; DF = 1 prevents fragmentation
• Reassembly at destination only

4.7 NAT

• Network Address Translation; private to public IP mapping
• Static NAT: One-to-one mapping
• Dynamic NAT: Pool of public IPs
• PAT (Port Address Translation): Overloading; maps private IP:port to public IP:port
• Breaks end-to-end connectivity; issues with some protocols (FTP, SIP)

5. Transport Layer

5.1 TCP

5.1.1 TCP Header

• Source Port (16), Destination Port (16), Sequence Number (32), Acknowledgment Number (32)
• Header Length (4), Reserved (6), Flags (6), Window Size (16)
• Checksum (16), Urgent Pointer (16), Options (variable)
• Flags: URG, ACK, PSH, RST, SYN, FIN
• Header size: 20-60 bytes

5.1.2 TCP Connection Management

• Three-way handshake: SYN → SYN-ACK → ACK
• Connection termination: FIN → ACK, FIN → ACK (four-way handshake)
• TIME_WAIT state: 2 × MSL (Maximum Segment Lifetime)
• States: CLOSED, LISTEN, SYN_SENT, SYN_RCVD, ESTABLISHED, FIN_WAIT_1, FIN_WAIT_2, CLOSE_WAIT, LAST_ACK, TIME_WAIT

5.1.3 TCP Flow Control

• Sliding window mechanism; receiver advertises window size
• Window size in header indicates available buffer space
• Zero window: Receiver buffer full; sender stops transmitting
• Silly window syndrome: Small segments; avoided by Nagle's algorithm and delayed ACK

5.1.4 TCP Congestion Control

• Slow Start: cwnd starts at 1 MSS; doubles each RTT until threshold. 
  Note: For GATE numerical problems, initial congestion window is assumed as 1 MSS unless explicitly stated otherwise.
• Congestion Avoidance: Linear increase after threshold; cwnd += 1/cwnd per ACK
• Fast Retransmit: Retransmit on 3 duplicate ACKs
• Fast Recovery: After fast retransmit, set threshold = cwnd/2; cwnd = threshold + 3
• Tahoe: On timeout, threshold = cwnd/2, cwnd = 1
• Reno: Fast recovery after 3 dup ACKs; timeout same as Tahoe

5.1.5 TCP Timers

• Retransmission Timer: RTO calculated using RTT estimation; exponential backoff
• Persistence Timer: Probes zero window
• Keep-alive Timer: Detects dead connections
• TIME_WAIT Timer: 2MSL wait before closing

5.2 UDP

• Header: Source Port (16), Destination Port (16), Length (16), Checksum (16)
• Header size: 8 bytes
• Connectionless; no reliability, flow control, or congestion control
• Used for: DNS, DHCP, TFTP, SNMP, RIP, streaming media, VoIP
• Lower overhead; suitable for real-time applications

5.3 Port Numbers

• Well-known ports: 0-1023; Registered: 1024-49151; Dynamic: 49152-65535

6. Application Layer

6.1 DNS

• Hierarchical distributed database; resolves domain names to IP addresses
• Root servers (13 root server clusters); TLD servers; authoritative servers
• Iterative vs Recursive queries
• Record types: A (IPv4), AAAA (IPv6), CNAME (alias), MX (mail), NS (name server), PTR (reverse), SOA (start of authority)
• Uses UDP port 53 (queries); TCP port 53 (zone transfers, large responses)

6.2 HTTP

• Stateless protocol; request-response model
• Methods: GET, POST, PUT, DELETE, HEAD, OPTIONS, PATCH
• Status codes: 1xx (informational), 2xx (success), 3xx (redirection), 4xx (client error), 5xx (server error)
• Common codes: 200 OK, 301 Moved Permanently, 302 Found, 304 Not Modified, 400 Bad Request, 401 Unauthorized, 403 Forbidden, 404 Not Found, 500 Internal Server Error, 503 Service Unavailable
• HTTP/1.0: Non-persistent; HTTP/1.1: Persistent connections, pipelining; HTTP/2: Multiplexing, server push ; HTTP/2 runs over TCP, while HTTP/3 runs over QUIC (UDP).
• Cookies: Maintain state; Set-Cookie header

6.3 Email Protocols

6.4 FTP

• Control connection: TCP port 21 (persistent)
• Data connection: TCP port 20 (non-persistent)
  Port 20 is used only in active FTP mode; passive FTP uses dynamically allocated server ports.
• Active mode: Server initiates data connection to client
• Passive mode: Client initiates data connection to server
• Stateful protocol; maintains user state

6.5 DHCP

• Dynamic Host Configuration Protocol; automatic IP address assignment
• DORA process: Discover (broadcast), Offer (unicast/broadcast), Request (broadcast), Acknowledge (unicast/broadcast)
• Lease time; renewal at 50% and 87.5% of lease
• Provides: IP address, subnet mask, default gateway, DNS server
• Uses UDP ports 67 (server) and 68 (client)

6.6 SNMP

• Simple Network Management Protocol; network monitoring and management
• Manager-agent architecture; MIB (Management Information Base)
• Operations: GET, GET-NEXT, GET-BULK, SET, TRAP (notification)
• Uses UDP port 161 (agent), 162 (trap)
• Versions: SNMPv1, SNMPv2c, SNMPv3 (security features)

7. Network Security

7.1 Cryptography Basics

7.2 Digital Signatures

• Authentication, integrity, non-repudiation
• Sender signs with private key; receiver verifies with public key
• Sign hash of message rather than entire message for efficiency

7.3 SSL/TLS

• Secure Sockets Layer / Transport Layer Security
• Operates between application and transport layers
• Handshake: Client Hello, Server Hello, Certificate exchange, Key exchange, Cipher spec, Finished
• Uses symmetric encryption for data transfer after asymmetric key exchange
• HTTPS uses TLS over TCP port 443

7.4 IPsec

• IP Security; network layer security
• Modes: Transport (end-to-end), Tunnel (gateway-to-gateway)
• Protocols: AH (Authentication Header), ESP (Encapsulating Security Payload)
• AH: Authentication and integrity; no encryption
• ESP: Authentication, integrity, confidentiality
• IKE (Internet Key Exchange) for key management

7.5 Firewalls

• Packet Filter: Layer 3-4; based on IP, port, protocol
• Stateful Inspection: Tracks connection state; examines packets in context
• Application Gateway (Proxy): Layer 7; deep packet inspection
• DMZ: Demilitarized Zone; isolated network segment for public servers

8. Performance Metrics

8.1 Key Formulas

8.2 Queuing Theory

• Little's Law: N = λ × T (N: avg number, λ: arrival rate, T: avg time in system)
• M/M/1 Queue: Average delay = 1/(μ - λ) where μ = service rate, λ = arrival rate
• Utilization ρ = λ/μ; system is stable if ρ < 1

9. Wireless Networks

9.1 IEEE 802.11 (WiFi)

9.2 WiFi Access Methods

• DCF (Distributed Coordination Function): CSMA/CA; contention-based
• DIFS (DCF Interframe Space): Wait time before transmission
• SIFS (Short Interframe Space): Shortest wait; ACK, CTS
• RTS/CTS: Request to Send / Clear to Send; hidden terminal problem solution
• NAV (Network Allocation Vector): Virtual carrier sensing

9.3 Mobile IP

• Home Agent, Foreign Agent, Care-of Address
• Indirect routing: Packets go via home agent (triangle routing)
• Direct routing: Correspondent directly sends to care-of address
• Registration, tunneling, encapsulation

10. Network Devices

11. Additional Protocols

11.1 VLAN

• Virtual LAN; logical segmentation of network
• IEEE 802.1Q: VLAN tagging; 4-byte tag (TPID + TCI)
• VID (VLAN ID): 12 bits; 4094 VLANs possible
• Trunk port: Carries multiple VLANs; Access port: Single VLAN

11.2 PPP

• Point-to-Point Protocol; WAN link; Layer 2
• Components: LCP (Link Control Protocol), NCP (Network Control Protocol), Authentication (PAP, CHAP)
• Frame format: Flag (0x7E), Address, Control, Protocol, Data, FCS, Flag
• Supports multiple network layer protocols

11.3 HDLC

• High-level Data Link Control; bit-oriented; synchronous
• Frame types: I-frame (information), S-frame (supervisory), U-frame (unnumbered)
• Flag: 01111110; bit stuffing for transparency

11.4 VPN

• Virtual Private Network; secure tunnel over public network
• Protocols: PPTP, L2TP, IPsec, SSL/TLS VPN
• Site-to-site VPN vs Remote access VPN

12. Quality of Service (QoS)

12.1 QoS Parameters

• Bandwidth: Data rate available
• Delay: Propagation + Transmission + Queuing + Processing
• Jitter: Variation in delay; critical for real-time applications
• Packet Loss: Percentage of packets lost; retransmission overhead

12.2 QoS Mechanisms

• Traffic Shaping: Regulate data rate; leaky bucket, token bucket
• Traffic Policing: Enforce traffic limits; drop/mark non-conforming packets
• Priority Queuing: High-priority traffic first
• Weighted Fair Queuing (WFQ): Allocate bandwidth proportionally
• DiffServ: Differentiated Services; DSCP field in IP header; PHB (Per-Hop Behavior)
• IntServ: Integrated Services; RSVP (Resource Reservation Protocol); per-flow reservation