(A30515) COMPUTER NETWORKS LAB
B. Tech (CSE) V Semester
Experiment 1
AIM: Implement the data link layer framing methods such as character, character-stuffing and
bit stuffing.
Theory: In Data Link layer, the stream of bits from the physical layer is divided into data frames.
The data frames can be of fixed length or variable length. In variable – length framing, the size of
each frame to be transmitted may be different. So, a pattern of bits is used as a delimiter to mark
the end of one frame and the beginning of the next frame. However, if the pattern occurs in the
message, then mechanisms needs to be incorporated so that this situation is avoided.
The two common approaches are −
• Bit - Stuffing − A pattern of bits of arbitrary length is stuffed in the message to
differentiate from the delimiter. This is also called bit - oriented framing.
In a data link frame, the delimiting flag sequence generally contains six or more consecutive 1s.
In order to differentiate the message from the flag in case of the same sequence, a single bit is
stuffed in the message. Whenever a 0 bit is followed by five consecutive 1bits in the message, an
extra 0 bit is stuffed at the end of the five 1s.
When the receiver receives the message, it removes the stuffed 0s after each sequence of five 1s.
The un-stuffed message is then sent to the upper layers.
• Byte - Stuffing − A byte is stuffed in the message to differentiate from the delimiter.
This is also called character-oriented framing.
If the pattern of the flag byte is present in the message byte sequence, there should be a strategy
so that the receiver does not consider the pattern as the end of the frame. Here, a special byte
called the escape character (ESC) is stuffed before every byte in the message with the same
pattern as the flag byte. If the ESC sequence is found in the message byte, then another ESC byte
is stuffed before it.
Algorithm for Bit−Stuffing
1. Start
2. Initialize the array for transmitted stream with the special bit pattern 0111 1110 which
indicates the beginning of the frame.
3. Get the bit stream to be transmitted in to the array.
4. Check for five consecutive ones and if they occur, stuff a bit 0
5. Display the data transmitted as it appears on the data line after appending 0111 1110 at the end
6. For de−stuffing, copy the transmitted data to another array after detecting the stuffed bits
7. Display the received bit stream
8. Stop
1
Program Code: // BIT Stuffing program
#include<stdio.h>
#include<string.h>
void main()
{
int a[20],b[30],i,j,k,count,n;
printf("Enter frame length:");
scanf("%d",&n);
printf("Enter input frame (0's & 1's only):");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
i=0; count=1; j=0;
while(i<n)
{
if(a[i]==1)
{
b[j]=a[i];
for(k=i+1;a[k]==1 && k<n && count<5;k++)
{
j++;
b[j]=a[k];
count++;
if(count==5)
{
j++;
b[j]=0;
}
i=k;
}}
else
{
b[j]=a[i];
}
i++;
j++;
}
printf("After stuffing the frame is:");
for(i=0;i<j;i++)
printf("%d",b[i]);
}
Output:
Enter frame length:5
Enter input frame (0's & 1's only):
1
1
2
1
1
1
After stuffing the frame is:111110
Algorithm for Character stuffing
1. Start
2. Append DLE STX at the beginning of the string
3. Check the data if character is present; if character DLE is present in the string (example
DOODLE) insert another DLE in the string (ex: DOODLEDLE)
4. Transmit DLE ETXat the end of the string
5. Display the string
6. Stop
Algorithm for Character De−stuffing
1. Start
2. Neglect initial DLE STX
3. If DLE is present in the text, ngelect it; if another DLE follows, copy the same to output.
4. Neglect the trailing DLE ETX
5. Stop
3
Program Code:
#include <stdio.h>
#include <string.h>
void main() {
int i = 0, j = 0, n, pos;
char a[20], b[50], ch;
printf("Enter string: ");
scanf("%s", a);
n = strlen(a);
printf("Enter position: ");
scanf("%d", &pos);
// Validate position
while (pos > n || pos < 1) {
printf("Invalid position, Enter again: ");
scanf("%d", &pos);
}
printf("Enter the character: ");
getchar(); // consume newline left by scanf
ch = getchar();
// Header for stuffed frame
b[0] = 'd';
b[1] = 'l';
b[2] = 'e';
b[3] = 's';
b[4] = 't';
b[5] = 'x';
j = 6;
while (i < n) {
// Insert stuffing at the given position
if (i == pos - 1) {
b[j++] = 'd';
b[j++] = 'l';
b[j++] = 'e';
b[j++] = ch;
b[j++] = 'd';
b[j++] = 'l';
b[j++] = 'e';
}
// Handle stuffing for existing "dle" in input
if (a[i] == 'd' && a[i + 1] == 'l' && a[i + 2] == 'e') {
b[j++] = 'd';
b[j++] = 'l';
4
b[j++] = 'e';
}
b[j++] = a[i++];
}
// Trailer for stuffed frame
b[j++] = 'd';
b[j++] = 'l';
b[j++] = 'e';
b[j++] = 'e';
b[j++] = 't';
b[j++] = 'x';
b[j] = '\0';
printf("\nFrame after stuffing:\n");
printf("%s\n", b);
}
OUTPUT
Enter string: cmrcet
Enter position: 3
Enter the character: r
Frame after stuffing:
dlestxcmdlerdlercetdleetx
5
Experiment 2
AIM: Write a program to compute CRC code for the polynomials CRC-12, CRC-16 and CRC,
CCIP.
Theory: CRC method can detect a single burst of length n, since only one bit per column will be
changed, a burst of length n+1 will pass undetected, if the first bit is inverted, the last bit is
inverted and all other bits are correct. If the block is badly garbled by a long burst or by multiple
shorter burst, the probability that any of the n columns will have the correct parity that is 0.5. so
the probability of a bad block being expected when it should not be 2 power(-n). This scheme
sometimes is known as Cyclic Redundancy Code.
The most commonly used polynomial lengths are:
• 9 bits (CRC-8)
• 17 bits (CRC-16)
• 33 bits (CRC-32)
• 65 bits (CRC-64)
Algorithm Steps:
Step 1: Declare int crc 16, SHIFT_CRC, shift Byte, Byte_SIZE as global variables.
Step 2: Input the data in a file.
Step 3: perform the crc computation using cal CRC 16 ().
Step 4: In cal CRC 16 each character from input shifted with shift-byte where value 987.
Step 5: Output of step 4 and step 5 are exclusive.
Step 6: store in a temporary variable.
Step 7: Byte value is now left_shifted by 1.
Step 8: The loop is repeated for the Byte_size.
Step 9: The computed crc is display as output in screen.
6
Source Code:
#include <stdio.h>
int data[20], gen[10], temp[20];
int dl, gl;
void left_shift(int c) {
for (int i = 0; i < gl - 1; i++) {
temp[i] = temp[i + 1];
}
if (c < dl) {
temp[gl - 1] = data[c];
} else {
temp[gl - 1] = 0;
}
}
void xor() {
if (temp[0] == 1) {
for (int i = 0; i < gl; i++) {
temp[i] = temp[i] ^ gen[i];
}
}
}
int main() {
int choice;
printf("1. Generate CRC\n2. Check CRC\nEnter choice: ");
scanf("%d", &choice);
printf("Enter the length of data: ");
scanf("%d", &dl);
printf("Enter the data bits: ");
for (int i = 0; i < dl; i++) {
scanf("%d", &data[i]);
}
printf("Enter the length of generator: ");
scanf("%d", &gl);
printf("Enter the generator bits: ");
for (int i = 0; i < gl; i++) {
scanf("%d", &gen[i]);
}
for (int i = 0; i < gl - 1; i++) {
data[dl + i] = 0;
}
for (int i = 0; i < gl; i++) {
temp[i] = data[i];
}
if (choice == 1) {
for (int c = gl; c < dl + gl; c++) {
xor();
left_shift(c);
}
printf("CRC: ");
7
for (int i = 1; i < gl; i++) {
data[dl + i - 1] = temp[i];
printf("%d", temp[i]);
}
printf("\nFinal Data with CRC: ");
for (int i = 0; i < dl + gl - 1; i++) {
printf("%d", data[i]);
}
printf("\n");
} else {
printf("Enter received data: ");
for (int i = 0; i < dl + gl - 1; i++) {
scanf("%d", &data[i]);
}
for (int c = gl; c < dl + gl; c++) {
xor();
left_shift(c);
}
int error = 0;
printf("Remainder: ");
for (int i = 1; i < gl; i++) {
printf("%d", temp[i]);
if (temp[i] != 0) {
error = 1;
}
}
printf("\n");
if (error) {
printf("Error detected in received data.\n");
} else {
printf("No error detected.\n");
}
}
return 0;
}
OUTPUT
1. Generate CRC
2. Check CRC
Enter choice: 1
Enter the length of data: 6
Enter the data bits: 1
0
1
1
0
1
8
Enter the length of generator: 4
Enter the generator bits: 1
1
0
1
CRC: 100
Final Data with CRC: 101101100
9
Experiment 3
AIM: 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.
Theory: In Go-Back-N ARQ, N is the sender's window size. Suppose we say that Go-
Back-3, which means that the three frames can be sent at a time before expecting the
acknowledgment from the receiver.
It uses the principle of protocol pipelining in which the multiple frames can be sent
before receiving the acknowledgment of the first frame. If we have five frames and the
concept is Go-Back-3, which means that the three frames can be sent, i.e., frame no 1,
frame no 2, frame no 3 can be sent before expecting the acknowledgment of frame no
1.
In Go-Back-N ARQ, the frames are numbered sequentially as Go-Back-N ARQ sends the
multiple frames at a time that requires the numbering approach to distinguish the
frame from another frame, and these numbers are known as the sequential numbers.
The number of frames that can be sent at a time totally depends on the size of the
sender's window. So, we can say that 'N' is the number of frames that can be sent at a
time before receiving the acknowledgment from the receiver.
If the acknowledgment of a frame is not received within an agreed-upon time period,
then all the frames available in the current window will be retransmitted. Suppose we
have sent the frame no 5, but we didn't receive the acknowledgment of frame no 5,
and the current window is holding three frames, then these three frames will be
retransmitted.
The sequence number of the outbound frames depends upon the size of the sender's
window. Suppose the sender's window size is 2, and we have ten frames to send, then
the sequence numbers will not be 1,2,3,4,5,6,7,8,9,10. Let's understand through an
example.
o N is the sender's window size.
o If the size of the sender's window is 4 then the sequence number will be
0,1,2,3,0,1,2,3,0,1,2, and so on.
The number of bits in the sequence number is 2 to generate the binary sequence
00,01,10,11.
10
Algorithm Steps:
Step 1: start the program.
Step 2: Open the input file in read mode.
Step 3: Read the size of the window
Step 4: Select randomly the number of packets is to be transferred.
Step 5: Read the content of the input file.
Step 6: Transfer the packet until it reaches the maximum defined size.
Step 7: Resume the window size and repeat the above two steps until packets in.
Step 8: Close the file.
Step 9: Stop the program.
Source Code:
#include <stdio.h>
int main() {
int w, i, f, frames[50];
// Input window size
printf("Enter window size: ");
scanf("%d", &w);
// Input number of frames to transmit
printf("Enter number of frames to transmit: ");
scanf("%d", &f);
// Input frame values
printf("Enter %d frames: ", f);
for (i = 0; i < f; i++) {
scanf("%d", &frames[i]);
}
printf("\nWith sliding window protocol, the frames will be sent in the following manner\n");
printf("(assuming no corruption of frames)\n\n");
11
printf("After sending %d frames at each stage, sender waits for acknowledgement from the receiver\n\n", w);
for (i = 0; i < f; i++) {
printf("%d ", frames[i]);
if ((i + 1) % w == 0) {
printf("\nAcknowledgement of above frames sent is received by sender\n\n");
}
}
// Handle remaining frames if any
if (f % w != 0) {
printf("\nAcknowledgement of above frames sent is received by sender\n");
}
return 0;
}
OUTPUT
Enter window size: 3
Enter number of frames to transmit: 5
Enter 5 frames: 2 23 4 12 14
With sliding window protocol, the frames will be sent in the following manner
(assuming no corruption of frames)
After sending 3 frames at each stage, sender waits for acknowledgement from the receiver
2 23 4
Acknowledgement of above frames sent is received by sender
12 14
Acknowledgement of above frames sent is received by sender
12
13
14
