Computer Networks Unit 2 - Data Link Layer & Network Layer

📡Chapter 2.1 — Data Link Layer

📡 CHAPTER 2.1 — DATA LINK LAYER MIND MAP

Design Issues → Framing, Error Control, Flow Control, Services to Network Layer

Error Detect/Correct → Parity, Checksum, CRC (detect) | Hamming Code (correct)

Sliding Window → Stop-and-Wait (W=1) → Go-Back-N (Rx W=1) → Selective Repeat (Rx W=N)

MAC → ALOHA (Pure 18.4%, Slotted 36.8%) → CSMA (1-persistent, non-persistent, p-persistent) → CSMA/CD (wired) | CSMA/CA (wireless)

Protocols → HDLC (bit-oriented, bit stuffing) | PPP (byte-oriented, point-to-point)

2.1.1 Introduction to Data Link Layer

📖 Data Link Layer (Layer 2): Takes packets from the Network Layer, wraps them into frames, and delivers them reliably from one node to the next directly connected node over the physical link.

💡 Real-life Analogy:

Think of a courier chain. The Network Layer decides the route Delhi → Mumbai. The Data Link Layer is the local delivery boy who carries the parcel only from one hub to the next hub, checks it is not damaged, and does not overload the next hub.

Main jobs of Data Link Layer

Framing: divides the bit stream into frames
Physical addressing: adds sender and receiver MAC address in the frame header
Error control: detects and corrects damaged or lost frames
Flow control: stops a fast sender from drowning a slow receiver
Access control: decides who uses a shared link (MAC sub-layer)

Sub-layer	Work
LLC (Logical Link Control)	Flow control, error control, interface to Network Layer
MAC (Media Access Control)	Access to shared channel, MAC addressing, frame delimiting

⚠️ Key Point: PDU of Data Link Layer = Frame. It works hop-to-hop, while Transport Layer works end-to-end.

2.1.2 Design Issues of Data Link Layer

📖 Data Link Layer: Layer 2 of OSI. Provides reliable node-to-node delivery of frames over a physical link using MAC (physical) addresses.

Design Issue	Meaning
Services to Network Layer	Unacknowledged connectionless, acknowledged connectionless, acknowledged connection-oriented
Framing	Splitting bit stream into frames (char count, byte stuffing, bit stuffing)
Error Control	Detect/correct damaged, lost, duplicate frames (ACK, timer, sequence no.)
Flow Control	Stop fast sender from flooding a slow receiver

Framing — Bit Stuffing

💡 Rule: Flag = 01111110. After every five consecutive 1s in data, sender inserts a 0; receiver removes it.
Data: 0111111011111 → Sent: 011111010111110 (zero stuffed after each run of five 1s).

Byte stuffing: Flag byte in data is preceded by an ESC byte. Used in PPP. Bit stuffing is used in HDLC.

2.1.3 Error Detection & Correction

📖 Types of Errors

Single-bit error: only 1 bit is changed

Burst error: 2 or more consecutive bits changed (length = first to last corrupted bit)

Method	Working	Remark
Parity	Add 1 bit so total 1s is even (or odd)	Detects odd-bit errors only; 2D parity detects more
Checksum	Sum data in 1s complement, send complement of sum; receiver sum must be all 1s	Used in IP/TCP/UDP
CRC	Append n zeros (n = generator degree), divide by generator using XOR, remainder = CRC	Detects burst errors; used in Ethernet
Hamming Code	Parity bits at positions 1,2,4,8…; need 2^r ≥ m+r+1	Detects & corrects single-bit error

📐 CRC Example

Data = 1001, Generator = 1011 (x³ + x + 1)
Append 3 zeros → 1001000
XOR division gives remainder 110
Transmitted frame = data + CRC = 1001110
Receiver divides by 1011 → remainder 000 → no error

Hamming: Syndrome (parity check bits read as binary) gives the position of the erroneous bit. Syndrome 0 means no error.

2.1.4 Checksum Step by Step

📖 Checksum: Sender adds all data words, takes the 1s complement of the sum, and sends it with the data. The receiver adds everything again, including the checksum. If the final result (after complement) is all 0s, data is accepted.

Side	Steps
Sender	1) Divide data into equal words (8 bits here) 2) Add all words 3) If carry goes beyond 8 bits, wrap it around (add carry to the result) 4) Complement the sum = checksum 5) Send data + checksum
Receiver	1) Add all received words + checksum 2) Wrap carry 3) Complement. All 0s = no error, otherwise discard the frame

Worked example with 4 frames is in the PYQs tab (Test-2, Q6).

2.1.5 CRC & Hamming Code — Worked Examples

📖 CRC (Cyclic Redundancy Check): Sender divides data (plus appended zeros) by a fixed generator polynomial using XOR (modulo-2) division. The remainder is attached to the data. Receiver divides again; remainder 0 means no error.

Step 1 — Choose generator

Generator 1011 (x³ + x + 1) has 4 bits, so degree n = 3.

Step 2 — Append zeros

Data 1001 + three zeros = 1001000.

Step 3 — XOR division

Divide 1001000 by 1011 (subtract = XOR, no borrow).

Step	Bits taken	XOR with	Result → remainder
1	`1001` first 4 bits	`1011` leading bit 1	0010 → 010
2	`0100` 010 + next bit 0	`0000` leading bit 0	0100 → 100
3	`1000` 100 + next bit 0	`1011` leading bit 1	0011 → 011
4	`0110` 011 + next bit 0	`0000` leading bit 0	0110 → 110

✅ Rule: leading bit 1 → XOR with the generator (1011). Leading bit 0 → XOR with 0000. After the last bit, the remainder 110 is the CRC.

Step 4 — Send

Codeword = data + CRC = 1001110. Receiver divides by 1011 and gets remainder 000, so frame is accepted.

📖 Hamming Code (7,4): Adds parity bits at positions that are powers of 2 (1, 2, 4). Each parity bit checks a fixed group of positions, so the failing checks point to the exact error position.

Parity bit	Checks positions
p1	1, 3, 5, 7
p2	2, 3, 6, 7
p4	4, 5, 6, 7

💡 Hamming Example (even parity)

Data bits d3 d5 d6 d7 = 1 0 1 1
p1 = parity of (d3, d5, d7) = (1, 0, 1) → 0
p2 = parity of (d3, d6, d7) = (1, 1, 1) → 1
p4 = parity of (d5, d6, d7) = (0, 1, 1) → 0
Codeword (position 1 to 7) = 0110011
Bit 6 flips → received 0110001. Re-check: p1 ok, p2 fails, p4 fails
Syndrome (p4 p2 p1) = 110 = 6 → flip bit 6 back to correct

✅ CRC: catches all burst errors up to length n, very reliable, cheap in hardware.

❌ CRC cannot correct errors, only detect. Hamming corrects 1 bit but cost is extra parity bits.

2.1.6 Stop-and-Wait Protocol

📖 Stop-and-Wait: Simplest flow control. Sender sends one frame and waits for its ACK before sending the next.

💡 Analogy: Sending a WhatsApp message and not typing the next one until the other person replies "ok".

Step 1

Sender sends frame 0 and starts a timer.

Step 2

Receiver checks frame, sends ACK.

Step 3

ACK arrives before timeout → send next frame. Timer expires first → resend same frame.

✅ Pros: Very simple, needs only 1 buffer.

❌ Cons: Link is idle while waiting, so long-distance links are badly wasted.

Example: T_t = 1 ms, T_p = 20 ms → a = 20. Efficiency = 1/(1 + 2a) = 1/41 ≈ 2.4%. This is why sliding window is needed.

2.1.7 Sliding Window Protocols

📖 Sliding Window: Sender may transmit multiple frames before ACK arrives. Frames are numbered; window = range of sequence numbers allowed to be outstanding. Improves link utilization over Stop-and-Wait.

Feature	Stop-and-Wait	Go-Back-N	Selective Repeat
Sender window	1	2^m − 1	2^m−1
Receiver window	1	1	2^m−1
On frame loss	Resend that frame	Resend lost frame and all after it	Resend only the lost frame
ACK	Per frame	Cumulative	Individual
Buffering at Rx	None	None (out-of-order discarded)	Needed (out-of-order stored)
Complexity / Efficiency	Low / Lowest	Medium / Medium	High / Best

📐 Sliding Window Formulas

a = T_p / T_t

Stop-and-Wait efficiency η = 1 / (1 + 2a)

Optimal window = 1 + 2a

Efficiency = N / (1 + 2a) when N < 1 + 2a

2.1.8 Go-Back-N Explained Simply

📖 Go-Back-N (GBN): A sliding window protocol where the sender can send several frames without waiting, but the receiver accepts frames only in order. If one frame is lost or damaged, the sender goes back to that frame and resends it and every frame after it.

💡 Real-life analogy: A teacher dictates pages 1, 2, 3, 4 to you. You miss page 2. You cannot write page 3 before page 2, so you ignore pages 3 and 4. The teacher repeats from page 2.

Step	What happens (window size = 4)
1	Sender sends frames 0, 1, 2, 3 one after another (no waiting)
2	Receiver gets 0 and 1, sends ACK 0, ACK 1
3	Frame 2 is lost. Frame 3 arrives but is out of order, so receiver discards it
4	Sender's timer for frame 2 expires (timeout)
5	Sender goes back and resends 2 and 3 (and anything sent after them)

✅ Pros: Simple, receiver needs no buffer (receiver window = 1).

❌ Cons: Wastes bandwidth because good frames are resent. Sender window must be at most 2^m − 1, otherwise old and new frames get confused.

Go-Back-N: F2 is lost, F3 is thrown away, sender goes back and resends F2 and F3.

2.1.9 Selective Repeat Explained Simply

📖 Selective Repeat (SR): Like Go-Back-N the sender sends many frames, but the receiver keeps out-of-order frames in a buffer and the sender resends only the lost frame.

💡 Analogy: You miss page 2 of the dictation but still write pages 3 and 4. You just ask the teacher to repeat page 2 alone.

Step 1

Sender sends F0, F1, F2, F3. F2 is lost.

Step 2

Receiver stores F3 in its buffer and sends a NAK or individual ACK for F3; F2 is missing.

Step 3

Only F2 is resent. Receiver now delivers F2, F3 to the upper layer in order.

	Go-Back-N	Selective Repeat
Resends	Lost frame + all after	Only lost frame
Receiver buffer	Not needed	Needed
Window size limit	2^m − 1	2^m−1
Best for	Reliable links, simple hardware	Noisy / long links

2.1.10 Media Access Control (MAC) Layer

📖 MAC: Sub-layer of Data Link Layer that decides who may transmit on a shared channel and avoids collisions.

Protocol	Vulnerable Time	Throughput S	Max Efficiency
Pure ALOHA	2 × T_fr	G·e^−2G	18.4% (G = 0.5)
Slotted ALOHA	T_fr (time slots)	G·e^−G	36.8% (G = 1)

CSMA — Carrier Sense Multiple Access ("listen before talk")

Persistence	Behaviour
1-persistent	Sense continuously; send immediately when idle (p = 1). High collision chance
Non-persistent	If busy, wait random time and sense again. Fewer collisions, more delay
p-persistent	If idle, send with probability p, else wait one slot (for slotted channels)

	CSMA/CD	CSMA/CA
Used in	Wired Ethernet (802.3)	Wireless LAN (802.11)
Idea	Detect collision while sending, stop, send jam signal, binary exponential backoff	Avoid collision: IFS wait, random backoff, optional RTS/CTS handshake, ACK
Condition	T_t ≥ 2 × T_p (min frame size)	Cannot detect collision in wireless, so avoid it

2.1.11 ALOHA Explained — with Numerical

📖 ALOHA: The oldest random-access protocol. A station sends whenever it has data. If no ACK comes (collision), it waits a random time and resends.

💡 Analogy: Pure ALOHA = people talking in a room without any rule. Slotted ALOHA = everyone may speak only when a bell rings (slot start), so overlaps are fewer.

Pure: a frame collides if any other frame starts within 2 × T_fr, so vulnerable time = 2T_fr
Slotted: collision only when two stations pick the same slot, vulnerable time = T_fr

Throughput S vs load G. Slotted ALOHA peaks at double the height of Pure ALOHA.

📐 Numerical — ALOHA Throughput

Given: T_fr = 1 ms, system generates 500 frames/s
G = 500 × 1 ms = 0.5
Pure ALOHA: S = G·e^−2G = 0.5 × e⁻¹ = 0.184 → 184 frames/s succeed
Slotted ALOHA (G = 1, i.e. 1000 frames/s): S = G·e^−G = e⁻¹ = 0.368 → 368 frames/s succeed

2.1.12 CSMA/CD — How Ethernet Handles Collisions

💡 Analogy: A group discussion: you listen before speaking, and if two people start together both stop, wait a random time, and try again.

Step 1 — Sense

Listen to the channel. If busy, wait.

Step 2 — Transmit

Channel idle → start sending the frame and keep listening.

Step 3 — Collision?

If another signal is detected, stop at once and send a short jam signal so everyone knows.

Step 4 — Backoff

After the n-th collision pick random K from 0 to 2ⁿ − 1 and wait K × slot time (binary exponential backoff). Give up after 16 attempts.

Minimum frame size: Sender must still be sending when the collision signal returns, so T_t ≥ 2T_p. For 10 Mbps Ethernet, 2T_p = 51.2 µs → min frame = 51.2 µs × 10 Mbps = 512 bits = 64 bytes.

⚠️ Why wireless cannot use CD: A wireless node cannot listen while sending, so CSMA/CA avoids collisions instead.

2.1.13 HDLC & PPP

	HDLC	PPP
Full form	High-Level Data Link Control	Point-to-Point Protocol
Type	Bit-oriented (bit stuffing)	Byte-oriented (byte stuffing)
Frame	Flag \| Address \| Control \| Data \| FCS \| Flag	Flag (7E) \| Address (FF) \| Control (03) \| Protocol \| Payload \| FCS \| Flag
Frame types	I (Information), S (Supervisory: ACK/NAK), U (Unnumbered: link setup)	LCP (link setup), NCP (network config), PAP/CHAP (authentication)
Use	Point-to-point & multipoint, modes NRM, ABM	Dial-up, ISP to home, point-to-point only

🌍Chapter 2.2 — Network Layer

🌍 CHAPTER 2.2 — NETWORK LAYER MIND MAP

IP Addressing → IPv4 = 32 bit | Classful A,B,C,D,E | Classless = CIDR a.b.c.d/n

Subnet / Supernet → Subnetting divides one network into many | Supernetting combines many into one

Routing → Optimality principle → Shortest Path (Dijkstra) → Flooding → Distance Vector (Bellman-Ford, RIP) → Link State (OSPF)

Congestion → Open loop (prevention) vs Closed loop (feedback) | Leaky Bucket (smooth) vs Token Bucket (bursty)

2.2.1 IP Addressing

📖 IPv4 Address: 32-bit logical address written in dotted decimal (e.g. 192.168.1.10). Has Network ID + Host ID.

Class	First Bits	Range	Default Mask	Hosts/Network
A	0	1 – 126	255.0.0.0 (/8)	2²⁴ − 2
B	10	128 – 191	255.255.0.0 (/16)	2¹⁶ − 2
C	110	192 – 223	255.255.255.0 (/24)	254
D	1110	224 – 239	—	Multicast
E	1111	240 – 255	—	Reserved / research

⚠️ Special IPv4 Addresses

127.x.x.x = loopback (own machine)

0.0.0.0 = this host / unknown

255.255.255.255 = limited broadcast

Usable hosts = 2^h − 2 (network and broadcast address excluded)

Classless Addressing (CIDR): No fixed classes; address written as a.b.c.d/n (n = prefix length). Avoids address wastage of classful scheme.

A 0…

B 10…

C 110…

First octet 0–255 split by class: A 1–126 · B 128–191 · C 192–223 · D 224–239 (multicast) · E 240–255 (reserved)

2.2.2 MAC Address vs IP Address

💡 Analogy: MAC address is like your name (fixed, tied to you). IP address is like your home address (changes when you move to another city/network).

Point	MAC Address	IP Address
Full form	Media Access Control	Internet Protocol
Layer	Data Link Layer (Layer 2)	Network Layer (Layer 3)
Size	48 bits (6 bytes)	32 bits (IPv4) / 128 bits (IPv6)
Format	Hexadecimal, e.g. `00:1A:2B:3C:4D:5E`	Dotted decimal, e.g. `192.168.1.10`
Assigned by	Manufacturer (burned into NIC card)	Network admin or DHCP server
Changes?	Permanent (physical address)	Changes with network (logical address)
Scope / use	Delivery between two directly connected devices (hop to hop)	End-to-end delivery across networks (routing)
Device	Switch / Bridge	Router

Remember: MAC changes at every hop, IP stays the same from source to destination.

2.2.3 IPv4 Packet Header

📖 IPv4 Header: Control information added in front of data by the Network Layer. It is 20 bytes minimum and 60 bytes maximum. Routers read it to decide where to send the packet. Each row below is 32 bits.

Version (4)	IHL (4)	Type of Service (8)	Total Length (16)
Identification (16)			Flags (3) \| Fragment Offset (13)
Time To Live (8)		Protocol (8)	Header Checksum (16)
Source IP Address (32)
Destination IP Address (32)
Options + Padding (0 to 40 bytes, optional)

Explanation of each field

Field	Size	Purpose
Version	4 bits	IP version. 4 for IPv4
IHL	4 bits	Header length in 32-bit words (min 5 = 20 bytes, max 15 = 60 bytes)
Type of Service	8 bits	Priority / quality of service (DSCP)
Total Length	16 bits	Header + data in bytes (max 65,535)
Identification	16 bits	Same ID for all fragments of one packet, used to reassemble
Flags	3 bits	Reserved, DF (Don't Fragment), MF (More Fragments)
Fragment Offset	13 bits	Position of this fragment in the original packet
TTL	8 bits	Hop limit; each router subtracts 1; at 0 the packet is dropped (stops endless loops)
Protocol	8 bits	Which upper layer gets the data: 6 = TCP, 17 = UDP, 1 = ICMP
Header Checksum	16 bits	Error check on the header only (recalculated at every router)
Source / Destination IP	32 + 32 bits	Sender and receiver IPv4 addresses
Options + Padding	0–40 bytes	Rarely used extras; padding makes header a multiple of 32 bits

2.2.4 Subnetting & Supernetting

💡 Subnetting Example

Divide 192.168.1.0/24 into 4 subnets
Borrow 2 bits → /26, mask = 255.255.255.192
Each subnet = 64 addresses (62 usable hosts)
Subnets: .0–.63 | .64–.127 | .128–.191 | .192–.255

📐 Subnetting Formulas

Subnets = 2ⁿ (n = borrowed bits)

Hosts per subnet = 2^h − 2 (h = host bits left)

📖 Supernetting

Combines several contiguous small networks into one larger block (reverse of subnetting)

Rule 1: blocks must be contiguous

Rule 2: number of blocks must be a power of 2

Rule 3: first address must be divisible by total block size

Example: 4 class C blocks 200.1.0.0 – 200.1.3.0 → 200.1.0.0/22

.0 – .63

.64 – .127

.128 – .191

.192 – .255

192.168.1.0/24 → 4 subnets of /26, each with 64 addresses (62 usable hosts)

2.2.5 Subnet Calculation — Step by Step

📐 Subnet Calculation — 5 Steps

Find the class from the first octet
Convert the mask to /n (count the 1s)
Subnet address = IP AND mask
Block size = 256 − mask octet
Broadcast = next subnet address − 1

Why subnet? Better use of IP addresses, less broadcast traffic, easier management and security, each department gets its own network.

Full solved example is in the PYQs tab (Test-2, Q7).

2.2.6 Routing Algorithms

📖 Optimality Principle: If router J lies on the optimal path from I to K, then the optimal path from J to K is on the same route. All optimal routes to a destination form a sink tree.

Algorithm	Working	Key Points
Shortest Path	Dijkstra: repeatedly pick unvisited node with least distance, relax neighbours	Needs full topology; basis of Link State
Flooding	Router sends every incoming packet on all lines except the arrival line	Very reliable, no topology needed; duplicates (use hop counter / sequence no.)
Distance Vector	Each router shares its whole table with neighbours only (Bellman-Ford). Used in RIP	Slow convergence, count-to-infinity problem (fix: split horizon, poison reverse)
Link State	Router learns neighbours, builds LSP, floods to all, runs Dijkstra. Used in OSPF	Fast convergence, more memory/CPU, scalable

2.2.7 Distance Vector — Worked Example

📖 Idea (Bellman-Ford): New distance = cost to neighbour + neighbour's distance to destination. Router keeps the minimum.

A —1— B→B —2— C→A wants C

Step	A's table for C	Why
Start	∞	A only knows B (cost 1)
A receives B's vector (B→C = 2)	1 + 2 = 3 via B	Better than ∞, so update
Link A–C (cost 5) added	min(3, 5) = 3 via B	Keep the smaller one

2.2.8 Dijkstra Steps & Count-to-Infinity Problem

Dijkstra Step 1

Set distance of source = 0, all others = ∞. Mark all nodes unvisited.

Step 2

Pick the unvisited node with smallest distance and mark it visited.

Step 3

For each neighbour, if (distance of picked node + link cost) is smaller than its current distance, update it.

Step 4

Repeat steps 2 and 3 until the destination is visited. Trace back parents to get the path.

💡 Count-to-Infinity: Network A — B — C. A reaches C via B (cost 2). The B–C link breaks. B hears from A "I can reach C in 2", so B thinks C = 3 via A. Then A updates to 4 via B, B to 5, and the costs keep rising forever.

✅ Fixes: Split horizon (do not tell a neighbour about routes learned from it), poison reverse (advertise such routes as ∞), and set a maximum hop limit (RIP uses 16 = infinity).

2.2.9 Congestion Control

📖 Congestion: Too many packets in the network → queues fill up, delay rises, packets are dropped, throughput collapses.

Open Loop (Prevention)	Closed Loop (Cure)
Policies applied before congestion (retransmission, window, ACK, discard policy, admission)	Uses feedback after congestion (choke packet, backpressure, ECN)

	Leaky Bucket	Token Bucket
Output	Constant rate always	Bursts allowed (if tokens available)
Idea	Bucket leaks at fixed rate; overflow packets discarded	Tokens added at rate r (capacity C); a packet needs a token to go
Idle host	Credit wasted	Saves tokens for later burst
Use	Smoothing bursty traffic	Flexible traffic shaping

📐 Token Bucket Burst Time: S = C / (M − r) (C = bucket capacity, M = max output rate, r = token rate)

2.2.10 Leaky & Token Bucket — Concept and Numerical

💡 Leaky Bucket: A bucket with a small hole. Water (packets) may pour in at any speed, but it drips out at a fixed rate. If the bucket overflows, extra water is lost.
💡 Token Bucket: Tokens are coins collected over time. To send a packet you spend a coin, so after a quiet period you can send a quick burst.

📐 Numerical — Token Bucket Burst Time

Given: C = 1 MB, r = 2 MB/s, M = 10 MB/s
Formula: S = C / (M − r)
Substitute: S = 1 / (10 − 2) = 1 / 8
Burst time S = 0.125 s
Data sent in burst = M × S = 10 × 0.125 = 1.25 MB (1 MB from bucket + 0.25 MB from new tokens)

2.2.11 Congestion Prevention Policies by Layer

Layer	Policies
Data Link	Retransmission policy, out-of-order caching, acknowledgement policy, flow control
Network	Virtual circuit vs datagram, packet queueing and service, discard policy, routing algorithm, packet lifetime
Transport	Retransmission, out-of-order caching, ACK policy, flow control, timeout determination

⚠️ Exam tip: Remember "prevention = open loop = act before congestion occurs".

⚡Ready for Exam?Sab padh liya? Ab Quick Revision karo — formulas, key points aur exam tips ek jagah!Quick Revision Karo →

⚡Quick Revision — Last Minute Exam Prep!

📌 How to use: Har topic mein pehle Definition, phir Example, phir Diagram hai. Pehle definition yaad karo, example se samjho, diagram se pakka karo.

📝 2025-26 Paper — One-line Recall

1️⃣ Go-Back-NSliding window ARQ. Lost frame → resend it + all after. Rx window = 1.

2️⃣ MAC vs IPMAC: 48-bit, Layer 2, hop-to-hop. IP: 32-bit, Layer 3, end-to-end.

3️⃣ ALOHA vs SlottedVulnerable 2T vs T. Max 18.4% vs 36.8%.

4️⃣ FloodingSend on all lines except incoming. Hop counter / sequence no. stops duplicates.

5️⃣ IPv4 Header20–60 bytes. Version, IHL, ToS, Length, ID, Flags, Offset, TTL, Protocol, Checksum, Src, Dst.

6️⃣ ChecksumAdd words, wrap carry, complement. Receiver total + checksum = all 1s.

7️⃣ SubnettingClass from 1st octet, IP AND mask. 180.25.21.172 /18 → Class B, subnet 180.25.0.0

📡 Chapter 2.1 — Data Link Layer

1. Framing & Bit Stuffing

📖 Definition: Framing splits the bit stream into frames. Bit stuffing inserts a 0 after every five consecutive 1s so data never looks like the flag 01111110.

💡 Example: Data 0111111011111 → sent 011111010111110. Receiver removes the stuffed 0s.

0 1 1 1 1 10 ← stuffed1 01 1 1 1 10 ← stuffed

Data 0111111011111 → after every five 1s a 0 is inserted

2. Error Detection & Correction

📖 Definition: Parity, Checksum and CRC detect errors. Hamming code can also correct a single-bit error.

💡 Example: CRC: data 1001 ÷ generator 1011 → remainder 110 → frame sent = 1001110.

Parity→Checksum→CRC

Hamming = detect + correct 1 bit

Hamming (7,4): positions 1–7. Parity bits (red) sit at positions 1, 2, 4

3. Sliding Window (Stop-and-Wait, GBN, SR)

📖 Definition: Sender can send many frames before an ACK. Window = how many frames may be outstanding.

💡 Example: Go-Back-N: F2 lost, F3 discarded, sender resends F2 and F3.

Stop-and-WaitWindow 1. η = 1/(1+2a). Simple but slow.

Go-Back-NSender 2^m−1, Rx 1. Resends from lost frame.

Selective RepeatBoth 2^m−1. Buffers out-of-order, resends only lost frame.

4. ALOHA

📖 Definition: Random access: send whenever you have data; on collision wait a random time and resend. Slotted ALOHA sends only at slot start.

💡 Example: T_fr = 1 ms, 500 frames/s → G = 0.5 → Pure ALOHA S = 0.184 → 184 frames/s.

Pure peaks at 0.184 (G = 0.5), Slotted at 0.368 (G = 1)

5. CSMA, CSMA/CD, CSMA/CA

📖 Definition: CSMA = listen before sending. CSMA/CD detects collision on wired Ethernet. CSMA/CA avoids collision on wireless.

💡 Example: 10 Mbps Ethernet: 2T_p = 51.2 µs → minimum frame = 512 bits = 64 bytes.

Sense→Send + listen→Collision?→Jam→Backoff→Retry

1-persistentSend as soon as idle.

Non-persistentBusy → wait random, sense again.

p-persistentIdle → send with probability p.

6. HDLC & PPP

📖 Definition: HDLC is a bit-oriented Data Link protocol (frame types I, S, U). PPP is a byte-oriented point-to-point protocol (LCP, NCP, PAP/CHAP).

💡 Example: Dial-up / ISP link uses PPP. HDLC marks frames with flag 01111110.

Flag

Address

Control

Data

FCS

Flag

HDLC frame (bit-oriented, bit stuffing)

Flag 7E

Addr FF

Ctrl 03

Protocol

Payload

FCS

Flag

PPP frame (byte-oriented, byte stuffing)

🌍 Chapter 2.2 — Network Layer

1. IP Addressing & Classes

📖 Definition: IPv4 address is a 32-bit logical address (network ID + host ID) written in dotted decimal. Classless (CIDR) uses a.b.c.d/n.

💡 Example: 180.25.21.172 → first octet 180 is in 128–191 → Class B (default mask /16).

A 0…

B 10…

C 110…

Class A 1–126 · B 128–191 · C 192–223 · D 224–239 (multicast) · E 240–255 (reserved)

2. Subnetting & Supernetting

📖 Definition: Subnetting splits one network into smaller ones. Supernetting joins contiguous networks into a bigger block.

💡 Example: 192.168.1.0/24 → borrow 2 bits → /26 → 4 subnets × 64 addresses (62 hosts). Four class C blocks → /22.

.0–.63

.64–.127

.128–.191

.192–.255

192.168.1.0/24 split into four /26 subnets

📐 Formulas

Subnets = 2ⁿ

Hosts per subnet = 2^h − 2

Subnet address = IP AND mask

3. MAC vs IP Address

📖 Definition: MAC is a physical 48-bit Layer 2 address. IP is a logical 32-bit Layer 3 address.

💡 Example: MAC = your name (fixed). IP = your home address (changes with network).

MAC48-bit hex · Layer 2 · set by manufacturer · hop-to-hop

IP32-bit dotted decimal · Layer 3 · set by admin/DHCP · end-to-end

4. IPv4 Packet Header

📖 Definition: Control information the Network Layer adds in front of data. Size 20 bytes minimum, 60 bytes maximum.

💡 Example: TTL starts at e.g. 64; every router subtracts 1; at 0 the packet is dropped. Protocol 6 = TCP, 17 = UDP.

Version (4)	IHL (4)	Type of Service (8)	Total Length (16)
Identification (16)			Flags (3) \| Fragment Offset (13)
Time To Live (8)		Protocol (8)	Header Checksum (16)
Source IP Address (32)
Destination IP Address (32)
Options + Padding (0 to 40 bytes, optional)

5. Routing (Flooding, Distance Vector, Link State)

📖 Definition: Routing decides the path of a packet. Flooding sends on all lines. Distance Vector shares tables with neighbours. Link State floods link info to everyone and runs Dijkstra.

💡 Example: Distance Vector: A–B cost 1, B–C cost 2 → A learns C = 3 via B. RIP uses DV, OSPF uses Link State.

Share table with neighbours→Bellman-Ford update

Learn own links→Flood LSP to all→Run Dijkstra

6. Congestion Control

📖 Definition: Congestion = too many packets in the network, so delay and loss rise. Leaky and Token bucket shape the traffic.

💡 Example: C = 1 MB, r = 2 MB/s, M = 10 MB/s → burst time S = C/(M−r) = 0.125 s.

Leaky: output always constant. Token: saved tokens let a burst go out.

🧠 Tricks to Remember

CD = Detect (wired Ethernet) | CA = Avoid (wireless)
Slotted ALOHA = double of Pure ALOHA (18.4% → 36.8%)
Class first bits: 0, 10, 110, 1110, 1111 = A, B, C, D, E
DV = tells neighbours everything | LS = tells everyone own links
MAC changes at every hop, IP stays same end-to-end

✅ Last Checklist

Can I solve checksum with 4 frames?
Can I find class, mask and subnet address?
Can I draw the IPv4 header?
Can I compare ALOHA vs Slotted and MAC vs IP?
Do I remember Leaky vs Token bucket?

📄Previous Year Questions

📝 Mid Semester Test-2 (2025-26)

Branch: BE-CSE/IT

Subject: Computer Networks (23CST-302 / 23ITT-302)

Semester: 5 · Time: 1 Hour · Max Marks: 20

Section A: 5 × 2 = 10 marks · Section B: 2 × 5 = 10 marks

Attempt all questions

Section A — 2 Marks Questions (Short Answer)

2M2025-26

Q1. State the meaning of Go-back-n with reference to Data Link Layer. [CO3 | BT1]▼

Answer:

Go-Back-N (GBN) is a sliding window ARQ protocol of the Data Link Layer. The sender transmits up to N frames without waiting for ACK, but the receiver accepts frames only in correct order (receiver window = 1). If a frame is lost or corrupted, the receiver discards it and all later frames, and the sender goes back and retransmits from the lost frame onward.

Example: Sender sends 0,1,2,3. Frame 2 is lost → 3 is discarded → timer of 2 expires → sender resends 2, 3. Sender window = 2^m − 1, ACKs are cumulative.

2M2025-26

Q2. Identify the difference between MAC address and IP address? [CO4 | BT1]▼

Answer:

Point	MAC Address	IP Address
Layer	Data Link (Layer 2)	Network (Layer 3)
Size	48 bits, hexadecimal	32 bits (IPv4), dotted decimal
Type	Physical, permanent, set by manufacturer	Logical, changes with network, set by admin/DHCP
Use	Hop-to-hop delivery in same LAN	End-to-end delivery across networks

Analogy: MAC = person's name, IP = home address.

2M2025-26

Q3. Compare ALOHA with Slotted ALOHA. [CO3 | BT2]▼

Answer:

Point	Pure ALOHA	Slotted ALOHA
Time	Continuous, send any time	Divided into slots, send only at slot start
Synchronization	Not needed	Needed (common clock)
Vulnerable time	2 × T_fr	T_fr
Throughput	S = G·e^−2G	S = G·e^−G
Max efficiency	18.4% at G = 0.5	36.8% at G = 1
Collisions	More	Half of Pure ALOHA
Complexity	Simple	Slightly complex

Slotted ALOHA doubles the efficiency because frames can collide only if sent in the same slot.

2M2025-26

Q4. Elaborate flooding w.r.t routing protocols. [CO4 | BT2]▼

Answer:

Flooding is a static routing technique where a router sends every incoming packet on all outgoing lines except the one it came from. It needs no routing table or topology knowledge.

Analogy: Spreading news by telling every friend, and each friend tells all their friends.

Aspect	Detail
Working	Packet arrives → copy sent on all other links → every neighbour repeats this
Problem	Huge number of duplicate packets, can loop forever
Controls	Hop counter (drop at 0) \| Sequence numbers (drop already-seen packets) \| Selective flooding (only toward the destination direction)
Advantages	Very reliable, finds shortest path automatically, simple, works even if many routers fail
Disadvantages	Wastes bandwidth, duplicates, congestion
Uses	Military networks, broadcasting, Link State routing (LSP distribution), wireless sensor networks

2M2025-26

Q5. Illustrate & explain the sketch of IPv4 packet header. [CO4 | BT2]▼

Answer:

Each row is 32 bits. Min header = 20 bytes (5 words), max = 60 bytes.

Version (4)	IHL (4)	Type of Service (8)	Total Length (16)
Identification (16)			Flags (3) \| Fragment Offset (13)
Time To Live (8)		Protocol (8)	Header Checksum (16)
Source IP Address (32)
Destination IP Address (32)
Options + Padding (0 to 40 bytes, optional)

Field	Size	Purpose
Version	4 bits	IP version. 4 for IPv4
IHL	4 bits	Header length in 32-bit words (min 5 = 20 bytes, max 15 = 60 bytes)
Type of Service	8 bits	Priority / quality of service (DSCP)
Total Length	16 bits	Header + data in bytes (max 65,535)
Identification	16 bits	Same ID for all fragments of one packet, used to reassemble
Flags	3 bits	Reserved, DF (Don't Fragment), MF (More Fragments)
Fragment Offset	13 bits	Position of this fragment in the original packet
TTL	8 bits	Hop limit; each router subtracts 1; at 0 the packet is dropped (stops endless loops)
Protocol	8 bits	Which upper layer gets the data: 6 = TCP, 17 = UDP, 1 = ICMP
Header Checksum	16 bits	Error check on the header only (recalculated at every router)
Source / Destination IP	32 + 32 bits	Sender and receiver IPv4 addresses
Options + Padding	0–40 bytes	Rarely used extras; padding makes header a multiple of 32 bits

Section B — 5 Marks Questions (Long Answer)

5M2025-26

Q6. List various Error Detection methods. Using Checksum method, evaluate & verify the bits at sender & receiver end having 4 frames of 8 bits: 11001100, 10101010, 11110000, 11000011. [CO3 | BT4]▼

Answer:

📖 Error Detection Methods

Parity check (simple and 2D)
Checksum
Cyclic Redundancy Check (CRC)
Hamming code is used for correction

Sender side

Step	Calculation
1	11001100 + 10101010 = 1 01110110 (carry 1) → wrap: 01110110 + 1 = 01110111
2	01110111 + 11110000 = 1 01100111 (carry 1) → wrap: 01100111 + 1 = 01101000
3	01101000 + 11000011 = 1 00101011 (carry 1) → wrap: 00101011 + 1 = 00101100 (this is the Sum)
4	Checksum = 1s complement of 00101100 = 11010011

Sent: 11001100, 10101010, 11110000, 11000011, 11010011

Receiver side (no error case)

Step	Calculation
1	Sum of 4 data frames (same as above) = 00101100
2	Add checksum: 00101100 + 11010011 = 11111111
3	Complement of 11111111 = 00000000

✅ Result = 0 → no error, frames accepted. If any bit flips, the final complement is non-zero and the receiver discards the frames.

5M2025-26

Q7. Identify the need of Sub-netting. Given IP address 180.25.21.172, identify its class. If subnet mask is 255.255.192.0, evaluate its subnet address. [CO4 | BT4]▼

Answer:

Need of subnetting: Efficient use of IP addresses, reduces broadcast traffic, improves security and performance, simplifies management, lets one network be split for departments/floors.

Step	Working
Class	First octet 180 lies in 128–191 (binary starts 10) → Class B (default mask 255.255.0.0)
Mask	255.255.192.0 = 11111111.11111111.11000000.00000000 = /18 → 2 bits borrowed → 2² = 4 subnets, 14 host bits → 2¹⁴ − 2 = 16,382 hosts per subnet
AND	IP: 180 . 25 . 00010101 . 10101100 Mask: 255 . 255 . 11000000 . 00000000 Result: 180 . 25 . 00000000 . 00000000
Subnet address	180.25.0.0

📐 Subnet Blocks (block size = 256 − 192 = 64)

Subnet 1: 180.25.0.0 (contains this IP, third octet 21)

Subnet 2: 180.25.64.0

Subnet 3: 180.25.128.0

Subnet 4: 180.25.192.0

Host range of subnet 1: 180.25.0.1 – 180.25.63.254

Broadcast of subnet 1: 180.25.63.255

The question prints the mask as "255 255.192 0", read as 255.255.192.0.

🌐 Computer Networks

📚 Chapters

2.1.1 Introduction to Data Link Layer

2.1.2 Design Issues of Data Link Layer

2.1.3 Error Detection & Correction

2.1.4 Checksum Step by Step

2.1.5 CRC & Hamming Code — Worked Examples

2.1.6 Stop-and-Wait Protocol

2.1.7 Sliding Window Protocols

2.1.8 Go-Back-N Explained Simply

2.1.9 Selective Repeat Explained Simply

2.1.10 Media Access Control (MAC) Layer

2.1.11 ALOHA Explained — with Numerical

2.1.12 CSMA/CD — How Ethernet Handles Collisions

2.1.13 HDLC & PPP

2.2.1 IP Addressing

2.2.2 MAC Address vs IP Address

2.2.3 IPv4 Packet Header

2.2.4 Subnetting & Supernetting

2.2.5 Subnet Calculation — Step by Step

2.2.6 Routing Algorithms

2.2.7 Distance Vector — Worked Example

2.2.8 Dijkstra Steps & Count-to-Infinity Problem

2.2.9 Congestion Control

2.2.10 Leaky & Token Bucket — Concept and Numerical

2.2.11 Congestion Prevention Policies by Layer

📝 2025-26 Paper — One-line Recall

📡 Chapter 2.1 — Data Link Layer

🌍 Chapter 2.2 — Network Layer

🧠 Tricks to Remember

✅ Last Checklist

Section A — 2 Marks Questions (Short Answer)

Section B — 5 Marks Questions (Long Answer)