Enlarged Diagram
Interactive Study Environment β€’ APJ Abdul Kalam Technological University
πŸ“„ Open Notes Reader β†—
KTU 2024 SCHEME 11 CONTACT HOURS THEORY MASTERCLASS

Module 3: Data Link Layer

Complete, beginner-friendly masterclass covering Framing (Bit/Byte Stuffing), Error Detection (CRC, Hamming Distance), HDLC & PPP, MAC Protocols (Pure/Slotted ALOHA, CSMA/CD, CDMA), ARP & MAC Addressing, Ethernet (802.3) & VLANs, Connecting Devices (Hubs, Switches, Routers), Wireless LANs (802.11, CSMA/CA, RTS/CTS), Bluetooth, and Mobile IP.

66 Pages
Official PDF Notes Synthesized
94 Figures
High-Res Diagrams Embedded
11 Parts
Step-by-Step Learning Progression
100% Theory
Hands-on Code Excluded (KTU Rule)
PART 01 CORE FOUNDATION β€’ 3M / 5M

Data-Link Layer: Sublayers & Framing

PDF Pages: 1 – 4
πŸ’‘ What is the Data Link Layer?

The Data Link Layer transforms a raw, error-prone physical transmission facility into a reliable link. It provides node-to-node (hop-to-hop) frame delivery across a single physical communication link (cable or wireless).

1. The Two Sublayers: LLC & MAC

In LAN architectures (IEEE 802), the Data Link Layer is divided into two distinct sublayers: Logical Link Control (LLC) and Medium Access Control (MAC):

Sublayer NamePositionPrimary Responsibilities
Logical Link Control (LLC) Upper Sublayer (Below Network Layer) Provides flow control, error control, and framing logic; multiplexes multiple network-layer protocols (IPv4, IPv6, ARP) over a common physical link. Independent of transmission medium.
Media Access Control (MAC) Lower Sublayer (Above Physical Layer) Controls which device gets to transmit on a shared medium at any given time (CSMA/CD, CSMA/CA, Token Passing); handles 48-bit physical MAC addressing and frame validation.
LLC and MAC Sublayers
Figure 1.1: Division of Data-Link Layer into LLC and MAC Sublayers (Page 2)

2. Framing: Packaging Packets into Frames

The data link layer separates the continuous bit-stream received from the physical layer into discrete units called frames. The two foundational framing approaches are:

A. Byte-Oriented (Character-Oriented) Framing & Byte Stuffing

Data is carried as a sequence of 8-bit bytes. Special 1-byte delimiter patterns called Flags mark the start and end of a frame (e.g., FLAG = 01111110 or ASCII DLE STX / DLE ETX).

Byte Stuffing and Unstuffing
Figure 1.2: Byte Stuffing and Un-stuffing Mechanism with ESC Bytes (Page 3)

B. Bit-Oriented Framing & Bit Stuffing

Data is viewed as an arbitrary stream of individual bits. Standard bit-oriented protocols (like HDLC) use the 8-bit flag 01111110 (six consecutive 1s bounded by 0s) to delimit frames.

Bit Stuffing and Unstuffing
Figure 1.3: Bit Stuffing: Inserting '0' After Every Five Consecutive '1's (Page 4)
⭐ High-Frequency KTU Question: Byte Stuffing vs. Bit Stuffing
ParameterByte StuffingBit Stuffing
Unit of OperationEntire 8-bit bytes (characters).Individual single bits.
Stuffed SymbolAn 8-bit ESC (Escape) byte.A single '0' bit.
Condition for StuffingWhen data byte matches Flag or ESC byte.After five consecutive '1's in data stream.
Overhead8 bits per escape (high overhead).1 bit per 5 ones (very low overhead).
PART 02 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Error Detection and Correction: Hamming Distance, CRC & Checksum

PDF Pages: 5 – 11
πŸ’‘ Why Error Detection?

Electromagnetic interference, thermal noise, and attenuation corrupt bits during transmission. Error detection enables the receiver to discover when corrupted bits exist. Error correction allows the receiver to reconstruct the original bits without retransmission.

1. Types of Errors & Hamming Distance

πŸ“ Hamming Distance Rules for Error Detection & Correction

The Hamming Distance \(d(x, y)\) between two codewords of equal length is the number of bit positions where the corresponding bits differ. The minimum Hamming distance \(d_{\text{min}}\) (d_min / \(d_{\min}\)) of a code dictates its power:

  • To guarantee detecting up to \(s\) bit errors: \[d_{\text{min}} \ge s + 1\]
  • To guarantee correcting up to \(t\) bit errors: \[d_{\text{min}} \ge 2t + 1\]

Example: To correct 2-bit errors (\(t = 2\)), the minimum Hamming distance must be \(d_{\text{min}} \ge 2(2) + 1 = 5\).

πŸ” Parity Check Schemes: Simple Parity & Two-Dimensional Parity

Before advanced polynomial codes like CRC, linear block parity codes provided elementary error detection:

  • Simple Parity Check (Simple parity): A single redundant bit (parity bit) is appended to a k-bit dataword so the total number of 1s is even (even parity) or odd (odd parity).
    • Hamming Distance: \(d_{\min} = 2\). Can detect any odd number of bit errors (guaranteed detection of 1-bit errors). Fails completely if an even number of bits flip (e.g. 2-bit error).
  • Two-Dimensional Parity Check (Two-dimensional parity): Data is organized into a 2D matrix (rows and columns). A parity bit is calculated for every row (Row parity) AND for every column (Column parity).
    • Detection & Correction Power: Can detect any pattern of up to 3 bit errors. Can correct single-bit errors without retransmission by finding the intersection of the erroneous row and column!
πŸ”’ Internet Checksum Algorithm

The Internet Checksum is based on One's complement addition of 16-bit words:

  1. The sender divides the data into a sequence of 16-bit words.
  2. All 16-bit words are summed using one's complement arithmetic (any carry out of the most significant bit is added back to the least significant bit).
  3. The sum is complemented (bitwise NOT) to form the checksum and transmitted with the data.
  4. The receiver adds all received 16-bit words, including the checksum. If the result is all 1s (which complements to zero), the data is accepted; otherwise, it is rejected.

2. Cyclic Redundancy Check (CRC) Masterclass

CRC is the most powerful and widely used error-detection code in computer networks (used in Ethernet, Wi-Fi, HDLC). It uses modulo-2 binary division (where addition and subtraction are identical to bitwise XOR).

CRC Division at Sender
Figure 2.1: CRC Binary Division at Sender (Page 8)
CRC Checker at Receiver
Figure 2.2: CRC Error Verification at Receiver (Page 8)
πŸ“ High-Frequency KTU Numerical Problem: Complete CRC Calculation

Problem: A data unit 110101 is to be transmitted using CRC with the generator polynomial \(G(x) = x^3 + x + 1\). Find:

  1. The divisor bit string.
  2. The CRC bits (remainder) and the transmitted codeword.
  3. The verification at the receiver when received without error, and when bit 3 is inverted.

Step-by-Step Solution:

1. Divisor from Polynomial:
\(G(x) = 1 \cdot x^3 + 0 \cdot x^2 + 1 \cdot x^1 + 1 \cdot x^0 \implies \mathbf{1011}\) (Degree \(n = 3\)).

2. Appending Zeros to Dataword:
Degree of generator is 3, so append \(3\) zeros to dataword 110101 \(\implies\) 110101000.

3. Modulo-2 Division at Sender:


            110000  (Quotient)
    1011 | 110101000
           1011
           -----
            1100
            1011
            ----
             1111
             1011
             ----
              1000
              1011
              ----
               0110
               0000
               ----
                1100
                1011
                ----
                 001  (Remainder = CRC bits!)
          

Remainder = \(\mathbf{001}\).
Codeword Transmitted: \(\text{Data} + \text{CRC} = 110101 + 001 = \mathbf{110101001}\).

4. Verification at Receiver (No Error):
Divide received codeword 110101001 by 1011. The remainder is strictly \(\mathbf{000}\) \(\implies\) Data is ACCEPTED without error!

5. Verification with Error:
If a bit is flipped (e.g., 110111001), the remainder is non-zero (syndrome \(\ne 0\)) \(\implies\) Error detected! Data is REJECTED.

3. Standard Polynomials

NamePolynomial ExpressionBit PatternStandard Use
CRC-8\(x^8 + x^2 + x + 1\)100000111ATM cells
CRC-16\(x^{16} + x^{15} + x^2 + 1\)11000000000000101HDLC, USB
CRC-32\(x^{32} + x^{26} + x^{23} + \dots + 1\)33 bitsEthernet (802.3), Wi-Fi (802.11)
PART 03 CORE PROTOCOLS β€’ 5M / 9M

Data Link Control (DLC) Protocols: HDLC & PPP

PDF Pages: 12 – 16
πŸ’‘ What is Data Link Control (DLC)?

DLC refers to the procedures and protocols used to manage reliable, structured communication between two directly connected nodes over a point-to-point or multipoint link.

3. Data Link Control (DLC) Flow & Error Control Protocols

Data Link Control provides reliable point-to-point transfer across an individual link using Sliding Window flow control mechanisms:

ProtocolSender Window Size (\(W_s\))Receiver Window Size (\(W_r\))Sequence Number Space (\(m\))Retransmission Behavior
Stop-and-Wait ARQ11\(\ge 2\) (0 and 1)Transmits 1 frame, waits for ACK before sending next. Simple but inefficient on long links.
Go-Back-N (GBN) ARQ\(2^m - 1\)1\(2^m\)Receiver accepts only strictly in-order frames; discards out-of-order frames. Sender retransmits all unacknowledged frames starting from the lost one.
Selective Repeat ARQ\(2^{m-1}\)\(2^{m-1}\)\(2^m\)Receiver buffers out-of-order frames. Sender retransmits ONLY the specific frames reported lost via Negative ACK (NAK). Maximum efficiency.

Piggybacking: A bidirectional optimization where an acknowledgment (ACK) is embedded directly into the header of an outgoing data frame traveling in the reverse direction, saving substantial bandwidth compared to sending dedicated ACK frames.

1. High-Level Data Link Control (HDLC)

🏒 HDLC Station Types & Transfer Modes
  • Primary Station: Controls link operation; issues commands.
  • Secondary Station: Operates under primary station control; issues only responses.
  • Combined Station: Acts as both primary and secondary; can issue both commands and responses in balanced configurations.

HDLC is an ISO-standard bit-oriented protocol for point-to-point and multipoint communication. It defines two operational modes:

HDLC Configurations
Figure 3.1: HDLC Station Configurations: NRM and ABM (Page 12)

The Three HDLC Frame Types (PDF Page 13)

HDLC Frame Formats
Figure 3.2: HDLC Frame Formats: I-Frame, S-Frame, and U-Frame (Page 12)
Frame TypeFirst Bit PatternPurpose & Functionality
I-Frame (Information) Starts with 0 Carries user application data from the network layer. Contains sender sequence number \(N(S)\) and piggybacked acknowledgment \(N(R)\).
S-Frame (Supervisory) Starts with 10 Carries flow and error control information when there is no user data to piggyback on: RR (Receive Ready), RNR (Receive Not Ready), REJ (Reject), and SREJ (Selective Reject).
U-Frame (Unnumbered) Starts with 11 Carries link setup, mode negotiation, disconnection, and network management commands (e.g., SABM, DISC).

2. Point-to-Point Protocol (PPP)

PPP is the dominant byte-oriented data link protocol used for establishing direct connections between two nodes (e.g., home PC to ISP via DSL or dial-up).

PPP Transition States
Figure 3.3: PPP Transition State Machine (Page 15)

PPP Authentication Protocols: PAP vs. CHAP (PDF Page 16)

ParameterPassword Authentication Protocol (PAP)Challenge Handshake Authentication Protocol (CHAP)
Handshake TypeSimple Two-Way Handshake.Secure Three-Way Handshake.
Password SecuritySends username and password in clear plaintext across the link! Highly vulnerable to sniffing.Password is NEVER transmitted over the wire!
Working MechanismClient sends password; server accepts or rejects.Server sends random "Challenge"; client hashes Challenge + Password (MD5) and returns response; server verifies hash.
Repeated AuthenticationOnly once at connection setup.Server can send fresh challenges periodically to prevent spoofing.
βš™οΈ Point-to-Point Protocol (PPP) Core Architecture: LCP and NCP

PPP relies on two main protocol suites to control link establishment and network negotiation:

  • Link Control Protocol (LCP): Responsible for establishing, configuring, testing, maintaining, and terminating the physical data link connection. LCP negotiates Maximum Receive Unit (MRU), authentication protocols, and compression.
  • Network Control Protocol (NCP): A family of protocols designed to negotiate network-layer parameters for specific layer-3 protocols. For IP networks, PPP invokes IPCP (Internet Protocol Control Protocol) to dynamically assign IP addresses to clients.
  • Authentication Schemes:
    • PAP (Password Authentication Protocol): Two-way handshake; sends plaintext username and password (insecure).
    • CHAP (Challenge Handshake Authentication Protocol): Three-way handshake; uses cryptographic MD5 challenge-response hash, preventing eavesdropping and replay attacks.
PART 04 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Multiple Access Protocols: ALOHA, CSMA & CSMA/CD

PDF Pages: 17 – 24
πŸ’‘ Why Multiple Access Protocols?

When multiple stations share a single broadcast transmission medium (like a common cable or the airwaves), multiple simultaneous transmissions collide and corrupt data. Multiple Access protocols regulate access to prevent or resolve collisions.

1. ALOHA Protocols: Pure ALOHA vs. Slotted ALOHA

ParameterPure ALOHASlotted ALOHA
Transmission RuleAny station can transmit at any arbitrary time whenever it has data ready.Time is divided into discrete slots equal to frame time \(T_{fr}\). Stations can only transmit at the start of a slot.
Vulnerable Period (\(V_t\))\(V_t = 2 \times T_{fr}\) (Frames collide if sent within \(2 T_{fr}\)).\(V_t = 1 \times T_{fr}\) (Vulnerable window is halved!).
Throughput Formula (\(S\))\(S = G \cdot e^{-2G}\)\(S = G \cdot e^{-G}\)
Maximum Throughput18.4% (at load \(G = 0.5\): \(S_{\text{max}} = \frac{1}{2e} \approx 0.184\)).36.8% (at load \(G = 1.0\): \(S_{\text{max}} = \frac{1}{e} \approx 0.368\)).
SynchronizationNone needed.Requires global master clock synchronization among all stations.
Pure and Slotted ALOHA Vulnerable Time
Figure 4.1: Vulnerable Time Comparison: Pure ALOHA (2*Tfr) vs. Slotted ALOHA (Tfr) (Page 18)
πŸ“ High-Frequency KTU Numerical Problem: Pure ALOHA Throughput

Problem: A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. Find the throughput if the system produces 500 frames per second.

Solution:

  1. Frame transmission time: \[T_{fr} = \frac{\text{Frame Length}}{\text{Bandwidth}} = \frac{200 \text{ bits}}{200 \times 10^3 \text{ bps}} = 10^{-3} \text{ s} = 1 \text{ ms}\]
  2. Average load \(G\) (frames generated per frame transmission time): \[G = \text{Frame Generation Rate } (\lambda) \times T_{fr} = 500 \text{ frames/s} \times 10^{-3} \text{ s} = \mathbf{0.5}\]
  3. Throughput \(S\) for Pure ALOHA: \[S = G \cdot e^{-2G} = 0.5 \cdot e^{-2(0.5)} = 0.5 \cdot e^{-1} = \frac{0.5}{2.71828} \approx \mathbf{0.1839 \text{ (18.39\%)}}\]
  4. Actual throughput in frames/s: \(500 \times 0.1839 = \mathbf{91.95 \text{ frames/s}}\).

2. Carrier Sense Multiple Access (CSMA) & Persistence Methods

Principle: "Sense before transmit." Stations listen to the medium before sending. If the channel is busy, stations defer transmission according to one of three persistence strategies:

CSMA Persistence Methods
Figure 4.2: CSMA Persistence Strategies: 1-Persistent, Non-Persistent, and p-Persistent (Page 22)
Persistence MethodBehavior When Medium is BusyCollision ProbabilityChannel Idle Time
1-Persistent Continuously senses channel; transmits immediately (with probability 1) as soon as channel becomes idle. Highest (If 2 stations wait for channel to clear, both transmit simultaneously upon idle \(\rightarrow\) collision!). Lowest (zero channel idle time).
Non-Persistent If busy, waits a random amount of time before sensing again. Lowest (reduces collisions drastically). Highest (channel may sit idle while stations are waiting their timers).
p-Persistent Continuously senses. When idle, transmits with probability \(p\), or defers to next slot with probability \((1-p)\). Balanced & Tunable (controlled by parameter \(p\)). Optimal compromise between collision rate and idle time.

3. CSMA with Collision Detection (CSMA/CD) & Random Access

Principle: "Sense before transmit, and LISTEN WHILE TRANSMITTING." Used in traditional half-duplex Ethernet (IEEE 802.3).

CSMA/CD Flowchart
Figure 4.3: CSMA/CD Operation Flowchart (Page 24)
πŸ“ High-Frequency KTU Derivation: Minimum Frame Size in CSMA/CD

Why is a minimum frame length mandatory in CSMA/CD?
Suppose Station A sends a packet to Station B at the farthest end of the cable (propagation time \(T_p\)). Just before the packet arrives, Station B senses the channel as idle and starts transmitting, causing a collision at time \(T_p\). The collision signal takes another \(T_p\) to travel back to Station A. Therefore, Station A can only detect the collision after a round-trip propagation time of \(2 \times T_p\)!

To ensure Station A is still actively transmitting when the collision signal returns (so it knows its own frame collided), the frame transmission time \(T_{fr}\) must satisfy:

\[T_{fr} \ge 2 \times T_p\]

Since \(T_{fr} = \frac{\text{Frame Size } (L)}{\text{Bandwidth } (B)}\), the Minimum Frame Size is:

\[L_{\text{min}} = 2 \times T_p \times B\]

Example: For Standard 10 Mbps Ethernet with maximum network propagation delay \(T_p = 25.6\ \mu\text{s}\): \[L_{\text{min}} = 2 \times (25.6 \times 10^{-6}\text{ s}) \times (10 \times 10^6\text{ bps}) = 512\text{ bits} = \mathbf{64\text{ bytes!}}\] This is why Ethernet frames can NEVER be smaller than 64 bytes (512 bits)!

⏱️ CSMA/CD Binary Exponential Backoff Algorithm & Contention Window

When two or more stations transmit simultaneously, a collision occurs. CSMA/CD handles retransmission attempts using the Binary Exponential Backoff (Exponential backoff) algorithm:

  1. Initialize collision counter \(k = 0\).
  2. Upon each collision, increment \(k = k + 1\).
  3. Randomly choose a backoff integer \(R\) from the Contention Window range: \[0 \le R \le 2^k - 1\]
  4. For \(k > 10\), the maximum contention window is capped at \(2^{10} - 1 = 1023\).
  5. Wait for backoff duration \(T_B = R \times \text{Slot Time}\) (where Slot Time for Standard Ethernet = 512 bit times = \(51.2\ \mu\text{s}\)).
  6. If \(k\) reaches 15 (or 16), abort transmission and report link failure to upper layers.
PART 05 CORE THEORY β€’ 5M / 9M

Controlled Access & Channelization (CDMA)

PDF Pages: 25 – 29

1. Controlled Access Protocols

2. Channelization: FDMA, TDMA & CDMA Masterclass

Channelization protocols divide the total available link bandwidth among multiple stations:

MethodDivision PrincipleInterference PreventionEfficiency
FDMA (Frequency-Division Multiple Access)Total frequency band split into distinct frequency channels.Guard bands between adjacent frequencies prevent crosstalk.Wasted bandwidth if a assigned station is idle.
TDMA (Time-Division Multiple Access)Entire frequency band allocated to each station for a dedicated time slot.Guard times and synchronization preambles prevent overlap.Wasted time slots when a station has no traffic.
CDMA (Code-Division Multiple Access)All stations transmit simultaneously across the entire frequency spectrum using unique mathematical codes.Each station is assigned an Orthogonal Sequence (Chipping Code).Maximum spectral efficiency; used in 3G cell networks.

CDMA Mathematical Principles & Walsh Tables

In CDMA, each station \(i\) is assigned a unique \(N\)-bit chip sequence \(\mathbf{C}_i\) chosen from a Walsh Table. Key mathematical properties of orthogonal sequences:

Walsh Matrix Generation: \(W_1 = [+1]\), and \(W_{2N} = \begin{bmatrix} W_N & W_N \\ W_N & -W_N \end{bmatrix}\):

\[W_2 = \begin{bmatrix} +1 & +1 \\ +1 & -1 \end{bmatrix}, \quad W_4 = \begin{bmatrix} +1 & +1 & +1 & +1 \\ +1 & -1 & +1 & -1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & -1 & +1 \end{bmatrix}\]
πŸ“ Worked Numerical Example: CDMA Decoding

Suppose Station 1 has code \(\mathbf{C}_1 = [+1, +1, +1, +1]\) and sends data bit 0 (represented as \(-1\)), so sent signal is \(\mathbf{S}_1 = [-1, -1, -1, -1]\).
Station 2 has code \(\mathbf{C}_2 = [+1, -1, +1, -1]\) and sends data bit 1 (represented as \(+1\)), so sent signal is \(\mathbf{S}_2 = [+1, -1, +1, -1]\).
On the shared channel, signals add linearly: \(\mathbf{S}_{\text{channel}} = \mathbf{S}_1 + \mathbf{S}_2 = [0, -2, 0, -2]\).
To recover Station 1's data, the receiver computes the inner product with \(\mathbf{C}_1\):
\[\mathbf{S}_{\text{channel}} \cdot \mathbf{C}_1 = (0)(1) + (-2)(1) + (0)(1) + (-2)(1) = -4\] Dividing by \(N = 4\): \(-4 / 4 = -1 \implies \text{Data Bit 0}\) correctly decoded!

In CDMA, all stations transmit simultaneously over the exact same frequency band. Transmissions do not interfere because each station is assigned a unique, mathematically orthogonal code vector (chip sequence).

CDMA Chips and Encoding
Figure 5.1: CDMA Orthogonal Chip Sequences and Common Channel Combining (Page 28)
⭐ Mathematical Rules of CDMA Orthogonal Vectors

Let \(\mathbf{C}_i\) and \(\mathbf{C}_j\) be chip sequences of length \(N\) assigned to stations \(i\) and \(j\):

  • Inner product with another station: \(\mathbf{C}_i \cdot \mathbf{C}_j = 0\) (Orthogonality).
  • Inner product with itself: \(\mathbf{C}_i \cdot \mathbf{C}_i = N\).

Decoding at Receiver: If the common channel signal is \(\mathbf{S} = d_1 \mathbf{C}_1 + d_2 \mathbf{C}_2 + \dots + d_k \mathbf{C}_k\), a receiver wanting data from station 1 computes: \[\frac{\mathbf{S} \cdot \mathbf{C}_1}{N} = \frac{d_1 (\mathbf{C}_1 \cdot \mathbf{C}_1) + 0 + \dots + 0}{N} = \frac{d_1 \cdot N}{N} = \mathbf{d_1}\] All other stations' signals vanish to zero!

Walsh Tables for Chip Sequence Generation

Walsh tables are generated recursively:

\[W_1 = [ +1 ], \quad W_{2N} = \begin{bmatrix} W_N & W_N \\ W_N & \overline{W_N} \end{bmatrix}\]

For \(N = 4\):


        W4 = [
          [ +1, +1, +1, +1 ],   (Station 1)
          [ +1, -1, +1, -1 ],   (Station 2)
          [ +1, +1, -1, -1 ],   (Station 3)
          [ +1, -1, -1, +1 ]    (Station 4)
        ]
      
PART 06 VERY HIGH PRIORITY β€’ 3M / 6M

Link-Layer Addressing & Address Resolution Protocol (ARP)

PDF Pages: 30 – 34
πŸ’‘ Why Do We Need Both IP and MAC Addresses?

An IP address is a logical address that defines the ultimate source and destination endpoints of a journey across the global Internet. A MAC (Physical) address is a 48-bit hardware address burnt into the NIC that identifies the machine within the current local network hop. As a packet travels across routers, the IP addresses remain constant, but the source and destination MAC addresses change at every single hop!

🏷️ MAC Address Categories: Unicast, Multicast & Broadcast
  • Unicast: Delivered to a single specific station. The least significant bit (LSB) of the first byte is 0 (e.g., 00:1A:2B:3C:4D:5E).
  • Multicast: Delivered to a group of subscribed stations. The LSB of the first byte is 1 (e.g., 01:00:5E:00:00:01).
  • Broadcast: Delivered to all stations on the local network. All 48 bits are set to 1 (FF:FF:FF:FF:FF:FF).

1. Address Resolution Protocol (ARP) Operation

When Host A wants to send an IP datagram to Host B on the same local network, it knows Host B's IP address (from DNS or configuration), but does not know Host B's physical MAC address. Host A uses ARP to resolve the IP address to a MAC address:

  1. ARP Request (Broadcast): Host A broadcasts an ARP Request packet across the local LAN: "Who has IP address 192.168.1.5? Please tell MAC 00:1A:2B:3C:4D:5E." Since the destination MAC is broadcast (FF:FF:FF:FF:FF:FF), all stations on the LAN receive and inspect it.
  2. ARP Reply (Unicast): Host B recognizes its own IP address, while all other hosts discard the request. Host B replies directly to Host A with a unicast ARP Reply containing its physical MAC address.
  3. ARP Caching: Host A saves this mapping in its local ARP Cache table with a TTL timer to avoid repeating queries for future packets.
ARP Request and Reply
Figure 6.1: ARP Operation: Broadcast Request and Unicast Reply (Page 31)

2. ARP Packet Format

ARP Packet Format
Figure 6.2: ARP Packet Format (Page 32)
Field NameLengthDescription & Example Value
Hardware Type (HTYPE)16 bitsDefines link-layer network type (Ethernet = 1).
Protocol Type (PTYPE)16 bitsDefines higher-layer protocol (IPv4 = 0x0800).
Hardware Length (HLEN)8 bitsLength of physical MAC address in bytes (Ethernet = 6).
Protocol Length (PLEN)8 bitsLength of logical IP address in bytes (IPv4 = 4).
Operation (OPER)16 bits1 for ARP Request; 2 for ARP Reply.
Sender Hardware Address (SHA)48 bits (6B)MAC address of the sending station.
Sender Protocol Address (SPA)32 bits (4B)IP address of the sending station.
Target Hardware Address (THA)48 bits (6B)All 0s in Request; Target station's MAC in Reply.
Target Protocol Address (TPA)32 bits (4B)IP address of the requested station.
PART 07 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Wired LANs: Standard Ethernet & Virtual LANs (VLANs)

PDF Pages: 35 – 43
πŸ’‘ What is Ethernet?

Ethernet (IEEE 802.3) is the universally dominant wired LAN technology. Conceived by Bob Metcalfe at Xerox PARC in the 1970s, it evolved from 10 Mbps coaxial bus systems to 100 Gbps switched optical architectures.

1. Standard Ethernet Frame Format (IEEE 802.3)

Standard Ethernet Frame Format
Figure 7.1: Standard Ethernet (802.3) Frame Format (Page 37)
Field NameSizeTechnical Description
Preamble7 bytesPattern of alternating 1s and 0s (10101010...) to synchronize receiver clock timing.
Start Frame Delimiter (SFD)1 bytePattern 10101011; the ending double-1 signals that actual frame fields begin immediately.
Destination MAC Address6 bytes (48 bits)Physical hardware address of destination NIC.
Source MAC Address6 bytes (48 bits)Physical hardware address of sending NIC.
Type / Length2 bytesIf value \(\ge 1536\) (e.g., 0x0800), defines higher-layer protocol (IPv4). If \(\le 1500\), defines payload length in bytes.
Data and Padding46 to 1500 bytesCarries IP packet. If payload is less than 46 bytes, padding bytes are appended to satisfy the 64-byte minimum frame size!
CRC / FCS4 bytes (32 bits)Cyclic Redundancy Check (CRC-32) to detect transmission bit errors.
⭐ Total Frame Length Range in Standard Ethernet

Excluding the 8-byte physical synchronization header (Preamble + SFD):

  • Minimum Frame Length: \(6 + 6 + 2 + 46 + 4 = \mathbf{64 \text{ bytes}}\).
  • Maximum Frame Length: \(6 + 6 + 2 + 1500 + 4 = \mathbf{1518 \text{ bytes}}\).

2. Evolution of Ethernet: Fast, Gigabit & 10-Gigabit Ethernet

Standard Ethernet evolved across four major generations while maintaining the exact same IEEE 802.3 MAC frame format:

GenerationData RateMedium & StandardsLine Encoding SchemeDuplex / Access Method
Standard Ethernet10 Mbps10Base5 (thick coax), 10Base2 (thin coax), 10Base-T (UTP)Manchester encodingHalf-duplex CSMA/CD or Full-duplex
Fast Ethernet100 Mbps100Base-TX (2 pairs Cat 5 UTP), 100Base-FX (2 fiber strands), 100Base-T4 (4 pairs Cat 3)4B5B + MLT-3 (100Base-TX)
4B5B + NRZ-I (100Base-FX)
Autonegotiation; star topology with switches/hubs
Gigabit Ethernet1000 Mbps1000Base-SX (short-wave fiber), 1000Base-LX (long-wave fiber), 1000Base-T (4 pairs Cat 5e)8B/10B + NRZ (optical)
4D-PAM5 (twisted-pair copper)
Full duplex switched (CSMA/CD optional with carrier extension)
10-Gigabit Ethernet10 Gbps10GBase-SR, 10GBase-LR, 10GBase-ER, 10GBase-EW. Supports LAN PHY (standard LANs) and WAN PHY (compatible with SONET OC-192).64B66B encoding (64B/66B)Exclusively full-duplex star; CSMA/CD completely removed

3. Physical Layer Implementations of 10 Mbps Ethernet

StandardTransmission MediumTopologyMax Segment LengthConnector
10Base5 (Thicknet)Thick coaxial cable (RG-8, 10 mm)Bus500 metersVampire tap & AUI cable
10Base2 (Thinnet / Cheapernet)Thin coaxial cable (RG-58, 5 mm)Bus185 metersBNC T-connector
10Base-TUnshielded Twisted Pair (Cat 3/5 UTP)Star (Hub/Switch)100 metersRJ-45 connector
10Base-FOptical fiber pair (850 nm multimode)Star2000 metersST or SC connector

4. Virtual Local Area Networks (VLANs)

🏷️ IEEE 802.1Q Frame Tagging & Trunk Links

VLANs segment broadcast domains logically across physical switches:

  • IEEE 802.1Q Standard: Defines an explicit 4-byte VLAN tag inserted into the Ethernet frame header between the Source MAC address and EtherType fields. Contains a 12-bit VLAN Identifier (VID), supporting up to 4096 distinct VLANs.
  • Access Links vs. Trunk Links:
    • Access Link: Connects a standard end device (PC, printer) to a switch port. Carries standard untagged Ethernet frames.
    • Trunk Link: Connects two VLAN-aware switches or a switch to a router. Carries multiplexed frames for multiple VLANs using 802.1Q tags to distinguish traffic.

A VLAN is a logical grouping of network devices configured through switch software to communicate as if they were attached to the same physical cable, regardless of their actual physical location.

VLAN Logical Separation
Figure 7.2: Logical Division of Physical Switch Ports into Separate VLANs (Page 42)

Advantages of VLANs

PART 08 CORE HARDWARE β€’ 3M / 5M

Connecting Devices: Hubs, Bridges, Switches & Routers

PDF Pages: 44 – 46

1. Connecting Devices: Classification Across OSI Layers

DeviceOperating LayerFunctionalityCollision DomainsBroadcast Domains
Repeater / HubPhysical (Layer 1)Regenerates electrical or optical signals; bit-level forwarder.Single shared collision domainSingle shared broadcast domain
Bridge / Two-layer switchData Link (Layer 2)Filters and forwards frames based on MAC destination address; maintains dynamic MAC table.Separates collision domains (one per port)Single shared broadcast domain
Router / Three-layer switchNetwork (Layer 3)Routes packets based on logical IP destination address; isolates subnets.Separates collision domainsSeparates broadcast domains
GatewayApplication / All Layers (Layer 7)Protocol converter connecting completely incompatible network architectures (e.g., SNA to TCP/IP).Separates all domainsSeparates all domains

Transparent Bridge Learning Algorithm & Spanning Tree Protocol (STP)

A Two-layer switch (Transparent bridge) builds its forwarding database automatically without manual configuration:

  • Dynamic Learning: When a frame enters port \(P\) with source MAC address \(S\), the switch creates/refreshes the mapping \(S \rightarrow P\).
  • Forwarding / Filtering: If destination MAC \(D\) exists in the table, the switch forwards out ONLY the mapped port. If \(D\) is unknown or broadcast, the switch floods the frame out all ports except the arrival port.
  • Loop Prevention via Spanning Tree Protocol (STP - IEEE 802.1D): Redundant links in bridged networks create catastrophic broadcast storms. STP dynamically calculates a loop-free logical tree by electing a Root Bridge and blocking redundant switch ports, keeping them in standby.
Connecting Devices Across OSI Layers
Figure 8.1: Connecting Devices and Their Operating Protocol Layers (Page 45)
Connecting DeviceOperating LayerFunctionality & AddressingCollision & Broadcast Domains
Repeater / Hub Layer 1 (Physical) Regenerates and amplifies electrical signals. Broadcasts incoming bits to all other ports. Blind to MAC or IP addresses. 1 Collision Domain.
1 Broadcast Domain.
Bridge / Switch Layer 2 (Data Link) Inspects destination MAC addresses. Uses a self-learning forwarding table to forward frames selectively to the correct port. Separates Collision Domains (each port is its own collision domain!).
1 Broadcast Domain.
Router Layer 3 (Network) Inspects destination IP addresses. Routes packets between different logical networks. Changes MAC addresses at each hop! Separates Collision Domains.
Separates Broadcast Domains!

How a Link-Layer Switch Learns MAC Addresses

  1. Frame Arrival: Frame arrives at Port 1 with Source MAC \(S\) and Destination MAC \(D\).
  2. Learning Step: Switch inspects Source MAC \(S\) and records in its table: MAC S -> Port 1.
  3. Forwarding Step: Switch checks table for Destination MAC \(D\):
    • If found: Forwards frame out *only* that destination port (Filtering/Forwarding).
    • If NOT found (or Broadcast): Floods the frame out all ports except the arrival port!
PART 09 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Wireless LANs: IEEE 802.11 (Wi-Fi) & Bluetooth

PDF Pages: 47 – 60
πŸ’‘ Why Can't Wireless Networks Use CSMA/CD?

In wireless transmission, signal energy attenuates drastically with distance. A transmitting station's own outgoing signal completely drowns out any faint collision signals from distant stations. Furthermore, stations may be out of radio range of each other! Hence, wireless networks use CSMA with Collision Avoidance (CSMA/CA) instead.

1. The Hidden and Exposed Station Problems

Hidden and Exposed Station Problems
Figure 9.1: Hidden Station Problem and Exposed Station Problem in Wireless LANs (Page 48)
Problem NameCause & ScenarioConsequence & Remedy
Hidden Station Problem Stations B and C can both reach Base Station A, but B and C are hidden from each other (out of mutual radio range). Both sense channel as idle and transmit to A simultaneously. Collision at A! Solved using RTS (Request to Send) and CTS (Clear to Send) control handshake frames.
Exposed Station Problem Station C hears Station B transmitting to A. C wants to transmit to D (which is far away from B and A). Hearing B, C unnecessarily defers transmission. Wasted channel capacity! C could have transmitted to D without causing interference. RTS/CTS alerts C that it can safely transmit.

2. IEEE 802.11 CSMA/CA Protocol Timeline

Before transmitting, a station waits an Interframe Space (IFS). IEEE 802.11 defines different IFS durations to prioritize control frames over data: SIFS < PIFS < DIFS < EIFS.

CSMA/CA Protocol Timeline with RTS/CTS and NAV
Figure 9.2: CSMA/CA Protocol Timeline: DIFS, RTS, SIFS, CTS, NAV, Data, ACK (Page 51)
  1. Sender senses channel. When idle for duration of DIFS (Distributed IFS), sender transmits an RTS (Request to Send) frame containing the requested transmission duration.
  2. Destination receives RTS and waits a short SIFS (Short IFS), then replies with a CTS (Clear to Send) frame.
  3. Network Allocation Vector (NAV): All neighboring stations hearing the RTS or CTS set a timer called NAV and remain silent for that entire reserved period!
  4. Sender transmits data frame; Destination confirms with an ACK after SIFS.
πŸ“‘ IEEE 802.11 Physical Layer Standards
StandardFrequency BandModulation SchemeMaximum Data Rate
802.11 (Legacy)2.4 GHz ISMFHSS or DSSS1 to 2 Mbps
802.11b2.4 GHz ISMHR-DSSS (DSSS)11 Mbps
802.11a5 GHz U-NIIOFDM54 Mbps
802.11g2.4 GHz ISMOFDM54 Mbps
802.11n2.4 & 5 GHzMIMO-OFDMUp to 600 Mbps

3. Bluetooth Architecture: Piconet & Scatternet

Bluetooth (IEEE 802.15.1) is a short-range wireless Personal Area Network (PAN) technology operating in the 2.4 GHz ISM band using Frequency Hopping Spread Spectrum (FHSS with 1600 hops/s).

Bluetooth Piconet and Scatternet
Figure 9.3: Bluetooth Piconet (1 Master, 7 Slaves) and Scatternet Architecture (Page 56)
πŸ“Ά Bluetooth Protocol Architecture: Radio, Baseband & L2CAP
  • Radio Layer: Operates in the 2.4 GHz ISM band. Uses Frequency-Hopping Spread Spectrum (FHSS) with 79 channels hopping at 1600 hops/second to avoid Wi-Fi interference.
  • Baseband Layer: Manages physical links, timing, frequency hopping, and TDMA time-slot polling between Master and Slave devices.
  • L2CAP (Logical Link Control and Adaptation Protocol): Adapts upper-layer protocols to the baseband. Provides protocol multiplexing, segmentation and reassembly (SAR) for packets up to 64 KB, and QoS.
PART 10 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Mobile IP Architecture & Triangular Routing (Triangle Routing)

PDF Pages: 61 – 65
πŸ’‘ Why Do We Need Mobile IP?

In standard IP routing, an IP address is strongly tied to a physical network prefix (the NetID). If a laptop moves to a foreign network and retains its original IP address, routers cannot route packets to it. If it changes its IP address, all active TCP connections break. Mobile IP allows a mobile host to migrate between different networks while keeping its permanent IP address!

1. Key Entities in Mobile IP

EntityRole & Functionality
Mobile Node (MN / Mobile Host)The node that moves its point of attachment from its home network to foreign networks without changing its IP address.
Home NetworkThe permanent home IP subnet where the mobile host's permanent IP address belongs.
Home Agent (HA)A router on the home network that acts as the proxy guardian for the mobile host when it is roaming away from home.
Foreign NetworkThe visited network where the mobile host is currently located.
Foreign Agent (FA)A router on the foreign network that provides routing and forwarding services to visiting mobile hosts.
Home AddressThe permanent 32-bit IP address assigned to the mobile host. Never changes!
Care-of Address (COA)A temporary IP address associated with the mobile host's current physical point of attachment in the foreign network. (Usually the IP address of the Foreign Agent).
Mobile IP Architecture and Triangular Routing
Figure 10.1: Mobile IP Architecture: Triangular Routing and Tunneling (Page 62)

2. The Three Phases of Mobile IP Operation

  1. Phase 1: Agent Discovery:
    • Foreign Agents and Home Agents periodically broadcast ICMP Agent Advertisement messages to announce their presence and Care-of Addresses.
    • Alternatively, a freshly connected mobile host broadcasts an Agent Solicitation message asking for local agents.
  2. Phase 2: Registration:
    • Mobile Host sends a Registration Request to the Foreign Agent containing its Home IP, Home Agent IP, and requested lifetime.
    • Foreign Agent relays the request to the Home Agent.
    • Home Agent verifies credentials, binds the Mobile Host's Home IP to the temporary Care-of Address (COA) in its binding table, and returns a Registration Reply through the FA to the MH.
  3. Phase 3: Data Transfer (Triangle Routing / Triangular Routing & Tunneling):
    • Step 1: A Correspondent Host (CH) sends an ordinary IP packet to the Mobile Host's Home Address. Standard routers route it to the Home Network.
    • Step 2 (Proxy ARP & Interception): The Home Agent intercepts the packet using Proxy ARP (answering with its own MAC address).
    • Step 3 (Tunneling / Encapsulation): The Home Agent encapsulates the entire original IP packet inside a new outer IP datagram with destination address set to the Care-of Address (COA), and forwards it across the Internet (Tunneling).
    • Step 4 (Decapsulation): The Foreign Agent receives the outer datagram, strips the outer header, and delivers the original packet to the Mobile Host.
    • Step 5 (Direct Return Path): The Mobile Host sends reply packets directly to the Correspondent Host through standard routing without passing through the Home Agent!
⭐ Inefficiency of Triangular Routing: The Double Crossing Problem

Because packets from the Correspondent Host must first travel to the Home Agent before being tunneled to the Foreign Agent, this indirect path forms a triangle (Triangular Routing). If the Correspondent Host and the Mobile Host are located in the exact same foreign city (e.g., Kochi) while the Home Agent is in New York, packets travel all the way from Kochi to New York and back to Kochi! This is known as the Double Crossing Problem.

PART 11 EXAM MASTERCLASS β€’ NUMERICALS & QUESTION BANK

KTU Examination Masterclass & Solved Problems

PDF Pages: 66 – 67
πŸ“ Master Numerical 1: Cyclic Redundancy Check (CRC-3)

Problem: Given dataword 100100 and divisor polynomial \(G(x) = x^3 + x^2 + 1\). Find the codeword, and show receiver verification when received with no error.

Solution:

  • Generator \(G(x) = x^3 + x^2 + 0x + 1 \implies \mathbf{1101}\) (Degree 3).
  • Append 3 zeros to dataword: 100100000.
  • Modulo-2 division of 100100000 by 1101 yields Remainder = \(\mathbf{001}\).
  • Codeword = \(\text{Data} + \text{Remainder} = 100100 + 001 = \mathbf{100100001}\).
  • Receiver divides 100100001 by 1101; Remainder = \(\mathbf{000}\) \(\implies\) Accepted!
πŸ“ Master Numerical 2: CSMA/CD Minimum Frame Size

Problem: A network has a bandwidth of 100 Mbps and a maximum distance between stations of 1 km. The signal propagation speed through the cable is \(2 \times 10^8\text{ m/s}\). Calculate the minimum frame size required for CSMA/CD.

Solution:

  • Propagation time \(T_p = \frac{\text{Distance}}{\text{Speed}} = \frac{1000\text{ m}}{2 \times 10^8\text{ m/s}} = 5 \times 10^{-6}\text{ s} = 5\ \mu\text{s}\).
  • Minimum transmission time \(T_{fr} = 2 \times T_p = 2 \times (5 \times 10^{-6}\text{ s}) = 10\ \mu\text{s}\).
  • Minimum frame size: \[L_{\text{min}} = 2 \times T_p \times \text{Bandwidth} = (10 \times 10^{-6}\text{ s}) \times (100 \times 10^6\text{ bps}) = 1000\text{ bits} = \mathbf{125\text{ bytes}}\]

KTU Module 3 Comprehensive Question Bank

Answer:

  • Hub: Operates at Layer 1 (Physical Layer). Regenerates electrical signals and broadcasts bits to all ports blindly without inspecting addresses. (Single collision domain).
  • Switch: Operates at Layer 2 (Data Link Layer). Inspects 48-bit MAC addresses and forwards frames selectively to the destination port using a self-learning table. (Separates collision domains).
  • Router: Operates at Layer 3 (Network Layer). Inspects 32-bit IP addresses and routes packets across different subnets. (Separates both collision and broadcast domains).

Answer Blueprint:

  1. Architecture (3 Marks): Draw and explain the Basic Service Set (BSS) (ad-hoc vs infrastructure with Access Point) and Extended Service Set (ESS) connected via a Distribution System (DS).
  2. Why CSMA/CA (1 Mark): State that wireless stations cannot detect collisions (CSMA/CD impossible) due to signal fading and hidden terminal issues.
  3. Interframe Spaces (1.5 Marks): Explain SIFS (highest priority for ACK/CTS), PIFS (PCF polling), and DIFS (DCF transmission).
  4. CSMA/CA Protocol Timeline (3.5 Marks): Draw the timing diagram showing:
    • DIFS sensing & back-off.
    • RTS transmission containing duration.
    • SIFS delay & CTS reply from receiver.
    • NAV (Network Allocation Vector): virtual carrier sensing where neighbors sleep.
    • Data transmission & receiver ACK after SIFS.
⚑ Module 3 Last-Minute Memory Mnemonics
  • Ethernet Frame Length: Min 64 bytes, Max 1518 bytes.
  • CSMA/CD Rule: \(T_{fr} \ge 2 \times T_p \implies L_{\text{min}} = 2 \times T_p \times B\).
  • ALOHA Max Throughput: Pure ALOHA = 18.4% (\(G = 0.5\)), Slotted ALOHA = 36.8% (\(G = 1.0\)).
  • Hamming Distance: Detect \(s\) errors \(\rightarrow d_{\text{min}} \ge s + 1\); Correct \(t\) errors \(\rightarrow d_{\text{min}} \ge 2t + 1\).
  • Bluetooth Piconet: 1 Master + Max 7 Active Slaves.
  • Wireless IFS Priority: Smallest to Largest → SIFS < PIFS < DIFS < EIFS.