Data Link Layer – Framing Methods

What is Framing?

Framing is a Data Link Layer function that divides the continuous stream of bits received from the
Network Layer into manageable units called frames.

Each frame contains:

• Start of frame

• Data

• End of frame

Why framing is needed?

• To identify frame boundaries

• To ensure synchronization

• To provide error control

• To help in flow control

Types of Framing Methods

1. Character Count

2. Character Stuffing

3. Bit Stuffing

1. Character Count Method

Theory

• The first byte of the frame specifies the number of characters in the frame.

• Receiver reads that many characters to know frame boundary.

Frame Format

[Count] [Data1] [Data2] ... [DataN]

Example

Data = HELLO

Frame:

5 HELLO

Advantages

✔ Simple
✔ Easy to implement
Disadvantages

If count field is corrupted → frame boundary lost

Rarely used in modern networks

C Program – Character Count

#include <stdio.h>

#include <string.h>

int main() {

char data[100];

int count;

printf("Enter data: ");

scanf("%s", data);

count = strlen(data);

printf("\nFrame transmitted:\n");

printf("%d %s\n", count, data);

return 0;

Sample Input

HELLO

Sample Output

Frame transmitted:

5 HELLO

2. Character Stuffing

Theory

• Uses special characters:

 o STX → Start of Text

o ETX → End of Text

o ESC → Escape character

• If STX/ETX appears in data, ESC is added before it.

Frame Format

STX DATA ETX

Example

Original Data:

A B STX C ETX D

After stuffing:

STX A B ESC STX C ESC ETX D ETX

Advantages

✔ Reliable
✔ No count field dependency

Disadvantages

Extra characters increase frame size

C Program – Character Stuffing

#include <stdio.h>

int main() {

char data[100], stuffed[200];

int i, j = 0;

printf("Enter data (use S for STX, E for ETX): ");

scanf("%s", data);

stuffed[j++] = 'S'; // STX

for (i = 0; data[i] != '\0'; i++) {

if (data[i] == 'S' || data[i] == 'E') {

 stuffed[j++] = 'X'; // ESC

stuffed[j++] = data[i];

stuffed[j++] = 'E'; // ETX

stuffed[j] = '\0';

printf("\nStuffed Frame: %s\n", stuffed);

return 0;

Sample Input

ABSECD

Sample Output

Stuffed Frame: SABSXSECD E

(Here X = ESC, S = STX, E = ETX)

3. Bit Stuffing

Theory

• Frame starts and ends with flag = 01111110

• To prevent flag pattern appearing in data:

o After five consecutive 1s, insert a 0

Frame Format

01111110 DATA 01111110

Example

Original Data:

1111101111110

After Bit Stuffing:

1111100 11111010

Final Frame:
01111110 111110011111010 01111110

Advantages

✔ Used in real protocols (HDLC)

✔ Works at bit level

Disadvantages

Slight increase in frame size

C Program – Bit Stuffing

#include <stdio.h>

#include <string.h>

int main() {

char data[100], stuffed[200];

int i, j = 0, count = 0;

printf("Enter bit stream: ");

scanf("%s", data);

for (i = 0; data[i] != '\0'; i++) {

stuffed[j++] = data[i];

if (data[i] == '1') {

count++;

if (count == 5) {

stuffed[j++] = '0'; // Stuffing

count = 0;

} else {

count = 0;

}
 stuffed[j] = '\0';

printf("\nStuffed Data: %s\n", stuffed);

printf("Final Frame:\n01111110 %s 01111110\n", stuffed);

return 0;

Sample Input

1111101111110

Sample Output

Stuffed Data: 111110011111010

Final Frame:

01111110 111110011111010 01111110

1 . Implement the data link layer framing methods such as character,

character-stuffing and bit stuffing
1a) #include <stdio.h>
#include <string.h>

/* ---------- CHARACTER COUNT ---------- */

void character_count() {
char data[100];
int count;

printf("\nEnter data: ");

scanf("%s", data);

count = strlen(data);

printf("\n--- Character Count Framing ---\n");

printf("Frame Transmitted:\n");
printf("%d %s\n", count, data);
}

/* ---------- CHARACTER STUFFING ---------- */

void character_stuffing() {
char data[100], stuffed[200];
int i, j = 0;
 printf("\nNote:\n");
printf("Use S for STX (Start of Text)\n");
printf("Use E for ETX (End of Text)\n");
printf("Use X for ESC (Escape)\n");

printf("\nEnter data: ");

scanf("%s", data);

stuffed[j++] = 'S'; // STX

for (i = 0; data[i] != '\0'; i++) {

if (data[i] == 'S' || data[i] == 'E') {
stuffed[j++] = 'X'; // ESC
}
stuffed[j++] = data[i];
}

stuffed[j++] = 'E'; // ETX

stuffed[j] = '\0';

printf("\n--- Character Stuffing ---\n");

printf("Stuffed Frame:\n");
printf("%s\n", stuffed);
}

/* ---------- BIT STUFFING ---------- */

void bit_stuffing() {
char data[100], stuffed[200];
int i, j = 0, count = 0;

printf("\nEnter bit stream (0s and 1s only): ");

scanf("%s", data);

for (i = 0; data[i] != '\0'; i++) {

stuffed[j++] = data[i];

if (data[i] == '1') {
count++;
if (count == 5) {
stuffed[j++] = '0'; // Bit stuffing
count = 0;
}
} else {
count = 0;
}
 }

stuffed[j] = '\0';

printf("\n--- Bit Stuffing ---\n");

printf("Stuffed Data:\n");
printf("%s\n", stuffed);

printf("\nFinal Frame:\n");
printf("01111110 %s 01111110\n", stuffed);
}

/* ---------- MAIN FUNCTION ---------- */

int main() {
int choice;

while (1) {
printf("\n====================================\n");
printf(" DATA LINK LAYER FRAMING METHODS\n");
printf("====================================\n");
printf("1. Character Count\n");
printf("2. Character Stuffing\n");
printf("3. Bit Stuffing\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
character_count();
break;

case 2:
character_stuffing();
break;

case 3:
bit_stuffing();
break;

case 4:
printf("\nExiting program...\n");
return 0;

default:
printf("\nInvalid choice! Try again.\n");
 }
}
}
1b) #include <stdio.h>
#include <string.h>

#define MAX 200

#define FLAG "01111110"

/* ---------------- CHARACTER COUNT ---------------- */

void characterCount() {
char data[MAX];

printf("\nEnter data: ");

scanf("%s", data);

printf("\n[Character Count Framing]\n");

printf("Frame: %lu %s\n", strlen(data), data);
}

/* ---------------- CHARACTER STUFFING ---------------- */

void characterStuffing() {
char data[MAX], stuffed[MAX];
int i, j = 0;

printf("\nSymbols used:\n");
printf("S -> STX (Start)\n");
printf("E -> ETX (End)\n");
printf("X -> ESC (Escape)\n");

printf("\nEnter data: ");

scanf("%s", data);

stuffed[j++] = 'S'; // Start of Frame

for (i = 0; data[i] != '\0'; i++) {

if (data[i] == 'S' || data[i] == 'E' || data[i] == 'X') {
stuffed[j++] = 'X'; // Escape before control character
}
stuffed[j++] = data[i];
}

stuffed[j++] = 'E'; // End of Frame

stuffed[j] = '\0';

printf("\n[Character Stuffing]\n");
 printf("Stuffed Frame: %s\n", stuffed);
}

/* ---------------- BIT STUFFING ---------------- */

void bitStuffing() {
char data[MAX], stuffed[MAX];
int i, j = 0, count = 0;

printf("\nEnter bit stream (0s and 1s only): ");

scanf("%s", data);

for (i = 0; data[i] != '\0'; i++) {

stuffed[j++] = data[i];

if (data[i] == '1') {
count++;
if (count == 5) {
stuffed[j++] = '0'; // Stuff 0 after five 1s
count = 0;
}
} else {
count = 0;
}
}

stuffed[j] = '\0';

printf("\n[Bit Stuffing]\n");
printf("Stuffed Data: %s\n", stuffed);
printf("Final Frame: %s %s %s\n", FLAG, stuffed, FLAG);
}

/* ---------------- MAIN MENU ---------------- */

int main() {
int choice;

do {
printf("\n=====================================\n");
printf(" DATA LINK LAYER FRAMING METHODS\n");
printf("=====================================\n");
printf("1. Character Count\n");
printf("2. Character Stuffing\n");
printf("3. Bit Stuffing\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
 switch (choice) {
case 1:
characterCount();
break;
case 2:
characterStuffing();
break;
case 3:
bitStuffing();
break;
case 4:
printf("\nProgram terminated.\n");
break;
default:
printf("\nInvalid choice! Try again.\n");
}
} while (choice != 4);

return 0;
}
Cyclic Redundancy Check (CRC)
What is CRC?
CRC (Cyclic Redundancy Check) is an error-detecting technique used in the Data Link
Layer.
It detects errors during data transmission using polynomial division (mod-2 arithmetic).

Basic Idea
1. Sender and receiver agree on a generator polynomial
2. Sender:
o Appends (degree of polynomial) zeros to data
o Divides data by generator using XOR
o Appends the remainder (CRC bits) to data
3. Receiver:
o Divides received frame by same generator
o If remainder = 0 → No error
o Else → Error detected

Standard CRC Polynomials

CRC Type Polynomial Binary Generator
CRC-12 x¹² + x¹¹ + x³ + x² + x + 1 1100000001111
CRC-16 x¹⁶ + x¹⁵ + x² + 1 11000000000000101
CRC-CCITT x¹⁶ + x¹² + x⁵ + 1 10001000000100001

CRC Example
[Link] a program to compute CRC code for the polynomials CRC-12, CRC-
16 and CRC CCIP
#include <stdio.h>
#include <string.h>

#define MAX 100

/* Function to perform XOR division */

void computeCRC(char data[], char generator[], char crc[]) {
int dataLen = strlen(data);
int genLen = strlen(generator);
char temp[MAX];

strcpy(temp, data);

for (int i = 0; i <= dataLen - genLen; i++) {

if (temp[i] == '1') {
for (int j = 0; j < genLen; j++) {
temp[i + j] = (temp[i + j] == generator[j]) ? '0' : '1';
}
}
}

strcpy(crc, temp + dataLen - genLen + 1);

}
/* Main Function */
int main() {
char data[MAX], dataWithZeros[MAX], crc[MAX];
char generator[MAX];
int choice;

printf("Enter binary data: ");

scanf("%s", data);

printf("\nSelect CRC Polynomial\n");

printf("1. CRC-12\n");
printf("2. CRC-16\n");
printf("3. CRC-CCITT\n");
printf("Enter choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
strcpy(generator, "1100000001111");
break;
case 2:
strcpy(generator, "11000000000000101");
break;
case 3:
strcpy(generator, "10001000000100001");
break;
default:
printf("Invalid choice!\n");
return 0;
}

int genLen = strlen(generator);

/* Append zeros */
strcpy(dataWithZeros, data);
for (int i = 0; i < genLen - 1; i++)
strcat(dataWithZeros, "0");

computeCRC(dataWithZeros, generator, crc);

printf("\n----- CRC RESULT -----\n");

printf("Generator Polynomial: %s\n", generator);
printf("CRC Code: %s\n", crc);
printf("Transmitted Frame: %s%s\n", data, crc);

return 0;
}
Sliding Window Protocol with Go-Back-N ARQ
The Data Link Layer is responsible for:
• Flow control → sender does not overwhelm receiver
• Error control → detect and recover from frame loss
To achieve this, Sliding Window Protocol is used with Go-Back-N (GBN) ARQ for loss
recovery.
Sliding Window Protocol (Flow Control)
What is Sliding Window?
• Sender can transmit multiple frames before waiting for acknowledgements.
• Number of frames allowed = Window Size
• Window slides forward as acknowledgements are received.
Key Terms
• Sender Window → frames that can be sent but not yet acknowledged
• Receiver Window → frames that receiver expects
• Sequence Number → identifies frames uniquely
Advantages
✔ Efficient use of bandwidth
✔ Reduces idle time
✔ Better than Stop-and-Wait
Go-Back-N ARQ (Error & Loss Recovery)
What is Go-Back-N?
• Sender sends multiple frames
• Receiver sends cumulative ACK
• If a frame is lost:
o Receiver discards that frame and all subsequent frames
o Sender retransmits from the lost frame onward
Key Rule
If frame k is lost → sender goes back to frame k and resends all frames
Example (Very Important for Exam)
Given:
• Total Frames = 7
• Window Size = 4
• Lost Frame = Frame 3
Transmission
Sender sends: 0 1 2 3
ACK received for: 0 1 2
Frame 3 lost
Receiver
• Discards frame 3 and any further frames
Retransmission
Sender retransmits: 3 4 5 6
✔ All frames received correctly

Algorithm (Exam-Friendly)
Sender Side
1. Send frames within window
 2. Start timer
3. If ACK received → slide window
4. If timeout → retransmit from lost frame
Receiver Side
1. Accept frames in order
2. Send cumulative ACK
3. Discard out-of-order frames
3. Develop a simple data link layer that performs the flow control using the
sliding window protocol, and loss recovery using the Go-Back-N mechanism.

#include <stdio.h>

int main() {
int totalFrames, windowSize;
int i, sent = 0, ack;
int lostFrame;

printf("Enter total number of frames: ");

scanf("%d", &totalFrames);

printf("Enter window size: ");

scanf("%d", &windowSize);

printf("Enter frame number to be lost (0 to %d): ", totalFrames - 1);

scanf("%d", &lostFrame);

printf("\n--- Sliding Window Transmission ---\n");

while (sent < totalFrames) {

printf("\nSender Window: ");
for (i = sent; i < sent + windowSize && i < totalFrames; i++) {
printf("%d ", i);
}

printf("\nSending frames...\n");

for (i = sent; i < sent + windowSize && i < totalFrames; i++) {

if (i == lostFrame) {
printf("Frame %d lost!\n", i);
break;
}
printf("Frame %d sent successfully\n", i);
}

if (i == lostFrame) {
printf("\nTimeout occurred!\n");
 printf("Go-Back-N: Retransmitting from frame %d\n", lostFrame);
sent = lostFrame;
lostFrame = -1; // loss handled
} else {
ack = i - 1;
printf("\nACK received up to frame %d\n", ack);
sent = ack + 1;
}
}

printf("\nAll frames transmitted successfully!\n");

return 0;
}
Shortest Path Through a Network

1. Theory
What is Dijkstra’s Algorithm?
Dijkstra’s algorithm is a greedy algorithm used to find the shortest path from a single
source node to all other nodes in a weighted graph.
It works only when edge weights are non-negative.
In Computer Networks, it is used in:
• Routing protocols
• Link State Routing (OSPF)
• Network path optimization
Key Concepts
• Graph → Nodes (routers) and edges (links)
• Weight → Cost of link (distance, delay, bandwidth)
• Source Node → Starting router
• Shortest Path → Minimum total cost
Working Principle
1. Initialize distance of source = 0
2. Initialize all other distances = ∞
3. Select unvisited node with minimum distance
4. Update distances of its neighbors
5. Mark node as visited
6. Repeat until all nodes are visited
Algorithm (Exam-Friendly)
1. Set distance[source] = 0
2. Set distance[others] = infinity
3. While unvisited nodes exist:
a. Pick node with minimum distance
b. Mark it visited
c. Update distances of adjacent nodes
Example
Given Graph (Adjacency Matrix)
 ABCD
A0 1 4 0
B1 0 2 5
C4 2 0 1
D0 5 1 0
Source Node: A
Step-by-Step Result
Node Shortest Distance from A
A 0
B 1
C 3
D 4
✔ Shortest path A → B → C → D
4. Implement Dijsktra's algorithm to compute the shortest path through a network

#include <stdio.h>
#include <limits.h>

#define MAX 20

int minDistance(int dist[], int visited[], int n) {

int min = INT_MAX, minIndex = -1;

for (int i = 0; i < n; i++) {

if (!visited[i] && dist[i] < min) {
min = dist[i];
minIndex = i;
}
}
return minIndex;
}

void dijkstra(int graph[MAX][MAX], int n, int source) {

int dist[MAX], visited[MAX] = {0};

for (int i = 0; i < n; i++)

dist[i] = INT_MAX;

dist[source] = 0;

for (int count = 0; count < n - 1; count++) {

int u = minDistance(dist, visited, n);
visited[u] = 1;
 for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] &&
dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

printf("\nVertex \t Shortest Distance from Source\n");

for (int i = 0; i < n; i++) {
printf("%d \t\t %d\n", i, dist[i]);
}
}

int main() {
int graph[MAX][MAX], n, source;

printf("Enter number of nodes: ");

scanf("%d", &n);

printf("Enter adjacency matrix (0 if no edge):\n");

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}

printf("Enter source node (0 to %d): ", n - 1);

scanf("%d", &source);

dijkstra(graph, n, source);

return 0;
}
What is a Broadcast Tree?
A broadcast tree is a loop-free structure that connects all hosts (nodes) in a subnet such
that:
• Every node receives the broadcast message
• No duplicate packets
• No cycles
• Minimum number of links used
In practice, a broadcast tree is a spanning tree of the subnet graph.
Why Broadcast Tree is Needed?
If broadcasting is done without control:
• Packets may loop indefinitely
 • Network congestion increases
• Duplicate packets reach hosts
Using a broadcast tree:
✔ Efficient broadcasting
✔ No loops
✔ Reduced traffic
How is a Broadcast Tree Constructed?
Common methods:
• Breadth First Search (BFS)
• Depth First Search (DFS)
• Minimum Spanning Tree (Prim / Kruskal)
In networking, BFS-based spanning tree is commonly used because it:
• Minimizes hop count
• Ensures shortest path from source
Example Subnet
Subnet with 6 Hosts
Hosts:
0, 1, 2, 3, 4, 5
Network Connections (Graph)
0 -- 1
| |
2 -- 3 -- 4
|
5
Adjacency Matrix:
012345
0011000
1100100
2100100
3011011
4000100
5000100
Broadcast Tree Construction (Using BFS)
Source Node: 0
BFS Traversal Order:
0→1→2→3→4→5
Broadcast Tree Edges:
0-1
0-2
1-3
3-4
3-5
✔ All nodes reached
✔ No cycles
✔ Efficient broadcast
Algorithm
1. Choose a source node
2. Mark source as visited
3. Add source to queue
4. While queue not empty:
a. Remove node u
b. For each unvisited neighbor v:
- Add edge (u, v) to broadcast tree
- Mark v visited
- Insert v into queue
[Link] an example subnet of hosts and obtain a broadcast tree for the subnet.

#include <stdio.h>

#define MAX 20

int main() {
int n, graph[MAX][MAX];
int visited[MAX] = {0};
int queue[MAX], front = 0, rear = -1;
int source;

printf("Enter number of hosts (nodes): ");

scanf("%d", &n);

printf("Enter adjacency matrix (0 or 1):\n");

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}

printf("Enter source host for broadcast: ");

scanf("%d", &source);

printf("\n--- Broadcast Tree Edges ---\n");

visited[source] = 1;
queue[++rear] = source;

while (front <= rear) {

int u = queue[front++];
 for (int v = 0; v < n; v++) {
if (graph[u][v] == 1 && !visited[v]) {
visited[v] = 1;
queue[++rear] = v;
printf("%d -> %d\n", u, v);
}
}
}

printf("\nBroadcast completed successfully.\n");

return 0;
}